Minimax a Alphabeta: cesta do srdce šachových programů

Šachové počítače jsou z hlediska laika obestřeny jakousi tajemnou aurou. Právě na šachách se kdovíproč často demo...


Šachové počítače jsou z hlediska laika obestřeny jakousi tajemnou aurou. Právě
na šachách se kdovíproč často demonstrují možnosti i omezení dnešních počítačů,
otázky, zda počítač "myslí". Jak algoritmus, umožňující počítači hrát šachy,
vůbec vypadá?
Prohledávání stromu hry
Nejdůležitější a nejzajímavější částí šachového programu je "mašinka" schopná
samostatně vymyslet tah. Dnešní šachové programy těží z několika desítek let
evoluce, jejímž výsledkem je téměř shodná základní struktura všech úspěšných
programů. Obdobně jsou postaveny i programy jiných deskových her, např. dámy.
Typický algoritmus vychází z tzv. statického hodnocení pozice. Program nejdříve
sečte hodnotu kamenů na šachovnici možné hodnoty jsou např. 100 bodů za pěšce,
350 za jezdce a střelce, 550 za věž a 1 000 za dámu. Za bílé figury tyto
hodnoty k celkovému hodnocení přičítá a za černé odečítá. Dále přidává k
celkovému hodnocení různé hodnoty poziční. Může například hodnotit pohyblivost
figur, pěšcové slabi-ny, vazby figur, bezpečnost králů a mnoho dalších faktorů.
Právě v pozičním hodnocení mají autoři prostor k uplatnění vlastních šachových
znalostí. Pouze je musejí popsat tak přesně, aby výsledkem bylo číselné
hodnocení. A to vyžaduje o něco víc, než jen umět dobře hrát šachy.
Minimax
Statického hodnocení nyní můžeme využít k volbě vhodného tahu. Jednoduše
vygenerujeme všechny tahy a necháme počítač ohodnotit výslednou pozici po
každém z nich. Pak už jen vybereme ten, který vede do pozice s nejlepším
hodnocením. Nemusíme se ovšem omezit na hloubku jediného půltahu. Místo
okamžitého vrácení statické hodnoty můžeme opět generovat tahy, všechny je
zkusmo provést, vybrat z výsledných hodnot hodnotu nejvýhodnější pro stranu na
tahu a tu vrátit. Když algoritmus dosáhne předem dané hloubky propočtu, vrátí
statické hodnocení. Je-li na tahu bílý, vrací rekurzivní algoritmus hodnotu
maximální, je-li na tahu černý, vrací hodnotu minimální. Proto se tomuto
algoritmu říká minimax.
Pro zjednodušení zápisu můžeme použít malý trik: při rekurzivním volání prostě
překlopíme znaménko výsledku a vždy hledáme nejvyšší hodnotu.
Prohledávaná struktura připomíná strom, a také se jí tak říká. Úvodní pozici se
běžně říká ko-řen (root). Pozicím umístěným ve stromě se říká uzly (nodes).
Uzlům, ve kterých propočet končí a z nichž se vrací statické hodnocení, se říká
listy (leaves, tips), ostatním se říká vnitřní uzly (internal nodes). Uzlům, ve
kterých hra podle pravidel končí (mat, remíza), se říká uzly terminální.
Alphabeta
Časová náročnost algoritmu minimax roste exponenciálně vzhledem k hloubce
prohledávaného stromu. V 50. letech byla vynalezena jednoduchá techni-ka, která
snižuje počet navštívených větví v některých vnitřních uzlech, přičemž výsledná
hodnota a tah v kořenu zůstávají nezměněny. Tím se výrazně sníží počet uzlů,
které je nutné navštívit v propočtu s danou hloubkou.
Tento algoritmus jde jednoduše vysvětlit na příkladu přemýšlení lidského
šachisty: když se mu podaří vyvrátit postup soupeře nějakým tahem, už své další
tahy v této pozici prostě neuvažuje a využije svůj čas ke zkoumání jiných
pozic. K něčemu podobnému vede vylepšený minimax na uzlu N7 (viz náš obrázek).
Když uzel N7 dostane návratovou hodnotu -4 z uzlu N8, může prostě ukončit
prohledávání a vrátit do uzlu N1 hodnotu -4, která je dostatečně špatná na to,
aby bílý v uzlu N1 zvolil raději tah do uzlu N2 s hodnotou +2. Uzly N9 a N10
ani jejich podstromy tak nejsou vůbec uvažovány.
Když tedy algoritmus postupuje směrem k listům, předává navíc dvě hodnoty
určující zatím nejlepší nalezenou možnost pro bílého a černého. Tyto hodnoty se
většinou označují alpha a beta. Algoritmu minimax, vylepšenému o tuto techniku,
se říká alphabeta.
Iniciální hodnoty alpha a beta v kořenu (viz vložený text s kódem) stromu jsou
nastaveny na minimální a maximální hodnotu. Voláme tedy root_alphabeta( &tah,
0, -CHECKMATE, CHECKMATE )
Funkce root_alphabeta() je speciální případ alphabety pro prohledání kořene,
který vrací mimo hodnoty i nejlepší nalezený tah.
Tahu, který způsobí odřezání zbylých větví ("vyvrácení postupu soupeře"), se
říká killer. Je vidět, že čím dříve dospějeme k takovému tahu, tím méně variant
musíme počítat. Efektivita alphabety tedy výrazně závisí na pořadí, v jakém
jsou tahy probírány. Chceme co nejdříve najít tah, který způsobí odřezání
zbylých větví. Autoři většinou doporučují toto pořadí:
1 tah, který již v totožné pozici byl killerem.
2 proměny pěšců a braní v pořadí jejich výhodnosti.
3 ostatní techniky, např. tahy, které v některých jiných pozicích byly killery.
Metoda okénka
Alphabetu jde také zrychlit tzv. metodou okénka. Před zahájením prohledávání
odhadneme inter-val, ve kterém může ležet výsledná hodnota. Jeho nejnižší a
nejvyšší bod pak použijeme místo hodnot -CHECKMATE a CHECKMATE při volání
funkce root_alphabeta(). Pokud náhodou výsledek padne mimo tento interval,
musíme vše spustit znovu, tentokrát s větším oknem. I tak ale v průměru můžeme
dosáhnout výsledku rychleji.
Iterativní prohlubování
Vlastnosti alphabety vedou k tomu, že je výhodnější prohledávat iterativně, tj.
nejdříve se prohledává do hloubky 1, pak 2, 3, 4 a dále. Ve vyšších iteracích
pak máme k dispozici důležité informace o tom, jak třídit tahy, a to nám
přináší další výrazné časové úspory. Navíc můžeme podle výsledku předchozí
iterace vhodně zvolit interval v metodě okénka.
Další výhodou iterativního prohledávání je jednodušší kontrola času. Po
ukončení iterace se program koukne na hodiny a může se rozhodnout, zda bude v
iterování pokračovat nebo provede zatím nejlepší nalezený tah.
Hashovací tabulky
Další technikou, kterou používají všechny úspěšné programy, je tabulka killerů
a transpozic. Pozice, které již program prošel, jsou uloženy do paměti. Pokud
se ve stromu vyskytne pozice shodná s některou uloženou, máme většinou k
dispozici vhodný killer a za splnění jistých předpokladů můžeme použít
výslednou hodnotu předchozího výpočtu a rovnou ji vrátit bez dalšího
prohledávání.
Do políčka transpoziční tabulky se většinou ukládají tyto hodnoty:
Hashovací klíč pozice, jakýsi "podpis", podle kterého se určí shoda pozice v
tabulce s aktuální pozicí. Při použití vhodných technik tvorby klíče lze
vystačit se čtyřmi nebo osmi byty.
Nejlepší nalezený tah, což je pozdější vhodný kandidát na killera.
Výsledná hodnota.
Typ hodnoty: přesná, vysoká (fail-high, výsledek byl | alpha), nízká (fail-low,
výsledek byl ú beta). Chceme-li později zjistit, zda lze hodnotu z tabulky
vrátit bez dalšího prohledávání, musíme vzít v úvahu i to, že předchozí
výsledek vznikl s nějakými mezemi alpha a beta a po-kud byl mimo tyto meze,
nemusí to být výsledek přesný.
Hloubka propočtu. I hloubku propočtu budeme později potřebovat ke zjištění, zda
můžeme vrátit hodnotu z hash tabulky bez dalšího prohledávání.
Tiché dohledání
Dosud popsaný algoritmus má jeden vážný problém. Vždy ukončí propočet v pevné
hloubce a může tak učinit předčasně v pozici, kde má strana na tahu nějakou
jednoduchou a silnou hrozbu. Zatím nejúčinnější známou metodou k odhalení
takových hrozeb je tiché dohledání (quiescence search). Vypadá podobně jako
běžná alfabeta s upraveným generováním tahů. Generují se většinou pouze braní,
někdy i šachy a obrany před šachy. Strana na tahu vždy nejdříve nechá pozici
staticky ohodnotit a s výslednou hodnotou naloží, jako by byla návratovou
hodnotou rekurzivního volání alphabety, tj. může zvýšit mez alpha nebo přímo
hodnotu vrátit, pokud je | beta (podle hesla "když jsem na tahu, nic mi
nehrozí"). Následuje prohledání všech braní běžným algoritmem alphabeta.
Kvalita techniky tichého dohledání se výrazně projeví na herní síle programu.
Extenze a prořezávání
Podíváme-li se blíže na pozice ve stromu prohledávaném běžnou alphabetou,
zjistíme že většina pozic jsou pozice jednoznačně vyhrané pro jednu ze stran a
na výsledek prohledávání mají minimální vliv. Autoři programů tedy zkoumají,
jak ze stromu bezpečně odstranit nezajímavé větve a v těch zajímavých zase
prohloubit propočet. Odstraňování nezajímavých větví říkáme prořezávání
(pruning). Prohloubení propočtu říkáme extenze.
Často používanou metodou prořezávání je tzv. metoda nulového tahu. Strana na
tahu vždy před zahájením prohledávání vlastních tahů zkusí předat právo tahu
soupeři, při tomto pokusu výrazně sníží hloubku prohledávání. Jestliže je
výsledek nulového tahu větší nebo roven hodnotě beta, předpokládáme, že máme k
dispozici i jiný tah s hodnotou alespoň beta a běžné tahy vůbec nepočítáme.
Výhodou této metody je jednoduchá implementace a znatelné zvýšení hloubky
propočtu. Nevýhodou je možnost taktických přehmatů v pozicích, kterým šachisté
říkají "zugzwang", kde povinnost táhnout vede k prohře.
Knihovna zahájení
Na knihovně zahájení není nic moc složitého. Většinou je to databáze pozic, ke
každé pozici se váže jeden nebo více tahů a k tahu jeho hodnota, která určuje,
s jakou pravděpodobností má být zahrán.
Zajímavější to začne být až ve chvíli, kdy vymýšlíme, jak do knihovny dostat
dobré tahy. V dávných dobách počítačového šachu byla knihovna zahájení téměř
ruční prací autora programu. Ken Thompson prý vlastníma rukama několik měsíců
ťukal do stroje obsah encyklopedie zahájení. Zámožnější programátoři často
tvorbou knihovny pověřili silného šachistu, který je kromě předání svých
teoretických znalostí též schopen přizpůsobit knihovnu hernímu stylu programu.
Dnes jsou k dispozici obsáhlé elektronické databáze velmistrovských partií a
ruce Kena Thompsona si konečně mohou odpočinout. Práci s převáděním tahů do
knihovny zahájení za něj udělá počítač. Navíc může stroj o každém tahu
zpracovat statistiku jeho četnosti a úspěšnosti a na jejím základě pak spočte
vhodnou pravděpodobnost pro pozdější vybírání z knihovny. Chytřejší programy
pak umějí pravděpodobnostní hodnoty tahů v knihovně upravit podle výsledků
vlastních partií. Jde vlastně o jednoduchou formu učení se.
Databáze koncovek
Stále více programů dnes využívá dokonalé znalosti některých typů koncovek s
malým materiálem. Program má v databázi uloženy všechny možné pozice koncovky
spolu s jejich přesným hodnocením to znamená buď počet tahů do matu, nebo
teoretickou remízu. Dnes jsou zpracovány všechny tří, čtyř a pětikamenové
koncovky a některé koncovky šestikamenové. Na Internetu jsou volně dostupné
databáze od Eugene Nalimova spolu s programem v C++, kterým je možné je
vygenerovat.
Časová a paměťová náročnost generování výrazně roste s počtem kamenů. Všechny
tříkamenové koncovky zaberou 70 KB, čtyřkamenové 30 MB a pětikamenové 7 GB. Z
toho je vidět, že touto cestou nemáme šanci dospět k úplné analýze šachové hry
od základní pozice, což by vlastně odpovídalo analýze dvaatřicetikamenové
"koncovky".
Díky počítačovým databázím šachových koncovek byly odhaleny chyby ve výsledcích
práce nejlepších lidských teoretiků šachových koncovek. Počítač tak za několik
hodin až dnů práce s generováním databáze odhalí to, na co lidským mozkům
nestačila staletí. Známým příkladem je koncovka dvou střelců proti jezdci. V
roce 1851 byl vydán podrobný rozbor této koncovky zpracovaný teoretiky Klingem
a Horowitzem. Výsledkem tohoto rozboru je mimo jiné typ pozice, ve které se
slabší strana ubrání (například bílý Kd5, Sa4, Sf8, černý Kb6, Jb7). Tuto
pozici pak převzali do svých děl pozdější renomovaní autoři učebnic a příruček
šachových koncovek. Podle objevitelů se jí běžně říká Kling-Horovitzova pozice.
Až výsledky databázového zpracování této koncovky ukázaly, že obrana je mnohem
obtížnější, a dokonce že ukázková Kling-Horowitzova pozice je vyhraná pro
silnější stranu.
Další informace
Podrobnější informace o technikách šachového programování najdete na stránce
Jamese Longa http://home.fda.net/wzrdking/ chessprg.htm. V nakladatelství Unis
vyšel v roce 1997 překlad knihy Šachy na PC od Dietera Steinwendera a Frederica
Friedela. Tato knížka obsahuje mj. i podrobných popis datových struktur a metod
generování tahů.
Oddělení jádra programu a rozhraní
Existuje celá řada komerčních šachových programů. Zájemci je jistě znají (lze
je také odkázat na knihu Šachy na PC, kterou vydalo nakladatelství Unis),
nicméně začátečník by se s celou problematikou jistě rád seznámil bez zátěže
pro vlastní kapsu. Z tohoto důvodu se v tomto článku budeme věnovat především
volně šiřitelným programům. Pro programátory je zde navíc častou výhodou také
dostupnost zdrojového kódu programu. Recenzi řady komerčních šachových programů
najdeme např. na http://www.icd chess.com.
Šachový program byl od počátku 80. let až do nedávna jednoduchým softwarovým
výrobkem "z jednoho kusu". Jeho zlepšení se netýkala celkového návrhu, ale jen
zvyšování herní síly a přidávání funkcí a komfortu do uživatelského rozhraní.
Až dnes se tento tradiční návrh dočkal významnější změny. Ta spočívá v oddělení
šachového "motoru" (v angličtině se běžně používá výraz engine, např. Crafty
engine for Fritz) od uživatelského rozhraní. Zároveň je definován a zveřejněn
protokol pro komunikaci šachového stroje a příslušné GUI. Uživatel tak může
provozovat s jednotným ovládáním a vzhledem programy, které jsou z hlediska
síly i stylu značně rozdílné. Je také mnohem snažší organizovat zápasy a
turnaje různých programů na jednom počítači.
Přenos tahů, jejich zobrazování a nakonec i vyhodnocení výsledků, to vše může
zajistit sám počítač. Na uživatele pak už jen zbývá vše sledovat, vytvořit si
názor na herní styl a sílu programů a diskutovat o tom na Internetu. Představme
nyní program, který přišel jako první s myšlenkou oddělení šachového stroje od
uživatelského rozhraní a dodnes hraje v šachovém softwaru výjimečnou úlohu.
Dosud má náskok před konkurencí v kvalitě komunikace prostřednictvím Internetu.
Náskok před konkurencí má náš program i v ceně je totiž volně šiřitelný a
jmenuje se Xboard.
Xboard a WinBoard
Xboard lze použít jako grafický interface k mnoha šachovým programům,
internetovým šachovým serverům, nebo prostě jako prohlížečku partií ve formátu
PGN. Původně byl programován pro Unixy s X Window. Jeho první verze vznikly
počátkem 90. let. V roce 1991 se pak projektu ujal Tim Mann, který jej spravuje
dodnes. Později Tim Mann vyrobil i port pro Win32. Xboard pro Windows se
jmenuje WinBoard.
Všechno začalo vlastně jen díky tomu, že šachový program GNU Chess byl kvůli
přenositelnosti na různé operační systémy napsán pouze s textovým rozhraním.
Jako grafický interface šachového programu byl tedy Xboard původně ušit na míru
textovému programu GNU Chess a ten byl také dlouho jediným programem, který pod
Xboardem fungoval. Později několik amatérských šachových programátorů
pochopilo, že je mnohem jednodušší napodobit ve svém programu vstupy a výstupy
GNU Chess a použít Xboard, než programovat vlastní grafický interface.
Xboard dává programátorům navíc lepší možnosti testování. Je možné pod ním hrát
zápasy dvou různých programů nebo svůj program automaticky připojit na šachový
server a tak jej přímo testovat v partiích proti lidem.
Tim Mann nedávno sepsal a vydal formální specifikaci protoko-lu pro komunikaci
mezi šachovým programem a Xboardem. To opět zvýšilo počet programů
spustitelných pod Xboardem. Xboard začal být tak populární, až si ho všimla
německá firma ChessBase a udělala prozíravý tah na šachovnici komerčních
šachových produktů. Pro program ChessBase Fritz 5.32 dnes existuje modul, který
umožní provozovat většinu Winboard-kompatibilních programů se stejným grafickým
rozhraním, jako má Fritz. Majitelé Fritze 5.32 si mohou tento modul stáhnout z
http://www.chess base.com.
Ani konkurence nespí. Ed SchrÖder v únoru oznámil, že obdobný modul připravuje
pro svůj program Rebel. Nizozemská firma MicroVision uvolňuje první betaverze
univerzálního šachového interface ChessVision pro Windows, taktéž schopného
spolupracovat s Winboard-kompatibilními programy (http://www. microvision.nl).
Xboard a WinBoard jsou volně šiřitelné a jsou k dispozici i ve zdrojových
textech. Instalační balíčky, dokumentaci a bližší informace najdete na
http://www.rese arch.digital.com/SRC/personal/
Tim_Mann/chess.html.
Seznam některých šachových programů, pracujících pod WinBoardem či Xboardem,
najdete také v rubrice Internet na straně 6.
Člověk proti stroji
O reálné herní síle šachových počítačů toho bylo napsáno opravdu hodně. Přitom
o ní víme až překvapivě málo. Počítače se totiž prakticky nezúčastňují turnajů,
ve kterých by se mohly utkat s lidmi. Máme tak k dispozici pouze výsledky
několika specializovaných turnajů a zápasů. Z řady důvodů nejsou výsledky navíc
příliš reprezentativní.
Použít můžeme partie ze zápasu mezinárodního mistra Deena Hergotta proti
programu Hiarcs 6 na Pentiu MMX/200 (z roku 1997) a 4 partie programu Rebel 2
proti velmistru Jusupovovi (1997) a 2 proti velmistru Anandovi (1998).
Mnoho se spekulovalo o síle počítače po zápase Kasparov Deep Blue v roce 1997,
který vyhrál počítač v poměru 3,5:2,5. Nic víc než spekulovat se z výsledku
pouhých šesti partií proti jedinému protivníkovi stejně nedá. Zápas tak splnil
svůj, podle mého názoru, hlavní účel, to jest reklamní. V laické veřejnosti se
vytvořil dojem, že počítač Deep Blue je dnes silnější než lidský mistr světa.
Deep Blue si zřejmě už nikdy nezahraje podezření, že by se dojem síly počítače
mohl vytratit stejně snadno jako se vytvořil, se samozřejmě objevilo krátce po
zápase.
9 0934 / pahn
Metoda minimax
Takto vypadá algoritmus/zdrojový kód programu pro vymyšlení toho nejlepšího
tahu, který vychází z posouzení pozic vzniklých jako následek všech možných
tahů a jejich hodnocení. Pro prohledání pozice v kořeni stromu je algoritmus
upraven tak, aby kromě hodnoty vrátil i tah.
int minimax(int ply)
{ int bestvalue = -CHECKMATE; int number_of_moves, i, value; tmove
m[MAX_NUMBER_OF_MOVES]; if( terminal_node() ) return game_result(); if( ply >
maxply) return static_evaluation(); generate_moves( moves,&number_of_moves );
for( i=0; i!=number_of_moves; i++ ) { makemove( m[i] ); value = -minimax( ply+1
); unmakemove(m[i] ); if( value > bestvalue ) bestvalue=value; } return
bestvalue;
}
Alphabeta je rozšířením algoritmu minimax. Její hlavní vylepšení zpočívá
zjednodušeně řečeno v tom, že některé pozice jsou analyzované do menší šířky a
ušetřený čas se pak využije v "rozhodujících" variantách. int alphabeta(int
ply, int alpha, int beta)
{ int number_of_moves, i, value; tmove m[MAX_NUMBER_OF_MOVES]; if(
terminal_node() ) return game_result(); if( ply > maxply ) return
static_evaluation(); generate_moves( moves, &number_of_moves ); for( i=0;
i!=number_of_moves; i++ ) { makemove( m[i] ); value = -alphabeta( ply+1, -beta,
-alpha); unmakemove( m[i] ); if( value > alpha ) { alpha = value; if( alpha >=
beta ) return alpha; } } return alpha;
}









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.