Monte-Carlo Tree Search and minimax hybrids
- 1 August 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23254270,p. 1-8
Abstract
Monte-Carlo Tree Search is a sampling-based search algorithm that has been successfully applied to a variety of games. Monte-Carlo rollouts allow it to take distant consequences of moves into account, giving it a strategic advantage in many domains over traditional depth-limited minimax search with alpha-beta pruning. However, MCTS builds a highly selective tree and can therefore miss crucial moves and fall into traps in tactical situations. Full-width minimax search does not suffer from this weakness. This paper proposes MCTS-minimax hybrids that employ shallow minimax searches within the MCTS framework. The three proposed approaches use minimax in the selection/expansion phase, the rollout phase, and the backpropagation phase of MCTS. Without requiring domain knowledge in the form of evaluation functions, these hybrid algorithms are a first step at combining the strategic strength of MCTS and the tactical strength of minimax. We investigate their effectiveness in the test domains of Connect-4 and Breakthrough.Keywords
This publication has 15 references indexed in Scilit:
- A Survey of Monte Carlo Tree Search MethodsIEEE Transactions on Computational Intelligence and AI in Games, 2012
- Experiments with Monte-Carlo Tree Search in the Game of HavannahICGA Journal: The Journal of the Computer Games Community, 2011
- Enhancements for Multi-Player Monte-Carlo Tree Search2011
- A Shogi Program Based on Monte-Carlo Tree SearchICGA Journal: The Journal of the Computer Games Community, 2010
- Transpositions and move groups in Monte Carlo tree search2008
- PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCHNew Mathematics and Natural Computation, 2008
- Monte-Carlo Proof-Number Search for Computer Go2007
- Bandit Based Monte-Carlo Planning2006
- Proof-number searchArtificial Intelligence, 1994
- An analysis of alpha-beta pruningArtificial Intelligence, 1975