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

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ů

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

27.8.2016 8:55 /Delujek
Dnes po 4 letech komunitního vývoje vyšla diaspora 0.6.0.0
diaspora* je open-source, distribuovaná sociální síť s důrazem na soukromý
Více v oficiálním blog-postu
Přidat komentář

24.8.2016 6:44 /Ondřej Čečák
Poslední týden CFP LinuxDays 2016; pokud byste rádi přednášeli na LinuxDays 2016 8. a 9. října v Praze, můžete svůj příspěvek přihlásit, následovat bude veřejné hlasování.
Přidat komentář

9.8.2016 22:56 /Petr Ježek
Zařazení souborového systému reiser4 do jádra 4.7 znamená konečně konec patchování jádra jen kvůli možnosti použít reiser4.
Přidat komentář

12.7.2016 13:14 /František Kučera
Spolek OpenAlt zve na 130. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 21. července od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

11.7.2016 16:53 /Redakce Linuxsoft.cz
Konference LinuxDays hledá přednášející. Přihlášky poběží do konce prázdnin, v září bude hlasování a program. Více na https://www.linuxdays.cz/2016/cfp/.
Přidat komentář

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

> Poslední diskuze

10.12.2016 11:01 / jeorge
kitchen designer

7.12.2016 8:10 / Hamon
scottish cottages

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

9.11.2016 7:42 / Mane
hardwood floor waxing

8.11.2016 13:38 / Mira
Konfigurace maldet na Centos serveru

Více ...

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