Tomas Oberhuber's Homepage

Vylepšení pro sekvenční verzi

Tak, jako se řeší hledání nejkratší cesty přechodem na hledání do šířky, i u šachových programů je možno najít podobné způsoby, jak sekvenční výpočet urychlit. Zde jde o iterativní hlednání do hloubky (známé v případě šachů i jako pyramidové hledání). Další přístup, který s předchozím souvisí a vzájemně se kombinují, je apriorní odhad hodnot alfa a beta. Je dobré zdůraznit, že na rozdíl od hledání do šířky v případě hledání nejkratší cesty, jsou oba uvedené přístupy heuristické, a není tedy zaručeno jejich stoprocentní fungování. Na druhou stranu je třeba uvést, že v praxi jednak dobře fungují, jednak je jejich použití možno upravit tak, aby fungovaly neheuristicky“, stoprocentně (za cenu možné delší doby výpočtu – jde ovšem o výjimečné případy; je totiž možné poznat, kdy heuristika selže a algoritmus se tak (s volněji zvolenými parametry) může restartovat). Navíc i každá hodnotící funkce je vlastně heuristickým prvkem, takže v šachu se bez heuristik tak jako tak neobejdeme.

Vylepšení pro paralelní verzi

Možná vylepšení paralelní verze bych rozdělil do tří oblastí:

1. implementace jemnějšího rozdělení tasků tak, aby počet procesů nebyl omezen počtem možných tahů u počáteční pozice. Jde o ,,pouhou“, zato složitou technikálii
2. komunikace (odesílání a přijímaní zpráv) se v aktuální verzi děje jen v „taktech v prvním patře stromu“ - tj. než proces započne resp. potom co dokončí prohledávání nějakého počátečního tahu. Odesílání zpráv je nutné provádět právě na této úrovni, ale přijmout aktualizovanou hodnotu parametru lze v podstatě kdekoli uvnitř stromu a lze očekávat, že to hledání urychlí.
3. oba výše uvedené body lze kombinovat a lze je zkombinovat i s uvedeným vylepšením pro sekvenční verzi. Vzhledem k lepší přehlednosti kódu i myšlenkových konstruktů je zde ale zřejmě nutné zvážit přechod na model komunikace master-slave. I když pyramidovým prohledáváním se ,,efekt hledání do hloubky“ sníží, přesto je jistě možné očekávat občasnou hodnotu efektivity paralelizace větší než jedna (záleží na zvláštnostech výchozí pozice). I v průměru lze ovšem očekávám vysokou efektivitu, i když zřejmě už menší než jedna.