MCTS-Minimax Hybrids with State Evaluations (Extended Abstract).

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 contin-
ues this line of research for the case where heuristic
state evaluation functions are available. Three differ-
ent 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 do-
mains 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.