ERA Banner
Download Add to Cart Share
More Like This
  • http://hdl.handle.net/10402/era.24886
  • Playing and Solving Havannah
  • Ewalds, Timo V
  • English
  • Havannah
    MCTS
    Monte-Carlo Tree Search
    Monte-Carlo
    Games
    solving games
    board games
    computer games
    artificial intelligence
    AI
    rave
  • Dec 21, 2011 2:56 PM
  • Thesis
  • English
  • 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's
  • Master of Science
  • Department of Computing Science
  • Spring 2012
  • Jonathan Schaeffer (Computing Science)
    Ryan Hayward (Computing Science)
  • Martin Mueller (Computing Science)
    Mazi Shirvani (Mathematics)