Havannah, a Monte Carlo approach

Includes bibliographical references (pages 69-70)This paper describes how the Monte Carlo Tree Search (MCTS) algorithm approach is used to implement a computer engine to play the board game known as Havannah, a game that has recently sparked interest in the artificial intelligence gaming community. A very simple approach using the MCTS is described with a slight variation to improve how memory is managed when building the Monte Carlo Tree. A few other improvements are also discussed as future considerations such as threading and memory management to further improve efficiency of how the Monte Carlo tree is generated.\ud The Havannah engine described was given the name of Wanderer and it was one of two that participated in the 2009 Computer Olympiads held in Spain. Its source code has remained private only to be used as part of research conducted by the California State University, Northridge Computer Science department graduate students. Since its inception, the source code has gone through several iterations but this paper describes the initial development which was aimed to check the feasibility of this algorithm with this type of board game. The MCTS has already been successfully used in different board games with the same style of play as the Havannah board game where connection of played points is required to win the game such as Go and Hex [8]. The computer engine that was developed to test the feasibility of the MCTS in Havannah was named Wanderer as it represents moves on the board that together form a destination. The programming language used was C++ as efficiency and optimization was required in order to fully test the computer engine???s capabilities. Through much refining and optimization of the code an initial version of Wanderer???s capabilities were tested during a programming competition held in Spain. Wanderer proved to be a strong competitor and took the winning spot proving that implementing this board game with a MCTS is feasible. Through testing and hands on experience playing with Wanderer, I can conclude that Havannah, just like other board games where similar algorithms have been used, was a perfect candidate for the Monte Carlo Tree Search algorithm