Using Heuristic Solver to Optimize Monte Carlo Tree Search in Dots-And-Boxes

Dots-and-Boxes is a popular pencil-and-paper game, where p layers drawing lines on a grid of dots alternately. In this paper, we propose a new technique to combine heuristic solver and Monte Carlo Tree Search, a simulation-based best-first search technique that has revolutionized the performance of computer Go. During the MCTS simulations, the search does not need to touch the terminal state but a given state that can be solved by heuristic solver. We show that combining heuristic solver with MCTS leads to stronger play performance in Dots-And-Boxes.