Verhetetlen malomprogramon dolgozik egy szegedi és egy pesti egyetemista
A mai modern korban a mesterséges intelligencia egyre több területen veszi fel a versenyt az emberi gondolkodással. Egy szegedi és egy pesti egyetemista közös munkájában olyan programon dolgozik, amely a malomjátékban arat győzelmet hús-vér kihívóival szemben.
Sokan hallottak már Kempelen Farkas legendás sakkozógépéről, amely sorra megverte Európa uralkodóit. Bár a szerkezet azóta megsemmisült, a hagyatéka tovább él. Hasonló elgondolás vezetett két informatikust, Danner Gábort és Gévay Gábort, akik egy olyan malomprogramon dolgoznak, amely képes minimum döntetlent kihozni bármely emberi ellenfél ellen. A mai modern számítástechnikának hála ez nem lehetetlen, ám ne gondoljuk, hogy a játék által kínált rengeteg lépéskombináció nem rejthet buktatót a programozók számára. Erről és másról is kérdeztük őket.
– Honnan jött az ötlet, hogy együtt dolgozzatok?
DG: Ezt még két évvel ezelőtt Gévay Gábor vetette föl, ő szokott malmozni. Azóta folyamatosan foglalkozunk vele, kisebb-nagyobb megszakításokkal. Én programtervező informatikus MSc szakra járok a Szegedi Tudományegyetemen, Gábor pedig az ELTE ugyanezen szakán tanul.
GG: A Ságvári-gimnáziumból programozás szakkörökről ismerjük egymást, sokat gyakoroltunk együtt. Ezért is gondoltam, hogy ezt a projektet is együtt csinálhatnánk.
– Miről is szól pontosan ez a malmozó program?
GG: A program a standard malomjátékot és annak két variánsát, a Laskert és a morabarabát ismeri. Ezek eltérnek egyrészt a korongszámban (10, illetve 12), másrészt a Laskerben nincs külön fölrakási és mozgatási fázis, illetve a morabarabában kicsit más a tábla. A programnak egyébként két része van. Az első megállapítja az összes lehetséges játékállás elméleti értékét, ami alatt azt értjük, hogy optimális lépések esetén mi lesz a játszma eredménye (döntetlen, nyerés, vesztés, illetve hány lépésben) az adott állásból indulva. Ezt a részt mi futtattuk le a gépeinken, és hetekig tartott. A második rész az így kiszámolt, összesen 263 GB-nyi adatbázist használja az optimális játék megvalósítására. Ehhez elegendő megnéznie, hogy a lehetséges lépések közül melyek visznek maximális értékű állásba.
DG: A program ebből kifolyólag minden helyzetből a legjobbat tudja kihozni. A szokásos malomjátéknál a kezdőállás elméleti értéke döntetlen, ami azt jelenti, hogy a programot nem lehet legyőzni, legjobb esetben is csak döntetlent lehet elérni ellene. Ha olyan játékállásba kerülünk, amelynek az elméleti értéke nyerés (mert az ellenfél hibázott), akkor mindenképpen nyerünk. Sok ilyen állásról még egy tapasztalt malomjátékos sem látná, hogy miként valósítható meg a biztos nyerés.
– Hol tartotok jelenleg a fejlesztésben?
DG: Mindhárom variáns adatbázisa ki van már számítva, és ezeket használni is tudja. A standard malmot tökéletesen játssza, verhetetlen, és egy pillanat alatt képes meghozni az optimális döntést. Ugyanígy van a Laskerben is. Viszont a morabaraba játéknál meglepő eredményre jutottunk: kiderült, hogy a többi variánssal ellentétben itt nyerés a kezdőállás értéke. Így ha a program kezd, akkor mindenképp nyer (49 lépésen belül), de ha az ellenfél, akkor a program megverhető. A programot több alkalommal is teszteltük egy internetes malomjátékban, ahol valós játékosok ellen játszotta a standard malmot. Egyetlen egyszer sem veszített.
GG: Viszont a program ellen meglepően könnyű volt döntetlent elérni. Azért, hogy elkerüljük ezt, beépítettünk egy másodlagos malom AI-t, ami a többféle lehetséges optimális lépés közül választja azt, amelyikben az ellenfél könnyebben hibázik, mert kevés és nehezen megtalálható optimális lépése van. A másodlagos AI-nak azonban jól jön néhány másodperc gondolkodási idő.
– Voltak akadályok a munkátok során?
DG: Rengeteg akadály volt. Sokszor szembekerültünk a program tervezése, illetve megvalósítása során vétett hibákkal. De ezek részei a munkának. A játékállások számát a tábla szimmetriáinak kihasználásával próbáltuk csökkenteni, ami sok bonyodalommal és nem várt nehézséggel járt.
– Volt valami emlékezetes pillanat a fejlesztés során?
GG: Amikor még korai szakaszában járt a projekt, és a kezelőfelület fejlesztés alatt állt, nem egyszer előfordult, hogy online meccs közben elszállt a program. Ilyenkor mindig nekem kellett átvennem a helyét, hogy megőrizzük a veretlenségünket.
– Mások is foglalkoztak már hasonlóval? Ez mennyiben számít újdonságnak?
DG: Azt tudtuk, hogy a standard malmot már megcsinálták, de csak utólag találtunk rá, hogy a Laskert is. Úgy tudjuk, hogy a morabarabát még nem számolták ki. A két fiú programja az eddigi 49 ember elleni meccsből 27-et megnyert, 22 döntetlennel végződött. Danner Gábor és Gévay Gábor elképzeléseik szerint jövő tavasszal benevezik a projektjüket a TDK-ra. Remélhetőleg az ottani kihívóival is hasonló precizitással „bánik majd el”.