Original title:
PNS for the game Arimaa
Translated title:
PNS for the game Arimaa
Authors:
Majerech, Ondřej ; Hric, Jan (advisor) ; Valla, Tomáš (referee) Document type: Bachelor's theses
Year:
2012
Language:
eng Abstract:
[eng][cze] The game of Arimaa is a strategic board game that has proved to be a challenge to computers. Not only because of its huge branching factor, but also thanks to the difficulty in creating a good evaluation function to be used with the Alpha-Beta algorithm. Proof-Number Search is an algorithm that does not depend on a heuristic evaluation function and it has been successfully applied to solving endgames of various other games. In this work, we adapt and implement the Proof-Number Search method for the game of Arimaa.Arimaa je strategická desková hra, kterou se stále počítačům nepovedlo pokořit. Problematický je zejména velký větvící faktor stromu hry a celková její charakteristika, díky které je obtížné sestrojit vhodnou ohodnocovací heuristiku pro alfa-beta prohledávání. Proof-Number Search je algoritmus nezávislý na dobré ohodnocovací heuristice, který byl již úspěšně použit na řešení koncovek jiných deskových her. V této práci jsme adaptovali a implementovali algoritmus Proof-Number Search pro hru Arimaa.
Keywords:
Arimaa; artificial intelligence; endgames; Proof-Number Search; Arimaa; koncovky her; Proof-Number Search; umělá inteligence
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/40300