2013 · 30 citations · 19 references
BusinessStrategyDecision TheoryGame TheoryOptimizationBacktracking AlgorithmsExploration-exploitation TradeoffMetaheuristic OptimizationMonte Carlo MethodsMonte Carlo SimulationAlpha-beta PruningBackpropagationDepth-first SearchHybrid AlgorithmsMinimax SearchMonte Carlo Tree SearchSearch Tree Pruning
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.
19
Theory of Games and Economic Behavior
David Hawkins · Philosophy of Science · 1945 · 4K citations
An analysis of alpha-beta pruning
Donald E. Knuth, Ronald W. Moore · Artificial Intelligence · 1975 · 1K citations
PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCH
Guillaume Chaslot, Mark H. M. Winands, H.J. van den Herik et al. · New Mathematics and Natural Computation · 2008 · 436 citations