Monte Carlo Tree Search in Lines of Action

• Published in: IEEE transactions on computational intelligence and AI in games. 2010-12, Vol.2 (4), p.239-250
• Main Authors: Winands, M H M, Bjornsson, Y, Saito, J
• Format: Article
• Language: English
• Subjects: Filling; Game-tree solver; Imaging phantoms; Lines of Action (LOA); Monte Carlo tree search (MCTS); Studies
• ISSN: 1943-068X; 2475-1502; 1943-0698; 2475-1510
• DOI: 10.1109/TCIAIG.2010.2061050

The success of Monte Carlo tree search (MCTS) in many games, where αβ-based search has failed, naturally raises the question whether Monte Carlo simulations will eventually also outperform traditional game-tree search in game domains where αβ -based search is now successful. The forte of αβ-based search are highly tactical deterministic game domains with a small to moderate branching factor, where efficient yet knowledge-rich evaluation functions can be applied effectively. In this paper, we describe an MCTS-based program for playing the game Lines of Action (LOA), which is a highly tactical slow-progression game exhibiting many of the properties difficult for MCTS. The program uses an improved MCTS variant that allows it to both prove the game-theoretical value of nodes in a search tree and to focus its simulations better using domain knowledge. This results in simulations superior in both handling tactics and ensuring game progression. Using the improved MCTS variant, our program is able to outperform even the world's strongest αβ-based LOA program. This is an important milestone for MCTS because the traditional game-tree search approach has been considered to be the better suited for playing LOA.