Redukční algoritmus - porovnání programů
(Václav Kotěšovec, 21.3.2000, updated 20.12.2000)
Tato stránka obsahuje doplňující komentář k porovnání časů řešení pomocných a sériovotahových pomocných matů (programy VKSACH, ALYBADIX, POPEYE a WINCHLOE) Solving time of helpmates and seriehelpmates. K této problematice se dále vztahuje článek Hashování. Detailní popis redukčního algoritmu obsahuje část MSaP Algoritmy a metody programování, viz též A guide for English-speaking readers
V případě úloh s proměnami černých pěšců dosahuje VKSACH výrazně lepších časů (příklad h#10 nebo příklad h#8). V případě sériovotahových úloh jsou rozdíly ještě výraznější (příklad sh#25 nebo příklad sh#20). Příčinou je pravděpodobně optimalizace výběru obrazců, viz Mezi šachovnicí a počítačem (1996), strana 260. Jde tu hlavně o to, že u blokujících černých kamenů se program nespokojí jen s faktem blokování (jak to asi dělají POPEYE a ALYBADIX), ale zkoumá, jestli tento černý kámen nemůže přímo zabránit matu. Pokud ano, obrazec se neuvažuje.
Naopak VKSACH má větší problémy s úlohami s možnými proměnami bílých pěšců (příklad h#7). Takové skladby jsou silnou stránkou programu POPEYE (příklad h#6).
Co se týče programu POPEYE jsem zjistil zajímavou věc. Pokud používáme "intelligent mode", je lepší nepoužívat parametr maxmem. Při předdefinovaných 2MB je v tomto případě více jak 2x rychlejší než při použití -maxmem 100M ! Nevím přesně čím je to způsobeno (možná zbytečným nulováním celé paměti s každým obrazcem ?!) Samozřejmě bez intelligent mode je lépe dát programu co nejvíce paměti pro hashování.
Program WINCHLOE (jak lze usuzovat podle zobrazení probíraných obrazců na druhé šachovnici) provádí také optimalizaci výběru obrazců a je velmi dobrý v úlohách zhruba do 7 tahů. Při větších délkách ale poněkud "ztrácí dech". Intelligent mode je implementován jen v DOSovém modulu volaném z WINCHLOE a tam není použito hashování. Naopak při řešení pod Windows lze využít paměť pro hashování, ale nelze zde použít "intelligent mode". Kombinace by zřejmě hodně pomohla u delších úloh. Je k tomu ještě možno poznamenat, že VKSACH sice také nepoužívá hashování, ale dost se mu blíží S-algoritmus (unique order of moves, see Algoritmy a metody programování), který v kombinaci s redukčním algoritmem značně urychluje řešení zejména delších úloh, speciálně sériovotahových.
Jsou v principu 2 metody, jak používat redukční algoritmus
1) Nejprve, tj. v základní pozici úlohy generovat všechny možné obrazce a do těch pak hledat cestu (tak to dělá VKSACH a asi i WINCHLOE). Jak ukazují výsledky, v případě sh#n je tato metoda vždy lepší.
2) Volat redukční algoritmus po každém tahu (tak to asi dělají POPEYE a ALYBADIX - intelligent mode). Tato metoda je podle mě obecně horší, protože novým generováním obrazců po každém tahu se ztrácí spousta času. Ovšem v úlohách s možnými proměnami bílých pěšců může být tato metoda účinnější, protože se po provedení tahu jiným bílým kamenem eliminuje množství obrazců s proměnami bílých pěšců, které bylo nutné ze základní pozice uvažovat.
Nejlépe by bylo obě metody nějak (?) kombinovat.
Silnou stránkou ALYBADIXu je metoda hrubé síly a hashování. Při použití "intelligent mode" je rychlejší jen v těch úlohách, kde tato optimalizace selhává (pozice kde nemá černý král žádné volné pole, spousta materiálu apod.) (příklad h#4)
Použití "intelligent mode" u patů (h=n a sh=n) je spíše symbolické. Použít se dá smysluplně jen pokud má černý jen samotného krále, příp. ještě maximálně 1-2 kameny. Jinak to není v žádném ze všech 4 programů nijak optimalizováno (je těžké na paty něco vymyslet). Zatímco u matových úloh stačí generovat obrazce pouze pro černého krále (a pokrytí jeho 9 polí), u patů by se musely "obrazce" generovat také pro všechny ostatní černé kameny a není vůbec jasné jak. U matů je pozice ostatních kamenů libovolná - mohou se podílet na obrazci (černé pouze blokováním pole), ale také nemusí.