Monte-Carlo Tree Search: A New Framework for Game AI

By Guillaume Chaslot, Sander C. J. Bakkes, Istvan Szita, Pieter H. M. Spronck. 2008

465 citations recorded by the source corpus.

Classic approaches to game AI require either a high quality of domain knowledge, or a long time to generate effective AI behaviour. These two characteristics hamper the goal of establishing challenging game AI. In this paper, we put forward Monte-Carlo Tree Search as a novel, unified framework to game AI. In the framework, randomized explorations of the search space are used to predict the most promising game actions. We will demonstrate that Monte-Carlo Tree Search can be applied effectively to (1) classic board-games, (2) modern board-games, and (3) video games.

Subfields: Artificial Intelligence, Sociology and Political Science

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 Sociology and Political Science

Citations in the corpus

Deep Multi-Agent Reinforcement Learning with Relevance Graphs (2018, methodology): “Policy gradient methods have been shown to be successful in combination with Monte-Carlo tree search (MCTS) [3], which is a general, powerful, and widely used decision making algorithm, most commonly applied to games.”
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].”
Winning Isn't Everything: Training Human-Like Agents for Playtesting and Game AI (2019, background): “MCTS agents for playing Settlers of Catan were reported in [5], [6] and shown to beat previous heuristics.”
Edge Computing with Artificial Intelligence: A Machine Learning Perspective (2022, methodology): “• The framework uses DNN to train with a self-supervised training process to predict the resource allocation action, with the training data generated by the Monte Carlo tree search (MCTS) [128] algorithm; • The authors modify the last layer of the traditional DNN used to estimate Q-function, so that”
On the Analysis of Complex Backup Strategies in Monte Carlo Tree Search (2016, background): “MDPs that only requires generative samples from the MDP. UCT was first popularized due to excellent performance in Computer Go (Gelly and Wang, 2006; Chaslot et al., 2008), and it has also performed well in large Partially Observable MDPs (POMDPs) (Silver and Veness, 2010).”
Textual Data Augmentation for Efficient Active Learning on Tiny Datasets (2020, unknown): “MCTS consists of four major steps: Selection, Expansion, Simulation, and Backpropagation (Chaslot et al., 2008).”
Variance Reduction in Monte-Carlo Tree Search (2011, unknown): “This general approach [6] has been successfully adapted to a variety of challenging problem settings, including Markov Decision Processes, Partially Observable Markov Decision Processes, Real-Time Strategy games, Computer Go and General Game Playing [15, 22, 2, 9, 12, 10].”
On Multi-Agent Learning in Team Sports Games (2019, background): “MCTS agents for playing Settlers of Catan were reported in (Szita et al., 2009; Chaslot et al., 2008) and shown to beat previous heuristics.”
Unmanned Aerial Vehicles for Search and Rescue: A Survey (2023, methodology): “It was ﬁrst proposed as a framework for game AI in the paper [124], which illustrated the detailed procedures for the MCTS.”
Deep learning in medical image registration: a survey (2019, background): “These approaches have been applied to various video/board games and have often been able to demonstrate superhuman performance [15, 40, 41, 112, 113, 124].”
Reset-free Trial-and-Error Learning for Robot Damage Recovery (2016, methodology): “Essentially, the authors use deep learning to pre-compute default policies and initial values for a Monte Carlo Tree Search (MCTS) [21] algorithm that plans (approximately) the best next action to take.”
A Survey of Monte Carlo Tree Search Methods (2012, background): “6The simulation and expansion steps are often described and/or implemented in the reverse order in practice [52], [67].”
On the nature and origin of intuitive theories : learning, physics and psychology (2015, methodology): “One could try to get around the size of the input space by considering samplingbased planning algorithms, such as Monte-Carlo-tree-search [29, 19] or Rapid Random Trees (RRT) [105].”