Student World

Š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é slabiny, 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á technika, 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 pokud 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
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.icdchess.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.chessbase.com.
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.research.digital.com/SRC/personal/Tim_Mann/chess.html.
Nová adresa je http://www.tim-mann.org/chess.html.

Č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.

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.

—omluváme se za formátování programu
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.

—omluváme se za formátování programu
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;
}

Poznámka: tento tex vyšel v technologické části Computerworldu. Nyní bylo provedena pouze kontrola funkčnosti odkazů.

autor Dušan Dobeš