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

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ů

18.6.2018 0:43 /František Kučera
Červnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 21. 6. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: F-Droid, aneb svobodný software do vašeho mobilu. Kromě toho budou k vidění i vývojové desky HiFive1 se svobodným/otevřeným čipem RISC-V.
Přidat komentář

23.5.2018 20:55 /Ondřej Čečák
Od pátku 25.5. proběhne na Fakultě informačních technologií ČVUT v Praze openSUSE Conference. Můžete se těšit na spostu zajímavých přednášek, workshopů a také na Release Party nového openSUSE leap 15.0. V na stejném místě proběhne v sobotu 26.5. i seminář o bezpečnosti CryptoFest.
Přidat komentář

20.5.2018 17:45 /Redakce Linuxsoft.cz
Ve čtvrtek 31. května 2018 připravuje webový magazín BusinessIT ve spolupráci s Best Online Média s.r.o. pátý ročník odborné konference Firemní informační systémy 2018. Akce proběhne v kongresovém centru Vavruška (palác Charitas), Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 15 hod. odpoledne. Konference je zaměřena na efektivní využití firemních informačních systémů a na to, jak plně využít jejich potenciál. Podrobnější informace na webových stránkách konfrence.
Přidat komentář

14.5.2018 7:28 /František Kučera
Květnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 17. 5. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: Audio – zvuk v GNU/Linuxu.
Přidat komentář

7.5.2018 16:20 /František Kučera
Na stránkách spolku OpenAlt vyšla fotoreportáž Pražské srazy 2017 dokumentující srazy za uplynulý rok. Květnový pražský sraz na téma audio se bude konat 17. 5. 2018 (místo a čas ještě upřesníme).
Přidat komentář

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

16.3.2018 22:01 /František Kučera
Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář

13.2.2018 0:41 /František Kučera
Únorový pražský sraz OpenAltu se koná 15. 2. 2018 a tentokrát se vydáme na návštěvu do jednoho pražského datacentra. Sejdeme se v 17:50 v severovýchodní části nástupiště tramvajové zastávky Koh-I-Noor. Po exkurzi se přesuneme do restaurace U Pštrosa (Moskevská 49), kde probereme tradiční témata (svobodný software a hardware, DIY, CNC, SDR, 3D tisk…) a tentokrát bude k vidění i IoT brána od The Things Network.
Přidat komentář

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

> Poslední diskuze

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

Více ...

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