LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Š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 7237×

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 * 64n, 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 * 64n - 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í p0pn - 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 p0 + 64 * p1 + 642 * p2 + ... + 64n - 1 * pn - 1 + (hraje_bily ? 64n : 0). Pro neprogramátory připomínám, že hodnota závěrečné závorky je 64n nebo 0 podle toho, zda je na tahu bílý nebo černý.

Koncovka dvou střelců

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.

KámenPoleIndexHodnotaVýsledek
Bílý králf3212121
První bílý střelece32020 * 641 280
Druhý bílý střelecd31919 * 64277 824
Černý krále53636 * 6439 437 184
Bílý na tahu64416 777 216
Suma26 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 * 64n čísel, vyplň je nulami
  3. Projdi přirozená čísla od 0 do 2 * 64n - 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 * 64n - 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 ad 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

pridej.cz

 

DISKUZE

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ů

17.9.2014 14:44 /MaReK Olšavský
SAP otevřel svou jQuery UI knihovnu OpenUI5 (kódové jméno „Phoenix“) pod licencí Apache 2.0. Nadstavbě jQuery UI přibyl silný konkurent.
Přidat komentář

17.9.2014 7:29 /MaReK Olšavský
Vyšel Minix 3.3.0, pro uživatele GNU/Linxu důležitý tím, že právě na Minixu začal vývoj jádra Linux. Mezi zajímavými novinkami je podpora architektury ARM Cortex-A8 (třeba BeagleBoard/BeagleBone), nebo vylepšená kompatibilita s aplikacemi z NetBSD, ale zatím není dostupný X11 server. Najde své uživatele?
Přidat komentář

17.9.2014 7:29 /MaReK Olšavský
Vývojáři Mozilly pracující na novém programovacím jazyku Rust mají plán pro verzi 1.0 i pro kroky následující. Asi se blíží vydání první „finální“ verze.
Přidat komentář

17.9.2014 7:29 /MaReK Olšavský
oddělení „The Qt Company“ do samostatné firmy, plně vlastněné mateřskou Digií, píše LinuxGizmos. Vývoj Qt změnil několik vlastníků, za poslední roky, a uvedl i nové produkty za příznivější cenu.
Přidat komentář

16.9.2014 5:08 /MaReK Olšavský
VESA uvolnila technický standard DisplayPort 1.3. DP 1.3 má šířku pásma 32,1 Gb/s, což je dostatečný tok na 5k display při frekvenci 60 Hz. Technicky by se mohlo HDMI, populární především u spotřební elektroniky, stát historickou kapitolou (DP není zatížen licenčními poplatky).
Přidat komentář

16.9.2014 5:08 /MaReK Olšavský
SUSE (a další značky včetně Novellu) mají zase jiného majitele, Attachmate byla koupena společností Micro Focus za US$ 2,3 mld. Micro Focus se dosud věnoval enteprise sféře a nástroji Visual COBOL.
Přidat komentář

16.9.2014 5:08 /MaReK Olšavský
Finální verze Enlightenment 19 byla dokončena a hlavním tahákem je plná podpora nastupujícího Waylandu. Z dalších změn může zaujmout nový modul dlaždic, modul pro integraci správce balíků, nebo návrat live pageru (známého z E16). Po dlouhých letech stagnace se Enlightenment začal zajímavě vyvíjet.
Přidat komentář

15.9.2014 22:25 /Petr Ježek
Enlightenment E19 přistál v repozitáři Testing pro Archlinux. Testování lze jen doporučit.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

16.9.2014 3:49 / MaReK Olšavský
Re: Těžko

15.9.2014 14:35 / Petr Ježek
Těžko

14.9.2014 11:04 / Petr Ježek
DE, ne WM

12.9.2014 12:09 / Thomas Jones
Great

9.9.2014 15:58 / František Kučera
Re: Díky za článek

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2014) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze | zákony online