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

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