2018-07-13
MCTS-minimax hybrids with state evaluations
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| doi.org/10.1613/jair.1.11208 | |
| International Joint Conference on Artificial Intelligence | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Baier, H., & Winands, M. (2018). MCTS-minimax hybrids with state evaluations. In Proceedings of the International Conference on Artificial Intelligence (pp. 5548–5552). doi:10.1613/jair.1.11208 |
|
