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

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ů

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ář

8.5.2016 17:19 /Redakce Linuxsoft.cz
PR: Dne 26.5.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í, cloudové služby, infrastruktura cloudu, efektivní využití cloudu, možné nástrahy cloudů a jak se jim vyhnout
Přidat komentář

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

2.3.2016 22:41 /Ondřej Čečák
Letošní ročník konference InstallFest již tento víkend!
Přidat komentář

14.2.2016 16:39 /Redakce Linuxsoft.cz
O víkendu 5. a 6. března 2016 proběhne na pražském Strahově 8. ročník tradiční konference InstallFest. Celkem za dva dny uvidíte ​30 přednášek​ a ​6 workshopů.
Přidat komentář

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

> Poslední diskuze

12.8.2016 11:51 / Josef Zapletal
Jak udělat HTML/Javascript swiping gallery do mobilu?

8.8.2016 14:58 / Adams
fairies for hire

28.7.2016 15:51 / pepan
Re: NetBeans vs Eclipse

10.6.2016 21:10 / pavel riha
FreeBSD 10.3 a virtualizace

8.6.2016 21:56 / Milan Gallas
Nevalidní prefix m

Více ...

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