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

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ů

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

27.2.2017 22:12 /František Kučera
Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
Přidat komentář

18.1.2017 0:49 /František Kučera
Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
Přidat komentář

8.1.2017 17:51 /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 19. ledna od 18:30 v pražském hackerspacu Brmlab. Tentokrát je tématem srazu ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. K vidění bude mechanická klávesnice dasKeyboard, trackball Logitech nebo grafický tablet (a velký touchpad) Wacom. Přineste i vy ukázat svoje zajímavé klávesnice a další HW. V 18:20 je sraz před budovou, v 18:30 jdeme společně dovnitř, je tedy dobré přijít včas. Podle zájmu se později přesuneme do nějaké restaurace v okolí.
Přidat komentář

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.
Komentářů: 1

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

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

> Poslední diskuze

17.4.2017 19:15 / Jakub shoop
chyba

9.3.2017 11:44 / Jaromir Obr
Re: chyba

18.1.2017 20:18 / martin horky
Spolupraca linuxu a microsoftu

17.1.2017 9:57 / Pavel Hrubeš
Re: Externí USB televizní karta

4.12.2016 22:54 / František Kučera
Dárek

Více ...

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