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ň.