ARCHIV

Šachové myšlení (5) - kaskádová metoda, prohlubování

Dnes si ukážeme, že rychlejší než propočet do hloubky n může být celá sada propočtů do hloubek 1, 2, 3 až n. Podíváme se také na některé metody prohlubování propočtu.

9.8.2006 10:00 | Jan Němec | Články autora | přečteno 14266×

Kaskádová metoda

Již víme, že herní síla programu úzce souvisí s hloubkou propočtu a ta je zase dána časem, který má program k dispozici na propočítávaný tah. Proto se může zdát nápad místo propočtu do hloubky n provést postupně propočet do hloubek 1, 2, 3, ..., n-1 a n na první pohled dost podivný. Přesto tímto způsobem velká většina kvalitních programů počítá a to především při výpočtu z kořene, v rekurzivním propočtu již situace není tak jednoznačná. Algoritmu se říká kaskádová metoda a váže se na něj celá řada dalších heuristik. Kaskádová metoda sama o sobě znamená pochopitelně zpomalení, ale ve spojení s navazujícími heuristikami je naopak obvykle znatelně rychlejší než prostý propočet do pevné hloubky n. Poskytuje rovněž lepší kontrolu propočtu než jednoduchá alfabeta metoda. Uvedeme si teď celou řadu důvodů, proč se kaskáda používá.

Zpomalení je malé

Pokud žádnou z možností kaskádové metody nevyužijeme, uškodí nám jen málo. Je-li průměrný větvící faktor šachů 38, dojde díky alfabeta prořezání k redukci na něco přes odmocninu z 38, dejme tomu 7. Režie navíc, tedy 7 + 7² + 7³ + ... 7^n-1 je v poměru s časem propočtu do největší hloubky (který musíme tak jako tak vykonat) tj. 7ⁿ malá. To ukazuje i praxe s jakýmkoli běžným silným šachovým programem. Pokud průběžně sledujeme výstupy z propočtu, obvykle zjistíme, že závěrečný propočet trvá podstatně déle než propočet do všech předchozích hloubek dohromady, i když rozdíl zřejmě nebude tak velký, jako v ideálním případě s částečnými součty posloupnosti mocnin sedmičky. Kaskádová metoda sama o sobě určitě nezpomalí program více než jeden a půl krát, což po přepočtení na hloubku stromu propočtu neodpovídá ani čtvrtině jediného půltahu.

Lepší časová kontrola

V praxi obvykle nezní zadání: "Dej mi nejlepší tah při propočtu do hloubky 8.", ale spíš: "Dej mi nejlepší tah, máš na to 20 vteřin." Je velmi obtížné předem stanovit hloubku propočtu, které dosáhneme v daném čase. Závisí to na větvícím faktoru v dané pozici i na efektivitě jednotlivých algoritmů a heuristik v procházených pozicích. V interaktivních programech bývá zadání pro jednoduchou alfabeta metodu ještě nepříjemnější: "Dej mi nejlepší tah, máš na to 20 vteřin, průběžně mě informuj o nejlepším nalezeném tahu a pokud zmáčknu mezeru, okamžitě mi dej řešení, které kvalitou odpovídá času výpočtu." To už se jednoduchou alfabeta metodou nedá splnit, neboť v případě přerušeného a nedokončeného výpočtu znám pouze nejlepší z několika propočítaných tahů a o zbývajících netuším nic. U kaskádové metody jsem na tom lépe. Provádím iterace tak dlouho, dokud mi zbývá čas nebo dokud mě uživatel propočet nepřeruší. Mohu průběžně vypisovat výsledky a za nejlepší tah prohlásit vítěze poslední dokončené iterace. Pouze pokud v nedokončené iteraci došlo ke změně nejlepšího tahu, bude zřejmě lepší nový vítěz.

Třídění tahů

V minulém dílu jsme se věnovali třídění tahu přímo v generátoru. Je zřejmé, že kaskádová metoda poskytuje mnohem lepší možnosti. Výpočet do hloubky jedna začneme s tahy setříděnými podle jednoduchých heuristik generátoru. Pokud v průběhu propočtu je nějaký tah lepší než dosavadní maximum, prostě jej přemístíme na začátek pole tahů. Tahy které předběhl přitom posuneme o jedno místo dozadu. Propočet do hloubky n+1 pak zahájíme vždy s polem tahů, tak jak zůstalo po propočtu do hloubky n. Při propočtu do vyšších hloubek tak budeme mít tahy setříděné podle toho, kdy naposled byly zlepšující a teprve zbytek pole pouze podle jednoduchých nekvalitních heuristik z minulého dílu. Díky tomu ve většině případů zahajujeme propočty tahem, který nakonec opravdu vyjde jako nejlepší. Velkou část těch zbývajících případů vyhraje tah, který byl někdy zlepšující (i když ne naposledy), bude tedy na jednom z předních míst pole. Navíc i zde bude zřejmě mít první propočítávaný tah určitou úroveň a pravděpodobně zvedne práh alfa podstatným způsobem. Případů, kdy zahájíme propočet několika špatnými tahy a vítěz bude až na chvostu, bude opravdu velmi málo. Může se jednat například o pozici s možností složité oběti nebo komplikovaného manévru, které předchozí iterace nedokáže dopočítat a kde změna hloubky propočtu o 1 zcela změní ocenění jednotlivých tahů.

Metoda okénka

Čistou alfabeta metodu voláme v kořeni s intervalem (alfa, beta) roztaženým od mínus do plus nekonečna. Když sestupujeme od kořene propočtu k listům (je to možná trochu zvláštní, ale v teoretické informatice se většina stromů kreslí kořenem nahoru :-)), interval se z obou stran svírá. Větší sevření znamená více přetečení bety v propočtu, více ořezání a tím i větší efektivitu. Snadno nahlédneme, že alfabeta metoda bez svírání intervalu je jen jiný název pro algoritmus minimax, zároveň víme, že výsledek alfabeta metody a minimaxu je stejný. Lze tedy říci, že alfabeta metoda svírá interval (alfa, beta) velmi defenzivně, tak aby při jakémkoli ohodnocení listů dala správný výsledek. Je celkem přirozená otázka, co by se stalo, kdybychom interval sevřeli více než předepisuje algoritmus alfabeta metody. Zjevně bude propočet rychlejší. Rozmyslet si musíme především to, zda bude také správný.

Vejde-li se cena nejlepšího tahu do sevřeného intervalu (alfa, beta), je vše v pořádku, dojde pouze k většímu ořezání špatných variant, toho jsme přesně chtěli dosáhnout. Výsledek bude někde mezi alfa a beta. Je-li cena nejlepšího tahu menší nebo rovná alfě, dojde při propočtu nějaké z odpovědí na každý tah (včetně nejlepšího) k přetečení bety, tedy žádný tah z naší pozice nepřekročí alfa, výsledkem propočtu bude alfa. V opačném případě, kdy je nejlepší tah lepší než beta, způsobí tento tah přetečení bety již na první úrovni zanoření a výsledkem je beta.

V minulém odstavci jsem už vlastně naznačil jádro všech heuristik metody okénka. Pokud mám rozumný důvod předpokládat, že výsledek propočtu s parametry (alfa, beta) bude s velkou pravděpodobností v intervalu (alfa2, beta2), který je podmnožinou původního intervalu, interval opravdu zmenším a provedu propočet. Pokud jsem se nemýlil, tj. výsledek je opravdu v (alfa2, beta2), ušetřil jsem nějaký čas díky většímu ořezávání. Je-li výsledkem alfa2, mám smůlu. Musím celý propočet zopakovat s širším nebo posunutým intervalem, například (alfa, beta2). Je-li výsledkem beta2, jde rovněž o neúspěch, ale stačí propočet zopakovat od tahu, který překročil beta2, tentokrát zřejmě s intervalem (alfa2, beta).

Díky kaskádové metodě počítáme tahy v dobrém pořadí, ve velké většině případů začínáme dobrým tahem. To nám umožní po propočtu jednoho nebo několika nejlepších tahů zmenšit betu na hodnotu dosavadního maxima, alfy, a zrychlit tím propočet méně favorizovaných tahů. Pokud jsme se spletli a nejlepší tah je až někde na chvostu, dojde k přetečení bety a propočet tahu zopakujeme s širším okénkem. Celý algoritmus můžete nalézt popsaný pod jménem negascout.

Hodnota pozice při propočtu do jednotlivých hloubek během kaskády se bude obvykle lišit jen málo. Můžeme tak zkusit sevřít interval již na počátku každé iterace (kromě té první) na nějaké okolí výsledku iterace předchozí. Pokud třeba vyjde cena pozice při propočtu do hloubky 5 jako plus čtvrt pěšce pro bílého, můžeme zkusit zahájit propočet do hloubky 6 s hodnotami alfa = -pěšec/4 a beta = +3*pěšec/4. Každopádně je zde dobré trochu experimentovat a doladit heuristiku na míru konkrétnímu programu. Může se stát, že liché hloubky propočtu budou vycházet pro hráče na tahu lépe než ty sudé, neboť právo tahu je výhoda, i to je třeba zohlednit. Je dobré šíři okénka nestanovit pevnou, ale v závislosti na změnách hodnoty pozice z předchozích iterací. Pokud se téměř neliší, můžeme okénko sevřít hodně, naopak při velkých změnách (typicky v útočných pozicích, kde malá změna hloubky propočtu může znamenat zásadní přehodnocení ceny pozice), jej příliš svírat nebudeme, případně na tuto heuristiku raději zcela rezignujeme.

Pod označením MTD-f se skrývá algoritmus, kdy se již pro první tah interval (alfa, beta) zcela uzavře a hodnotu pozice získávám opakovanými výpočty a posouváním intervalu. Uvádím jej spíše jen jako zajímavost, efektivní je pouze ve spojení s hash tabulkami, o kterých si něco řekneme v jednom z dalších dílů.

Prohlubování

Herní algoritmus, tak jak jsem jej popsal, počítá do pevně dané hloubky. Pokud se při propočtu dostane na úroveň listu, ukončí variantu a pozici odhadne statickou ohodnocovací funkcí bez ohledu na to, co se na šachovnici právě děje. V klidných pozicích bez taktických možností je to tak správně, ohodnocovací funkce zde pracuje obvykle poměrně dobře, případné prohloubení propočtu o jeden nebo dva půltahy by znamenalo jen malé zlepšení odhadu ceny varianty. Zcela jinak je tomu v pozicích takticky zaměřených. Představte si, že odhadujeme pozici statickou ohodnocovací funkcí uprostřed výměny těžkých figur na jediném volném sloupci nebo poté, co bílý sebral dámou krytého pěšce. Dobře zřejmě nedopadne ani odhad pozic tah před matem, kde vítězná strana obětovala materiál. Přitom by stačila často jen o málo větší hloubka propočtu a program by hrozby včas viděl. Celkovou hloubku nemůžeme příliš zvyšovat, propočet stromu má exponenciální časovou složitost a program by se nedopočítal. Řešením je prohlubování jen těch variant, které jsou zvlášť zajímavé.

Dopočet do tiché pozice

Dopočet do tiché pozice patří v šachách k nejjednodušším a zároveň nejdůležitějším vylepšením alfabeta metody, na úroveň hry programu má zcela zásadní vliv. Pokud se v propočtu dostanu do listu, neodhaduji pozici statickou ohodnocovací funkcí, ale jakousi modifikací alfabeta metody. Od běžného propočtu se liší tím, že uvažuji pouze braní a proměny pěšce. Vzhledem k tomu, že hráči odepírám všechny ostatní (takzvané tiché) tahy, musím mu umožnit nehrát, jinak bych jej nutil i do nevýhodných braní a proměn pěšců. Funkce tedy vrací maximum z hodnoty pozice odhadnuté statickou ohodnocovací funkcí a rekurzivního dopočtu braní, kde pochopitelně i soupeř má právo nehrát. Právě dopočet do tiché pozice řeší případy nedopočítaných výměn. Dopočet pochopitelně hodně zdržuje a sníží základní hloubku propočtu, ale pozitivní efekt je i tak obrovský. Kladný vliv má i na stabilitu propočtu, s dopočtem do tiché pozice se již nestává příliš často, aby změna hloubky propočtu o jedna zásadním způsobem změnila hodnotu varianty. V praxi se můžeme setkat s omezením maximální hloubky dopočtu, jinak by se mohl program zabývat zcela nesmyslnými variantami, kdy si oba hráči navzájem pobírají kameny silnou figurou zabloudivší do soupeřova tábora.

Prohlubování taktických variant

Dopočet do tiché pozice je účinný, ale neřeší všechny případy. Ve zvlášť nadějných variantách bývá dobré hloubku propočtu o jedničku zvětšit, nemusí se přitom nutně jednat o braní nebo proměny pěšce a k prohloubení nemusí dojít v listu. Narozdíl od dopočtu do tiché pozice se jedná opravdu jen o zvětšení proměnné s hloubkou propočtu o jedna v základním algoritmu propočtu, nebudu zde tedy umožňovat hráčům nehrát. Kdy přesně má smysl prohlubovat je složitá otázka a různé programy se zde mohou lišit. Za typické kandidáty na prohloubení bych označil varianty, kde je sebrána figura, která v minulém tahu sama brala, neboť se obvykle jedná jen o dokončení výměny. Pokrytí šachu představením bývá často jen oddálení matu na základní řadě nebo jiné katastrofy za horizont propočtu, proto prohloubím i zde. Zcela obecně, jakékoli varianty s vynucenými tahy může mít smysl prohloubit. Dále tu jsou vidle pěšcem i jezdcem a podobné taktické údery. Své místo mezi prohloubeními mají i varianty s tzv. Fischerovým střelcem. Sebrat černým střelcem nekrytého pěšce na h2 (nebo analogický ve zbývajících třech rozích šachovnice) je velmi lákavé, neodolal tomu ani jinak geniální Fischer v zápase se Spasským o titul mistra světa ani celá řada slabých šachových programů v mnohem méně slavných partiích. Většinou to pro černého skončí špatně, neboť často prostě stačí zahrát g3, pro chyceného střelce si dojít a pak už jen uplatnit převahu střelce proti dvěma ztraceným pěšcům. Je to o to mrzutější, že černý obvykle může nevyhnutelnou ztrátu všelijak oddalovat i o několik tahů. Program by proto zde měl prohlubovat propočet, aby ztrátu střelce uviděl. Prohlubovat bývá dobré i u taktických hrozeb králi, zlepší se tím hra v útočných pozicích. V listech zase budeme prohlubovat proměnu pěšce.

Vymyslet nebo nalézt ve zdrojových kódech šachových programů se dá celá řada dalších druhů prohloubení. Vždy je však třeba postupovat velmi opatrně, omezovat maximální počet prohloubení, vázat některá prohloubení na konkrétní pozici ve stromu a podobně. Stále musíme mít na paměti, že prohloubení jedné varianty znamená zkrácení všech ostatních variant, neboť čas propočtu bývá omezený.

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

Dnes jsme probrali prohlubování, v příštím dílu se zaměříme na opačný proces zvaný prořezávání.

Verze pro tisk