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

> Šachové myšlení (10) - Tahy

Efektivita šachového programu hodně závisí na reprezentaci tahů a způsobu jejich ukládání. Řekneme si něco tahu v jednom 16-bitovém čísle, zásobníku tahů a nakonec o propočtu s pseudolegálními tahy.

9.11.2009 00:00 | Jan Němec | Články autora | přečteno 10247×

Reprezentace tahu

V šachovém propočtu musíme nějak reprezentovat tah. Příslušný datový typ by neměl být příliš velký, neboť tahů budeme skladovat hodně. Navíc někdy se může hodit i přímo tahem indexovat nějaké pole, což by pro velké typy nebylo možné. Tak tomu může být například v historické heuristice, pokud si pro každý tah pamatujeme, jak byl v minulosti dobrý. Kdyby nám šlo pouze o velikost, mohli bychom tah reprezentovat číslem - pořadím, ve kterém ho vygeneruje nějaký pevně daný generátor tahů. Tah by pak zabral jen několik bitů. Kdyby navíc generátor nějak třídil tahy podle jejich kvality, většina tahů z běžné partie by měla čísla jako 0, 1 nebo možná 2 a jen hodně překvapivé tahy by měly čísla větší. Případná komprese by pak průměrnou velikost tahu stlačila na 2 nebo 3 bity. To by se hodilo, pokud bychom navrhovali reprezentaci tahu pro databázi miliónů partií. My potřebujeme tah reprezentovat v propočtu, kde je kromě velikosti důležitá i rychlost běžných šachových rutin. Velkou většinu tahů (budeme jim říkat normální tahy) provedeme prostě takto:

sachovnice[kam] = sachovnice[odkud];
sachovnice[odkud] = 0;
/* + nastavení zkažených rošád, pokud se táhlo králem nebo věží ze základního postavení */

Výjimky tvoří proměny pěšce, braní mimochodem a rošády. Těchto tahů je však poměrně málo a není třeba zde šetřit každou instrukci. Na šachovnici 12x10 je index pole 7-bitové číslo. Pro reprezentaci tahu pomocí polí odkud a kam nám tedy budou stačit dvě 7-bitová čísla + informace (1 bit) o tom, zda jde o normální tah, to je celkem 15 bitů, takže se s nepatrnou rezervou vejdeme do dvoubytového typu u16 (obvykle unsigned short). U nenormálních tahů si budeme pamatovat, že to je nenormální tah (1 bit) a zda se jedná o rošádu, braní mimochodem nebo proměnu pěšce (2 bity) a do zbývajících 13 bitů se už vše potřebné vejde snadno, neboť políčka odkud a kam již není třeba reprezentovat ve vší obecnosti. Například u proměny bílého pěšce nám stačí 3 bity (8 hodnot a7 až h7) na odkud, 3 bity (8 hodnot a8 až h8) na kam a 2 bity na proměněnou figurku (jezdec, střelec, věž, dáma).

Takto definovaný datový typ tah je poměrně malý a zároveň umožňuje efektivní rutiny.

Zásobník tahů

Již víme, že rekurzivní propočet prochází strom hry a v každé navštívené pozici generuje tahy. Těch pozic jsou ovšem milióny, takže v generování a skladování tahů je třeba šetřit bez nadsázky každou mikrosekundu. Přesto si jsem jistý, že by se našli programátoři, kteří by nepsali něco takového:

int rekurzivniPropocet(/* ... */) {
/* ... */

  Vector<Integer> tahy = generujTahy(); // Zde je problém

  for (int i = 0; i < tahy.size(); i++) {
    tahni(tahy.elementAt(i).intValue());
    rekurzivniPropocet(/* ... */);
    tahniZpet(tahy.elementAt(i).intValue());
  }

/* ... */
}

Schválně jsem výjimečně použil javu, neboť s garbage collectorem je vše ještě mnohem horší. Problém je, že tahy jsou zde reprezentovány pomocí na heapu alokovaného vektoru plného na heapu alokovaných tahů. Jedním ze základních pravidel optimalizace je odstranění alokací v cyklu a v rekurzivním volání. O malý krok lepší je tedy C++ řešení

  std::vector<u16> tahy;
  generujTahy(tahy);

ale stále to není ono, neboť i zde musí funkce generujTahy alokovat. Bez alokace se obejdeme, pokud budeme tahy skladovat v obyčejném céčkovském poli

  u16 tahy[MAX_TAHU_Z_POZICE];
  generujTahy(tahy);

ovšem zde zase máme problém s konstantou MAX_TAHU_Z_POZICE. Bude-li moc malá, v divokých pozicích se čtyřmi dámami program selže, při velké konstantě zase bude mrhat pamětí se všemi negativními důsledky včetně zbytečného zaplňování rychlé cache paměti procesoru. Určitou nevýhodou všech uvedených řešení je navíc lokální proměnná tahy. Může mít dobrý smysl zajímat se o tahy z naší pozice i v pozici jiné, například nějaká heuristika se může rozhodovat na základě počtu tahů v předchůdci v stromu propočtu. Proto by vygenerované tahy neměly být lokální.

Běžně se proto celá záležitost řeší zásobníkem tahů:

  u16 tahy[MNOHO];
  int hranice[MAX_HLOUBKA_PROPOCTU + 1]
  int index_v zasobniku;

Tahy generujeme pouze do pole tahy. V poli hranice máme odděleny tahy z jednotlivých pozic na cestě stromem hry a index_v zasobniku ukazuje aktuální zanoření. Pokud program počítá nejlepší tah ze základního postavení a právě propočítává variantu 1. e4 e5, bude zásobník vypadat nějak takhle:

tahy = 1. tah bílý1. tah černý 2. tah bílývolno
0123...8...19 20212223...28...39 40414243...64 656667...
a3a4b3b4...e4...Jh3 a6a5b6b5...e5...Jh6 a3a4b3b4...Jh3 000...
hranice = {0, 20, 40, 65, 0, 0, 0, ...} index_v zasobniku = 2;

Tedy tahy jsou uloženy v jediném globálním jednorozměrném poli, přičemž tahy z aktuálně propočítávané pozice mají index hranice[index_v zasobniku]hranice[index_v zasobniku + 1] - 1. V úvodní definici jsem uvedl konstanty MNOHO a MAX_HLOUBKA_PROPOCTU. MAX_HLOUBKA_PROPOCTU je nejvyšší možná hloubka zanoření rekurze, na dnešních počítačích a bez nějakých opravdu ďábelských prohlubovacích metod by mělo stačit 32. Vhodná velikost MNOHO pak půjde shora odhadnout MAX_TAHU_Z_POZICE * MAX_HLOUBKA_PROPOCTU.

Pseudolegální tahy

Na následujícím obrázku je postupně černý v matu, patu a speciálním případu patu, kdy černý nemá k dispozici dokonce ani tah vedoucí do šachu.

Pat a mat

Šachy mají vlastně trochu zvláštní pravidla. Jako by se hrálo na sebrání krále, ale snad aby partii nerozhodla jen prostá nepozornost, hráč ani nesmí nabídnout soupeři svého krále k sebrání. Ve vážných partiích nastavení krále neprohrává partii, ale vrací se jako jakýkoli jiný nemožný tah. Mat je vlastně situace, kdy hráč nemůže zabránit sebrání svého krále v příštím tahu. Jak známo, matem partie končí, hráč už ani nemá právo zkusit, jestli soupeř mat opravdu vidí a krále sebere. V praxi to ovšem není příliš důležité, šachisté obvykle vzdávají partie i několik desítek tahů před matem, takže je vlastně jedno, že se hraje na mat a ne na sebrání krále. Jedinou důležitou výjimkou je pat. Nastane-li pat, král není v šachu, ale jakýkoli tah k šachu vede. Kdyby se hrálo na sebrání krále, pat by byla prohra (snad kromě případů, kdy není k dispozici vůbec žádný tah, ani ten vedoucí do šachu). Ve skutečných šachách je pat remíza.

Tahům které by byly přípustné, kdybychom směli (podle pravidel nesmíme) vystavit svým tahem vlastního krále šachu, budeme říkat pseudolegální tahy. Těm skutečně přípustným pak legální tahy. V příkladu na obrázku má černý v matu a běžném patu tři pseudolegální tahy, ale ani jeden legální. Ve zvláštním patu vpravu dole nemá černý ani legální ani pseudolegální tah. Je zřejmé že vygenerovat všechny pseudolegální tahy dá méně práce než vygenerovat jen ty legální, neboť odpadnou testy na šach. Šachové programy toho obvykle využívají. Provádějí propočet, jako by se šachy hrály na sebrání krále a ne jen do matu, tedy propočítávají se všechny pseudolegální tahy. A jak se ty nepřípustné tahy odfiltrují? Třídící algoritmus generátoru tahů dá sebrání krále na první místo, a tak propočet pozice vzniklé nepřípustným pseudolegálním tahem (vlastní král v šachu) ihned vrací jako návratovou hodnotu - cenu pozice nějakou mezní hodnotu. Tím se ořeže propočet nepřípustných variant. Pokud jsou všechny tahy nepřípustné jedná se o pat nebo mat.

Poněkud jiná je situace, pokud hráč na tahu je v šachu. Obvykle má v této situaci hráč spoustu pseudolegálních tahů, ale jen několik málo skutečně legálních. To jsou ty tahy, které šach kryjí. Zde nemá smysl počítat se všemi pseudolegálními tahy, je lepší napsat pro generování tahů ze šachu speciální funkci, která generuje pouze přípustné tahy.

Pokračování příště

V příštím dílu probereme ohodnocovací funkci.

Verze pro tisk

pridej.cz

 

DISKUZE

java a alokace pameti 9.11.2009 01:22 Radim Kolář
|- Re: java a alokace pameti 9.11.2009 08:23 Aleš Hakl
|- Re: java a alokace pameti 9.11.2009 08:50 Jan Němec
L Re: java a alokace pameti 9.11.2009 23:01 Jan Němec
  L Re: java a alokace pameti 9.11.2009 23:08 Jan Němec
dama 13.11.2009 21:03 Radim Kolář
L Re: dama 15.11.2009 13:34 Jan Němec
Odhad konstanty MNOHO 16.4.2010 19:04 Marika Ivanová
  L Re: Odhad konstanty MNOHO 17.4.2010 02:51 Marika Ivanová
    L Re: Odhad konstanty MNOHO 19.4.2010 09:34 Jan Němec




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

1.12.2016 22:13 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.
Přidat komentář

4.9.2016 20:13 /Pavel `Goldenfish' Kysilka
PR: Dne 22.9.2016 proběhne v Praze konference Cloud computing v praxi. Tématy bude např. nejnovější trendy v oblasti cloudu a cloudových řešení, provozování ERP v cloudu, o hostování různých typů softwaru, ale třeba i o zálohování dat nabízeném podnikům formou služby.
Přidat komentář

1.9.2016 11:27 /Honza Javorek
Česká konference o Pythonu, PyCon CZ, stále hledá přednášející skrz dobrovolné přihlášky. Máte-li zajímavé téma, neváhejte a zkuste jej přihlásit, uzávěrka je již 12. září. Konference letos přijímá i přednášky v češtině a nabízí pomoc s přípravou začínajícím speakerům. Řečníci mají navíc vstup zadarmo! Více na webu.
Přidat komentář

27.8.2016 8:55 /Delujek
Dnes po 4 letech komunitního vývoje vyšla diaspora 0.6.0.0
diaspora* je open-source, distribuovaná sociální síť s důrazem na soukromý
Více v oficiálním blog-postu
Přidat komentář

24.8.2016 6:44 /Ondřej Čečák
Poslední týden CFP LinuxDays 2016; pokud byste rádi přednášeli na LinuxDays 2016 8. a 9. října v Praze, můžete svůj příspěvek přihlásit, následovat bude veřejné hlasování.
Přidat komentář

9.8.2016 22:56 /Petr Ježek
Zařazení souborového systému reiser4 do jádra 4.7 znamená konečně konec patchování jádra jen kvůli možnosti použít reiser4.
Přidat komentář

12.7.2016 13:14 /František Kučera
Spolek OpenAlt zve na 130. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 21. července od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

11.7.2016 16:53 /Redakce Linuxsoft.cz
Konference LinuxDays hledá přednášející. Přihlášky poběží do konce prázdnin, v září bude hlasování a program. Více na https://www.linuxdays.cz/2016/cfp/.
Přidat komentář

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

> Poslední diskuze

9.11.2016 7:42 / Mane
hardwood floor waxing

8.11.2016 13:38 / Mira
Konfigurace maldet na Centos serveru

2.11.2016 11:06 / Warlock
Odkaz v PHP

20.10.2016 0:13 / Jan Kuba
Re: Basic

19.9.2016 21:04 / Marek Schoř
Poděkování

Více ...

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