LINUXSOFT.cz Přeskoč levou lištu

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

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ů

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

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

> Poslední diskuze

31.7.2023 14:13 / Linda Graham
iPhone Services

30.11.2022 9:32 / Kyle McDermott
Hosting download unavailable

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

Více ...

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