Source-linked AI summary
Monte Carlo Tree Search: A Review of Recent Modifications and Applications
Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, Jacek Mańdziuk
TL;DR
MCTS is effective for combinatorial games but often requires problem-dependent modifications in complex games and practical domains. This survey reviews 240 papers, concentrating on post-2012 extensions and hybrid approaches. It finds that MCTS was extensively hybridized with other search and optimization algorithms, while knowledge integration remains constrained by data and model-training challenges.
Problem
Base MCTS can perform poorly under practical computational constraints in complex problems, motivating domain-specific modifications and hybrid approaches.
Method
The survey analyzes 240 papers, mostly published since 2012, and organizes MCTS enhancements by application domains and modification types.
Results
MCTS was extensively hybridized with other search and optimization algorithms during the eight years following the previous major survey.
Takeaways & Limitations
Embedding knowledge into MCTS without introducing too much bias is identified as a potential way to improve performance.
Takeaways & Limitations
Introducing machine learning into MCTS is constrained by the availability and quality of training data, while model training can also suffer from overfitting and inadequate position coverage.
Abstract
from arXiv · showhide
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.
1 Introduction
MCTS searches combinatorial decision spaces and has expanded from game playing into practical decision domains. This survey emphasizes post-2012 modifications, especially those addressing difficult environments and organizing the literature by applications and extensions.
- MCTS represents problem configurations as nodes and state transitions or actions as edges in a search tree.
- Although MCTS is applicable without domain knowledge, heuristics can improve efficiency and convergence when incorporated into the approach.
- MCTS has increasingly been applied beyond games, including planning, scheduling, control, and combinatorial optimization, with modifications extending it to POMDPs.
- Real-world and real-time problems challenge vanilla MCTS through enormous branching factors, large state spaces, continuous environments, and fast-paced decisions.
- The survey focuses on post-2012 contributions and organizes them by MCTS extension types while also grouping references by application and method.
- Its main content covers classic MCTS, perfect-information games, and imperfect-information games through extensions such as action reduction, UCT alternatives, early termination, determinization, information sets, and heavy playouts.
2 Classic MCTS
Classic MCTS iteratively searches a state space, simulates outcomes, and updates statistics to balance exploration with exploitation. It is an anytime method whose standard components and enhancements support asymmetric search under finite computational budgets.
- MCTS models sequential decision problems with states, available actions, probabilistic transitions, and rewards, formally applying to Markov Decision Processes.
- MCTS is an anytime algorithm that can stop under a computational budget and return the currently best action using empirical action values.
- Each iteration performs selection, expansion, simulation, and backpropagation, with random terminal-state simulations providing payoffs for updating path statistics.
- UCT balances exploration and exploitation using action values, visit counts, and a game-dependent exploration constant, commonly initialized at 2 for normalized Q values.The recommended value assumes Q values lie in [0, 1].
- UCT and random sampling produce asymmetric search that explores promising lines more thoroughly than less promising ones.
- Alternatives include UCB1-Tuned, EXP3, and Thomson sampling, while RAVE, transposition tables, and opening books reuse information or strengthen search in specific settings.
3 Games with Perfect Information
MCTS extensions for perfect-information games mainly reduce branching, terminate simulations early, or replace UCT selection, with domain-specific and hybrid methods addressing tactical and large decision spaces.
- MCTS extensions are organized into action reduction, early termination, and UCT alternatives.Action reduction limits available actions, early termination ends simulations prematurely, and UCT alternatives modify the selection phase.
- Action Reduction: Action reduction methods eliminate actions to enable deeper inspection of promising branches when trees grow sideways under high branching factors.
- Action Reduction: O-MCTS selects predefined multi-action options aimed at subgoals instead of individual actions, enabling more in-depth search within the same time.After an option reaches its subgoal, the expansion phase is conducted.
- Action Reduction: IMCTS uses calibrated Naive Bayes and action-type independence models to provide prior action distributions during exploration, outperforming other MCTS approaches in an RTS domain.The models are trained on bot-duel data and derive distributions for legal actions in the current state.
- UCT Alternatives: UCT alternatives include RAVE-style shared action values, heuristic progressive win bias, heavy playouts, evaluation functions, and shallow minimax search for tactical traps.These methods respectively reuse simulation information, incorporate heuristics, alter simulations, guide value estimation, or address averaging of sampled outcomes.
4 Games with Imperfect Information
Imperfect information increases the complexity of MCTS by introducing hidden states and larger branching factors. The survey presents determinization, information-set methods, heuristic playouts, policy updates, and combined enhancements as responses to these challenges.
- Challenges: Imperfect information creates probability distributions over hidden game states, substantially increasing the branching factor of tree search.RTS games may hide map regions and enemy units behind a fog of war.
- Determinization: Determinization samples unknown features to create multiple perfect-information trees, but this increases branching factor and requires pruning or compact representations.In Magic: The Gathering, domain-knowledge move pruning and binary tree representation reduced CPU time per move.
- Information Sets: Information Set MCTS groups indistinguishable states into information sets, consolidating move statistics and addressing strategy fusion and computational-budget allocation.Unlike determinization, each node represents an information set rather than a single state.
- Heavy Playouts: Heavy playouts should combine domain knowledge with randomness: reduced-rule-based stochastic rollouts outperformed deterministic expert rollouts, while fully random playouts performed poorly.The comparison was conducted in Magic: The Gathering.
- Policy Updates: Genetic programming improved Pac-Man’s average score by 18% over a random default policy without significant computational overhead.The evolved policy was selected after optimizing nine GP and MCTS parameters.
- Combined Enhancements: Across applications, combining MCTS extensions generally produces the strongest results, but no single modification works universally.Reported combinations include risk-sensitive UCT, reversal penalties, macro-actions, limited expansion, and domain-specific heuristics.
5 Combining MCTS with Machine Learning
The survey reviews how machine learning is combined with MCTS to improve policies, value estimates, simulations, and performance across games and other domains. These approaches can produce stronger agents and faster generalization, but depend on substantial, high-quality training data and accurate models.
- AlphaGo-inspired approaches: MCTS combined with deep reinforcement learning forms the backbone of AlphaGo-style systems using policy and value functions.AlphaGo uses deep convolutional networks for both functions, with its initial policy trained by supervised learning on expert moves.
- AlphaGo-inspired approaches: MoHex-CNN outperformed MoHex 2.0, while MoHex-3HNN further improved performance using a three-head network producing policy, state-value, and action-value outputs.
- AlphaGo-inspired approaches: DeepEzo achieved a 79.3% winning rate against MoHex 2.0 but lost to MoHex-3HNN in direct competition.
- MCTS as a trainer for ML models: MCTS can act as a demonstrator or trainer for reinforcement learning in hard-exploration domains under time constraints.In Pommerman, shallow MCTS helped the agent learn to avoid being killed by its own delayed-action bomb.
- Temporal-difference learning: TD-based methods adapt MCTS simulations or policies when uniform random simulation performs poorly, with TD-UCT Merged Bootstrapping with AMAF besting alternatives across four games.
- Advantages and challenges: Machine learning can improve MCTS quality, approximation, and real-time generalization, while requiring large amounts of high-quality data and careful training to avoid overfitting.
6 MCTS with Evolutionary Methods
The survey covers evolutionary methods that optimize MCTS evaluation functions, tree policies, default policies, or simulations. These methods can outperform random or baseline policies and sometimes generalize across board sizes, but their effectiveness is game-dependent and may require costly offline evolution.
- Evolving evaluation functions: Genetic programming can evolve board-evaluation functions that guide MCTS simulations instead of using purely random moves.A stochastic subset of available actions is evaluated, and the highest-scoring action is selected for simulation.
- Evolving evaluation functions: Evolved heuristic evaluation improved MCTS players in both tested games but was time-consuming and therefore most suitable for offline preparation.
- Evolving policies: Evolutionary methods can optimize MCTS tree policies, default simulation policies, or both rather than constructing a new evaluation function.
- Evolving policies: Hivemind evolved board patterns and move-selection strategies whose policies outperformed baseline default policies, including uniform random selection, and generalized to different board sizes.
- Evolving policies: In four of five tested games, evolved heuristics performed similarly to UCB; in the remaining game, they produced poor results while still revealing game-specific exploration insights.
- Evolutionary search alternatives: Comparisons between MCTS and RHEA found that neither algorithm was inherently stronger because effectiveness depended on the particular game.
- Evolutionary search alternatives: Evolutionary MCTS uses action sequences in every tree node rather than starting from an empty vanilla-MCTS tree.
7.1 Planning
MCTS planning applications extend the base algorithm with abstractions, hierarchical actions, model modifications, and decentralized search to address large or difficult planning spaces. Reported applications include strong performance for ASAP-UCT, hierarchical UCT, and decentralized multi-robot planning.
- Automated planning commonly formulates problems as MDPs or POMDPs, using simulated environments with states, goals, and available actions.
- Simplifications of a Problem / Model: ASAP-UCT combines state-action abstractions, search-depth controls, reward-lock handling, and dynamic abstraction timing for large planning problems.Its abstraction computation reduces naive complexity from O(n^2) to O(rk^2).
- Simplifications of a Problem / Model: ASAP-UCT achieved statistically significantly better results than vanilla UCT and three other algorithms in six problems from three domains, except for one comparison.
- Hierarchical and Distributed MCTS: Hierarchical Monte-Carlo planning decomposes top-level tasks into irreducible subtasks and uses macro actions with nested action-selection routines.The approach was evaluated on Taxi and includes theoretical analysis of bias induced by Hierarchical UCT.
- Hierarchical and Distributed MCTS: Hierarchical MCTS is efficient when a problem admits a hierarchy and aims to mitigate the curses of dimensionality and history.
- Planning in Robotics: Dec-MCTS gives each robot an individual search tree, periodically sharing compressed trees to update the joint policy distribution for online replanning.Across eight simulated team-orienteering environments, it achieved a median 7% better score than standard single-tree MCTS.
7.2 Security
Security-game applications use Monte Carlo methods to approximate defender strategies in multi-act and multi-step settings where exact formulations are computationally expensive. Mixed-UCT and O2UCT provide scalable UCT-based alternatives for strategy approximation.
- Security games model defenders as leaders and attackers as followers who commit to mixed strategies in an asymmetric Stackelberg framework.The follower observes the leader’s committed strategy before selecting a response.
- Exact security-equilibrium calculation is computationally expensive, so practical approaches often simplify formulations and primarily address single-act games.
- Monte Carlo simulation was introduced as an alternative route to efficient security-equilibrium approximations for multi-act games.
- Mixed-UCT iteratively computes the leader’s strategy against a gradually improving follower represented by a combination of past followers.The method is described as scaling well in time and memory across various security-game types.
- O2UCT alternates guided MCTS sampling of attacker strategies with construction of a defender mixed strategy for which the sampled attacker strategy is an optimal response.
7.3 Chemical Synthesis
Chemical-synthesis applications combine MCTS with neural networks trained on reaction knowledge to guide retrosynthetic search. The resulting 3N-MCTS architecture changes rollout, expansion, and filtering decisions.
- 3N-MCTS applies MCTS to computer-aided retrosynthesis, transforming molecules into increasingly simpler precursors with guidance from three neural networks.The networks were trained on reaction knowledge from organic chemistry research.
- A rollout policy network trained on 17134 reaction rules samples actions during MCTS simulations.Each included rule appeared at least 50 times before 2015.
- An in-score filter network predicts whether proposed transformations are likely to work and discards unsuccessful candidates during expansion.
- An expansion policy network selects the most promising node to add instead of expanding the first non-tested action.
- MCTS combined with deep neural networks has also been applied to chemical and physical problems such as FluidStructure Topology Optimization.
7.4 Scheduling
Scheduling applications combine MCTS with heuristics and local search to handle resource allocation and dynamic events. Reported approaches include hybrid schedule construction and a 20% makespan reduction for production workloads.
- MCTS can generate initial solutions for multi-mode resource-constrained multi-project scheduling, which local search then modifies using hyper-heuristics.
- RAPSP extends resource-constrained project scheduling to complex, nondeterministic, dynamic environments involving risk management.
- ProUCT combines heuristic solvers that create baseline schedules with UCT testing alternative branches caused by dynamic events.The approach was subsequently extended and summarized in later work.
- 20%: Spear was reported to reduce the makespan of production workloads while outperforming modern heuristics.
7.5 Vehicle Routing
The survey groups MCTS applications to vehicle-routing problems around techniques that simplify, factorize, or otherwise reshape the search. These modifications target the large and structured search spaces of routing tasks.
- CVRP and related transport problems combine route planning with scheduling, motivating MCTS applications to this problem class.
- Problem simplification by having a “good” initial solution: Several approaches construct a good initial solution using classical TSP or modified Clarke and Wright savings algorithms.MCTS can then generate or steer alternative starting solutions.
- Problem factorization: Problem factorization assigns each vehicle or route a separate MCTS tree, while synchronized simulations produce a vector of actions.
- Macro-actions and action heuristics: Macro-actions and action heuristics replace atomic actions and can drastically reduce the search space.Some approaches interleave macro-actions with regular actions.
- Other modifications: Other routing methods replace UCT with route-assessment formulas or ϵ-Greedy selection, and one approach evaluates non-terminal states with a fitness function.
7.6 Multi-Domain MCTS with Heuristics
A general framework combines MCTS with heuristics by searching over low-level heuristic applications, forming a hierarchical hyper- or meta-heuristic.
- The framework represents MCTS nodes as low-level heuristics applied to states, creating a hierarchical hyper- or meta-heuristic.
- Tests across six domains found results competitive with state-of-the-art methods.
- The framework demonstrates that MCTS can organize heuristic choices rather than directly searching only primitive actions.
8 Parallelization
Parallelization increases the number of MCTS iterations or combines statistics across concurrent searches through leaf, root, tree, and hybrid approaches. Reported applications include specialized hardware, game-specific solvers, and scalable distributed implementations.
- Parallel MCTS is primarily intended to increase iterations per second, thereby gathering more statistics for MCTS/UCT evaluation.
- The three major approaches are Leaf Parallelization, Root Parallelization, and Tree Parallelization.
- Base approaches: Leaf Parallelization runs K independent playouts from one expanded node and aggregates their results for back-propagation.
- Base approaches: Root Parallelization builds independent trees and aggregates first-level statistics, providing more confident combined statistics with minimal communication overhead.
- Base approaches: Tree Parallelization shares one tree across processes and uses synchronization mechanisms such as locks and mutexes.
- Parallel policy adaptation: At 16 threads, adaptive playouts achieved a 68% performance ratio relative to static playouts because global-lock synchronization harmed computational performance.
- Specialized hardware: A modified Tree-Parallel MCTS with grain-size control reported 5.6 times speedup over the sequential version on an Intel Xeon E5-2596 processor.
- Hybrid parallelization: A hybrid Root-Tree approach with hierarchical Leaf Parallelization was more effective than either method alone across nine General Game Playing games.
9 Conclusions
The survey reviews 240 MCTS papers, emphasizing post-2012 modifications, hybridization, and applications beyond traditional games. It concludes that MCTS is versatile and anytime, but remains constrained by search-space growth, domain bias, unpredictability, and real-time simulation challenges.
- The review analyzes 240 papers, mostly published after the 2012 survey, and organizes them by application domains and baseline enhancements.
- Hybridization trends include combining MCTS with machine learning, self-adaptation, and domain knowledge.
- MCTS + Domain Knowledge: Domain knowledge can enter through heavy playouts, action prioritization or reduction, evaluation functions, and early termination.
- Human-in-the-Loop: Embedding knowledge may improve performance, but direct or human-guided inclusion must avoid introducing excessive bias.
- MCTS in New Domains: MCTS applies beyond games to sequential decision problems representable as trees with assessable leaf solutions, including optimization, planning, and scheduling.
- MCTS in Real Time Games: Real-time video games remain challenging because of computational complexity, stochastic unpredictability, and difficulty constructing suitable forward models.
- MCTS builds asymmetric trees, balances exploration and exploitation with UCT, has theoretical convergence justification, and can return a solution at any stopping time.
- Search-space explosion is a central weakness, motivating model simplification, action reduction, offline MCTS-generated training data, and learning-based representations.