Sakkprogramozás
Fogalmak:
sakk
Kapcsolódó könyvfejezetek:
6.1. Kétszemélyes játékok
Kapcsolódó könyvfejezetek:
6.6. A jelenleg legfejlettebb játékprogramok A tartalom szövege (HTML):
Sakkprogramozás
Sakkprogramozás történelmi áttekintése
A sakkprogramozás hosszú ideje kihívást jelent az emberiség számára [6]. Már a 18. században szenzációt jelentett Kempelen Farkas „A Török” nevű gépezete (1. ábra), amely kitűnő eredménnyel győzte le kihívóit - sajnos később azonban kiderült, hogy a gép egy emberi játékost rejtett magában, így ez még nem a sakkprogramozás igazi kezdete volt.
1. ábra. Kempelen Farkas gépe, „A Török”
Az 1940-es években megjelenő első primitív elektromos számítógépek alapvetően háborús célokra készültek, azonban a tudósok felfedezték a számítógépek nyújtotta lehetőségeket és hamar hétköznapi emberi feladatok megoldását akarták gépesíteni. A gondolkodó gép nagyon népszerű elképzelés volt már ebben az időben is, és a tudósok úgy gondolták, hogy a sakkozás problematikája megfelelő kihívás az intelligens számítógépek számára. Egy angol tudós, Alan Turing 1947-ben megírta az első sakkozni képes programot, de számítógép híján toll és papír segítségével tesztelte. ’49-ben Claude Shannon leírta a máig használt alapvető algoritmusokat.
Az 1950-es években a számítógépek szűkös számítási kapacitása miatt csak nagyon egyszerű programokat tudtak írni, de az ’60-es években készített sakkprogramok már képesek voltak legyőzni egy amatőr játékost. 1967-ben indult el először sakkversenyen számítógép és 1400 pontot ért el, ami egy jó gimnáziumi játékos szintjét jelentette.
A ’70-es évektől gép-gép sakktornákat indítottak, amely a tudósokat tovább ösztönözte. Ekkorra kialakult a két alapvető megközelítés: tudás-alapú és “brute force” jellegű. 1977-ben a Belle nevű eszköz már 160.000 pozíciót vizsgált másodpercenként. Ekkor megjelentek a máig használt algoritmusok elődei is, amelyekről később fogok írni. A ’80-as évek közepére egyre gyakoribb volt, hogy egy sakktornát gép nyerjen. A ’90-es években egyre több különböző mikroprocesszorra épülő sakkozó gép készült és már nagymester szintű játékosokkal is összemérték tudásukat.
Az igazi nagyon áttörést az IBM által fejlesztett Deep Blue jelentette, amely az első ember által készített gép volt, amely megverte az aktuális sakkvilágbajnokot. Az 1997-es Kasparov elleni győzelem bebizonyította, hogy a számítógépek jobb sakkjátékosok lehetnek, mint bármely ember. A mérközés illetve az IBM által készített gép részleteit az írásom végén mutatom be.
Egy sakkprogram alapvető működése
Egy sakkprogram megírása során alapvető fontosságú a teljesítményoptimalizálás. A hatalmas állapotterű keresések rendkívül gyors adatmodellt igényelnek, így nagyon fontos, hogy a program hogyan tárolja a sakktáblát, valamint, hogy hogyan kezeli a szabályokat. A lehetséges lépések felderítésének megvalósításánál a gyorsaságra és a kis memóriaigényre kell törekedni, hiszen ez egy rendkívül gyakori művelet. Ezek azonban csak az alapokat adhatják meg a rendkívül hatékony algoritmusoknak.
A mesterséges intelligencia tudományában minden a keresésen alapul és nincs ez máshogy a sakkprogramozásnál sem. Ebből kifolyólag szeretném áttekinteni a ma használt kereső algoritmusokat.
Minimax
Minden itt használatos keresés őse a Minimax keresés [2]. Tegyük fel, hogy van arra mód, hogy minden egyes pozícióról eldönthetjük, hogy az melyik játékosnak kedvez. Ha a pozíció A játékosnak kedvez, akkor az valamilyen pozitív számmal értékelhető, ha B-nek, akkor negatívval. Ha mindkettőnek ugyanolyan jó, akkor az értelem szerűen 0 pont. A kiindulóállapot “döntetlen”, azaz 0 pont. Innen minden játékos hozzáadhat vagy kivonhat pontokat. Az A játékos célja, hogy maximálja, a B játékosé, hogy minimálisra leszorítsa a pontokat. A keresés során minden lehetséges lépéssort egy számmal értékelünk, majd a legoptimálisabbat kiválasztjuk. A probléma ezzel, hogy a keresési tér hatalmas, azaz rengeteg féle lépés létezik, hiszen a keresés komplexitása exponenciális.
Egy játékos lehetséges lépéseinek száma az elágazási tényező (b, mint branching factor). Az előre megvizsgált lépések számát d-vel jelöljük (mint depth). A keresés komplexitása O(bd), amely egyértelműen exponenciális. A szemléltetés végett, egy sakkjátszma közepén, nagyjából 35 különféle lépést tehet meg a játékos. Ilyen esetekben egy 4 lépés/játékos -t vizsgáló (8-ply) algoritmusnak 1500000 utat kellene megvizsgálnia.
Alfa-béta vágás (Alpha-Beta Pruning)
A minimax keresés belátható, hogy helyes eredményt ad (azaz a keresés teljes), de az is belátható, hogy lassú. Olyan ágakat is megvizsgál, ahol már az első lépéstől egyértelmű, hogy jó nem sülhet ki belőle. Ezen próbál az Alfa-béta vágás segíteni [1]. Az alapötlet, hogy ha a lépésünkre az ellenfélnek már van egy nagyon erős lépése, akkor azt inkább ne is vizsgáljuk tovább.
Az algoritmus működése során számon tart egy alfa értéket, amely azt a minimális értéket tárolja, amit a maximalizáló játékos már biztosított magának a keresés eddigi részéből. Ennek megfelelően egy béta értéket is számon tarthatunk, ami az a maximális érték, amit a minimalizáló játékos már megtalált. Az algoritmus kezdetekor ezek plusz és minusz végtelen értékűek. A alfa és béta értékek által közbezárt itervallumablak folyamatosan szűkül. Amikor ez az intervallumablak bezárul, akkor már nem érdemes tovább vizsgálódni, hiszen - mindkét játékosról a legjobb játékot feltételezve - nem állható elő az az állapot. Ez az algoritmus továbbra is megtalálja a legjobb lépést, de a lépésszáma O(sqrt(bd))-re is lecsökkenhet.
Ehhez azonban szükséges, hogy mindig a lehető legjobb lépést vizsgáljuk meg elsőként. Legrosszabb esetben az is előfordulhat, hogy nincs javulás, hiszen a lépéseket pont a leggyengébbtől a legjobb felé vizsgáljuk. Erre a megoldást a lépések a keresést megelőző rendezése teszi lehetővé. Ha tudnánk azonban, hogy melyik lépés a legjobb, nem lenne értelme keresni, tehát ez nem olyan egyszerű. A megfelelő heurisztika megalkotásánál csak iránymutatások ismertek, így leginkább próbálkozni lehet érdemes. A királynő feláldozása például a legtöbb esetben nem jelent győzelmet, tehát ezt érdemes a vége felé vizsgálni. Ehhez hasonló ötletekkel lehetséges lényeges gyorsulást előidézni a keresésben.
Iteratívan mélyülő Alfa-Béta vágás
A kereső algoritmusok esetében az iteratívan mélyülő megoldások sokszor nagyon hatékonyak. Lehetővé teszi, hogy a mélységi keresés alacsony tárigényét valamint a szélességi bejárás teljességét ötvözzük. Az Alfa-béta vágás iteratív változatában először 1 mélységig végzünk egy keresést [2]. Ennek eredménye alapján sorrendezzük a lépéseket, majd végzünk egy 2 mélységű Alfa-béta keresést és így tovább. Ez a keresés egyértelműen növeli a vágások hatékonyságát és gyakoriságát és így lényegesen gyorsítja a keresést, annak ellenére, hogy látszólag többször kell egy ágat vizsgálni.
További keresést optimalizáló ötletek
Természetesen végtelen számú olyan trükk és ötlet létezik, amely a keresést hatékonyabbá teszi. Éppen ezektől lehet egy sakkprogram sikeres. Ezekből néhányat szeretnék most röviden bemutatni.
Az Alfa-béta keresés (még az iteratívan mélyülő verzója is) egy fát jár be. Ez a fa, azonban bizonyos helyeken ismétléseket tartalmazhat, hiszen akár különböző lépéssorokkal ugyanazt a végeredményt is elérhetjük. Ebben próbál segítséget nyújtani a transzpozíciós tábla [1], amely gyakorlatilag egy gyorsítótárként funkcionál a kereséshez. Ahelyett, hogy a részfát másodszor is feleslegesen bejárjuk, inkább ebből a táblázatból olvassuk ki az eredményt. Ezzel számottevő gyorsulást lehet elérni. Az iteratívan mélyülő megoldások esetén a tábla hatása még szembetűnőbb, hiszen ott újra és újra be kell járni az előző szinteket is. Ezeket ezzel a táblával lényegesen meggyorsíthatjuk.
A kereséseket eddig minden ágon ugyanolyan mélységbe végeztük. Ez nem mindig jó. Sokkal hatékonyabb, ha a keresést olyan mélységig végezzük, ahol már a játék “megnyugszik”, azaz épp nem történik ütés.
Sok esetben hasznos lehet, ha megvizsgáljuk mi történik akkor, ha feltételezzük, hogy mi nem lépünk, de az ellenfél kettőt is. Ez nyilván a szabályoknak nem felel meg, de érdekes információkat rejthet, azaz jó heurisztika lehet. Például ha én nem lépek, de az ellenfél két lépés alatt sem tud felülkerekedni rajtam, akkor biztosak lehetünk abban, hogy az előző lépésem nagyon jó volt. Mindezt anélkül, hogy az összes lehetséges lépésemet megvizsgáltuk volna, ami lényeges erőforrás megtakarítást jelent.
Lépések kiértékelése
Egy másik alapvetően fontos állítás, hogy a programnak tudnia kell, hogy melyik lépés a legjobb számára, azaz valami módon rangsorolnia kell a lépéseket [2], [3]. Amíg a kereső algoritmusok viszonylag általánosok, függetlenek a sakk szabályaitól, addig a lépések értékeléséhez szükséges algoritmusok nagyon szorosan a szabályokhoz kapcsolódnak. Ebben a fejezetben ezeket szeretném sorra bemutatni.
A legegyszerűbb megoldás az úgynevezett „Material Balance” módszer, amely egyszerűen értékeket ad minden bábunak. Különböző irodalmak ([2], [3]) különböző konkrét értékeket ajánlanak, azonban arányokban nagy különbség nem található. Nagyságrendileg a király végtelent ér, a királynő 900 pontot, a bástya 500-at, a futó 325-öt, a huszár 300-at és a paraszt 100 pontot.
A cél, hogy a bábuink értéke maximális legyen, valamint, hogy az ellenfélnek minél nagyobb veszteséget okozzunk. Némileg talán meglepő, hogy egy ennyire egyszerű algoritmus hatékony lehet, de sok olyan program készült amely csak ezt az elvet alkalmazza. A módszer előnye, hogy az ezt használó kereső algoritmus képes könnyedén megtalálni azt is, hogy mikor érdemes feláldozni egy bábut, hiszen ha kellően sok lépéssel előre lát, akkor észreveheti, hogy néhány lépésen belül akár matt is adható, annak ellenére, hogy egy értékes bábut elveszít.
Egy másik figyelembe vehető értékelési szempont a mobilitás, azaz hogy hány elérhető lépése lesz a bábunak. Belátható, hogy ha egy bábu több lépésből választhat, akkor valószínűbb, hogy megtalálja a jó lépést. Figyelembe kell azonban venni, hogy egy futár például megteheti, hogy oda vissza járőrözik, ennek azonban értelme nem sok van.
A táblán való uralkodás figyelembevétele is fontos lehet egy pozíció megítélésénél. Egy mezőn akkor uralkodik egy játékos, ha van olyan bábuja, ami azt a mezőt képes megtámadni. Nyilvánvaló, hogy egy általunk uralt területre lépni általában biztonságos, míg az ellenfél által uralt terület veszélyes. A sakkban nagyon fontos a tábla közepének uralása és ezt különösen fontos a nyitásnál figyelembe venni. Ezeknek a kezelése azt igényli a programtól, hogy nyilvántartsa, hogy mely területet uralja a másik játékos.
Érdemes lehet figyelembe venni, hogy melyik bábut mikor érdemes játékba hozni. Természetesen nagyon különféle stratégiák léteznek, de alapvetően megállapítható, hogy a futót és a huszárt érdemes korán előre küldeni, a királlyal érdemes hamar sáncolni, a bástyák és a királynő pedig maradjon a helyén egészen addig, amíg valami meghatározó támadási lehetőségük nem lesz.
A parasztok habár a legkisebb értékű bábuk, létszámuk miatt érdemes lehet külön foglalkozni velük egy lépés értékelésénél. Amennyibe egy paraszt az ellenséges parasztok mögé kerül, az rendkívül előnyös, hiszen könnyedén komoly károkat okozhat és akár királynővé is cserélhető. Ha két vagy több paraszt egymás mögé kerül, akkor könnyedén akadályozhatják egymást, ami nem előnyös.
Összefoglalva tehát kritikus, hogy milyen módon értékeljük egy lépés eredményességét. Fontos azonban figyelembe venni, hogy sokszor a kevesebb több. Ha túl bonyolultá válik az értékelő algoritmus, akkor alkalmatlan lesz a gyors, hatékony kiértékelésre. Sok esetben jobb eredményt ad az, ha egy egyszerű értékelő algoritmus mellett inkább nagyobb mélységben keresünk a lépések után.
Garry Kasparov az IBM Deep Blue ellen
1997. május 11-én megtörtént az, amire kevesen számítottak. Vagy legalábbis csak későbbre várták. Emberek által készített számítógép legyőzte a világ legjobb sakkjátékosát. Ez döntő mérföldkő volt a mesterséges intelligencia fejlesztések számára.
Garry Kasparov 1996-ban játszott először a Deep Blue-val (2. ábra). Akkor a győzelmet aratott, annak ellenére, hogy egy játszmát a gép nyert. Egy évvel rá azonban visszavágót hirdettek és a Deep Blue továbbfejlesztett változata (becenevén Deeper Blue), 3.5 - 2.5 arányban győzni tudott [3]. Az utolsó játszma, amely a döntő volt, kevesebb, mint egy órát tartott és mindössze 19 lépésből állt.
2. ábra. Gary Kasparov Deep Blue ellen (Forrás: Wikimedia Commons, Szerző: Childman1204)
Utólag sokan próbálták elemezni a játékot és különböző megállapításokra jutottak. Amiben látszólag egyetértettek az az, hogy Kasparov hibázott. Hogy miért, azt nem tudhatjuk. Az azonban bizonyos, hogy Kasparov nem ismerte a gép játékát, míg a gép rengeteg adattal rendelkezett ellenfeléről. Egyesek szerint Kasparov nem a megszokott játékát játszotta, hanem inkább olyan trükkökkel próbálkozott, amivel talán nehézségeket okozhat egy gép számára.
Sokakban felmerült a kérdés, hogy ezzel vajon a gépek ténylegesen az emberek fölé emelkehetnek? Erre azonban a Deep Blue fejlesztői szerint még várni kell [4], hiszen azt állítják, hogy a Deep Blue nem használt mesterséges intelligenciát, hanem a nyers ereje segítségével tudott győzedelmeskedni.
A gép nagyon erősen párhuzamosan működött, hiszen 30 különálló feldolgozó egységgel rendelkezett. Néhány ezekből speciálisan a sakkhoz kötődő számításokra lett kialakítva. Ezek segítségével 200 millió pozíciót tudott másodpercenként megvizsgálni [5]. Ezt a hatalmas számot még egy mai processzor sem tudja megközelíteni (egy Intel Core 2 Duo processzor nagyjából 8 millió lépést tud megvizsgálni egy másodperc alatt). Ma persze már sokkal hatékonyabb algoritmusok léteznek, így akár egy hétköznapi gépen is nagyon erős sakkprogramokat lehet találni.
Irodalomjegyzék
[1] Computer Chess: Algorithms and Heuristics for a Deep Look into the Future, Reiner Feldmann, Lecture Notes in Computer Science, 1997, Volume 1338/1997
[2] http://www.gamedev.net/reference/programming/features/chess1/, Chess Programming, Fracois-Dominic Laramée
[3] Kasparov versus Deep Blue: The Rematch, Schaeffer J., Plaat A., ICCA Journal, 1997, Vol. 20.
[4] www.research.ibm.com/deepblue/, IBM Research – Deep Blue
[5] http://www.academicchess.org/Focus/DeepBlue/IBMbillwall.shtml, Bill Wall: Deep Blue Chess Computer
[6] http://www.computerhistory.org/chess/, History of Computer Chess
Szerző: Horányi Gergő, BME