| Abstrakt: | Algoritmus na prehľadávanie herného stromu založený na alfa-beta osekávaní
a intenzívnom používaní transpozičnej tabuľky je ukážkovým príkladom ťažko
paralelizovateľného algoritmu. Pri rozdeľovaní jeho prehľadávacieho priestoru na
podproblémy, ktoré je možné riešiť paralelne, sa spravidla nevyhneme tomu, aby
procesory nevykonávali zbytočné, duplicitné výpočty. Pri jednoduchých metódach
rozdeľovania je ich množstvo často tak veľké, že úplne zatieni prínos získaný
použitím viacerých procesorov.
Je to dané jednak tým, že alfa-beta algoritmus využíva informácie získané pri
prehľadávaní predošlých častí stromu na osekávanie prehľadávania v jeho nasledujúcich
častiach. Ďalším dôvodom je skutočnosť, že iba pomerne malé percento
vrcholov v herných stromoch používaných hier sú unikátne vrcholy a veľká väčšina
vrcholov sú ich opakované výskyty. Sekvenčný algoritmus sa vie vďaka transpozičnej
tabuľke veľkému množstvu takýchto opakovaných výpočtov úspešne vyhnúť.
Vhodné rozdelenie problému na paralelne riešiteľné podproblémy a realizácia
transpozičnej tabuľky v distribuovanom systéme sú teda dva kľúčové a komplikované
problémy, ktoré treba pri návrhu paralelného algoritmu riešiť.
Náplňou tejto práce je riešenie týchto problémov, a na základe týchto riešení
navrhnutie pokročilého paralelného algoritmu, dosahujúceho uspokojivý výkon.
|
|---|