MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)

MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)

Hendrik Baier, Mark H. M. Winands

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Journal track. Pages 5548-5552. https://doi.org/10.24963/ijcai.2018/782

Monte-Carlo Tree Search (MCTS) has been found to show weaker play than minimax-based search in some tactical game domains. In order to combine the tactical strength of minimax and the strategic strength of MCTS, MCTS-minimax hybrids have been proposed in prior work. This article continues this line of research for the case where heuristic state evaluation functions are available. Three different approaches are considered, employing minimax in the rollout phase of MCTS, as a replacement for the rollout phase, and as a node prior to bias move selection. The latter two approaches are newly proposed. Results show that the use of enhanced minimax for computing node priors results in the strongest MCTS-minimax hybrid in the three test domains of Othello, Breakthrough, and Catch the Lion. This hybrid also outperforms enhanced minimax as a standalone player in Breakthrough, demonstrating that at least in this domain, MCTS and minimax can be combined to an algorithm stronger than its parts.
Keywords:
Heuristic Search and Game Playing: Game Playing
Heuristic Search and Game Playing: Heuristic Search