Monte Carlo Tree Search
Plans by building a tree of possible futures, spending more simulations on promising moves, and choosing the move whose subtree looks best.
Also MCTS · UCT · game tree search
Coulom, 2006; Kocsis and Szepesvári (UCT), 2006
Before moving in a board game, imagine many quick games from each possible move. Spend more of your imagination on moves that keep turning out well, then play the one that won most often.
Where it fits
+All relationships as a list
Is a kind of / part of
Siblings
Uses / built on
How it works
Classic game programs like Deep Blue searched a huge tree of moves and judged positions with hand-written rules. That fails in Go, where positions are hard to evaluate and the tree is astronomically wide. MCTS instead uses sampling.
Each iteration has four steps:
- Selection: walk down the existing tree, at each node choosing a child by a rule that balances “this move has won a lot” with “this move has rarely been tried”, the same exploration-exploitation trade-off as in bandits.
- Expansion: add a new child node.
- Simulation: play the game out quickly (randomly, or with a learned evaluation) to get a result.
- Backpropagation: pass the result back up the path, updating win counts. (Not the same as neural-network backpropagation, despite the name.)
After thousands of iterations, the most-visited move is played. AlphaGo combined MCTS with neural networks that suggested promising moves and evaluated positions, replacing random play-outs.
Everyday use cases
- Case 01
Board game AI
The core search in AlphaGo and AlphaZero, and in many Go programs before them.
- Case 02
Planning and scheduling
Choosing sequences of decisions when outcomes can be simulated.
Famous examples
- 2016AlphaGo
DeepMind's Go program that combined deep neural networks with tree search and, in March 2016, beat top professional Lee Sedol 4 games to 1.
- 2017AlphaZero
DeepMind's single algorithm that learned chess, shogi and Go from scratch through self-play, given only the rules, and beat the strongest existing programs in each.
Strengths, weaknesses and when to use it
Strengths
- Needs no hand-written evaluation function in its basic form.
- Can stop at any time and still give a reasonable move.
Weaknesses
- Needs a fast simulator of the environment.
- Expensive when every decision requires many simulations.
When to use itFor turn-based decisions where you can simulate outcomes, like games and planning problems.
Check yourself
- Q01
How does MCTS decide where to spend its simulations?
Show answer
A: It balances moves that look good with moves it has tried rarely