Š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 14395×
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 + 72 + 73 + ... 7n-1
je v poměru s časem propočtu do největší hloubky (který
musíme tak jako tak vykonat) tj. 7n 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
|
Nejsou žádné diskuzní příspěvky u dané položky.
Příspívat do diskuze mohou pouze registrovaní uživatelé.
|
|

Vyhledávání software

Vyhledávání článků
28.11.2018 23:56 /František Kučera Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz 22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz 20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
Více ...
Přidat zprávičku
 Poslední diskuze
31.7.2023 14:13 /
Linda Graham iPhone Services
30.11.2022 9:32 /
Kyle McDermott Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš Re: zavináč
2.12.2018 23:56 /
František Kučera Sraz
5.10.2018 17:12 /
Jakub Kuljovsky Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?
Více ...
|