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

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ů

24.11.2014 7:19 /MaReK Olšavský
O přízeň uživatelů kodeků se uchází 2 balíky, FFmpeg a Libav (který je forkem FFmpeg, vzniklým v roce 2011).Mainstreamové distribuce, jako Debian, Ubuntu, nebo Fedora, používají Libav, ale Ubuntu by se mělo vrátit k FFmpeg, počínaje verzí 15.04. Ubuntu tímto činí další krok, který je nezávislý na mateřské distribuci Debian.
Přidat komentář

24.11.2014 7:19 /MaReK Olšavský
Blíží se dlouhé zimní večery a Steam přichází s nabídkou simulátoru kozy :-) za příjemných 9,99 €, samozřejmě i ve verzi pro GNU/Linux. Kolik toho zvládne jedna koza sežrat a zničit?
Přidat komentář

21.11.2014 7:41 /MaReK Olšavský
Američtí uživatelé již to zjistili, když byl ve Firefoxu defaultní vyhledávač přenastaven na Yahoo, ale Google již není jediným partnerem pro vyhledávání (a financování).
Přidat komentář

20.11.2014 7:36 /MaReK Olšavský
Libby Clark sepsala, pro Linux Foundation, příběh zapojení SanDisku do vývoje F/L/OSS. SanDisk se postupně stal 7. největším přispěvatelem do vývoje Cephu.
Přidat komentář

20.11.2014 7:36 /MaReK Olšavský
Zajímá-li vás astronomie a jste nakloněni GNU/Linuxu, jinak byste asi nenavštívili náš web, měli byste si vyzkoušet čerstvé vydání Astro Linuxu (verze 3.0). Výběr software, pro distribuci založenou na Debianu, je přizpůsoben právě astronomům.
Přidat komentář

20.11.2014 7:36 /MaReK Olšavský
Vývojáři odešlí z Nokie po ukončení snah o linuxová zařízení vytvořili společnost Jolla Ltd, která vypustila do světa první mobilní telefon a teď asi přepsala rekordy crowdfundingu kampaní na výrobu tabletu se Sailfish OS, která během 3 hodin vybrala potřebnou částku.
Přidat komentář

19.11.2014 7:20 /MaReK Olšavský
WhatsApp, potažmo současný majitel Facebook, daroval US$ 1 mil do FreeBSD Foundation. Jedná se o historicky nejvyšší jednorázovou částku pro FreeBSD a nejspíše i pro svobodný software.
Přidat komentář

19.11.2014 7:20 /MaReK Olšavský
Bezplatná verze „úvodu do GNU/Linuxu“, kterou spustila Linux Foundation na stránkách edX má úspěch, zatím jím prošlo 300 000 účastníků.
Přidat komentář

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

> Poslední diskuze

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

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

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

24.10.2014 17:47 / Petr Ježek
Andreas

16.10.2014 7:56 / Leo
Sanba

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