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

> Šachové myšlení (7) - Haš tabulky

Dvě různé varianty mohou vést ke stejné pozici. Ukážeme si, jak zařídit, aby šachový program tyto pozice počítal jen jednou.

15.2.2007 06:00 | Jan Němec | Články autora | přečteno 9723×

Haš tabulky

V dílech o alfabeta metodě a jejích vylepšeních jsme se snažili zrychlit propočet pomocí ořezání. Třídili jsme tahy podle jejich očekávané kvality a svírali interval (alfa, beta), jak to jen šlo, abychom odřízli propočet variant, které nemohou ovlivnit výběr tahu z úvodní pozice. Existuje ovšem ještě zcela jiný druh variant, jejichž propočet si můžeme ušetřit. Jde o dvojice variant, které se od sebe liší pouhým prohozením tahů. Pokud program počítá nejlepší tah ze základního postavení do hloubky 5 půltahů, nevynechá ani variantu 1. e4 c5 2. Jf3 a musí ji propočítat ještě do zbývající hloubky 2 půltahy. Zcela stejný propočet by přitom následoval i ve variantě 1. Jf3 c5 2. e4. Je přitom zřejmé, že vzniklou pozici stačí zkoumat jen jednou.

V zahájení a střední hře se spoustou figur na šachovnici, velkým množstvím tahů z pozice, a tedy i malou hloubkou propočtu, dochází k podobným duplicitám ještě poměrně zřídka, mnohem horší je situace v koncovkách s malým počtem figur. Typickým příkladem je koncovka dvou králů, v níž mají obě strany už jen několik zablokovaných pěšců. Král se obvykle snaží vytlačit soupeřova monarchu (obvykle i s využitím nevýhody tahu), pobrat soupeřovy pěšce a prosadit ty své do dámy. Obě strany přitom mají na výběr jen několik málo přípustných tahů, a tak hloubka propočtu roste oproti střední hře i dvojnásobně. Při podobných hlubokých propočtech dochází k opakovanému vyhodnocování jedné varianty vzniklé jen přehozením tahů zcela běžně. Právě v podobných typech pozic přitom může mít počítač s lidským soupeřem problémy. Jednoduchý charakter pozice totiž umožní lépe oprostit plán výhry nebo obrany od detailního propočtu (případně lidský propočet degeneruje na jedinou, ale zato dlouhou variantu bez větvení) a umožní vidět mnohem dál i člověku.

Řešením je přímočaré. Výsledky jednotlivých propočtů si budeme pamatovat v nějaké datové struktuře a před zahájením každého rekurzivního propočtu se napřed do této struktury podíváme. Pokud uspějeme, místo nového propočtu okamžitě vrátíme zapamatovanou hodnotu. Vypadá to na první pohled velmi jednoduše a ono to i jednoduché je, přesto je třeba dát na některé věci pozor, trochu se zamyslet a neimplementovat během několika vteřin s pomocí standardní knihovny mapu pozice na integer.

Pokud má naše struktura fungovat efektivně a nezpůsobit víc škody než užitku, musíme vzít na vědomí následující fakta:

  • Ukládat je třeba i hloubku propočtu, neboť nelze nahradit propočet výsledkem předchozího propočtu do menší hloubky.
  • Alfabeta metoda nedává jen mezivýsledky typu pozice má cenu = +3, ale i pozice má cenu <= +3 nebo >= +3. I tyto mezivýsledky si budeme pamatovat a využívat je.
  • Musíme pracovat velmi rychle s velkým množstvím dat.
  • Program by neměl číst z disku, struktura se musí za každou cenu vejít do paměti.
  • Je lepší, když struktura zapomíná, než kdyby swapovala.
  • Pozice obsahuje 64 polí a stavovou informaci o tahu, právu na rošády a braní mimochodem, ale jeden záznam ve struktuře by měl mít jen několik bytů.

Výše uvedené požadavky jsou poměrně specifické, knihovní datové struktury, jaké najdeme například v Javě nebo C++ STL nám rozhodně vyhovovat nebudou. Raději si sami naimplementujeme haš tabulku v běžném céčkovském poli.

Hašování obecně řeší problém ukládání objektů se složitějším klíčem do pole. V našem případě je klíčem pozice, objektem pak informace o výsledku výpočtu, tedy hloubka, cena a příznak, zda se nejedná jen o dolní nebo horní odhad. Především je třeba každému klíči přiřadit index v poli. Definujeme tedy hašovací funkci z množiny všech klíčů do {0, 1, 2, ... N - 1}, kde N je velikost pole. Uložení do haš tabulky spočívá v nakopírování objektu do pole na příslušný index. Při čtení z haš tabulek postupujeme obdobně, i zde nám index pole určí stejná hašovací funkce klíče.

Velkým problémem hašování jsou kolize. Dva různé klíče mohou mít stejnou hodnotu funkce a tedy i stejný index v poli. Existují různé metody hašování šité na míru různým aplikacím, ale obecně platí, že kolize jsou jevem negativním, který se snažíme vhodnou velikostí tabulky a návrhem hašovací funkce co nejvíce omezit. Pokud hašujeme dostatečně malou a předem známou množinu dat a můžeme haš funkci navrhnout této množině na míru, lze se kolizím zcela vyhnout. To ovšem není náš případ, šachových pozic je mnohonásobně víc než velikost haš tabulky a předem nevíme, které z nich v propočtu navštívíme. Ke kolizím tedy docházet bude. Jednotlivé haš metody se s kolizemi vypořádávají různým způsobem: vytvářejí v poli na místě kolize malou datovou strukturu (například spojový seznam), zkoušejí data zahašovat do tabulky o něco dál a podobně, ale tyto metody jsou pro nás zbytečně komplikované, mohou vést k dalším alokacím paměti nad původní velikost tabulky, případně jsou příliš pomalé.

Naštěstí nepotřebujeme 100% řešení, a tak kolize budeme ignorovat. Nová nebo cennější hodnota v tabulce prostě přepíše starou nebo méně cennou. Máme aspoň o starost méně, nemusíme řešit problémy s pamětí, neboť tabulka bude po celou dobu stejně velká bez ohledu na to, kolik v ní skutečně je uloženo hodnot a ke kolika kolizím došlo. Běžný program za 1 vteřinu může vyhodnotit na dnešních rychlých počítačích asi milion pozic za vteřinu a pro každou uloží do tabulky 8 bytů, generuje tady zhruba 8 MB za vteřinu propočtu. Kdybychom si pamatovali výsledky v nějaké datové struktuře bez zapomínání, paměť by mohla dojít. Vše závisí na poměru mezi množstvím dostupné pamětí, rychlostí (programu i počítače) a dobou přemýšlení. Pokud má program krátký čas na přemýšlení, hodně přidělené paměti a je pomalý, nejlepší je v případě kolize haš funkce pokaždé přepsat starou hodnotu novou. To je asi typický případ pro dnešní hardwarovou sestavu a běžné využití šachového programu. Je-li tomu naopak a máme paměti kritický nedostatek (například mnoho procesů na jednom stroji, program má přemýšlet měsíc, reálný režim MS DOS :-), ...), bude lepší přepisovat starou hodnotu pouze pokud je nová hodnota výsledkem propočtu do stejné nebo větší hloubky.

Co přesně budeme do tabulky ukládat? Měli bychom maximálně šetřit místem a vejít se do 8 bytů. Bohužel C nezná typy s pevně definovanou velikostí (a Java zase neumožňuje definovat, zda je číslo se znaménkem), proto zavedu vlastní typy, kde s znamená signed a u unsigned a následuje velikost v bitech. Na dnešních běžných platformách bychom v C využili signed short, unsigned char a unsigned int.

typedef struct {
  s16 cena;   /* cena pozice */
  u8 hloubka; /* hloubka propočtu */
  u8 priznak; /* xxxxxxHD
                 D - pozice je stejná nebo lepší než cena
                 H - pozice je stejná nebo horší než cena
                 (=> H & D - pozice má přesně danou hodnotu) */
  u32 kod;    /* G haš funkce pozice */
} HashPrvek;

Především musíme ukládat cenu pozice. Ta by se měla vejít do 16 bitového čísla se znaménkem, tedy s16. Kdy smíme tuto hodnotu z tabulky využít nám říká osmibitová hloubka propočtu a příznak, zda se jedná o dolní či horní odhad v alfabeta propočtu nebo o přesnou hodnotu tj. vlastně horní i dolní odhad zároveň. Poslední 32 bitové číslo je zde kvůli kolizím. Může se stát, že 2 různé pozice - jedna, jejíž propočet je uložen v tabulce a druhá, kterou v tabulce hledáme, abychom se vyhnuli výpočtu - mají stejnou hodnotu haš funkce, a tedy i stejné políčko v tabulce. Tyto případy musíme nějak detekovat, ve výpočtu k nim bude docházet poměrně často. Správně bychom měli do tabulky ukládat kvůli této kontrole i pozici, ale na to není čas ani místo. V nekomprimovaném tvaru může mít pozice kolem 70 bytů (64 polí + nějaké drobné na právo tahu, práva rošád a braní mimochodem), což je příliš mnoho. Na nějakou komprimaci není čas, navíc ani kvalitní bezztrátová komprese by velikost nezredukovala dostatečně tj. na několik bytů.

Jak tedy budeme pozice identifikovat? Pomůžeme si druhou hašovací funkcí. Pokud definujeme 2 různé hašovací funkce F a G, které mají na vstupu pozici a vracejí u32 a tabulku velikosti N, výsledek pozice P budeme ukládat do tabulky na pozici F(P) mod N (mod - zbytek po celočíselném dělení) a kontrolním kódem bude G(P). Načíst a použít hodnotu z tabulky místo propočtu můžeme pouze při stejném kontrolním kódu. Problém se tím nevyřeší, pouze se stane méně pravděpodobným. Co když pro dvě různé pozice P1 a P2 platí, že F(P1) mod N = F(P2) mod N a zároveň G(P1) = G(P2)? Programátoři i těch nejsilnějších programů obvykle prostě jen doufají, že k tomu bude docházet dostatečně zřídka. Při správném návrhu funkcí F a G a haš tabulce zcela zaplněné cizími pozicemi je pravděpodobnost shody při jednom dotazu 2-32. Program probírající milion pozic za vteřinu by se tedy měl stát obětí kolize méně než jednou za hodinu výpočtu. Část falešných hodnot načtených kvůli kolizím nebude použita kvůli příznaku nebo malé hloubce, velká většina ostatních případů vůbec neovlivní výsledek propočtu. Mohou třeba jen označit špatný tah za ještě horší nebo ke kolizi dojde ve variantě, kterou alfabeta metoda nějakým způsobem zahodí. Zcela výjimečně pak dojde k malé tragedii a program prostě zahraje hrubou chybu. Pokud se s tím nechceme smířit, použijeme 64 bitovou haš funkci G, ke kolizi pak dojde zhruba jednou za 600 000 let výpočtu.

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

V příštím dílu si řekneme, jak navrhnout hašovací funkce F a G tak, aby byly dostatečně rychlé a kvalitní zároveň.

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ů

14.11.2017 16:56 /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 – tradičně první čtvrtek před třetím pátkem v měsíci: 16. listopadu od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.11.2017 11:06 /Redakce Linuxsoft.cz
PR: 4. ročník odborné IT konference na téma Datová centra pro business proběhne již ve čtvrtek 23. listopadu 2017 v konferenčním centru Vavruška, v paláci Charitas, Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00. Konference o návrhu, budování, správě a efektivním využívání datových center nabídne odpovědi na aktuální a často řešené otázky, např Jaké jsou aktuální trendy v oblasti datových center a jak je využít pro vlastní prospěch? Jak zajistit pro firmu či jinou organizaci odpovídající služby datových center? Podle jakých kritérií vybrat dodavatele služeb? Jak volit součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně spravovat datové centrum? Jak eliminovat možná rizika? apod.
Přidat komentář

13.9.2017 8:00 /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 – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

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

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

> Poslední diskuze

5.12.2017 11:50 / Thomas
kitchen renovations

18.9.2017 14:37 / Rojas
high security vault

15.9.2017 7:33 / Wilson
new zealand childcare jobs

31.8.2017 12:11 / Jaromir Obr
Re: ukůládání dat ze souboru

30.7.2017 11:12 / Jaromir Obr
Národní znaky

Více ...

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