ARCHIV

Š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 14895×

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

  
0
1
2
3
...
8
...
19
  
20
21
22
23
...
28
...
39
  
40
41
42
43
...
64
  
65
66
67
...



  
a3
a4
b3
b4
...
e4
...
Jh3
  
a6
a5
b6
b5
...
e5
...
Jh6
  
a3
a4
b3
b4
...
Jh3
  
0
0
0
...



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] až 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.

Š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

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 Re: java a alokace pameti 9.11.2009 23:01 Jan Němec   Re: java a alokace pameti 9.11.2009 23:08 Jan Němec dama 13.11.2009 21:03 Radim Kolář Re: dama 15.11.2009 13:34 Jan Němec Odhad konstanty MNOHO 16.4.2010 19:04 Marika Ivanová   Re: Odhad konstanty MNOHO 17.4.2010 02:51 Marika Ivanová     Re: Odhad konstanty MNOHO 19.4.2010 09:34 Jan Němec Zobrazit označené Zobrazit vše Příspívat do diskuze mohou pouze registrovaní uživatelé.