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 7579×

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ů

19.12.2014 7:20 /MaReK Olšavský
Předvánoční dárek pro databázaře vyšel v podobě PostgreSQL 9.4. O novinkách napsal český článek Pavel Stěhule. Opravy chyb a drobná vylepšení jsou standardem, podpora datového typu JSON je velkým skokem vpřed.
Přidat komentář

19.12.2014 7:20 /MaReK Olšavský
Zdá se, že by se Intel mohl přecijen uchytit; vedle ARM; v segmentu chytrých telefonů. Čínské Lenovo plánuje pro rok 2015 nasazení Intelovského Atomu v nových smrtphonech.
Přidat komentář

19.12.2014 7:20 /MaReK Olšavský
Jazzový zpěvačka/pianistka Dinah Washington propůjčila jméno CMS Wordpress 4.1, jehož nejvýraznější novinkou je mód pro „nerušené psaní“.
Přidat komentář

18.12.2014 7:00 /MaReK Olšavský
Porovnání FreeBSD a OpenBSD (delší článek) vyšlo na blogu Network Filter. Asi nikoho nepřekvapí, že nelze jednoznačně určit vítěze a jednoznačné doporučení „nasaďte XYZ“.
Přidat komentář

18.12.2014 7:00 /MaReK Olšavský
Snad již poslední novinkou o vydání distribuce Fedora 21 jsou verze pro 64 bitové mikroprocesory ARM (oznámení) a pro mikroprocesory Power (oznámení). Obě verze budou mít asi poměrně malou cílovou skupinu ve správcích serverů. BTW: OpenPOWER Foundation se rozrostla o Rackspace.
Přidat komentář

18.12.2014 7:00 /MaReK Olšavský
Vznik další distribuce často komentuji slovy „kdybyste měli pocit, že distribucí je málo“, ale podle dlouhodobého sledování stránek DistroWatch naopak počet distribucí klesá. Lze to vnímat jako pozitivní jev, kdy se vývojáři spojují, místo vytváření bezpočtu derivátů.
Přidat komentář

17.12.2014 7:19 /MaReK Olšavský
Martin Malý napsal článek pro (nás) pamětníky o počítačích za železnou oponou. Zatím zvládl podchytit stav pouze někdejšího Česko—Slovenska :-).
Přidat komentář

17.12.2014 7:19 /MaReK Olšavský
National Geographic je známý svými populárně naučnými TV stanicemi, nebo vydáváním časopisu. Jak používá svobodný software prozradil Shah Selbe.
Přidat komentář

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

> Poslední diskuze

16.12.2014 3:59 / Jaroslav Kelt Kuchera
Download Perl

11.12.2014 6:42 / MaReK Olšavský
Po instalaci

10.12.2014 19:26 / Vladimir VASIL
Re: Sanba

11.11.2014 14:24 / Libor Suchý
Nekonečný while cyklus

10.11.2014 19:09 / Libor Suchý
Re: tabulka - bitovy sucet

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