LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

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

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ů

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

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?

20.9.2018 10:04 / Jan Ober
Jaký kurz a software by jste doporučili pro začínajcího kodéra?

20.9.2018 10:00 / Jan Ober
Re: Gimp

Více ...

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