Kiss Miklós

"The possession of anything begins in the Mind" - Bruce Lee

Site Tools




látogató számláló

Larion

Larion egy reversi-t (más néven othello) játszó program.

Letöltés

Tulajdonságok

Larion főablaka

  • Szerkeszthető játéktábla (több előre készített)
  • Játék a számítógép ellen
    • Tanított (újra tanítható) mesterséges intelligencia
    • Állítható gépi játékerő
  • Játsza lementése, visszatöltése
  • Mentett játszma folytatása
  • Játék időre
  • Korlátlan lépésvisszavonás (kezdőállásig)
  • Hálózati játék (Skype-on keresztül)
  • Intuitív kezelőfelület

Részletes leírás

Bevezetés

A hagyományos reversi játékot két játékos játssza egy 8×8-as táblán. Az egyik játékos sötét, a másik játékos világos bábukkal játszik, az 1. ábrán látható kezdőállásból indulva. A játékosok felváltva lépnek, és mindig sötét lép elsőként.

1. ábra
1. ábra
Szabványos reversi kezdőállás

Egy lépés során egy új bábut kell a táblára helyezni, úgy hogy az vízszintesen, függőlegesen vagy átlósan legalább egy, már a táblán lévő saját bábuval együtt közrefogjon egy vagy több ellenséges bábut üres mezők nélkül. A lépés eredményeként az összes irányban a fenti feltétel teljesülése esetén a közrefogott bábuk színt váltanak, azaz a lépő játékos színét veszik fel. Ha egy játékos nem tud lépni (mert nincs olyan üres mező, amire a fenti feltétellel lehetne bábut helyezni), akkor passzolnia kell, és az ellenfél lép. Passzolni csak akkor lehet, ha nincs érvényes lépése a soron következő játékosnak. Ha egyik játékosnak sincs érvényes lépése, a játék véget ér (ez nem csak akkor következhet be, ha megtelt a tábla).

Az a játékos nyer, akinek a játék végén több bábuja van a táblán. Ha mindkét játékosnak ugyanannyi bábuja van, akkor az eredmény döntetlen.

Larion is a fenti szabályoknak megfelelően játszik, és megköveteli az emberi játékos(ok)tól is a szabályok betartását. A fentieken felül azonban Larion képes tetszőleges formájú és belső szerkezetű táblán játszani tetszőleges kezdőállásból indulva.

Célok

A program megtervezésekor a cél volt egy olyan játékmotor megalkotása, ami bármelyik (a program által) megrajzolható táblán (és kezdőállásból) erősen tud játszani. Azaz képes egy jobb amatőr játékost is legyőzni egy kiegyenlített állásból indulva. Másodlagos célok között szerepelt egy kellemes kinézetű és könnyen használható kezelőfelület megalkotása.

Megvalósítás

A célkitűzés magas mércét állított. Ahhoz, hogy elérhető közelségbe kerüljön a cél, számos program működésének tanulmányozására volt szükség, és sok szakirodalom tapasztalatainak felhasználására.

Amire szükség volt: csúcstechnológiákat használó gyors keresőalgoritmus(ok) és egy versenyképes heurisztikus függvény.

A játék jellegéből adódóan (két személyes, teljes információtartalmú, zéró végösszegű játék) a klasszikus keresőalgoritmusok, mint amilyen a minimax is használhatók. Persze önmagában a minimax nem elég, ezért a tényleges programba bekerült keresőalgoritmus, és az azt segítő technikák a következők:

  • alfa-béta keresés negamax változata,
  • elsődleges variáció elemzése,
  • iteratív mélyítés,
  • transzpozíciós tábla,
  • történeti heurisztika,
  • nyugalmi állapot keresés.

Az alfa-béta keresés nem más, mint a minimax keresés vágásokkal kiegészített változata, amely matematikailag bizonyíthatóan azonos eredményt szogláltat, viszont átlagosan sokkal kevesebb idő alatt. A keresés során az aktuális játékállapot értéke alfa és béta értékek közé kell, hogy essen. Ha ez nem teljesül, akkor az állás annyira jó (vagy rossz), hogy a játékos - akinek a lépését elemezzük - úgysem fogja azt választani, tehát fölösleges tovább vizsgálni azt. Az alfa és béta távolságát nevezzük ablaknak.

Az elsődleges variációs elemzés egy extra kiegészítés az alfa-béta kereséshez, ami egy elfogadhatóan jó lépés megtalálása után a többi lépést a lehető legszűkebb ablakkal vizsgálja. Ennek a haszna, hogy a (későbbiekben leírt) lépésrendezés miatt jó eséllyel az elsőnek vizsgált lépés lesz a legjobb, ezért nagyon sok vágás fog bekövetkezni a keresés során.

Nulla szélességű ablakkal keresve csak annyit tudunk eldönteni, hogy a vizsgált játékállás jobb vagy rosszabb-e, mint az eddigi legjobb (alfa), viszont ezt sokkal gyorsabban megtehetjük, mint a normál keresést. Tehát a lépésrendezés miatt jó eséllyel az első vizsgált lépés lesz a legjobb, és a többiről elég bebizonyítani, hogy nem jobbak nála. Persze ha ez nem bizonyítható (azaz a lépés jobb), akkor ezt újra kell vizsgálni normál méretű ablakkal, hogy megkapjuk a lépés valódi értékét. Ezután folytathatjuk a nulla ablakos keresést.

Az iteratív mélyítés több célt szolgál. Ez egy keret az alfa-béta algoritmus fölé, ami a teljes keresést több lépésben végzi el. Először egy 1 mélységű, aztán 2 mélységű, 3 mélységű stb. kereséseket végez. Ennek előnye, hogy a keresések között ritkán változik meg a legjobbnak vélt lépés (azaz egy 3 mélységű keresés és egy 4 mélységű keresés sokszor ugyanazt a lépést választja), tehát az előző keresés eredményét felhasználva a következő mélység keresésekor adunk egy jó tippet az alfa-béta algoritmusnak. Ez lehetővé teszi, hogy sok vágást végezzen az algoritmus, mert egy jó lépést próbál elsőként. Ezzel együtt megnöveli a keresés sebességét is, mert a vágások miatt ugyanolyan mélységű keresés elvégzéséhez kevesebb játékállást kell megvizsgálnia. Még egy előnye van az iteratív mélyítésnek: jobb időgazdálkodást tesz lehetővé. Mielőtt elkezdenénk egy 10 mélységű keresést, ami időigényes lehet, végzünk előtte 1, 2, 3, … mélységű kereséseket is. Ha eközben az algoritmus kifut az időből, akkor is rendelkezik már egy megalapozottan kiválasztott lépéssel, mert szinte lehetetlen nem befejezni egy 1 mélységű keresést. És a mélyítésnél nyugodtan megszakítható a keresés (pl. időtúllépés miatt), nem kell a félig felépített keresőfákkal bajlódni.

A történeti heurisztika szerepe előállítani egy olyan sorrendjét a vizsgálandó lépéseknek, amiben az első lépések között szerepel a keresés által majd kiválasztott legjobb lépés. Ezt tapasztalati úton tudja megvalósítani, azaz ha egy állásban találunk egy jó lépést, akkor ezt a lépést érdemes lehet egy következő hasonló állásban is az elsők között megvizsgálni, mert lehet, hogy ugyanaz lesz a hatása.

Példának egy sakkállás (2. ábra): világos lép, sötét vezér mattal fenyeget h2-n. A keresőalgoritmus nézi a lépéseket: a2-a3, és a lehetséges válaszok között előbb-utóbb megtalálja d6-h2++ mattot. Ezután vesz egy másik lehetséges lépést: a2-a4. Ha most minden gondolkodás nélül újra végigkeresné a válaszokat, megint megtalálná a d6-h2++ mattot. Viszont ha emlékezne valahogy erre a „gyilkos lépés”-re, akkor megspórolhatná a hosszas keresést, egyből próbálhatná a d6-h2++ lépést, és azonnal kiderülne, hogy a2-a4 sem jó választás. Tehát a történeti heurisztika egy olyan táblázat, ami minden lépésben minden mezőhöz egy számlálót tartalmaz, és ha történik egy alfa-béta vágás, akkor a lépéshez tartozó számlálót növeli az algoritmus. Ezeket az értékeket felhasználva minden keresés megkezdése előtt a lehetséges lépéseket a táblázat alapján sorba rendezzük, és ez alapján dolgozunk.

2. ábra
2. ábra
Példa a gyilkos heurisztika szerepére: világos lép, és Vh2++ ellen tennie kell valamit

A nyugalmi állapot keresése a „horizont effektust” próbálja enyhíteni azzal, hogy csak olyan esetekben hívja meg az álláskiértékelő függvényt, amikor nem várható drasztikus változás az erőviszonyokban. Ez sakkban például egy olyan állás, amiben nem lehet ütni, reversiben pedig ahol egyik sarkot sem lehet elfoglalni.

Álláskiértékelő függvény

A játékprogramok talán legkritikusabb része. Feladata, hogy egy számban kifejezze, hogy az aktuális állás melyik játékosnak előnyös, és, hogy milyen mértékben. Általában ez az a pont a programokban, ahol megjelenik a tudása a programnak.

Ez a függvény egy heurisztikus függvény, azaz a szabályok ismerete helyett olyan játékspecifikus ismeretekre van szüksége, ami alapján minőségi értékelést tud adni. Persze fel kell ismernie a végállapotokat is (például sakkban a patt, matt), és ezeknek lehetőleg tényleges értéket szolgáltatni. A függvénynek lehetőleg képesnek kell lennie felismerni rejtett taktikai buktatókat, hogy minél kevésbé hibázzon a program; persze mindezt a lehető leggyorsabban, hogy ne vegyen el sok időt a kereséstől.

Hiába tud egy program sok-sok lépést előre keresni, ha gyengén méri fel az ott talált állásokat, és ez alapján rossz lépéseket játszik meg. Viszont egy olyan program sem biztos, hogy erősen játszik, ami nagyon pontosan tud értékelni egy-egy állást, de ehhez rengeteg időt fogyaszt el, és ezért csak pár lépéssel tud előre keresni.

A (világ)bajnok reversi programokat tanulmányozva szembetűnő megoldás volt minták felismerésével megoldani a kiértékelést. A legerősebb programok tartalmaznak valamilyen mintafelismerést, és nem ritka az olyan kiértékelő függvény sem, ami csak ilyeneken alapszik. LOGISTELLO, egy világbajnok reversi program, amit Michael Buro készített, ~40 különböző szerkezetű mintát keres a játéktáblán, és ezek alapján értékel egy állást. Ezek a minták például a sarkok 3×3-as környezeteit tartalmazzák (3. ábra), a sorokat, az oszlopokat, a széleket a hozzájuk tartozó két X mezővel (4. ábra), a 3 mezőnél hosszabb átlókat, és a sarkok 2×5-ös környezeteit (5. ábra).

3. ábra
3. ábra
LOGISTELLO – sarkok 3×3-as környezete
4. ábra
4. ábra
LOGISTELLO – táblaszél és a két X mező
5. ábra
5. ábra
LOGISTELLO – sarkok 2×5-ös környezete

A kiértékelőfüggvény ezek után az összes mintát „leveszi” az éppen aktuális tábláról, és egy táblázatból kiveszi a hozzájuk tartozó értékeket külön-külön. Az így kapott értékeket egyszerű lineáris operátorral (összeadás) összesíti, és a kapott érték az állás értéke. Természetesen ezekhez a mintákhoz tartozó értékeket előre be kell állítani. Ez viszont kézzel már nem elvégezhető, mert rengeteg minta van. Ráadásul a minták jelentése az emberek számára általában nem egyértelmű, mert az emberek máshogy gondolkodnak. Buro a „tanításra” egy játszmaadatbázist használt, ami emberi és erős gépi játékosok játszmáit tartalmazta vegyesen, és ezekre behangolta a több ezer paramétert.

Larion állásértékelő függvénye

Larion esetében kissé más a helyzet. Itt nem használhatók fix méretű minták, mert tetszőleges alakú táblán tudnia kell játszani a programnak. Mégis, ha versenyképes (vagy legalább játékerős) programot akarunk, akkor valahogy a mintafelismerésen alapuló értékelés lehet célravezető. Ezért Larion is mintákat használ, viszont ezek a minták nem közvetlenül a bábuk elhelyezkedéséből adódnak, hanem egyéb tulajdonságokat számol belőlük, és ezeket kezeli mintáknak. Ezzel inkább az emberi gondolkodás felé hajlik, nem úgy, mint pl. LOGISTELLO. Larion a következő tulajdonságokat vizsgálja:

  • mobilitás,
  • ellenfél potenciális mobilitása,
  • stabil bábuk,
  • birtokolt sarokmezők,
  • birtokolt központi mezők,
  • birtokolt oldalsó mezők,
  • birtokolt minősítetlen mezők,
  • birtokolt veszélyes mezők,
  • bábuk száma,
  • tipikus oldalfelállással rendelkező oldalak száma,
  • tipikus oldalfelállású oldalak,
  • soron következő játékos.

Viszont ahhoz, hogy ilyen tulajdonságokat tudjon számolni, szükség van a tábla szerkezeti ismeretére is (pl. központi mezők ismerete). Ez az analizálás egy tábla betöltésekor megtörténik. Az analizálás során a tábla celláit a következő osztályokba sorolja:

  • A (sarok) mező,
  • B (sarok) mező,
  • C (központi) mező,
  • E (oldalsó) mező,
  • P (nem minősített) mező,
  • W (sarok melletti) veszélyes mező,
  • X (sarok melletti) veszélyes mező,
  • Y (sarok melletti) veszélyes mező,
  • Z (sarok melletti) veszélyes mező.

Az ’A’ és ’B’ mezők közötti különbség a birtoklásukkal potenciálian támadható mezők száma, és a táblán lévő összes mező számának arányából adódik. Az ’A’ mező valamivel értékesebb lehet (emberi szempontból), mint a ’B’ mező. Egy táblán lehet, hogy csak ’A’ vagy csak ’B’ sarokmező van, de lehet az is, hogy mindkettő. ’W’, ’X’, ’Y’, ’Z’ mezők közötti különbség hasonlít az ’A’ és ’B’ viszonyára. Ezek olyan mezők, amik érintkeznek ’A’ vagy ’B’ mezőkkel, tehát ha egy sarok szabad, akkor birtoklásuk az ellenfelet sarokmezőhöz juttathatja, ami jelentős élőny lehet a játék elején és közepén. A ’Z’ mező a legveszélyesebb (emberi szempontból) és a ’W’ a legkevésbé. Egy táblán többféle mező is előfordulhat.

’E’ mezőnek minősül minden olyan mező, ami a tábla szélén van, és nem ’A’, ’B’, ’W’, ’X’, ’Y’, vagy ’Z’ típusú. Oldalsó mezők birtoklása változó hatású lehet. ’C’ mezőnek minősül minden olyan mező, ami a tábla geometriai közepe környékén van. Ennek a meghatározása valamivel bonyolultabb, mert olyan tábla esetén is pontos, ami több táblára van bontva (pl. 6. ábra). Ennek a meghatározása úgy történik, hogy vízszintesen és függőlegesen az összes sarokpont között meghatározzuk a függőleges illetve vízszintes felező egyeneseket, és ahol ezek metszik egymást, onnan kiindulva bejelöljük a központi mezőket. Az összes ilyen pontra ráillesztünk egy 7 mező átlójú rombuszt, és a fedésben lévő cellát megjelöljük. Ezután a táblához nem tartozó mezőkre ráillesztünk egy 5 mező átlójú rombuszt, és a fedésben lévő mezők jelölését megszűntetjük, ha az előbb megjelöltük. Ezután minden jelöltként maradt mezőt ’C’ típusúnak minősítünk. Az összes maradék mező, amit semmilyen módon nem jelöltünk, ’P’ típusú lesz.

6. ábra
6. ábra
Több táblára bontott tábla
7. ábra
7. ábra
Szabványos tábla mezőinek típusai Larion szerint

Egy szabványos 8×8-as reversi tábla mezőinek típusa a 7. ábrán látható.

A mezők típusának ismeretén kívül még szükségünk van az összes oldalmező gyors elérésére, hogy stabilitást és oldalkonfigurációkat tudjunk számolni. Ehhez létrehozunk egy listát, amibe belerakjuk az összes ’A’, ’B’, és ’E’ típusú mezőt.

A kiértékelőfüggvény először is megnézi, hogy a játék véget ért-e. Ezt a lépésgenerátor által beállított állapotjelző alapján dönti el. Ha a játék véget ért, akkor egszerűen visszaadja a sötét és világos bábuk számának különbségét. Ha a játék nem ért véget, akkor kiszámolja a potenciális mobilitást, szükség esetén a stabilitást és az oldalkonfigurációkat, és megszámolja a különböző típusú bábukat. Ezekből az értékekből ki tudja számolni, hogy a mintákat tartalmazó táblázatokban hova kell indexelni, és az ott talált értékeket egyszerűen összegzi, és egészre kerekítve visszaadja.

A táblák indexelése felvet egy újabb problémát. Egy kicsi táblán (8×8) sokkal kisebb tartományban mozoghat például a bábuk száma, mint egy nagy (14×14) táblán. Ha közvetlenül a darabszámokat használnánk indexeléshez, akkor ha az egyik táblán pontos eredményt számolunk ki, akkor a másik táblán valószínűleg hibás következtetésekhez jutunk; esetleg mindkettőn rosszul számolunk. Ezért az indexelések egy normalizált tartományban történnek, és a mindenkori táblának megfelelően arányosan átszámoljuk a kapott értékeket indexekre. Ez általában a táblán lévő mezők számától függ.

További finomítás, hogy a játékot 20 játékszakaszra osztjuk, mert a megnyitásban és a végjátékban merőben más-más stratégiák működnek jól. Mivel a programunk igen nagy táblákon is képes játszani, ahol sok lépés van, ezért a 20 játékszakasz szükségesnek bizonyul.

Paraméterek hangolása

Larion jelenleg 53360 paramétert használ. Nyilvánvaló, hogy ennyi paramétert kézzel beállítani pontosan rendkívül időigényes lenne. Szükség van tehát egy automatizált folyamatra, amit szokás tanulásnak is nevezni.

Larion tanításához használt algoritmus a MOUSE algoritmus, amit Kostas Tournavitis publikált 2002-ben. Ez egy megerősítéses tanulást megvalósító algoritmus. Az alapötlet úgy tanítani a programot, hogy az ne igényeljen emberi beavatkozást.

Ez több problémát is felvet: biztosítani kell, hogy a program lehetőleg minél több különböző játékállást megvizsgáljon (felderítés), és azt is biztosítani kell, hogy a tanulás során jónak bizonyult variációkat gyakrabban újrajátssza (kiaknázás).

A felderítés lényege, hogy a program olyan variációkat is kipróbáljon, amiket korábban még nem próbált, a kiaknázásé pedig, hogy bebizonyítsa (vagy megcáfolja), hogy a jónak vélt variációk tényleg erősek. A kiaknázás során a véletlenek szerepét próbáljuk meg minimalizálni a nagy számok törvénye alapján. A MOUSE algoritmus a TD(λ) algoritmusra épül. Ez utóbbi talán az eddigi legjobb megerősítéses tanulásos algoritmus, ami skalárral való jutalmazáson keresztül lehetővé teszi, hogy már a meglévő felügyelt tanító technikát a kiértékelő függvény finomhangolására használjuk. λ a temporális differencia előterjesztésének mértékét határozza meg. λ = 1 esetén a parmétervektort úgy hangoljuk, hogy egy t időpillanatban előrejelzett értéket közelebb viszünk a végeredményhez. Ezt nevezik Monte-Carlo visszatérésnek is. Ez a frissítések során nagyobb változásoknak van kitéve, mert a jutalmazások véletlenszerűek lehetnek. Az egyoldalúság és a változatosság közötti kompromisszum csökkentése érdekében TD(λ) exponenciálisan súlyozott n lépéses összegeket használ λ csökkentő paraméterrel. Ha λ kicsi, akkor a tanulás lassabb, ha λ nagy, akkor gyorsabb, viszont lehetnek nagy ingadozások is.

Tapasztalatok szerint a tanulás minősége nagyban függ a játéktér felderítésének a mértékétől. Ezért törekedni kell a tanulás során a minél nagyobb mértékű felderítésre. A legegyszerűbb megközelítés, hogy mindig véletlenszerűen választjuk ki a következő lépést. Kétségtelenül ez a stratégia járja be a legnagyobb játékteret, viszont hiányzik belőle a kiaknázás, ugyanis valószínűtlen, hogy ugyanaz az állás megismétlődik, és ugyanazt a lépést választjuk ki, hogy nagy jutalmakat kapjunk. A másik oldalon pedig ott van, hogy mindig a legjobbnak vélt lépést válasszuk (mohó stratégia), több jutalmat kap, de hiányzik belőle a felderítés. Az ε-mohó stratégia megpróbál egyensúlyozni a kettő között. Ezzel a módszerrel a tanulás a mohó stratégiát követi, de ε valószínűséggel másik lépést választ.

Tournavitis a cikkében részletesen leírja ennek a stratégiának a működését, a tapasztalatokat, és a változtatásokat. A végleges konklúzió, amit Larion is használ, hogy az ε-mohó stratégia az első néhány lépését mindenképpen véletlenszerűen játsza, és csak azután kezdi el a tényleges ε-mohó stratégiát. További nehézségeket jelent a megerősítéses tanulás használata, ha függvényközelítésre használjuk. Ezek nevezetesen a zajos becslések és az általánosítás. Egy állapotban a paraméterek megváltoztatása hatással lesz a többi állapot előrejelzésére is. Ennek egyik megoldása, ha a paramétereket nem azonnal változtatjuk meg, hanem csak az első MinDarab előfordulásuk után, ahol MinDarab » 1. Ez egyszerre csökkenti az eltéréseket és a zajos becsléseket. Az esetek túlnyomó többségében viszont egyetlen játék során a minták nagy része nem szerepen többször, mint MinDarab. Ennek orvoslására több játékot is lejátszunk, mielőtt a paramétereket ténylegesen megváltoztatnánk (1 korszak). Önmagában ez is képes a zajt csökkenteni. Sajnos a korszakok hosszának a növelése a tanítási időt is növeli.

A MOUSE(μ) algoritmus

Kostas Tournavitis publikációjának fordítása - részlet

A MOUSE algoritmus (MOnte-Carlo learning Using heuriStic Error reduction) a fenti megfigyelések további finomítása. Az előzőkben tárgyalt technika hibája, hogy még ha egy korszak hosszát 100000 játszmára növeljük, akkor sem biztos, hogy egyes minták előfordulnak MinDarab-szor. Ezeket a mintákat pedig ilyenkor nem lehet finomhangolni.

Többfajta ötlet tanulmányozása után Tournavitis a következő megoldást választotta:

  • Feltételezés: A korábbi korszakok során a kiértékelőfüggvény rosszabb volt, mint a mostani. Sőt, minél korábbi egy kiértékelőfüggvény, annál rosszabb.
  • Heurisztikus modell: Az utolsó korszak kiértékelési hibái egy k = 1/μ értéknél rosszabbak, ahol 0 < μ < 1, és μ egy heurisztikus paraméter, aminek jelentése, hogy a tanulóalgoritmus mennyire bízhat egy korábbi kiértékelésben. Ez a lineáris modell feltehetően jó közelítés megfelelően kicsi tanulási együttható esetén.
  • Algoritmus: A legutóbbi kiértékelési hibákat szorozzuk meg μ-vel, adjuk hozzá a mostani korszak kiértékeléséi hibáihoz, és végezzünk egy kis lépést a gradienssel ellentétes irányban. Minták esetében ennek a kiszámítása nagyon egyszerű: meg kell szorozni a hibákat μ-vel minden egyes minta esetén.

Az algoritmus hatékonyságáról és összehasonlításáról Tournavitis cikke sok részletet közöl, amiktől én most eltekintenék. Végeredményben egy rendkívül jól használható tanító algoritmust kaptunk, amit bizonyít, hogy Charly+ (Tournavitis reversi programmotorja) nulla tudásról képes volt megtanulni úgy játszani, hogy a világ legjobb programjaival megmérkőzve 4-ik helyezést ért el egy bajnokságon.

Larion tanítása

Kissé át kellett gondolni a MOUSE algoritmust, hogy Larion esetében is használható legyen. Ennek okai, hogy Larion tetszőleges táblán képes játszani, azaz másfajta mintákat használ, és, hogy a rendelkezésre álló erőforrások teljesítménye is viszonylag kicsi. Míg Charly+ egy csúcstechnológiákkal felszerelt, kioptimalizált versenyprogram, addig Larion egy jóval lassabb – bár erősen optimalizált – tanulási célokkal megírt program.

Charly+ esetében egy korszak hossza 100000 játékból állt, és MinDarab = 100 volt a minták módosításának előfeltétele. A program 5 napig tanult, ezalatt több milliárd játékot játszott le.

Larion esetében arra is figyelni kellett, hogy lehetőleg minden fajta táblán nagyjából azonos szinten játszon. Ezért egy korszakban 4 teljesen különböző játéktáblán lett tanítva, amelyek a 8.-11. ábrákon láthatók. Ez a négy tábla tartalmazza az összes lehetséges típusú mezőt, amit a korábbiakban leírtam, és ezek közül 3 szabványosnak mondható versenytábla is. Az általam választott tanulási együtthatók a következők voltak:

  • Korszak hossza = 4 * 125 (minden táblán 125 játszma)
  • MinDarab = 20
  • α = 0,01 (tanulási együttható)
  • μ = 0,95 (hiba előterjesztési együttható)
8. ábra
8. ábra
Normál 6×6-os tábla
9. ábra
9. ábra
Normál 8×8-as tábla
10. ábra
10. ábra
Nyolcszögletű 10×10-es tábla
11. ábra
11. ábra
Átlós elrendezésű 6×6-os táblák

A korszakhossz és MinDarab azért lett lecsökkentve (Charly+-hoz képest), mert a program jelentősen lassabban számol. A fenti beállításokkal Larion 20.000.000 játékot játszott végig (40.000 korszak), amihez körülbelül 3 napot vett igénybe egy 2600 MHz-es Celeron processzoron. Larion is az ε-mohó stratégia módosított változatát használja, azaz a lépések első 20%-át (a maximális lépésszámhoz viszonyítva) véletlenszerűen választja, ezután viszont csak 20% eséllyel választ ki véletlen lépést, 80% eséllyel egy 2 mélységű alfa-béta keresés végeredményét használja. Az alfa-béta keresésnél újabb döntést kellett hozni: pontos eredményekkel hangoljuk a paramétereket, vagy inkább sok kevésbé pontos értékkel. Larion inkább az utóbbi megoldást választotta, mivel az eredmények pontosítása exponenciálisan növelte volna a futásidőt (4 mélységű kereséssel hetekig futott volna).

A tanulás során a paraméterek alakulását rögzítettem. Sajnos csak kevés adat került tárolásra, így pontos következtetéseket nehéz levonni belőlük. A program további javítása előtt célszerű újra elvégezni a mostani tanítást részletesebb adatok tárolásával. Amiket érdemes lenne figyelni:

  • játékszakaszonkénti paraméterek alakulása,
  • táblánként különbontani a paraméterek változását.

A most rendelkezésre álló adatok csak a paraméterek hibáinak együttes változását mutatják tekintet nélkül arra, hogy melyik paraméter melyik játékszakaszhoz tartozik. Ennek a grafikonja látható a 12. ábrán.

12. ábra
12. ábra
A paraméterek átlagos hibájának változása a korszakok előrehaladtával

Mint látható, az első pár játék során a hiba 0-ról felszökik rendkívül nagy értékekre. Ez annak a következménye, hogy kezdetben minden paraméter értéke 0, és az első pár játszma alapján a hiba továbbterjesztés miatt az hibák nőnek (ameddig nem fordulnak elő újra a minták). Az is tisztán kivehető, hogy ezután gyorsan elkezd csökkenni az átlagos hiba, és körülbelül a 600-ik korszak után már jelentősen lecsökkent. A táblázat csak az első 20000 korszak hibáit tartalmazza, a további 20000 korszak nem hozott jelentősebb javulást. Ennek oka lehet, hogy a 20 játékszakasz hibáit összegezve ábrázoltuk. Sajnos nem áll rendelkezésre a tanulás során a hibák játékszakaszonkénti mértéke, bár érdemes lenne tanulmányozni.

Az eredmények meglepően jók, Larion játékereje igen jó. Érdemes lenne tovább kísérletezni, hogy a paraméterek változtatása milyen mértékben módosítja a játékerejét a programnak. Elsősorban a korszakok hosszára, és a MinDarab hangolása lehet érdekes, de a játékszakaszok számának változtatása is hozhat javulást. Nem tűnik azonban jónak, hogy további tulajdonságokat vegyünk fel vizsgálatra a meglévők mellé (mint például paritás viszgálat), mert a táblák általános szerkezete miatt ezek ellenőrzése rendkívül bonyolult és időigényes lenne.

Larion teljesítményének értékelése

Larion a kitűzött célokat teljes mértékben teljesíti. Sikerült megalkotni egy olyan általános játékmotort, ami 0 tudásról indulva, csak önmagával játszva képes volt elérni egy komolyabb amatőr játékos szintjét. Első próbálkozásra ez igen komoly eredmény. További javulást lehetne elérni a keresőmotor jobb optimalizálásával, illetve a tanulást befolyásoló paraméterek finomhangolásával. Ez utóbbi azonban rengeteg időt igényelne még egy komolyabb erőforrásokkal rendelkező hardveren is. Érdemes lehet megfontolni a tanító algoritmus átírását úgy, hogy az képes legyen egyszerre több számítógépen is futni, ezzel is növelve a tanulás sebességét.

Felhasznált irodalom