ARCHIV

Šachové myšlení (6) - Prořezávání

Šachista - člověk propočítává vždy jen jeden nebo několik málo nejnadějnějších tahů, alfabeta metoda všechny, které mohou ovlivnit výsledek. Kvalitní programy se snaží lidskému myšlení aspoň trochu přiblížit a ty nejhorší tahy vyřadit bez propočtu.

31.10.2006 06:00 | Jan Němec | Články autora | přečteno 12402×

Základní myšlenka

Hodnotu minimaxového stromu hry (a tím i výběr tahu z úvodní pozice propočtu) ovlivňují vždy pouze nejlepší tahy z jednotlivých navštívených pozic. Pokud chceme, aby program hrál dobře, musíme se snažit dopočítat nejlepší varianty co možná nejhlouběji. K tomu ovšem potřebujeme mít dost času a ten je třeba někde ušetřit. Naštěstí nejlepší varianta bývá obvykle pouze jedna a pokud existuje v pozici hned několik přesně stejně dobrých nejlepších variant, pro výpočet hodnoty stromu hry nám stačí ohodnotit jedinou takovou variantu. Všimněte si, že je jedno, zda nějaká varianta vyjde druhá nejlepší, docela dobrá, spíše špatná, úplně špatná a nebo zda ji vůbec nepočítáme. Ta poslední možnost je pro nás z časových důvodů nejvýhodnější. V terminologii alfabeta metody můžeme prohlásit, že je-li nějaký tah zcela jistě stejný nebo horší než alfa, nemá cenu jej počítat. Tato úvaha nás vedla k navržení alfabeta metody. Můžeme zajít o něco dál a prohlásit, že pokud je nějaký tah s velkou pravděpodobností stejný nebo horší než alfa, rovněž jej nebudeme počítat. Z této myšlenky vychází celá řada heuristik. Obvykle nejprve nějakým povrchním způsobem (který je řádově rychlejší než propočet do předepsané hloubky) odhadneme cenu tahu. Při povrchním odhadu obvykle tahu poněkud nadržujeme, v tom případě prostě porovnáme výsledek s alfou a výsledek menší nebo rovno znamená, že tah zahodíme a nebudeme provádět propočet do úplné hloubky. Druhou možností je, že odhad provedeme nestranný, potom musíme být opatrnější, tah smíme zahodit, pouze je-li jeho cena výrazně menší než alfa.

První pokusy

Ve zdrojovém kódu jednoho programu jsem našel velmi rychlou a jednoduchou heuristiku: pokud v úvodní pozici k propočtu do hloubky 3 mám o dámu méně než alfa, propočet provedu pouze do hloubky 2. Nenáročnost a časová úspora je zřejmá, před přehmaty typu přehlédnutí chycené figury nás brání dostatečná rezerva (celá dáma), před jinými materiálními přehmaty pak navíc ještě dopočet taktických variant. Na většinu případů, kdy jedna strana obětuje celou dámu za rychlý mat by měl stačit propočet do hloubky 2 s různými prohlubováními. Podobných heuristik můžeme vymyslet celou řadu, lze je různě dolaďovat a kombinovat, výkonu algoritmu jistě prospějí, na druhou stranu zázraky zde čekat nemůžeme, neboť k ořezání dojde jen málokdy.

Některé programy, například Crafty, se snaží v pozicích blízko listu ořezávat mnohem víc. Jsou-li v propočtu 3 nebo méně půltahů od listu, zmenšují o jedna hloubku každého tahu, který není nějakým způsobem zajímavý. Především by to neměl být kandidát na prohloubení, nesmí jít o šach, braní, tah postouplým pěšcem, tah s dobrou hodnotou historické heuristiky a podobně.

Právo a povinnost táhnout znamenají téměř vždy výhodu. K velké většině případů, kdy tomu tak není pak dochází v koncovkách. Jsou-li na šachovnici jen králové a pěšci, nastává nevýhoda tahu (tzv. zugzwang) zcela běžně. Známá je hlavně situace, kdy se král silnější strany snaží protlačit svého jediného pěšce do dámy, zatímco soupeřův král čeká někde na cestě k políčku proměny. K remíze by mu stačilo prostě nehrát, ale to pravidla neumožňují. Výsledek partie rozhodne ovládnutí tzv. kritických polí před pěšcem. Méně častá je nevýhoda tahu v koncovkách pěšců a jedné lehké figury na obou stranách, ale i zde se občas vyskytne. Je-li figur na šachovnici více, stávají se pozice s nevýhodou tahu raritou a zcela výjimečné případy ze střední hry pak otiskují šachové učebnice jako opravdové kuriozity.

Obecné vlastnosti výhody tahu můžeme snadno využít k navržení další heuristiky prořezávání. Máme-li provést propočet do hloubky 1, nejsme-li v šachu a pozice nemá charakter koncovky, zkusíme provést jen rychlejší propočet taktických variant. Je-li výsledek alespoň beta vrátíme betu rovnou i bez propočtu. Jinými slovy, pokud nehrozí soupeřův útok nebo vynucený tah (šach, koncovka) a stojíme dobře i pokud se zřekneme práva tahu, nejspíš stojíme dobře i ve skutečnosti. Pokud výsledek zkráceného propočtu nedosáhne hodnoty beta, musíme provést úplný propočet do hloubky 1.

Metoda nulového tahu

Předchozí heuristika je docela účinná, ale je možné použít pouze při propočtu do hloubky 1, tedy těsně před listem. Pochopitelně by se nám hodilo podobným způsobem prořezávat strom hry na všech úrovních. Zdánlivě přirozené jednoduché zobecnění pro všechny liché hloubky, tj. zkusit překročit betu propočtem do hloubky 2n místo 2n + 1 by nebylo úplně nejšťastnější. Je pravda, že v základním propočtu do pevné hloubky se tím zříkáme posledního tahu, tedy zvýhodňujeme soupeře, tedy pokud dojde k překročení bety v heuristice, mělo by k němu dojít i v propočtu do původní hloubky. Bohužel situaci nám komplikují ostatní ořezávací a prohlubovací heuristiky, s nimiž jsme při propočtu do hloubky 1 počítat nemuseli. Pokud dojde na cestě k listu k lichému počtu prohloubení a ořezání, situace se rázem otočí a propočet do hloubky 2n bude oproti 2n + 1 výhodnější pro nás a ne pro soupeře. Heuristika pak může snadno naznačit, že tah překročí betu, i když tomu tak ve skutečnosti nebude. Je třeba vymyslet něco jiné.

Řešením pro vyšší hloubky je nedávat soupeři výhodu tahu až uštípnutím listu, ale věnovat mu ji rovnou. Prostě ignorovat pravidla šachu a nechat soupeře hrát dvakrát za sebou. Přesněji řečeno změnit ve výchozí pozici právo tahu, a zmenšit hloubku propočtu o 1. Pokud takto modifikovaný propočet přesáhne betu, zřejmě by ji přesáhl i původní propočet do plné hloubky, neboť jsme právem táhnou dvakrát za sebou soupeře zvýhodnili. Můžeme tedy opustit funkci s hodnotou beta. Tato metoda se nazývá metodou nulového tahu a do určité míry se podobá lidskému myšlení. Šachista obvykle před zahájením detailního propočtu nějakého aktivního plánu v povrchním propočtu vynechává soupeřovy tahy a teprve pokud plán vypadá slibně, začne více uvažovat i soupeřovy odpovědi. Většinu hloupých variant tak odhalí hned na první pohled.

Metoda nulového tahu je poměrně účinná, nicméně i ona má svá omezení. Nemůžu ji použít rekurzivně, tedy pokud již jsem v propočtu, kde k nulovému tahu došlo. V krajním případě při nulových tazích za obě strany by totiž propočet zdegeneroval na nicnedělání. Nejde ji použít v pozicích s rizikem vynuceného tahu, tedy při omezeném materiálu. Rovněž nelze vynechat vlastní tah, pokud nás soupeř šachuje, dostali bychom se tím do nepřípustné pozice. Metoda nedává dobrá výsledky ani pokud je na dohled mat soupeřovu králi (beta je velmi velká). Macení je aktivní operace a vynechání tahu je příliš velkou nevýhodou.

Vztah prohlubování a prořezávání

Pokud se zamyslíme nad vztahem mezi prohlubováním a zmenšováním hloubky propočtu vybraných variant, zjistíme, že jde jen o jiný název pro stejnou věc. Cílem šachového programu nebývá propočet do nějaké předem stanovené hloubky, ale propočet do maximální možné hloubky v zadaném čase. Pokud program některé varianty preferuje a prohlubuje, logicky tím zpomaluje propočet a v zadaném čase se dopočítá do menší základní hloubky. Všechny ostatní nepreferované varianty tedy zkrátil. Platí to i naopak. Pokud program provádí u některých variant pouze jednodušší odhad a tím je zkracuje, ušetří čas a dopočítá se do větší hloubky. Všechny ostatní varianty tedy prohloubil.

Zatím jsem se v popise algoritmů držel hodně při zemi. Se všemi popsanými metodami jsem se setkal ve zdrojových kódech skutečných silných programů. V následujících dvou odstavcích se však trochu odvážu. Popíšu návrh na změnu přístupu k prořezávání a prohlubování a na prohlubování nejlepších variant. Silné programy nějakým způsobem obsahují obě metody, ale nikde jsem je neviděl implementovány v plné obecnosti. Jestliže seriál byl dosud praktickým návodem, jak napsat průměrný šachový program snadno a rychle a získat tak třeba zápočet za ročníkový projekt na matfyzu, nyní půjde spíše o pobídku k samostatnému výzkumu, který občas končí úspěšnou diplomkou, velmi často objevením další slepé uličky a jen tu a tam zlepšením šachového programu o pár dalších elo bodů.

Prohlubování a prořezávání má zásadní vliv na kvalitu hry, přesto ve zdrojových kódech silných programů jsem nalezl příslušné heuristiky implementované zhruba tak, jak jsem je popsal v tomto seriálu. Nikde jsem se nesetkal s pokusem sjednotit v kódu programu pohled na prohlubování a ořezávání. Řešení by přitom mohlo být poměrně jednoduché. Při vyhodnocování ceny pozice nás zajímá pouze varianta, které se nakonec ukáže jako nejlepší. Každému tahu bychom mohli nějakým předběžným odhadem přiřadit pravděpodobnost, číslo mezi 0 a 1, které by vyjadřovalo šanci, že tah je nejlepším tahem z pozice. Větší číslo by měly třeba proměny pěšců, braní, vynucené tahy, tahy s dobrou historií a podobně, naopak k nule by se blížila pravděpodobnost tahů u nichž při klasickém přístupu propočet zkracujeme. Součet pravděpodobností všech tahů z pozice by byl 1. Pravděpodobnost varianty by pak byl součin pravděpodobností jejích tahů. Kaskádová metoda by místo iterace po celočíselných hloubkách iterovala po nějaké stupnici (třeba 1/38ⁿ) od jedničky k nule, pravděpodobné varianty by tedy byly propočítány hlouběji. Tento přístup k prohlubování a ořezávání umožňuje oproti přístupu klasickému přesněji stanovit hloubku propočtu a lépe sladit jednotlivé heuristiky.

Hodnotou minimaxového stromu je odhad ceny listu nejlepší varianty. Je zřejmé, že prohloubení tohoto listu by mělo zásadní vliv na výsledek celého propočtu. Naopak varianty, kde ani jeden tah není ve své pozici nejlepší jsou zřejmě kandidátkami na zkrácení. I zde se na problém můžeme dívat více z hlediska pravděpodobnosti. Nejlepším tahům z jednotlivých navštívených pozic předchozího propočtu kaskádové metody bychom přidělili větší čísla. Například pokud bychom statistickými metodami zjistili, že nejlepší tah v kořeni propočtu do hloubky 5 se při propočtu do hloubky 6 s pravděpodobností 70% nemění, mohli bychom mu přiřadit pravděpodobnost 0,7 a všem ostatním rozdělit zbylých 0,3. Problém však rozhodně není jednoduchý, bylo by zapotřebí si nějakým způsobem pamatovat mezivýsledky z předchozího propočtu, neboť prostá alfabeta metoda má tendenci "zbytečné" údaje zapomínat, ostatně proto je také tak paměťově efektivní. Pamatovat si tedy celý strom propočtu? To by zřejmě bylo příliš náročné a pomalé. Nebo si do nějakých hash tabulek zapisovat nejlepší tahy variant? Snad ano, těžko říci. Každopádně zajímavý námět na samostatnou výzkumnou práci.

Pokračování příště

V příštím dílu si řekneme, jak zabránit opakovanému propočtu stejné pozice, ke které jsme došli vícekrát různým pořadím tahů. Řeč bude o hašování.

Verze pro tisk