Usage
  • 61 views
  • 43 downloads

Playing and Solving Havannah

  • Author / Creator
    Ewalds, Timo V
  • 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.

  • Subjects / Keywords
  • Graduation date
    2012-06
  • Type of Item
    Thesis
  • Degree
    Master of Science
  • DOI
    https://doi.org/10.7939/R3DG6P
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
    English
  • Institution
    University of Alberta
  • Degree level
    Master's
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Jonathan Schaeffer (Computing Science)
    • Ryan Hayward (Computing Science)
  • Examining committee members and their departments
    • Mazi Shirvani (Mathematics)
    • Martin Mueller (Computing Science)