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

> Šachové myšlení (9) - Reprezentace pozice

Šachovnici lze a má dobrý smysl reprezentovat i jinak než dvourozměrným polem 8x8. Může to zjednodušit kód a podstatně urychlit myšlení programu. Ukážeme si všechny tři v dnešních šachových programech běžně užívané reprezentace.

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

Existují tři běžně užívané způsoby reprezentace šachovnice.

Šachovnice v poli 8x8

Snad každý programátor bez zkušeností s psaním šachů by asi celkem automaticky po několika vteřinách a bez velké duševní námahy navrhl něco jako

s8 sachovnice[8][8];

Tedy prosté dvourozměrné pole 8x8. Možná by ho jenom rozvinul do jednoho rozměru na

s8 sachovnice[64];

s tím, že sachovnice[0] bude a1, sachovnice[1] a2, atd. a sachovnice[63] bude pochopitelně h8.

Zásady kulturního programování velí používat pro prázdné pole a jednotlivé kameny libovolně předefinovatelné symbolické konstanty, ale v tomto případě je lepší nechat zásady stranou a konstanty pro kameny určit "natvrdo". Mně se osvědčila 0 pro prázdné pole a 1 až 6 postupně pro bílého pěšce, jezdce, střelce, věž, dámu a krále. Pro černého používám odpovídající záporná čísla. Takto definované konstanty umožňují například indexovat nejrůznější pole s údaji pro jednotlivé kameny (například koeficienty hašovací funkce, hodnotu kamene, atd.) přímo svojí hodnotou, snadno lze provádět for cyklus přes všechny kameny a podobně. Konstanta pro kámen zároveň vyjadřuje jeho význam v běžné pozici. Pěšec je nejméně důležitý, má tedy jen jedničku, jezdec je o něco lepší, přiřadíme mu dvojku atd. To může trochu zjednodušit například třídění tahů již v generátoru, je velmi jednoduché třeba lehce zvýhodnit braní méně významnou figurou a poslat je do třídění tahů podle nadějnosti před propočtem s malým bonusem. (Když pěšec bere jezdce, je to téměř jistě dobrý tah, ale u braní dámou to platí jen, pokud jezdec není krytý. Proto je braní pěšcem o něco nadějnější.)

Šachovnice v poli 10x12

Šachovnice 8x8 vypadá dobře a myšlenka vložit ji do středu většího pole se zdá být na první pohled šílená. Proč mrhat pamětí a opouštět krásné kulaté hodnoty jako 8 a 64 a nahradit je následující obdélníkovou hrůzou rozvinutou do jednorozměrného pole?

s8 sachovnice[120] =  
 { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h*/
   100,   4,   2,   3,   5,   6,   3,   2,   4, 100, /* 1 */
   100,   1,   1,   1,   1,   1,   1,   1,   1, 100, /* 2*/
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 3*/
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 4*/
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 5*/
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 6*/
   100,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1, 100, /* 7*/
   100,  -4,  -2,  -3,  -5,  -6,  -3,  -2,  -4, 100, /* 8*/
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100
 };

#define a1 21
#define b1 22
#define c1 23
/* ... */
#define h1 28
#define a2 31
#define b2 32
#define c2 33
/* ... */
#define f8 96
#define g8 97
#define h8 98

Zkuste si napsat generátor tahů pro šachovnici 8x8, pro začátek alespoň tahy bílého jezdce. Asi to skončí nějak takhle:

int sloupec, radek;
for (sloupec = 0; sloupec < 7; sloupec++)
  for (radek = 0; radek < 7; radek++) {
    switch (sachovnice[sloupec][radek]) {
      /* ... */
      case 2:  /* bílý jezdec */
        if (sloupec + 2 < 8 && radek + 1 < 8 && sachovnice[sloupec + 2][radek + 1] <= 0)
          zaradTah(sloupec, radek, sloupec + 2, radek + 1);
        if (sloupec + 2 < 8 && radek - 1 >= 0 && sachovnice[sloupec + 2][radek - 1] <= 0)
          zaradTah(sloupec, radek, sloupec + 2, radek - 1);
        
        /* a ještě šest dalších směrů tahu jezdce */
        
        break;
      /* ... */
    }
  }

Takový kód se pochopitelně špatně ladí, zvlášť pokud navíc máme generátor ve více variantách (například pro nalezení pouze všech braní nebo tahů ze šachu), stačí v jediném řádku zaměnit < 8 za >= 0 a jezdec jednou za několik partií vesele vyskočí ze šachovnice třeba na f9. Navíc kontrolovat meze šachovnice je nejen otravné pro programátora, ale i zdržuje procesor během propočtu.

Lepší je proto netestovat meze, ale nasázet do zvětšeného pole kolem šachovnice speciální hodnotu. Jezdec skočí o dvě políčka ve směru x nebo y, okraj tedy musí být ve směru osy y široký 2 pole. Ve směru x stačí okraj jen jedno pole neboť jezdec při skoku ze sloupce a nebo h ven z šachovnice o 2 doskočí na okraj sousedící s odvrácenou stranou šachovnice. Například pokud zkusíme táhnout jezdcem z a1 doleva o 2 a nahoru o 1, skočíme na ch2, kde je speciální hodnota indikující okraj. (Šachovnici 10x12 je lepší si představit na válci, dole bude okraj šířky 2 pod 1. řadou, nahoře stejně široký okraj nad 8. řadou. Okraje u sloupce a a h spolu sousedí, takže dohromady mají rovněž šířku 2. Jednorozměrná implementace je na válec navinutá jako pružina - péro od auta o dvanácti závitech.)

Jednorozměrná implementace s okrajem pak umožní takto jednoduchý generátor.

/* O kolik se může pohnout jezdec v rozvinuté jednorozměrné šachovnici */
const s8 ofsety[8] = {21, 19, 12, 8, -21, -19, -12, -8};
/* .... */

for (pole = a1; pole <= h8; pole++) {
  switch(sachovnice[pole]) { 
    case 2: /* bílý jezdec */
      for (j = 0; j <= 8; j++) 
        if (sachovnice[pole + ofsety[j]])) <= 0) zaradTah(pole, pole + ofsety[j]);
      break;
    /* ... */
  }
}

Všimněte si pole ofsety. Jedná se o všechny posuny jedním tahem jezdce na šachovnici 10x12. Podobné pole bychom ve skutečném programu měli ještě 3: pro střelce, věž a poslední pro krále s dámou. Obsahovaly by jen posuny o jedno políčko v jednotlivých směrech. Dlouhonohé figury jako střelec, věž a dáma by se pak pochopitelně řešily cyklem.

Bitové pole

Zcela odlišnou reprezentací šachovnice je bitové pole. Nějakému boolovskému jevu na políčku odpovídá jeden bit. Šachovnice má 64 polí, takže jev na jednotlivých polích můžeme reprezentovat 64 bitovým číslem. Jevem může být třeba výskyt bílých věží. V základním postavení bude tomuto jevu odpovídat 1 | (1 << 7), tedy 129. Ta první jednička je za Va1, druhá a posunutá o 7 bitů za Vh1 (a1 má index 0, takže neposouváme, h1 je na indexu 7, takže posouváme o 7, kdyby stála na h8, posouvali bychom o 63). Pro každý typ kamene budeme mít jednu proměnnou, takže 12 proměnným může reprezentovat celou šachovnici. Jevem však nemusí být jen výskyt konkrétního typu kamene, ale třeba napadení pole (jakýmkoli) černým pěšcem a podobně.

A teď to přijde. Zajímá vás, jestli je (jakákoli) bílá dáma napadená pěšcem? Snadná odpověď:

bile_damy & napadeno_cernym_pescem;

Nebo snad raději volná políčka?

~kameny;

Výhoda bitových polí vynikne na 64 bitové architektuře, tam je tohle všechno jediná a navíc jednoduchá instrukce. Zároveň je zřejmé, že některé rutiny budou vypadat zcela jinak než na šachovnici 8x8 nebo 10x12. V generátoru tahů nebudeme v cyklu procházet políčka šachovnice, ale pro každý typ kamene v cyklu jedničkové bity jejího bitového pole. Pro nalezený kámen (dejme tomu Jg1) můžeme vygenerovat všechna cílová políčka hromadně opět jediným jednoduchým příkazem

u64 tahy_jezdce_g1 = tahy_jezdce[g1] & ~bile_kameny;

stačí mít (jednou na začátku programu) předdefinované pole tahy_jezdce s 64 64-bitovými konstantami reprezentujícími možná cílová pole jezdce.

Všem zájemcům o bitová pole bych doporučil ke studiu zdrojový kód programu Crafty. Je vidět, že s bitovými poli lze neuvěřitelně a hlavně neuvěřitelně efektivně kouzlit. Na druhou stranu pro začátečníka nebo programátora zvyklého na šachovnici 8x8 a 10x12 mohou být některé postupy dost neočekávané a kód na první pohled nečitelný. Přiznám se, že prvních pět minut studia kódu generátoru napsaného nad bitovým polem jsem chápal, že vůbec jde o šachy, pouze díky názvům identifikátorů a komentářům. Rozhodně bych bitová pole doporučil lidem, kteří to se šachovým programováním myslí vážně, ale už ne třeba studentům, kteří chtějí za víkend napsat zápočtový program na hledání matu druhým tahem.

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

V přištím dílu si řekneme něco o zásobníku tahů a počítání s pseudolegálními tahy.

Verze pro tisk

pridej.cz

 

DISKUZE

Nejsou žádné diskuzní příspěvky u dané položky.



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

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

18.6.2018 0:43 /František Kučera
Červnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 21. 6. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: F-Droid, aneb svobodný software do vašeho mobilu. Kromě toho budou k vidění i vývojové desky HiFive1 se svobodným/otevřeným čipem RISC-V.
Přidat komentář

23.5.2018 20:55 /Ondřej Čečák
Od pátku 25.5. proběhne na Fakultě informačních technologií ČVUT v Praze openSUSE Conference. Můžete se těšit na spostu zajímavých přednášek, workshopů a také na Release Party nového openSUSE leap 15.0. V na stejném místě proběhne v sobotu 26.5. i seminář o bezpečnosti CryptoFest.
Přidat komentář

20.5.2018 17:45 /Redakce Linuxsoft.cz
Ve čtvrtek 31. května 2018 připravuje webový magazín BusinessIT ve spolupráci s Best Online Média s.r.o. pátý ročník odborné konference Firemní informační systémy 2018. Akce proběhne v kongresovém centru Vavruška (palác Charitas), Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 15 hod. odpoledne. Konference je zaměřena na efektivní využití firemních informačních systémů a na to, jak plně využít jejich potenciál. Podrobnější informace na webových stránkách konfrence.
Přidat komentář

14.5.2018 7:28 /František Kučera
Květnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 17. 5. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: Audio – zvuk v GNU/Linuxu.
Přidat komentář

7.5.2018 16:20 /František Kučera
Na stránkách spolku OpenAlt vyšla fotoreportáž Pražské srazy 2017 dokumentující srazy za uplynulý rok. Květnový pražský sraz na téma audio se bude konat 17. 5. 2018 (místo a čas ještě upřesníme).
Přidat komentář

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

16.3.2018 22:01 /František Kučera
Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář

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

> Poslední diskuze

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

Více ...

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