Sördöngölő

A Sördöngölő egy amőbaprogram, amely a klasszikus japán amőba (go-moku) játék egy változatát játssza. A program nem interaktív (tehát nincs felhasználói felülete, ember csak körülményesen játszhat vele), hanem más amőbaprogramok elleni versenyjátékra lett kifejlesztve. A verseny szabályai és a tesztkörnyezet a weben is elérhetők.

Életciklus

A programot Szabó Péter, a verseny idején harmadéves hallgató írta.

A program a Budapesti Műszaki Egyetemen, műszaki informatikusoknak oktatott Mesterséges Intelligencia tárgy 2001. őszi féléves kurzusán meghirdetett amőbaversenyre készült. A program ezen a versenyen, 9 induló közül bejutott a négyes döntőbe, és ott 4. helyezést ért el.

A program fejlesztése a verseny lezajlása után abbamaradt. A dokumentáció (honlap) elkészítése után a szerző nem kíván tovább a project-tel foglalkozni, de a forrást a GNU GPL licensz alatt szabadon használhatóvá és elérhetővé tette.

A Java-ban írt amőbaszerver a szerző által javított változata (pl. helyesen érzékeli, ha nyer valaki, és hibás lépés esetén új játékot indít) és az eredeti változat is letölthetők. A szerver futtatása: először a CLASSPATH nevű környezeti változót kell beállítani samoba6.zip-re (UNIX alatt export-tal), majd java amobaServer.AmobaMain debug=1 timeout=9876543. JDK1.1 vagy JRE1.1 szükséges. Figyelem! A java -classpath, java -cp, java -jar kapcsolók csak JDK1.2-ben és afölött működnek helyesen.

Algoritmus

A program lelke egy meglepően egyszerű (,,potya'') súlyozásos módszerrel választja a ki a mezőt, ahova lépjen. Minden mezőre előállít egy pozitív egész értéket, és a legnagyobb értékű mezőre lép. A továbbiakban ezt részletezzük.

A téglalap alakú tábla egy 5 hosszúságú vízszintes, függőleges vagy valamelyik átlós irányú szakaszát vonal-nak nevezzük. A vonal tehát egy olyan alakzat, amelyet ha az egyik játékos kitölt a saját színével, akkor azonnal ő nyer. nyertes vonal-nak nevezzük azt a vonalat, melynek kitöltésével a nyertes nyert. Minden mezőn 20 vonal halad át (irányonként 5). Egy vonalat befejezhetőnek nevezünk (valamelyik játékos szempontjából), ha az ellenfél eddig még egyik mezőjére sem lépett.

A befejezhetetlen vonal félértéke legyen 0, a befejezhető vonal félértéke pedig függjön attól, hogy eddig hány saját lépést tettünk bele (0 -> 0, 1 ->, 565 2 -> 2130, 3 -> 7483, 4 -> 43848). Egy mező értékét a következőképp számíthatjuk: érték = (a rajta áthaladó vonalak félértékének összege, saját szempontból) *19/16 + (a rajta áthaladó vonalak félértékének összege, az ellenfél szempontjából) + random (0..3). Már említettük, hogy a program mindig a legnagyobb értékű mezőre lép. Ezt az indokolja, hogy olyan helyre kell lépni, ami vagy nagyon jó a játékosnak (saját félértékek, támadás), vagy jó az ellenfélnek (ellenfél félértékei, védekezés). Egy mező akkor számít jónak (valaki szempontjából), ha nagy esélye van arra, hogy benne lesz az ő nyertes vonalában. Ezt az esélyt fejezi ki a félértékek összege.

Az algoritmus finomítható a benne szereplő konstansok (félértékek meghatározása és a támadási szorzó (19/16)) változatásával. A Sördöngölő konstansaira a szerző a Turbo Gomoku állandóiból kiindulva, 200-as populációban, véletlen génmutálással talát rá.

Az algoritmus nem igazán intelligens, semmit nem garantál (pl. azt sem, hogy a három lépésben megnyerhető állásokat megnyeri), viszont a gyakorlatban, úgy tűnik, jól működik. A konstansokba bújtatott ,,logika'' elég ahhoz, hogy észrevegye és megakadályozza az ellenfél nyílt hármasát vagy dupla hármasra való törekvését és számos egyéb nyilvánvaló helyzetben helyesen lép.

Emellett óriási előnye, hogy a következő lépés villámgyorsan számolható mai PC-n (századmásodpercnél gyorsabban). A működést tovább gyorsítja, hogy a vonalak félérték-összegét (kezdetben 0) folyamatosan karbantartja, így a lépés kiszámítása lényegében a pályamérettel arányos halmazban maximumkeresés, plusz konstans darab szám módosításából áll. Mindezt bináris kupaccal megvalósítva O(log n)-es időigényt kapunk, ahol n a pálya hosszabb oldalának hossza. (A program nem ennyire gyors, mert a minimumkeresést lineáris időben valósítja meg.)

A szerző nem ezt az algoritmust kívánta beadni, de csak ennek megírására jutott ideje. A szerző terveiben egy szokásos, alfabéta nyeséssel kiegészített minimax algoritmus gyors, futási sebességre optimalizált megvalósítása szerepelt. A ténylegesen implementált algoritmust is használta volna, de csak arra az esetre, ha a minimax keresés elakadna vagy túllépné az időt. Sajnos azonban a minimax rutin nem készült el, csak ez a ,,potya'' algoritmus.

Fordítási és futtatási környezet

A program fejlesztése Linux operációs rendszer alatt, GNU fejlesztőeszközökkel történt. A program lefordításához és futtatásához szükség van a Linux legalább 2.0-ás változatára, a GNU Make, GNU Bash és GNU G++ programokra, továbba a libc és libstdc++ könyvtárak tetszőleges, de működő verziójára. A program nem tartalmaz Linux-specifikus részt, portolása más UNIX-okra (vagy egyéb POSIX rendszerekre) néhány perc alatt elvégezhető. (A fő portolási problémát a másképp nevezett .h file-ok és a socket-könyvtárak link-elése, továbbá a másodpercnél pontosabb időzítés okozzák.)

A program a szerző által kifejlesztett CHP ,,nyelven'' íródott. A CHP nyelvű programok fordítása úgy történik, hogy a CHP preprocesszor a forrás .chp file-okból .cpp és .hpp file-okat készít, amit a C++ fordító lefordít, és végül a linker összeállítja az előálló object file-okból a futtatható programot. A CHP preprocesszor része a Sördöngölő disztribúciónak. Az inkrementális fordításról a Makefile és a CHP preprocesszor közösen gondoskodnak. A felhasználónak a kicsomagolás után csak azt kell beírnia, hogy make, és kis időn belül előáll a sor nevű futtatható file.

Indításkor a programnak parancssori argumentumokban lehet megadni a szerver címét, a rendelkezésre álló memóriát, a login nevet, a jelszót és az időlimitet. Minderről részletesebben a program angol nyelvű segítséget ad, ha paraméterek nélkül hívjuk meg.

Miért Linux (UNIX, POSIX) környezet? Mert a szerző amúgy is ebben van otthon, továbbá az ebben a környezetben működő GNU G++ fordítóprogram készíti -- a szerző tudomása szerint -- a leggyorsabb futtatható programot. Emellett természetesen filozófiai okok is közrejátszottak.

Miért C++? Mert a programnak gyorsnak kell lennie (feltéve, hogy van benne minimax algoritmus...), és nem szabad pazarolni a szűk memóriát. Ez a szempont egyértelműen kizárta a Java-t, a Perl-t, a Ruby-t és az egyéb script-nyelveket. Az ANSI C és az assembly is szóba jöhetett volna, de a szerző úgy érezte, hogy ezek nem okoznak akkora sebességnövekedést, amennyivel nehezebb bennük fejleszteni. A program alig használja ki a C++ objektumorientált lehetőségeit, viszont az inline kulccsszót (ami hiányzik a sima C-ből) nem tudja nélkülözni.

Architektúra

Az architektúrát a szerző a minimax algoritmushoz igazította. (Sajnos a tényleges algoritmus kimaradt.) A program futása során egy szülő és egy gyermek folyamatból áll. A szülő folyamat kommunikál a szerverrel és a gyermek folyamattal. A gyermek gondolkodik a következő lépésen, és ha megtalálja, akkor megsúgja a szülőnek, aki továbbadja a szervernek. Az ellenfél válasza a szervertől először a szülőhöz jut el, majd tőle a gyermekhez.

A szülő fő feladata (a lépések továbbítása mellett) a gyermek felügyelete. A szülő érzékeli, ha a gyermek ,,elszállt'', és újat indít (természetesen olyat, amely az épp aktuális játékállásból indul). A gyermek küldhet végleges és bizonytalan lépést is a szülőnek. A bizonytalan lépés azt jelenti, hogy a gyermek még nem biztos abban, hogy tényleg oda akar lépni, de ha már nem lenne több ideje gondolkodni, akkor biztosan oda lépne. A szülő megjegyzi a legutolsó bizonytalan lépést, figyeli az időtúllépés közeledtét, és ekkor a bizonytalan lépést küldi el a szervernek. Sokkal jobb egy kétséges értékű, de legalább szabályos lépést tenni, mint időtúllépés miatt elveszteni a meccset. A túlzott memóriahasználatot kernel által nyújtott resource limit-ek beállításával (setrlimit(2) rendszerhívás) akadályozzuk meg. Ha a gyermek -- a saját ellenőrzése ellenére -- túl sok memóriát használ, akkor az operációs rendszer kilövi. Ez nem baj, mert ekkor a szülő új gyermeket indít.

A szülő valósítja meg az amőba-protokoll nem válaszlépéssel kapcsolatos részeit is, például bejelentkezés, játék végének elfogadása, középső kezdő lépés megtétele. A gyermek tervezett felépítése a következő lett volna: először lefuttatja a villámgyors ,,potya'' kódot (és küld egy bizonytalan lépést), majd egy iteratívan mélyülő alfabéta keresésbe kezd. Minden végigszámolt mélységre kapott eredményt bizonytalan lépés formájában továbbítja a szülőnek.

A szülő--gyermek kettéválasztás fő célja az, hogy banális okok miatt ne veszítsünk játszmát. A banális okok a következők: időtúllépés, memóriatúllépés, ritkán beütő hibás memóriakezelés (segmentation fault), a szinkron elvesztése a szerverrel a futó számítások miatt.

A forráskód felépítése

A forráskód egyetlen csomagból áll (ez maga a teljes Sördöngölő). A csomagban szereplő modulok és funkcióik:

Egyéb, járulékos file-ok:

Tanulság

A potya algoritmus 13 : 5 arányban veri a tanszéki ,,buta'' amőbaprogramot. Az éles versenyben is benne van a mezőny erősebb felében. A szerző egyik ismerőse úgy tudja, hogy a matematikusok bebizonyították, hogy a potyához hasonló állás-kiértékelés megfelelő konstansokkal nyerő stratégiát játszik (feltéve, hogy ő kezd). Mindezek ellenére az alfabéta keresést meg kellett volna írni, például azért is, hogy fejlődjön a szerző programozási készsége.

Az amőbajátékról: a Victoria nevű amőbaprogram (sajnos nem letölthető) mindig nyer, ha ő kezd, és mindig nyer a nem a nyerő stratégiát játszó ellenfél ellen. Mindez azért lehetséges, mert matematikusok és go-moku nagymesterek összefogtak, kielemezték a játékot és megtalálták a nyerő stratégiát. (Ennek programkód-formába öntése túlságosan körülményes lett volna a szerzőnek, mivel a neten szinte csak metainformációt talált.)

A szerző a feladatot és a versenyt tanulmányai szempontjából hasznosnak ítélte, és gratulál a győzteseknek.