Tomas Oberhuber's Homepage

Základem minimaxu je procházení stavového stromu do hloubky (s pevnou nebo podle okolností variabilní, každopádně však ohraničenou hloubkou hledání). Dostanu-li se k listu stromu, tj. k nějaké „koncové“ pozici, ohodnotím tuto pozici hodnotící funkcí. Ta je prubířským kamenem šachových programů. Větší detaily o hodnotící funkci diskutuji v následujícím odstavci, pro jednoduchost nyní předpokládejme, že pozice se ohodnotí podle materiálu, tj. matematicky řečeno váženého součtu figur bílého a černého (figury černého resp. figury protivníka jsou vzaty záporně). Mám-li tuto hodnotící funkci, jak najdu nejlepší tah?

Myšlenka minimaxu je velmi blízká základní zásadě při hledání nejlepšího tahu u šachistů – najdu takový tah, abych i při sebelepší odpovědi soupeře měl možnost táhnout tak, abych i při sebelepší další odpovědi soupeře měl možnost táhnout tak, abych.....atd. (až do určité hloubky propočtu, kterou zvládne šachový mistr resp. program)...měl možnost táhnout tak, aby pozice po dané posloupnosti tahů byla pro mě co nejvýhodnější.

Jinými slovy – nejde o to najít ve stavovém stromu cestu k uzlu/pozici s nejlepším ohodnocením pro stranu, která je na tahu ve výchozí pozici. To bych totiž hledal nejlepší tah za předpokladu, že soupeř bude ,,spolupracovat“ a ze svého pohledu bude dělat nejhorší tahy.
Minimax počítá naopak s nejlepšími odpovědmi soupeře. Když má ohodnocení všech listů resp. uzlů, které mají společného předka, nastaví ohodnocení předka jako maximum ohodnocení přímých potomků (pokud v pozici příslušné k předkovi hraje strana, která je na tahu ve výchozí pozici), resp. jako minimum těchto ohodnocení (pokud je na tahu druhá strana). Vybírání minima v případech, kdy je na tahu soupeř, právě odpovídá počítání s jeho nejlepším tahem, nejméně výhodným pro mě resp. program jakožto hráče, který je na tahu ve výchozí pozici. Tento popis minimaxu je zřejmě nedostatečný, proto odkazuji na článek o něm:

Hodnotící funkce

Algoritmus minimax v určitých částech stavového stromu minimalizuje, v určitých částech maximalizuje hodnotící kritérium poduzlů. U listů stromu se pak hodnotící kritérium vypočte pomocí takzvané hodnotící funkce. Hodnotící funkce ohodnotí pozici, která přísluší listu, z pohledu
hráče, který je na tahu. Při prvním přiblížení můžeme za výsledek hodnotící funkce považovat takzvaný materiál, neboli vážený součet kamenů, jež zbyly na šachovnici. Obvykle se používá následující ohodnocení:

Figury protivníka pak vezmu záporně. Základem je ohodnocení pěšce, které však záměrně není 1, protože existují ještě jiná (viz dále), jemnější kritéria (a kvůli rychlosti je vhodné pracovat v celočíselné aritmetice). Toto hodnocení odpovídá hodnocení figur lidskými hráči.
Šachisté, pokud přijde řeč na ohodnocení figur, by výše uvedené ohodnocení sice zřejmě zprvu přijali, jistě by ale ihned dodali, že takovéto ohodnocení figur (říkají mu “absolutní hodnota figur”) sice v průměru zhruba platí, ale hodnota figur se vlastně může pozici od pozice velmi lišit vzhledem k tomu, jaký smysl má postavení figur v dané pozici. Takovému ohodnocení říkají “relativní hodnota figur” a tuto relativní hodnotu figur určují šachisté vlastně nejen na základě pozice, ale také, a to je z hlediska programátora největší problém, na základě své intuice.

Pouček o relativní hodnotě figur v dané pozici je nepřeberné množství. Některé lze velmi snadno algoritmizovat (dva střelci jsou lepší než jezdec a střelec, králem je třeba rošovat a měl by před sebou mít dostatečnou pěšcovou ochranu, dvojpěšec není výhodný (dva pěšci stejné
barvy jsou na stejném sloupci), figury je dobře mít pohyblivé, pěšce je dobré mít v centru šachovnice, atd....). U jiných to jde hůř (pozor na chycené střelce v rozích šachovnice (kdy jsou chycení?), útočné postavení figur vůči nepřatelskému králi, rozestavení pěšců vůči nepřátelským střelcům), a u zbylých to téměř nelze (skutečná hodnota pěšce uprostřed matového útoku, proměnlivá hodnota pěsce v koncovkách, zablokování pozice (u zablokovaných pozic mají naopak převahu jezdci nad střelci), oběť (například za aktivitu)).

Pro zachycení těchto pouček se používá taktéž nepřeberné množství heuristik. Kromě toho, zda daná heuristika skutečně zachycuje ten aspekt pozice, který má, je nutné mít na zřeteli dvě věci:

1. hodnotící funkce je co do rychlosti kritická část programu. Složité heuristiky náročné na čas v ní nemají místo
2. poučky a stejně tak i použité heuristiky nejsou “nezávislé”. Pro heuristiky to znamená, že dvě heuristiky můžou izolovaně fungovat dobře, v kombinaci spolu pak hůře.

Z uvedených důvodů je hodnotící funkce největší alchymistickou laboratoří v šachovém programu, nad kterou každý programátor šachů stráví značnou část svého pracovního úsilí. Následuje přehled heuristik, ne nutně používaných jen v hodnotící funkci, které by měly relativní
hodnotu figur zachytit:

Obsazená pole

Většinu figur resp. kamenů (kameny jsou fugury a pěšci) je výhodné mít ve středu šachovnice. Pro lehké figury (střelci, jezdci) je to výhodné, protože ze středu šachovnice kontrolují nejvíce polí, u pěšců kvůli výhodné celkové pěšcové struktuře. Zavádějí se proto pole hodnot – bonusů, odpovídajících výhodnosti postavení na šachovnici pro daný druh kamene. Pro (bílého) jezdce může takovéto pole vypadat následovně:

Indexy tohoto pole odpovídají políčkům na šachovnici, kde daný jezdec stojí. Stojí-li například na poli e4, má podle této tabulky bonus 10. Bonusy všech figur se přičtou (bonusy soupeřových figur jsou vzaty záporně) k absolutní hodnotě figur na šachovnici (tj. k materiální hodnotící funkci).

Kontrolovaná pole, pohyblivost figur

Zde se bere v úvahu počet kontrolovaných polí všech figur určité barvy. Kontrolovat více polí je samozřejmě výhodné kvůli tomu, že kontrolovaná pole jsou pro soupeřovy kameny hůře přístupná, ale i kvůli pohyblivosti vlastnícj figur. Zde je nutné si uvědomit, že počet kontrolovaných polí a počet možných tahů se u pěšců a krále rozcházejí (král se nemůže vystavit do šachu a pěšci berou jinak než když táhnou na volná pole). Sluší se poznamenat, že právě dvě výše uvedené techniky nejsou zdaleka v uvedeném smyslu nezávislé. Pokud například jezdcem obsadím centrální pole, dostanu bonus za jeho obsazení. Pohyblivost tohoto jezdce je však pravděpodobně také lepší
než na okraji šachovnice.

Volné sloupce a diagonály

Je výhodné obsadit tzv.volné sloupce, což jsou zjednodušeně řečeno sloupce, na kterých není pěšec stejné barvy. Totéž platí o volných diagonálách, které ovšem na rozdíl od sloupců nejsou všechny stejně dlouhé a je samozřejmě výhodnější obsadit co nejdelší volnou diagonálu.

Koncovky
Koncovky patří k nejnáročnějším aspektům hry co se týká hodnotící funkce i způsobu propočtu variant. Slabosti v obou těchto stránkách se při hře proti lidskému soupeři projeví “v plné kráse”. Stručně uvedu dvě techniky, pomocí kterých se hra programu v koncovkách může zlepšit

• hašování pozic

zde jde o techniku pomáhající při propočtu variant. Pozice se hašují a do hašovací tabulky se ukládá ohodnocení pozic. V koncovce je totiž velmi pravděpodobné, že ke stejné pozici dospěji různou posloupností tahů. Když při propočtu na pozici narazím poprvé, uložím její hodnocení do tabulky. Pokud na ní narazím po druhé, už ji nemusím propočítávat dál, jen si odečtu její hodnocení z hašovací tabulky

• pravidla pro koncovky

zde jde o implementaci (jednoduchých) taktických pravidel pro koncovky. Většinou se implementují v hodnotící funkci. Problém je v tom, že souvisí nejen s vlastní statickou pozicí, ale i s jejím propočtem. Navíc je takových pravidel nespočet. Jednoduchým příkladem může být “pravidlo čtverce”, které určuje, jestli pěšec může králi “utéct do dámy”.

“Visící” kameny

Je důležité, a lidští hráči to podvědomě dělají, aby se ohodnocovaly pouze tzv. klidné pozice, tj. pozice, v nichž nehrozí jedné straně bezprostřední nebezpečí. Kdybych například na konci propočtu vzal svojí dámou krytého protivníkova pěšce, nemůžu si dovolit ohodnotit pozici tak, že mám jednoho pěšce navíc a pozice je pro mě tedy výhodná, protože “je jasně vidět”, že soupeř mi příštím tahem vezme drahocennou dámu. Programy schopnost “vidět” samy od sebe samozřejmě nemají, proto jim “musíme pomoci”.

Toto je oblast, kdy selhávají vlastně všechny hodnotící funkce, protože jenom podle rozestavění kamenů nelze dobře algoritmicky rozhodout, zda hráči “něco visí”. Pokud ovšem neprovedeme další propočet variant a ve stavovém stromu neklesneme o několik pater hlouběji.
Problém se řeší pomocí tzv. hledání klidu (quiescence search), kdy z uzlů, které by pro normální propočet (všech variant) byly listy, prohloubím propočet, ale jen podstromem obsahujícím tzv. úderné tahy (tahy, kdy beru protivníkovu figuru, dávám šach nebo mat, popřípadě dojdu pěšcem na 8. resp. 1 řadu – tj. na pole přeměny). Vzniklý podstrom má omezenou hloubku a malý faktor rozvětvení (v úvahu se berou jen úderné tahy), takže výpočetní složitost nenaroste o moc.

Samozřejmě je žádoucí, aby před dosažením maximální hloubky tohoto podstromu se pozice “sama uklidnila”, tj. aby před dosažením maximální hloubky podstromu u ní nebyly k dispozici již žádné úderné tahy. Toho se ve většině případů také dosáhne. Hodnotící funkci pak
použijeme na nově vzniklé, hlubší listy, u nichž předpokládáme, že odpovídají klidným pozicím.

Poznámka: I v programu, ve kterém se počítá jen s absolutní hodnotou figur (= s “materiálem”), se kromě vlastního materiálu musí vzít v úvahu minimálně ještě to nejdůležitější, o co v šachu jde, a to je mat. Pokud je v pozici mat, pozice se hodnotí jako +∞ (v praxi maximální přípustná hodnota datového typu) pro toho, kdo mat dal, jako -∞ pro toho, kdo mat dostal. Užitečné je samozřejmě registrovat alespoň nejjednodušší variantu remízy, kterou je pat, který se hodnotí neutrálně jako 0. Mat i pat se hodnotí těmito konstantami samozřejmě nezávisle na tom, jaké kameny a v jaké pozici na šachovnici ještě zbyly!!