ARCHIV

Šachové myšlení (13) - Databáze koncovek

Již umíme naučit náš program hrát zahájení jako velmistři. Dnes se si řekneme, jak naučit program hrát několikakamenné koncovky naprosto dokonale. Počítač třeba v koncovce dámy proti dvěma střelcům, kterou dokonale nezvládají ani ti nejlepší lidští velmistři, bez přemýšlení zahlásí mat 50. tahem a opravdu předvede nejrychlejší cestu k výhře.

14.4.2010 13:00 | Jan Němec | Články autora | přečteno 13181×

S ubývajícím počtem kamenů a blížícím se koncem partie se pozice postupně zjednodušuje. Při propočtu ubývá možných variant, spousta z nich vede do stejné pozice, jiné zase brzy končí matem nebo remízou. Je přirozené ptát se, kdy program dopočítá všechny podstatné varianty stromu hry až do konce a začne hrát dokonale. Budeme chtít, aby v remízové pozici udržel remízu, vyhranou pozici vyhrál tím nejrychlejším způsobem a v prohraných pozicích partii alespoň co nejvíce protahoval. Pokud zkusíte standardnímu prohledávacímu algoritmu předložit třeba nějakou pozici z koncovky střelce a jezdce proti samotnému králi, budete nejspíš zklamaní. Kvalitní program koncovku sice zvládne, zatlačí soupeřova krále do rohu barvy střelce a tam ho zmatí, ale rozhodně nenajde ten nejrychlejší postup a maty třeba 20. tahem zdálky prostě neuvidí. V opravdu těžkých koncovkách typu dáma proti dvěma lehkým figurám pak běžný kvalitní myslící algoritmus již bude chybovat a některé vyhrané pozice vyhrát nedokáže. V omezeném čase není možné ani v poměrně jednoduché koncovce projít celý graf hry z kořene k listům, díky kolizím v hašovací funkci navíc budeme řadu variant počítat opakovaně, takže s dokonalou hrou nemůžeme počítat ani v elementární koncovce dámy proti samotnému králi.

Naštěstí je to s pozicemi z koncovek podobné, jako s těmi ze zahájení. Dají se naučit. Všech možných pozic několikakamenné koncovky je sice z lidského pohledu mnoho, ale počítač má posunutá měřítka. Jednoduchý horní odhad pro počet pozic n-kamenné koncovky je 2 * 64ⁿ, neboť každá figurka může být na jednom ze 64 polí a možnosti se násobí. Úvodní dvojka je tam kvůli právu tahu, buď hraje bílý nebo černý. Rošádami a braním mimochodem si situaci komplikovat nebudeme. Například šance, že by program potřeboval hrát koncovku dámy proti věži (bez dalších kamenů) a soupeř dosud netáhl ani králem ani věží je opravdu minimální. Braní mimochodem se zase vyhneme omezením se jen na některé pěšcové koncovky. Náš odhad bychom mohli i zpřesnit na 2 * 64 * 63 * 62 * ... * (64 - n + 1), protože dva kameny nemohou být na stejném políčku, takže 1. kámen má 64 možností, druhý jen 63 atd. Mohli bychom také vyškrtat nepřípustné pozice, ztotožnit stejné kameny atd., ale úvodní vzorec nám zároveň dává návod, jak velmi jednoduše a efektivně každé pozici zkoumané koncovky přidělit číslo od 0 do 2 * 64ⁿ - 1 (její místo v tabulce příslušné koncovky) a naopak ke každému číslu z uvedeného intervalu přiřadit pozici.

Stanovíme si pořadí kamenů naší koncovky podle jejich barvy a materiální hodnoty. Například pro koncovku jezdce a střelce to může být pořadí bílý král, bílý střelec, bílý jezdec, černý král. Očíslujeme políčka šachovnice od 0 do 63, a1 bude 0, a2 1 atd., h8 bude 63. Máme-li n jednoznačně seřazených kamenů, označíme čísla políček, na nichž se nacházejí p₀ až p_{n - 1}. U koncovek s opakováním jednoho druhu kamene (například koncovka krále proti dvěma střelcům) budeme jako první uvažovat kámen s vyšším indexem políčka. Číslo pozice pak bude p₀ + 64 * p₁ + 64² * p₂ + ... + 64^{n - 1} * p_{n - 1} + (hraje_bily ? 64ⁿ : 0). Pro neprogramátory připomínám, že hodnota závěrečné závorky je 64ⁿ nebo 0 podle toho, zda je na tahu bílý nebo černý.

Na obrázku je příklad pozice z koncovky dvou střelců. Pořadí kamenů bude KSSk, tedy bílí král a oba střelci a nakonec černý král. Na tahu je bílý a na naší šachovnici hraje nahoru, střelci jsou tedy na d3 a e3, bílý král na f3 a černý na e5. V následující tabulce je výpočet čísla pozice v rámci dané koncovky. Výsledek je 26 293 525.

Opačný převod z čísla na pozici bude analogický, číslo rozložíme na cifry v 64-kové soustavě a to budou indexy políček jednotlivých kamenů.

Vlastní algoritmus vygenerování databáze n kamenné koncovky už bude jednoduchý:

1. Rekurzivně stejným algoritmem vygeneruj databáze koncovek, které z naší koncovky mohou vzniknout. (Například pro koncovku dámy proti věži vygeneruj nejprve koncovku se samotnou dámou a se samotnou věží.)
2. Naalokuj místo pro 2 * 64ⁿ čísel, vyplň je nulami
3. Projdi přirozená čísla od 0 do 2 * 64ⁿ - 1, ke každému vygeneruj pozici. Je-li nepřípustná (2 kameny na sobě, šach nehrajícímu), vlož do pole čísel na daný index konstantu CHYBA, je-li černý v matu vlož 1, je-li bílý v matu, vlož -1.
4. Projdi přirozená čísla od 0 do 2 * 64ⁿ - 1, přeskoč ty, kde je na daném indexu v poli jiné číslo než nula. Ke každému číslu vygeneruj pozici. Na náš index do pole vlož stručně řečeno hodnotu propočtu minimaxem do hloubky 1 s ohodnocením pomocí již spočítaných hodnot a nul v poli. Podrobně řečeno: Dejme tomu, že hraje bílý (pro černého budeme postupovat analogicky). Vygeneruj z pozice tahy, zahraj je. Pokud zahraným tahem přešla pozice do jiného druhu koncovky (proměna pěšce, braní), podívej se do tabulky pro tuto koncovku, kolikátým půltahem bílý dává nebo dostává mat, případně zda je pozice remízová. Pokud zůstal zachován typ koncovky, spočítej si index pozice a podívej se do pole, zda a jak již máme pozici ohodnocenou. 0 znamená, že zatím nevíme, kladné číslo, že je pozice vyhraná za bílého, záporné, že za černého. Je-li mezi čísly alespoň jedno kladné vlož do pole na náš index to nejmenší z těch kladných čísel zvětšené o 1. (Například z 0, 0, 0, 5, 3, -2, 0, 0, -2, -4 vyber 3 a do pole na náš index dej 3 + 1 = 4. Znamená o, že dáváme mat 2. tahem, neboť jsme o 3 půltahy od 1, což je mat.) Jsou-li všechna čísla záporná, je pozice za bílého prohraná, vyber z nich to nejmenší (s největší absolutní hodnotou) a do pole na náš index ho dej zmenšené o 1. (Například z -2, -4, -6, -6, -4 vyber -6 a do pole dej -7. To jsme na tahu a dostáváme mat 3. tahem.) Poslední možností je, že mezi čísli je alespoň jedna 0 a zbytek jsou buď nuly nebo záporná čísla. V tom případě ještě nemůžeme rozhodnout a v poli necháme nulu.
5. Pokud jsme zapsali do pole alespoň jednu nenulu, pokračuj bodem 4.
6. Ulož pole tak, jak je, do souboru.

Máme-li vygenerovanou tabulku, je již velmi jednoduché napsat optimální algoritmus hry. Jedná se o prostý minimax do hloubky 1. Místo běžné ohodnocovací funkce se budeme dívat do tabulky. 0 znamená, že žádná ze stran nemůže vyhrát, tedy remíza. Kladná čísla jsou pozice vyhrané za bílého, čím dál od jedničky, tím dál od matu. Totéž platí s černým pro záporná čísla. V remízových pozicích pak můžeme spustit i klasický myslící algoritmus omezený na tahy, které nevedou k naší prohře. Jde jen o to, aby v remízových pozicích, kde ovšem o remízu bojuje soupeř, program nerezignoval na teoreticky marnou, ale prakticky proti reálnému soupeři často nadějnou snahu o výhru a nezahrál prostě jakýkoli neprohrávající tah. Například v těžké (pro 2 jezdce), ale remízové koncovce dámy proti dvěma jezdcům by program asi neměl nastavit dámu. To sice objektivně není chyba, neboť i koncovka krále a dvou jezdců proti samotnému králi je remízová, ale subjektivně to jistě chyba je a uživatel by to asi programu neodpustil.

Pokud si dáte tu práci a výše uvedený algoritmus pro generování tabulky koncovky naprogramujete, zjistíte, že ani na dnešních počítačích není dostatečně rychlý. Při jednoduché implementaci bez velkých optimalizací získáte na počkání jen (elementární) tříkamenné koncovky a přes noc i ty zajímavější čtyřkamenné. Dnes jsou přitom běžné kvalitní programy na PC vybavené kompletně vyřešenými šestikamennými koncovkami a případně i některými sedmikamennými. Soubory s vygenerovanými koncovkami zaberou řádově několik GB. Jednou z nejjednodušších a zároveň velmi účinných metod, jak výpočet zrychlit a zmenšit i objem vygenerovaných dat je využití nejrůznějších symetrií. 50% ušetříme, pokud jednotlivé koncovky budeme generovat jen pro jednu stranu tj. nikoliv celkem dvakrát: jednou pro bílého a jednou pro černého. Dále můžeme ušetřit překlápěním šachovnice. Pokud vyloučíme rošády, můžeme pozici ztotožnit s jejím osově souměrným obrazem, kdy osa vede mezi sloupci d a e. Generovat tedy budeme jen pozice, na nichž je bílý král na sloupcích a až d a jejich dvojčata budeme pomocí osové souměrnosti transformovat. V bezpěšcových koncovkách můžeme podobně překlápět i podle vodorovné osy mezi 4. a 5. řadou a dokonce i podle na hlavní diagonály a1 - h8. Bílý král tak bude vždy v trojúhelníku a1-d1-d4. Místo 64 možných polí tak zbude bílému králi pouze 10 polí, lze tedy očekávat díky osovým souměrnostem zhruba 6,4-násobné zrychlení a úsporu paměti při generování i při uložení výsledků.

V tabulce jakékoli koncovky se poměrně často a relativně pravidelně opakují číselné hodnoty. Je zřejmé, že data půjde úspěšně komprimovat téměř jakoukoli rozumnou metodou. Vzhledem ke způsobu využití je nutné, aby pro přečtení hodnoty z komprimované tabulky stačilo dekomprimovat jen nějaké malé okolí a nikoli celou tabulku.

V některých koncovkách je problém s pravidlem padesáti tahů. K výhře bychom potřebovali více než padesát tahů bez braní a tahu pěšcem. Některé jinak vyhrané pozice se s uvedeným pravidlem vyhrát prostě nedají. Jiné vyhrát jdou, ale místo nejkratší cesty k matu musíme sledovat nejkratší cestu do jednodušší vyhrané koncovky. Například pokud v koncovce dámy proti dvěma střelcům můžeme zvolit

• Variantu, kde v 51. tahu sebereme 1. střelce, v 60. tahu druhého a v 65. dáváme mat
• Variantu, kde v 49. tahu sebereme 1. střelce, v 63. tahu druhého a v 68. dáváme mat,

bude náš algoritmus toužící po co nejrychlejším matu preferovat první variantu, ačkoli striktně vzato (pokud pravidlo 50 tahů chápeme opravdu jako součást pravidel šachu a nikoli jen jako ne zcela plnohodnotnou pomůcku proti nekonečným partiím) jde o chybu a správně by měl zvolit druhou variantu. Proto se někdy jako kritérium při generování tabulky volí nejen vzdálenost od matu, ale i vzdálenost k jednodušší vyhrané koncovce. Program pak nezahlásí: "Dávám mat 65. tahem.", ale: "Za 49 tahů přejdu do jednodušší vyhrané koncovky."

Konec seriálu

Databází koncovek celý seriál končí, přeji čtenářům hodně programátorské radosti a úspěchů s vlastními šachově-programátorskými experimenty.

Verze pro tisk