Monte Carlo Tree Search (MCTS): Principles, Algorithms, Advantages, and Applications

Introduction

On March 9, 2016, Google’s AlphaGo defeated world Go champion Lee Sedol, marking a milestone for artificial intelligence. AlphaGo first learned by mimicking human games, then improved through self‑play using reinforcement learning, and finally employed Monte Carlo Tree Search (MCTS) with value and policy networks to evaluate and select moves.

What is MCTS?

MCTS (Monte Carlo Tree Search) is a decision‑making method for combinatorial games that combines random simulations with tree search to find optimal moves. It gained rapid attention after its success in computer Go and can be applied to any domain that can be expressed as a {state, action} model.

Basic Algorithm

The basic MCTS loop consists of four steps:

Selection : Starting from the root, recursively select the most promising child node until a leaf node is reached.

Expansion : If the leaf is not terminal, create one or more child nodes and pick one for simulation.

Simulation : Run a playout from the selected node to the end of the game.

Backpropagation : Propagate the simulation result back up the tree to update statistics.

Each node stores the estimated value from simulations and the number of times it has been visited.

Node Selection

Bandits and UCB

Node selection uses the Upper Confidence Bound (UCB) formula, originally from the multi‑armed bandit problem, to balance exploitation and exploration:

where v_i is the node’s value estimate, n_i the visit count, N the parent’s total visits, and C a tunable constant.

Exploitation vs. Exploration

The UCB term rewards nodes with high estimated payoff (exploitation) while encouraging visits to less‑explored nodes (exploration), allowing MCTS to converge to reliable estimates given enough iterations.

MCTS and UCT

Kocsis and Szepesvári (2006) extended UCB to tree search, creating Upper Confidence Bounds for Trees (UCT), which can be described as UCT = MCTS + UCB .

Advantages

Heuristic‑Free

MCTS does not require domain‑specific heuristics; it can operate with only the basic rules of a game, making it reusable across many games with minimal adjustments.

Asymmetric Search

The algorithm focuses computational effort on promising parts of the tree, which is especially beneficial for games with large branching factors such as 19×19 Go.

Asymmetric growth

Any‑time Property

MCTS can be stopped at any moment and will return the best current estimate, allowing the constructed tree to be discarded or reused later.

Simplicity

Implementations are straightforward; a minimal version can be found at http://mcts.ai/code/index.html .

Disadvantages

Computational Cost

For large or complex games, MCTS may require millions of simulations to reach expert‑level performance, which can be prohibitive in time‑constrained settings.

Limited Performance in Small Games

In some relatively small games, the algorithm may still fail to find optimal moves within reasonable time because the search space is too large to explore sufficiently.

Enhancements

Domain Knowledge

Incorporating game‑specific knowledge can prune illegal moves or bias simulations toward realistic play, dramatically improving performance at the cost of generality.

Domain‑Independent Techniques

Methods such as AMAF (All‑Moves‑As‑First) or simulation policies that favor winning actions enhance MCTS without relying on specific game knowledge, and are a major focus of current research.

Background and History

1928 – John von Neumann introduced the minimax theorem, laying the foundation for tree‑based decision making.

1940s – Monte Carlo methods were developed for solving problems via random sampling.

2006 – Rémi Coulom combined these ideas to create MCTS for Go; Kocsis and Szepesvári formalized it as the UCT algorithm.

Research Interest

Since its inception, over 150 papers on MCTS have been published, averaging one new paper every two weeks, with many variants, enhancements, and optimizations explored.

Recent Advances

The first international MCTS workshop was held at Imperial College London in August 2010, featuring talks on the state of the art, challenges, and applications such as Hex, General Game Playing, and Havannah.

For further reading, see the original Chinese article at http://mcts.ai/about/index.html and the source on Jiǎnshū.