- Playing and Solving Havannah
- Ewalds, Timo V
Monte-Carlo Tree Search
- Dec 21, 2011 2:56 PM
- Adobe PDF
- 813802 bytes
- Havannah is a recent game that is interesting from an AI research perspective. Some of its properties, including virtual connections, frames, dead cells, draws and races to win, are explained. Monte Carlo Tree Search (MCTS) is well suited to play Havannah, but many improvements are possible. Several forms of heuristic knowledge in the tree show playing strength gains, and a change to the rules in the rollout policy significantly improves play on larger board sizes. Together, a greater than 80 winning rate, or 300 elo gain, is achieved on all board sizes over an already fairly strong player. This MCTS player is augmented with a few engineering improvements, such as threading, memory management and early draw detection, and then used to solve all 6 openings of size 4 Havannah, a game with a state space on the order of 6x10^15 states. Castro, the implementation and test bed, is released open source.
- Master of Science
- Department of Computing Science
- Spring 2012
Jonathan Schaeffer (Computing Science)
Ryan Hayward (Computing Science)
Martin Mueller (Computing Science)
Mazi Shirvani (Mathematics)
Theses and Dissertations Spring 2009 to present
Department of Computing Science
Delete your item from era
Do you really want to delete "Playing and Solving Havannah" ?
Resotre your item to era
Do you really want to restore "Playing and Solving Havannah" ?
Purge your item from era
Do you really want to permanently delete "Playing and Solving Havannah" ?
Remove your item from era
Do you really want to remove "Playing and Solving Havannah" ?