Experiments with Monte-Carlo Tree Search in the Game of Havannah

Article type: Research Article

Authors: Lorentz, Richard J.¹

Affiliations: Northridge, USA

Note: [1] Department of Computer Science, California State University, Northridge CA 91330-8281 USA, email: lorentz@csun.edu

Note: [2] This is a fully revised and expanded version of work originally presented at CG 2010 (see Lorentz, 2011). Emphasis has shifted to larger board sizes. All experiments have been redone to reflect the larger board sizes, to correct some design flaws in the original conference work, and to include more samples for each test. Also, the discussion of the transposition tables is new.

Abstract: Havannah is a game played on an hexagonal board of hexagons where the base of the board typically ranges from four to ten hexagons. The game is known to be difficult to program. We study an MCTS-based approach to programming Havannah using our program named WANDERER. We experiment with six enhancements of the basic MCTS algorithms and discover which are most useful for improving WANDERER. At normal time controls of approximately 30 seconds per move WANDERER can make quite strong moves with bases of size four or five, and play a reasonable game with bases of size six or seven. At longer time controls (ten minutes per move) WANDERER (1) appears to play nearly perfectly with base four, (2) is difficult for most humans to beat at base five, and (3) gives a good game at bases six and seven.2

DOI: 10.3233/ICG-2011-34303

Journal: ICGA Journal, vol. 34, no. 3, pp. 140-149, 2011