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

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ů

15.4.2014 7:32 /MaReK Olšavský
Vývojáři Linux Mintu vydali Cinnamon 2.2, vlastní desktop (který byl ještě nedávnou „pouhou“ nadstavbou GNOME3) nabízející vše dobré z GNOME2. Pro Mint Linux a Ubuntu už v repozitářích je, do ostatních distribucí se postupně dostane. Vedle příjemného oznámení dnes stojí i finanční problémy GNOME Foundation, za něž pravděpodobně může pozitivně diskriminační program OPW, jež znamenají financování jen nezbytně nutných činností spjatých s vývojem GNOME a GTK.
Přidat komentář

15.4.2014 7:32 /MaReK Olšavský
Na blogu The Linux Rain vyšel článeček s 5 důvody „proč je podpora Linuxu od GOG.com dobrou zprávou“. Nové tituly budou, v rámci možností, vycházet na Valve, ale existuje spousta kvalitních titulů, leč se starším datem vydání.
Přidat komentář

15.4.2014 7:32 /MaReK Olšavský
Linksys, nyní již ve vlastnictví Belkinu, připravil nový router s dobrou výbavou a svobodným formwarem WRT.
Přidat komentář

11.4.2014 12:41 /MaReK Olšavský
Projekt svobodného laptopu Novena uspěl a už se sériově vyrábí, byť pro leckoho může být překážkou poměrně vysoká cena cca US$ 2000. Na webu VentureBeat si můžete přečíst rozhovor s Andrewem „Bunnie“ Huangem o důvodech konstrukce svobodného laptopu. Pořídí si jej Richard M. Stallman?
Přidat komentář

11.4.2014 12:41 /MaReK Olšavský
OT: Pro mnoho uživatelů je velmi těžké loučení s Windows XP, ale byly kritizovány možná ještě více, než aktuální Windows 8. Je důvod litovat?
Přidat komentář

10.4.2014 7:02 /MaReK Olšavský
Firma ARM, jež vyvíjí a licencuje stejnojmenou mikroprocesorovou architekturu dalším výrobcům, poskytuje i vlastní vývojové nástroje. Zajisté i k nelibosti zastánců GPL se postupně přesouvá k LLVM, od zcela vlastního překladače. LLVM je mnohem modulárnější a flexibilnější, leč s trochu problematickým licencováním.
Přidat komentář

10.4.2014 7:02 /MaReK Olšavský
Společnost DMP ohlásila x86 minipočítač s Debianem, který má spotřebu pouhých 2,3 W. Minipočítač není určen do domácností, ale pro průmyslová nasazení, v malém množství jej lze koupit za US$ 89.
Přidat komentář

10.4.2014 7:02 /MaReK Olšavský
Březen roku 1989 byl přelomovým pro dnešní Arpanet, když Tim Berners-Lee začal pracovat na novém způsobu propojování jednotlivých stránek. Web OpenSource.com připomíná (s mírným zpožděním) významný milník ve vývoji open source, který by nebyl možný bez svobodných licencní a do budoucna bude i dále posilovat svobodu sdílení.
Přidat komentář

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

> Poslední diskuze

7.4.2014 6:31 / MaReK Olšavský
Re: No, nevím

4.4.2014 10:22 / Petr Ježek
No, nevím

4.4.2014 10:18 / Petr Ježek
ATI

24.3.2014 13:54 / Michal Linha
Re: Delimiter

24.3.2014 13:46 / Michal Linha
Re: Delimiter

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