Monte Carlo Tree Search: A Review of Recent Modifications and Applications

Abstract

Monte Carlo Tree Search (MCTS) is a powerful approach to designing game-playing bots or solving sequential decision problems. The method relies on intelligent tree search that balances exploration and exploitation. MCTS performs random sampling in the form of simulations and stores statistics of actions to make more educated choices in each subsequent iteration. The method has become a state-of-the-art technique for combinatorial games, however, in more complex games (e.g. those with high branching factor or real-time ones), as well as in various practical domains (e.g. transportation, scheduling or security) an efficient MCTS application often requires its problem-dependent modification or integration with other techniques. Such domain-specific modifications and hybrid approaches are the main focus of this survey. The last major MCTS survey has been published in 2012. Contributions that appeared since its release are of particular interest for this review.

arXiv comment99 pages, Accepted to Artificial Intelligence Review journal

References in corpus (10)

• Learning to Plan Chemical Syntheses
• Thinking Fast and Slow with Deep Learning and Tree Search
• Decentralized Cooperative Planning for Automated Vehicles with Hierarchical Monte Carlo Tree Search
• Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing
• Monte-Carlo Tree Search for Simulation-based Strategy Analysis
• Improving multivariate Horner schemes with Monte Carlo tree search
• Traditional Wisdom and Monte Carlo Tree Search Face-to-Face in the Card Game Scopone
• Double-oracle sampling method for Stackelberg Equilibrium approximation in general-sum extensive-form games
• Learning Policies from Self-Play with Policy Gradients and MCTS Value Estimates
• Integrating Acting, Planning and Learning in Hierarchical Operational Models

Cited by in corpus (4)

• A Parallel Monte-Carlo Tree Search-Based Metaheuristic For Optimal Fleet Composition Considering Vehicle Routing Using Branch & Bound
• An In-depth Summary of Recent Artificial Intelligence Applications in Drug Design
• Learning compositional programs with arguments and sampling
• A Fast Evolutionary adaptation for MCTS in Pommerman