PA026 Projekt z AI: Go

Autor: Čestmír Kalina - 396477 «cestmir at mail dot muni dot cz», 2013

---

Představení problému

Go je hra s nulovým součtem 2 hráčů s dokonalou informací. Klasickým přístupem při modelování umělého agenta je kombinování alpha-beta prohledávání s heuristikou, která si klade za cíl evaluovat stav hráče na základě doménové znalosti (predprogramovaná databáze znalostí, SOM, ...). Tento přístup se ukázal jako použitelný u her jako šachy nebo dáma, ale často selhává u hry Go a to zejména kvůli velkému množství herních kombinací. Tento důvod mne přivedl na nápad implementovat, nebo spíše upravit již funkčního agenta, a to přidáním heuristiky, která by nebyla nutně vázána s empiricky zjištěnou doménovou znalostí.

Popis projektu

Prvním krokem projektu bylo zvolení modifikovaného programu (resp. agenta). Na základě benchmarku [1] jsem si zvolil GNU Go [2], které (mimo jiné) používá svoji různorodou doménovou znalost (v tomto případě typické vzory, více na http://www.gnu.org/software/gnugo/gnugo_4.html#SEC40).

Po identifikaci agenta bylo potřeba vybrat model, kterým by se jeho chování měnilo. Jako takový mi posloužil Isinguv model feromagnetismu [3], [4], kdy model gobanu (herní desky GNU Go) pro agenta byl přenášen do podoby spinu jednotlivých atomů a to tak, že místo (resp. okolí), ve kterém agent má svoje kameny, má mít odlišný spin od místa (okolí), kde tomu tak není. Po této inicializaci se simulovaným žíháním mění stav IM a výsledná reprezentace IM je použita jako heuristika, která udává pole, na kterém favorizuje umístění dalšího kamene. 

Pozn.: Motivací pro použití IM byl izomorfismus mezi IM a Hopfieldovou sítí, která by se snad dala využít dále mimo tento projekt (domněnka).

Použití programu

IM je implementován jako hook jedné z analytických funkcí hry GNU Go. IM je parametrizovatelný, a sice definováním maker, které mění jeho chování. Nevýhodou je nutnost rekompilace GNU Go při každé změně parametrů. Tento přístup byl zvolen z prostého důvodu: chtěl jsem minimalizovat zásah do hry GNU Go (pro předání parametrů pomoci **argv by bylo potřeba většího zásahu než je tomu tak v této chvíli).

USE_ISING_MODEL_HOOK
pokud je makro definováno, použije se IM při výpočtu agenta

ISING_MODEL_ITER
specifikuje počet iterací IM

ISING_MODEL_INFLUENCE
specifikuje pravděpodobnost použití IM (pozn.: uniformní distribuce, parametr je roven card Omega)

ISING_MODEL_2D_RULE
pravidlo upravující chování IM

Zdrojový kód

gg-3.8_im_patched.tar, konkrétně soubory engine/ising.c a engine/worms.c.

Popis spuštění

Jednoduché spuštění GNU Go ELF32/ELF64 souboru v interface/gnugo.

Ukázka použití

Obrázek 1: rozehraná hra proti modifikovanému GNU Go agentovi.

Výsledky

Model se liší oproti klasickému IM ve výpočtu energie systému, konkrétně v sumaci energie okolních atomů (tj. nejedná se o přesný IM, kde se počítá jen s nejbližším okolím). Konkrétně se používají tyto typy okolí: V rámci evaluace byly zkoušeny i další, jako například supremum lineární kombinace spinů, která měla být větší než empiricky volená konstanta, nebo průměr spinů větší než emp. volená konstanta, ale tyto metody se ukázaly po další evaluaci jako nevhodné.

Evaluace byla zajištěna programem GoGui [5].