Hashování
(Václav Kotěšovec, 17.3.2000, updated 15.12.2000)
Princip "hashování" spočívá v tom, že program průběžně ukládá do paměti pozice, které již zkoumal s informací o výsledku (obvykle počet tahů). V průběhu řešení se pak vždy nejprve podívá do této paměti, zda se pozicí již předtím nezabýval. Pokud ano, použije dříve zjištěnou informaci a vrací se na původní úroveň řešení. Pokud pozice v paměti ještě uložena není, pokračuje v analýze do dalších úrovní.
VKSACH nepoužívá hashování (v době jeho vzniku se o dnešních velikostech paměti RAM nikomu ani nesnilo). Programy ALYBADIX, POPEYE a WINCHLOE používají hashování dané velikostí dostupné paměti RAM. Nazval bych to sekvenční hashování podle klíče. Do paměti jsou ukládány pozice s informací v kolika tazích byla zkoumána (většinou, že je v tomto počtu tahů neřešitelná).
Velikost jedné položky je dána počtem kamenů plus délkou doplňující informace (obvykle stačí 1 byte). Data mohou být i komprimována, ale např. při paměti RAM 32 MB a úloze s 20 kameny se do této paměti vejde informace o cca 1600000 prozkoumaných pozicích.
Vlastní prohledávání je urychleno rozdělením těchto pozic podle klíčů (např. pozice králů apod.). Díky těmto podadresářům je čas na vyhledání pozice zhruba O(log(p)) a ne O(p), jak by tomu bylo při sekvenčním prohledávání (a čas vyhledání by tak mohl být absurdně i delší než přímý výpočet).
ALYBADIX má navíc jednu užitečnou vlastnost, tzv. "EverTree". Může si zapamatovat "tree" od předchozí úlohy (tzn. že v tomto případě nenuluje paměť s novým řešením), což se dá využít např. při testování dvojníků nebo při vlastním skládání.
Zásadní problém nastává při zaplnění dostupné paměti (to nastane u vícetahových úloh od určitého počtu tahů vždy!). Potom se musí některé hodnoty "obětovat", uvolnit část paměti a pokračovat dále. ALYBADIX takto např. při "pruning" ponechá čtvrtinu "nejcennějších" informací (měly by to být ty, které je výpočetně náročnější obnovit) a zbytek je volný pro nové pozice. Při nutnosti častého opakování tohoto postupu se metoda stává neefektivní.
Zmínka v textu, že v současné době lze přezkoušet prakticky každý h#n nebyla nijak přehnaná. Důkazem mohou být časy řešení nejdelšího ortodoxního pomocného matu (300 MHz):
ALYBADIX 35 sec
POPEYE 4 min 48 sec
WINCHLOE 12 min 32 sec
VKSACH několik hodin (bez hashování)
Popeye WIN32-Version 3.61 (97 MB)
Bernhard Hegermann
1511 The Problemist FCS 10/1934
+---a---b---c---d---e---f---g---h---+
| |
8 . . . . . . -K T 8
| |
7 . . . . -B . -B . 7
| |
6 . -B . . B . B . 6
| |
5 . B . . -B . . . 5
| |
4 . B . . B . . . 4
| |
3 . B . . -B . -B . 3
| |
2 . . . . B . B . 2
| |
1 . . . . . L K . 1
| |
+---a---b---c---d---e---f---g---h---+
h#28 11 + 7
1.Kg8*h8 Kg1-h1 2.Kh8-g8 Kh1-g1 3.Kg8-f8 Kg1-h1 4.Kf8-e8 Kh1-g1 5.Ke8-d8 Kg1-h1 6.Kd8-c7 Kh1-g1 7.Kc7-d6 Kg1-h1 8.Kd6*e6 Kh1-g1 9.Ke6-f6 Kg1-h1 10.Kf6-g5 Kh1-g1 11.Kg5-f4 Kg1-h1 12.Kf4*e4 Kh1-g1 13.Ke4-d4 Kg1-h1 14.Kd4-c3 Kh1-g1 15.Kc3*b3 Kg1-h1 16.Kb3*b4 Kh1-g1 17.Kb4*b5 Kg1-h1 18.Kb5-c4 Kh1-g1 19.b6-b5 Kg1-h1 20.b5-b4 Kh1-g1 21.b4-b3 Kg1-h1 22.b3-b2 Kh1-g1 23.b2-b1=D Kg1-h1 24.Db1-f5 Kh1-g1 25.Df5-f7 g6*f7 26.Kc4-c3 f7-f8=D 27.Kc3-d2 Df8-c8 28.Kd2-e1 Dc8-c1 #
Loesung beendet. Zeit = 4:48.410 m:s
ALYBADIX
White: Kg1 Vh8 Sf1 Pb3 Pb4 Pb5 Pe2 Pe4 Pe6 Pg2 Pg6
Black: Kg8 Pb6 Pe3 Pe5 Pe7 Pg3 Pg7
H#28 (11+7)
Solution:
28#
1.Kg8xh8 Kg1-h1 2.Kh8-g8 Kh1-g1 3.Kg8-f8 Kg1-h1 4.Kf8-e8 Kh1-g1
5.Ke8-d8 Kg1-h1 6.Kd8-c7 Kh1-g1 7.Kc7-d6 Kg1-h1 8.Kd6xe6 Kh1-g1
9.Ke6-f6 Kg1-h1 10.Kf6-g5 Kh1-g1 11.Kg5-f4 Kg1-h1 12.Kf4xe4 Kh1-g1
13.Ke4-d4 Kg1-h1 14.Kd4-c3 Kh1-g1 15.Kc3xb3 Kg1-h1 16.Kb3xb4 Kh1-g1
17.Kb4xb5 Kg1-h1 18.Kb5-c4 Kh1-g1 19. b6-b5 Kg1-h1 20. b5-b4 Kh1-g1
21. b4-b3 Kg1-h1 22. b3-b2 Kh1-g1 23. b2-b1D Kg1-h1 24.Db1-f5 Kh1-g1
25.Df5-f7 g6xf7 26.Kc4-c3 f7-f8D 27.Kc3-d2 Df8-c8 28.Kd2-e1 Dc8-c1 #
Time(h:m:s): 00:00:35,21 Search Depth(Plies): Max
1 variations (1/1)
Moves(All/W/B): 1326712/817224/509488
TEST: /No Setplay/All variations = Text-Board-Text
/Tree 1-0-652567E (148 MB)
Helpbadix C
Hashování 1:1
Před několika lety mě napadla velmi prostá myšlenka, použitelná v praxi zatím ale jen pro 4-5 kamenů. Neukládejme do paměti seznamy pozic, ale přiřaďme každé pozici pevnou adresu v paměti, kde bude uložena jen informace o ni. Rychlost vyhledávání je pak O(1), tedy prakticky nulová, protože se nic nemusí prohledávat (jako v případě seznamů), jen se jde vyzvednout informace přímo na dané místo v paměti, jehož adresa se určí snadno podle aktuální pozice kamenů. Tuto metodu jsem nazval "hashování 1:1" (čti: hešování jedna k jedné) a výsledky jsou skvělé.
Ve verzi VKSHASH je to ovšem použitelné jen pro 4 kamenové pozice bez pěšců (v případě h#n). S pěšci by bylo potřeba již více paměti RAM.
Na šachovnici 8x8 je v případě h#n pro každou figuru potřeba 65 adres, uvažuje se pozice na 64 polích šachovnice plus možnost, že kámen byl brán.
Pro každého pěšce (pawn) je 64*5+1 možností, u exo je třeba připočítat možné proměny na exokameny (promotions to fairy pieces).
Tak např. při úloze KP-KP by byla potřebná paměť 65*(64*5+1)*65*(64*5+1) bytů.
V případě sh#n mají černé kameny (black pieces) 65 možností
Bílé kameny (white pieces) 2 možnosti (buď zůstane na svém původním poli nebo je sebrán).
Bílý král (white king) má jen 1 možnost.
V případě CIRCE jsou pro bílé kameny 3 možnosti (ještě může být přemístěn na své původní pole).
Ovšem pro PlatzWechselCirce je počet možností 65 i pro bílé kameny.
Obecně je na šachovnici NxN pro úlohy bez pěšců potřebné množství paměti (N2+1)K, kde K je počet kamenů.
Pro 4 kameny tak stačí "jen" 17 MB, pro 5 kamenů je už potřeba více jak 1 GB paměti RAM.
Pokud má bílý (white) B kamenů a černý (black) C kamenů, je na šachovnici 8x8 potřebná paměť následující:
h#n (nebo h=n) bez pěšců 65(B+C)
sh#n (nebo sh=n) bez černých pěšců 2(B-1)*65C
sh#n CIRCE 3(B-1)*65C
a pro každého pěšce 64*(5+E)+1, kde E je počet typů exokamenů (number of different fairy pieces).
Viz též Interesting problem for testing
Příklady:
h#n 4 kameny, z toho 0 pěšců 17.02 MB (17850625)
h#n 4 kameny, z toho 1 pěšec 84 MB
h#n 4 kameny, z toho 2 pěšci 415 MB
h#n 5 kamenů, z toho 0 pěšců 1106 MB
sh#n 2 bílé kameny, 4 černé kameny (z toho 0 pěšců) 34 MB
sh#n 2 bílé kameny, 4 černé kameny (z toho 1 pěšec) 168 MB
sh#n 2 bílé kameny, 4 černé kameny (z toho 2 pěšci) 830 MB
sh#n 2 bílé kameny, 4 černé kameny (z toho 3 pěšci) 4100 MB
sh#n 5 bílých kamenů, 3 černé kameny (z toho 0 pěšců) 21 MB (1378 MB pro CIRCE)
sh#n 10 bílých kamenů, 3 černé kameny (z toho 0 pěšců) 134 MB (5155 MB pro CIRCE)
sh#n 10 bílých kamenů, 4 černé kameny (z toho 0 pěšců) 8716 MB
Výsledky:
h#45 řeší programy na 300 MHz takto:
VKSHASH (s parametrem /S2) 1 min 24 sec
POPEYE 1 min 44 sec
WINCHLOE 4 min 45 sec
ALYBADIX exokrále neumí
h#41 řeší
VKSHASH 3 min 38 sec
POPEYE (-maxmem 100000) 5 min 2 sec (ale s jen 2MB RAM už za 6 min 13 sec)
WINCHLOE 6 min 19 sec
ALYBADIX exokrále neumí
8 8 0
H#45/S2'Václav Kotěšovec,5.Pr. Pat a Mat 16/1992,Nachtreiterhüpfer Nb3_f4,royal Cc2/Nb3
CC2
NB3CG8NF4
-------*
1.Cg8-a2 Cc2-a4 2.Ca2-c4 Ca4-c2 3.Cc4-g4 Cc2-a4 4.Cg4-e4 Ca4-c2 5.Ce4-b1 Cc2-a4 6.Cb1-b4 Ca4-c4 7.Cb4-d4 Cc4-e4 8.Nb3-f5 Ce4-g6 9.Nf4-h8 Cg6-e4 10.Cd4-f4 Ce4-g4 11.Nh8-e2 Cg4-e4 12.Cf4-d4 Ce4-c4 13.Nf5-b3 Cc4-a2 14.Nb3-f5 Ca2-f2 15.Nf5-b3 Cf2-d2 16.Cd4-d1 Cd2-f2 17.Cd1-f3 Cf2-f4 18.Cf3-f5 Cf4-f6 19.Nb3-h6 Cf6-f4 20.Nh6-d4 Cf4-c4 21.Ne2-c6 Cc4-e4 22.Nc6-e2 Ce4-g6 23.Ne2-h8 Cg6-e4 24.Nd4-h6 Ce4-g6 25.Nh8-f4 Cg6-e4 26.Cf5-f3 Ce4-g4 27.Nh6-f2 Cg4-e4 28.Nf2-d6 Ce4-g4 29.Cf3-f5 Cg4-e4 30.Nd6-h4 Ce4-g6 31.Nh4-f8 Cg6-e4 32.Cf5-f3 Ce4-g4 33.Cf3-f5 Cg4-e6 34.Cf5-d7 Ce6-c8 35.Nf8-b6 Cc8-e6 36.Nb6-h3 Ce6-c8 37.Nh3-d5 Cc8-e6 38.Cd7-d4 Ce6-c4 39.Cd4-b4 Cc4-e6 40.Nf4-d8 Ce6-c4 41.Nd8-a2 Cc4-e6 42.Na2-c6 Ce6-b6 43.Nc6-a2 Cb6-b3 44.Na2-c6 Cb3-b5 45.Cb4-b6 Cb5-b7 #
Pocet reseni:00001
1:24
8 8 0
H#41/ZS2'Václav Kotěšovec,6288 feenschach 102/1991,0.1.1..._ Fers Fb1,Nachtreiterhüpfer Nd1/Ne4_ royal Nd1/Cf2
ND1
CF2FB1NE4
-------*
1. - Nd1-h3 2.Fb1-a2 Nh3-d1 3.Fa2-b3 Nd1-h3 4.Fb3-c4 Nh3-d1 5.Fc4-d5 Nd1-h3 6.Fd5-e6 Nh3-d1 7.Fe6-f5 Nd1-h3 8.Ff5-g4 Nh3-d1 9.Fg4-f3 Nd1-h3 10.Cf2-f4 Nh3-d5 11.Ff3-e2 Nd5-h3 12.Fe2-d3 Nh3-d5 13.Fd3-c4 Nd5-h3 14.Fc4-b5 Nh3-d5 15.Fb5-c6 Nd5-h3 16.Fc6-d7 Nh3-d5 17.Fd7-e6 Nd5-h3 18.Fe6-f5 Nh3-d5 19.Cf4-f6 Nd5-h7 20.Ne4-g8 Nh7-d5 21.Cf6-f4 Nd5-h3 22.Ff5-g4 Nh3-d5 23.Fg4-f3 Nd5-h3 24.Cf4-f2 Nh3-d1 25.Ff3-e4 Nd1-h3 26.Ng8-d2 Nh3-d1 27.Nd2-f6 Nd1-h3 28.Fe4-d5 Nh3-b6 29.Cf2-f7 Nb6-f4 30.Fd5-e6 Nf4-d8 31.Fe6-d7 Nd8-h6 32.Nf6-b8 Nh6-d8 33.Fd7-e6 Nd8-h6 34.Fe6-f5 Nh6-d4 35.Nb8-e2 Nd4-h6 36.Cf7-f4 Nh6-d4 37.Ne2-g6 Nd4-h6 38.Ff5-g4 Nh6-f2 39.Cf4-h4 Nf2-h6 40.Fg4-f5 Nh6-d4 41.Ff5-e6 Nd4-f8 #
Pocet reseni:00001
3:38
Popeye WIN32-Version 3.61 (97 MB)
Václav Kotěšovec
5.Pr. Pat a Mat 16/1992
+---a---b---c---d---e---f---g---h---+
| |
8 . . . . . . -G . 8
| |
7 . . . . . . . . 7
| |
6 . . . . . . . . 6
| |
5 . . . . . . . . 5
| |
4 . . . . . -NH . . 4
| |
3 . -NH . . . . . . 3
| |
2 . . G . . . . . 2
| |
1 . . . . . . . . 1
| |
+---a---b---c---d---e---f---g---h---+
h#45 1 + 3
Koeniglich b3 c2
1.Gg8-a2 kGc2-a4 2.Ga2-c4 kGa4-c2 3.Gc4-g4 kGc2-a4 4.Gg4-e4 kGa4-c2 5.Ge4-b1 kGc2-a4 6.Gb1-b4 kGa4-c4 7.Gb4-d4 kGc4-e4 8.kNHb3-f5 kGe4-g6 9.NHf4-h8 kGg6-e4 10.Gd4-f4 kGe4-g4 11.NHh8-e2 kGg4-e4 12.Gf4-d4 kGe4-c4 13.kNHf5-b3 kGc4-a2 14.kNHb3-f5 kGa2-f2 15.kNHf5-b3 kGf2-d2 16.Gd4-d1 kGd2-f2 17.Gd1-f3 kGf2-f4 18.Gf3-f5 kGf4-f6 19.kNHb3-h6 kGf6-f4 20.kNHh6-d4 kGf4-c4 21.NHe2-c6 kGc4-e4 22.NHc6-e2 kGe4-g6 23.NHe2-h8 kGg6-e4 24.kNHd4-h6 kGe4-g6 25.NHh8-f4 kGg6-e4 26.Gf5-f3 kGe4-g4 27.kNHh6-f2 kGg4-e4 28.kNHf2-d6 kGe4-g4 29.Gf3-f5 kGg4-e4 30.kNHd6-h4 kGe4-g6 31.kNHh4-f8 kGg6-e4 32.Gf5-f3 kGe4-g4 33.Gf3-f5 kGg4-e6 34.Gf5-d7 kGe6-c8 35.kNHf8-b6 kGc8-e6 36.kNHb6-h3 kGe6-c8 37.kNHh3-d5 kGc8-e6 38.Gd7-d4 kGe6-c4 39.Gd4-b4 kGc4-e6 40.NHf4-d8 kGe6-c4 41.NHd8-a2 kGc4-e6 42.NHa2-c6 kGe6-b6 43.NHc6-a2 kGb6-b3 44.NHa2-c6 kGb3-b5 45.Gb4-b6 kGb5-b7 #
Loesung beendet. Zeit = 1:44.690 m:s
Popeye WIN32-Version 3.61 (97 MB)
Václav Kotěšovec
6288 feenschach 102/1991
+---a---b---c---d---e---f---g---h---+
| |
8 . . . . . . . . 8
| |
7 . . . . . . . . 7
| |
6 . . . . . . . . 6
| |
5 . . . . . . . . 5
| |
4 . . . . -NH . . . 4
| |
3 . . . . . . . . 3
| |
2 . . . . . -G . . 2
| |
1 . -FE . NH . . . . 1
| |
+---a---b---c---d---e---f---g---h---+
h#41 1 + 3
Koeniglich f2 d1
1...kNHd1-h3 2.FEb1-a2 kNHh3-d1 3.FEa2-b3 kNHd1-h3 4.FEb3-c4 kNHh3-d1 5.FEc4-d5 kNHd1-h3 6.FEd5-e6 kNHh3-d1 7.FEe6-f5 kNHd1-h3 8.FEf5-g4 + kNHh3-d1 9.FEg4-f3 kNHd1-h3 10.kGf2-f4 kNHh3-d5 11.FEf3-e2 kNHd5-h3 12.FEe2-d3 kNHh3-d5 13.FEd3-c4 + kNHd5-h3 14.FEc4-b5 kNHh3-d5 15.FEb5-c6 + kNHd5-h3 16.FEc6-d7 kNHh3-d5 17.FEd7-e6 + kNHd5-h3 18.FEe6-f5 kNHh3-d5 19.kGf4-f6 kNHd5-h7 20.NHe4-g8 kNHh7-d5 21.kGf6-f4 kNHd5-h3 22.FEf5-g4 + kNHh3-d5 23.FEg4-f3 kNHd5-h3 24.kGf4-f2 kNHh3-d1 25.FEf3-e4 kNHd1-h3 26.NHg8-d2 kNHh3-d1 27.NHd2-f6 kNHd1-h3 28.FEe4-d5 kNHh3-b6 29.kGf2-f7 kNHb6-f4 30.FEd5-e6 kNHf4-d8 31.FEe6-d7 kNHd8-h6 32.NHf6-b8 kNHh6-d8 33.FEd7-e6 kNHd8-h6 34.FEe6-f5 kNHh6-d4 35.NHb8-e2 kNHd4-h6 36.kGf7-f4 kNHh6-d4 37.NHe2-g6 kNHd4-h6 38.FEf5-g4 kNHh6-f2 39.kGf4-h4 kNHf2-h6 40.FEg4-f5 kNHh6-d4 41.FEf5-e6 kNHd4-f8 #
Loesung beendet. Zeit = 5:02.090 m:s