A Survey of Monte Carlo Tree Search Methods

By Cameron Browne, Edward Jack Powley, Daniel Whitehouse, Simon M. M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez Liebana, Spyridon Samothrakis, Simon Colton. 2012

3,443 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Economics and Econometrics, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Economics and Econometrics

In Evaluation & Benchmarks

Citations in the corpus

The Arcade Learning Environment: An Evaluation Platform for General Agents (2012, background): “By expanding the more valuable branches of the tree and carrying out a random simulation at the leaf nodes, UCT is known to perform well in many different settings (Browne et al., 2012).”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “Search Algorithms There are two classical search algorithms for zero-sum turn-taking games of perfect information: minimax (and alpha-beta) search [29, 59], and Monte Carlo tree search (MCTS) [18, 30, 16].”
TreeQN and ATreeC: Differentiable Tree Planning for Deep Reinforcement Learning (2017, methodology): “One strategy for on-line planning is to use look-ahead tree search (Knuth & Moore, 1975; Browne et al., 2012).”
Planning chemical syntheses with deep neural networks and symbolic AI (2017, background): “[29] Each edge ( s, a ) in the search tree stores the action value Q ( s, a ) , the visit count N ( s, a ) and a prior probability P ( s, a ) received from the expansion policy network.”
Value Prediction Network (2017, methodology): “Monte-Carlo Tree Search (MCTS) methods [15, 3] have been used for complex search problems, such as the game of Go, where a simulator of the environment is already available and thus does not have to be learned.”
SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient (2016, methodology): “For simplicity, we use the standard LSTM as the generator, while it is worth noticing that most of the RNN variants, such as the gated recurrent unit (GRU) (Cho et al. 2014) and soft attention mechanism (Bahdanau, Cho, and Bengio 2014), can be used as a generator in SeqGAN.”
Towards modular and programmable architecture search (2019, methodology): “Researchers have considered a variety of search algorithms, including reinforcement learning [13], evolutionary algorithms [14, 15], MCTS [16], SMBO [16, 17], and Bayesian optimization [18].”
Benchmark and Survey of Automated Machine Learning Frameworks (2019, methodology): “Monte-Carlo tree search (Kocsis & Szepesvári, 2006; Browne et al., 2012) is a heuristic best-first tree search algorithm.”
Survey on Automated Machine Learning (2019, background): “Therefore, the predictions are passed to a Monte Carlo tree search (Browne et al., 2012).”
DeepArchitect: Automatically Designing and Training Deep Architectures (2017, methodology): “MCTS uses two policies: a tree policy , which determines the path to be traversed from the root to the frontier of the already expanded tree; and a rollout policy , which determines the path to be traversed from the frontier of the already expanded tree until a leaf is reached.”
Causally Correct Partial Models for Reinforcement Learning (2020, methodology): “Additionally, we enhance the MCTS with chance nodes (Browne et al., 2012).”
Woulda, Coulda, Shoulda: Counterfactually-Guided Policy Search (2018, methodology): “We refer to λ as a planner to highlight that it could consist of a procedure that solves episodes starting from arbitrary, full states s 1 sampled form the model, by repeatedly calling the model transition kernel, e.g. a search procedure such as MCTS (Browne et al., 2012) or an expert policy.”
Reinforcement Learning in Healthcare: A Survey (2019, methodology): “s that directly estimate value functions without building a model of the environment [43]. Using some advanced exploration strategies and planning methods such as DP or Monte Carlo Tree Search (MCTS) [44], MRL methods are usually able to learn an accurate model quickly and then use this model to pla”
MOReL : Model-Based Offline Reinforcement Learning (2020, methodology): “A number of algorithms based on MPC [23, 64], search-based planning [65, 25], dynamic programming [49, 26], or policy optimization [27, 51, 66, 67] can be used to approximately realize this.”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “In certain noisy environments, Monte Carlo Tree Sampling (MCTS; [29]) and similar techniques may be applied toM to plan successful future action sequences for C.”
Go-Explore: a New Approach for Hard-Exploration Problems (2019, neutral): “Classical planning algorithms such as UCT [47–49] (a powerful form of Monte Carlo tree search [49, 50]) obtain 0 points on Montezuma’s Revenge because the state space is too large to explore effectively, even with probabilistic methods [30, 51].”
Formal Mathematics Statement Curriculum Learning (2022, background): “In such games, deep learning systems exhibit a considerable degree of reasoning, especially when trained with self-play combined with a search procedure such as Monte Carlo Tree Search (MCTS) (Browne et al., 2012).”