MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)

Hendrik Baier*, Mark H. M. Winands

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

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 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.
Original languageEnglish
Title of host publicationPROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE
PublisherInternational Joint Conferences on Artificial Intelligence
Pages5548-5552
Number of pages5
ISBN (Print)9780999241127
DOIs
Publication statusPublished - Jul 2018
EventTwenty-Seventh International Joint Conference on Artificial Intelligence - Stockholmsmässan, Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018
https://www.ijcai-18.org/

Conference

ConferenceTwenty-Seventh International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI-18
Country/TerritorySweden
CityStockholm
Period13/07/1819/07/18
Internet address

Cite this