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

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ů

15.5.2017 23:50 /František Kučera

Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).


Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

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

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

> Poslední diskuze

11.5.2017 23:32 / lelo
Re: Problém se správcem balíčků

11.5.2017 5:45 / davd mašek
Re: Problém se správcem balíčků

10.5.2017 22:54 / lelo
Re: Problém se správcem balíčků

10.5.2017 22:19 / davd mašek
Problém se správcem balíčků

17.4.2017 19:15 / Jakub shoop
chyba

Více ...

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