ŠACHOVÉ ENGINY Semestrální práce pro předmět 4IZ430 Principy inteligentních systémů
Contents 1.
Úvod ................................................................................................................................................ 2
2.
Evaluační funkce .............................................................................................................................. 2
3.
Procházení stromu variant .............................................................................................................. 6
4.
Učení se ........................................................................................................................................... 8
5.
Závěr ................................................................................................................................................ 8
6.
Zdroje............................................................................................................................................... 8
1. Úvod Šachy jsou oblast, kde se dají schopnosti umělé inteligence dobře srovnávat se schopnostmi lidí. Srovnávání začlo v sedmdesátých letech a pokračuje až dodnes. V roce 1997 šachový stroj Deep Blue 2 poprvé porazil tou dobou nejlepšího lidského šachistu Garriho Kasparova. Na Deep Blue se v dalším textu budu odkazovat a ukazovat na něm mnohé principy šachové umělé inteligence. V současné době už lidské schopnosti těm počítačovým těžko konkurují a to i na relativně slabším hardwaru, jako jsou například mobilní přístroje. Pro hodnocení šachových schopností se používá hodnocení Elo, který předpokládá vyrovnané šance pro stejně hodnocené šachisty, rozdílné šance pro rozdílné hodnocení šachistů. Pokud se předpoklad nenaplní, hodnota ELO se u obou lehce upraví k odpovídající hodnotě. (Wikipedia - Computer chess) Současní nejlepší šachisté dosahují hodnoty Elo kolem 2850, stupnice reálně začíná na 1000 bodech. Na standartních počítačích dosahují nejlepší programy hodnocení přes 3250 bodů, což je v šachovém světě propastný rozdíl. (CCRL) V této práci rozeberu, na jakých principech šachové enginy pracují. Rozeberu princip výpočtu evaluační funkce, témata týkající se procházení stromu variant a některé principy, které se dají považovat za učení se šachového enginu.
2. Evaluační funkce Z důvodu komplexity stromu, reprezentujícího všechny možné šachové partie, hodnotí enginy pozice výpočtem heuristické funkce. Otázka balancování složitosti evaluační funkce a hloubky propočtu je vždy otázkou konkrétního šachového enginu. Pro rovnovážnou pozici funkce vychází 0, pro pozici výhodnější pro bílého vychází kladné číslo, pro černého záporné. Tyto parametry se dělí na statické a dynamické, rozhodující je při tom proměnlivost v závislosti na fázi hry, konkrétněji na počtu figur zbývajících ve hře. Důležitá je také kombinace těchto proměnných, věže jsou výhodnější v pozicích s odkrytými sloupci, nechráněný král v koncovce s malým počtem figur na šachovnici nemusí být vůbec problém, narozdíl od začátku hry, kdy se na šachovnici vyskytuje mnoho figur. Ve výpočtu evaluační funkce hrají roli tisíce proměnných. U Deep Blue 2 se jednalo o 8150 proměnných (Murray Campbell). Následují příklady a skupiny těchto proměnných. Materiál Příklad hodnocení materiálu:
Král – 1 000 000 bodů dáma – 9 bodů věž – 5 bodů jezdec a střelec 3 body pěšec – 1 bod (proto bývá i sám pěšec jednotkou)
Minus 0,5 bodu za zdvojené pěšce, plus 0,5 bodu za pěšce na 6. a 7. řadě (3. a 2. u černého). Dva střelci za 7 bodů, jezdec za 4 body v zablokované pozici atd. Materiál a jeho mobilita je základem pro tzv. rychlou evaluaci, kdy engine vidí okamžitě velkou výhodu v pozici a nemusí počítat funkci pomalé evaluace. Mobilita Samotná hodnota materiálu bývá často násobena jeho mobilitou, tj. počtem polí, na které se daná figura může přesunout.
Obrazek 1. Zdroj: Autor Kontrola centra šachovnice Často bývá spojena s mobilitou. Přidává bonus za kontrolu polí d4, d5, e4 a e5, případně i širšího centra
Obrázek 2. Zdroj: Autor Bezpečnost krále Přidává postihy za špatnou kontrolu v okolí vlastního krále.
Obrázek 3. Zdroj: Autor Vazby Pokud se figura nemůže hnout, protože by následovala ztráta cenné figury či je takto přivázaná přímo ke králi, mluvíme o tzv. vazbě. Odkrytý útok V případě, že figury brání v útoku na cennou figuru a bylo by možné je v dalším průběhu odstranit, hovoříme o odkrytém útoku. Převaha pěšců Pokud se na jedné straně šachovnice nalézají 2 pěšci proti jednomu soupeřovu, či 3 na 2, hovoříme o převaze pěšců na daném křídle. Je tu potenciál proměnění pěšce v dámu. V případě 4 na 3 pěšce o převaze nehovoříme. Kontrola sloupců a diagonál Odkryté a poloodkryté sloupce lze obsadit věžemi, u diagonál pak střelci. Další parametry evaluační funkce Věž na 2./7. Řadě, blokády, slabá barva, vývin figur, dobře postavené a „věčné“ figury, ... Databáze zahájení Když se na šachovnici nalézá mnoho figur, vede to logicky k nejkošatějšímu stromu možných variant. Avšak programy se vyhýbají počítání těchto variant a hodnocení evaluační funkce, protože se v šachové praxi průběhem času nasbíralo mnoho zahájení, která nevedla jasně k horší pozici a
statistické šance v těchto hrách jsou rozumné jak pro černého, tak pro bílého (a proto jsou hrané šachisty stále znovu a znovu). Počítač Deep Blue 2 využíval 2 tyto databáze – jednu menší s cca 4000 pozicemi, která byla sestavena ručně lidmi, tak aby mu co nejvíce vyhovovala. Tyto zahájení končily zpravidla ostrou pozicí a nebo pozicí, ve které Deep Blue 2 v dřívějším testování projevil, že má navrch nad statistikami lidí. Tuto databázi Deep Blue 2 preferoval. Byla zde však ještě druhá, širší databáze, která obsahoval asi 700 000 her šachových velmistrů, která měla pomoci, v případě, že by Kasparov odbočil ze stromů v první databázi. Jak se však rozhodnout, kterou linii zahrát a zároveň udržet variabilitu a nepředvídatelnost? Deep Blue byl ochoten zahrát kteroukoli větev neoříznutou alfa-beta ořezáváním (níže v textu). Na hodnocení linií měly vliv následující faktory:
Počet her ve kterých byla linie/chod zahrán Poměr mezi počtem her, ve kterých byl zahrán chod A a B Průměrná síla Elo (výše) hráču, kteří danou linii zahráli Aktuálnost partií, kde byl zahrán daný chod (čím aktuálnější, tím lepší) Výsledek partie Komentář k chodu (v šachové teorii jsou chody doplněny o značku „!“ pro chod považovaný za silný, „?“ pro chod považovaný za slabý a ještě několik dalších méně objektivních značek
Databáze koncovek Přestože šachy nebyly zatím vyřešeny do konce z počáteční pozice (o tom níže), ze všch pozic s posledními 5 figurami na šachovnici a z všech smysluplných pozic s posledními 6 figurami na šachovnici k tomu už však došlo. (Endgame Tablebases Online) Z tohoto důvodu již engine nemusí počítat ani evaluovat takové pozice, ale má je uložené v databázi, případně v paměti ROM na specializovaných strojích.
3. Procházení stromu variant Šachy jsou hrou s nulovým součtem (co jeden hráč získá, druhý ztratí) a k procházení stromu variant se používá minimax algoritmus, tj. každý hráč minimalizuje maximální možné ztráty, hráči hledají Nashova ekvilibria této dynamické hry. Cílem v šachách je mat, v horších pozicích to může být i pat a tudíž remíza. Šachy na rozdíl od například dámy nebo piškvorek nepatří k vyřešeným hrám na žádné úrovni, tj. není jasný nejlepší chod v každé pozici ani není jasné, jestli má některá ze stran ze základní pozice vynucenou výhru (jako například začínající hráč v piškvorkách 15x15 polí), nebo jestli je to při nejlepší hře remíza (jako v dámě). Vyřešení šachů je nedetrministicky polynomiální problém. Počet možných her (čili průchodů stromem variant) je až 10^120. Šachové figurky jsou následující: věž, kůň, střelec, dáma, král a pěšec. Na každém ze 64 políček může stát každá z těchto figur v jedné z dvou barev a pole může také být prázdné. Toto dává 13^64 pozic, avšak po odečtení pozic, kterých v šachách nelze dosáhnout, více než 2 králů na šachovnici, 2 šachy zároveň, pěšců na prvních řadách aj. se počet pozic odhaduje na 10^50 pozic. (Wikipedia - Shannon number) . Dnešní nejlepší počítač dosahuje výkonu 34 peta flopů (3.4*10^15) (Wikipedia - Tianhe 2), při hodnocení pozice odhadneme, že je třeba vykonat 100 operací, což je počet tahů, které se dají v dané pozici zahrát, nebo kterými se dá do pozice dostat (pokud postupujeme regresně). Za jednu sekundu tudíž tento počítač zhodnotí 3.4*10^13 pozic. Podle Moorova zákonu se výkon počítačů každé 2 roky zdvojnásobuje. Za 2 roky (cca 63*10^6
sekund). Dnes tedy nejvýkonnější počítač určíme na úlohu počítání 10^50 šachových pozic. Tudíž 3.4*10^13 * 2^n = 10^50. Proměnná n neboli počet dvouletých intervalů vychází 121, a proto se vyřešení všech šachových pozic odhaduje na 22. století. Procházení a evaluování stromu variant se dá samozřejmě velmi dobře paralelizovat, například počítač Deep Blue 2 se sestával z 30 procesorů a 480 speciálních šachových čipů. Pro další urychlení se k urychlení prohledávání stromu používají postupy zmíněné níže. Alfa-Beta ořezávání Šachový program neprochází všechny větve stromu, pro příklad větev se ztrátou dámy v klidné pozici neprochází do stejné hloubky jako relevantnější varianty. Obecně je důležité neukončovat prohledávání stromu v ostrých pozicích, tj. tam, kde následuje braní materiálu. V takových pozicích je evaluace zbytečná a mají být hodnoceny v pořadí kdy „levná figura bere „drahou“ až po situaci kdy „drahá“ bere „levnou“. Zabíjecí heuristiky Pro alfa-beta ořezávání budou nejdříve procházeny chody s nejlepšími výsledky v již evaluované pozici na stejné vrstvě (komponentě souvislosti) grafu – je šance, že se jedná o nejlepší chod a je jedno, co soupeř odpověděl. Heuristika nulového chodu Předpokládá, že následující vybraný tah vylepší pozici, tj. při alfa-beta ořezávání se tato vrstva vynechá a hodnotí se alfa-beta až v následující (musí být dobře ošetřeno, že tah skutečně vylepší pozici, jsou i takové, kde nutnost táhnout pozici prohrává). Prohledávání do hloubky s iterativně se zvyšující se hloubkou prohledávání Jedná se o kombinaci prohledávání do hloubky a do šířky, která se hodí díky řazení chodů k prohledávání, alfa-beta ořezávání a také díky schopnosti poskytnout při nedokončeném vyhledávání nejlepší chod do určité úrovně. Rozhodování se o čase Šachová partie má typicky domluvené podmínky, týkající se času. Pro vážné partie se jedná například o 2 hodiny pro každého hráče na prvních 40 tahů, další hodina pro každého na dalších 20 tahů a posléze půl hodiny pro každého s bonusem 2 sekund za každý tah pro dohrání partie. Pokud některému ze soupeřů dojde čas, jedná se zpravidla o prohru, s vyjímkou, že soupeř nemá dostatečný materiál na výhru (soupeři zbyl jen král, král s jezdcem nebo král se střelcem). V případě Deep Blue byla práce s časem následující: před každým prohledáváním byly nastaveny 2 limity: normální, který znamenal čas do další časové kontroly (vypršení času) vydělen zbývajícím počtem tahů s přidáním bufferu. Pokud je v tomto časovém limitu nalezen adekvátní tah, pozice je „normální“ a tah je zahrán. Druhý limit je „panický“ limit, který je asi jednou třetinou „normálního“ limitu. Pokud je po naplnění limitu splněná některá z následujících podmínek, čerpá se čas až do „panického“ limitu.
Aktuální nejlepší linie zhoršuje pozici o 15 a více bodů Aktuální nejlepší linie kontinuálně zhoršuje pozici
V zápase s Kasparovem z roku 1997 Deep Blue došel k limitu „paniky“ pouze jednou (Murray Campbell).
4. Učení se Mnoho výše zmíněných postupů se dá považovat za učení se. S učitelem Jelikož se všechny soutěžní partie šachu zapisují a převádějí do elektronické podoby, lze pro učení s učitelem použít databázi partií šachových velmistrů. Učení probíhá následujícím způsobem (Koppel):
Ulož si testovací pozice a chody, zahrané velmistry, které vedly k výhře S daným nastavením se evaluační funkce se pokus určit následující chod Porovnej se skutečně zahraným chodem
Zpětnovazební učení Každý z mnoha parametrů v evaluační funkci má svoji váhu a důležitý je také poměr mezi těmito vahami, také v závislosti na fázi partie. Šachové programy používají genetické algoritmy pro ladění evaluační funkce, upřednostňují nastavení, které vedlo k získání výhry či výhody v partii.
5. Závěr Rozebral jsem princip výpočtu evaluační funkce, témata týkající se procházení stromu variant a některé principy, které se dají považovat za učení se šachového enginu.
6. Zdroje (nedatováno). Načteno z Wikipedia - Computer chess: http://en.wikipedia.org/wiki/Computer_chess (nedatováno). Načteno z Wikipedia - Shannon number: http://en.wikipedia.org/wiki/Shannon_number (nedatováno). Načteno z Wikipedia - Tianhe 2: http://en.wikipedia.org/wiki/Tianhe-2 CCRL. (nedatováno). Načteno z CCRL 40/40 Rating List: http://www.computerchess.org.uk/ccrl/4040/ Koppel, P. M. (nedatováno). Načteno z Evolution and Coevolution of Evaluation Functions: http://u.cs.biu.ac.il/~koppel/papers/gm-simul.pdf Murray Campbell, A. J.-h. (nedatováno). Deep Blue. Načteno z http://commonsenseatheism.com/wpcontent/uploads/2011/02/Campbell-Deep-Blue.pdf
