Monte Carlo tree search
Era 3 · From the expert boom to the statistical turn (1980–2011) › Reinforcement learning
- Lineage
- Data and learning
- Kind
- Theory
Who
MTA SZTAKI
What happened
France's Rémi Coulom presents Monte Carlo tree search at the Computers and Games conference in Turin, and the Crazy Stone program wins the 9 × 9 Go tournament at the Computer Olympiad. In September, Hungarian researchers Levente Kocsis and Csaba Szepesvári publish UCT, a version with theoretical guarantees.
Why it mattered
A program evaluates moves by playing thousands of random games to the end, with no need for a hand-written evaluation function. It moves computer Go forward and is one of the two pieces of AlphaGo.
The full story
Chess had been cracked with alpha-beta search and a good evaluation function, but in Go that recipe failed: there are far more possible moves on each turn, and nobody knew how to write a reliable formula for telling who is winning. In 2006 the best Go programs played like weak amateurs.
The alternative was to evaluate a position by playing many games from it with random moves and counting how many are won. Bernd Brügmann had tried this in Go in the 1990s. Coulom combined those simulations with a search tree that grows selectively: it devotes more simulations to the moves that look promising without entirely abandoning the others. That is where the name Monte Carlo tree search came from.
Kocsis and Szepesvári, of the Computer and Automation Research Institute of the Hungarian Academy of Sciences, worked out how to allocate the simulations with a formula taken from the multi-armed bandit problem, which balances exploring new moves against exploiting good ones, and proved that the method converges to the best move. Their algorithm, UCT, was adopted right away, for example in the MoGo program.
Within a few years Go programs reached master level on the small board. In 2015 AlphaGo combined this search with neural networks that choose and evaluate moves.
Leads to
AlphaGo beats Fan Hui (October 5, 2015)
Documented direct influence
AlphaGo combines Monte Carlo tree search with policy and value networks; the paper cites the work of Coulom and of Kocsis and Szepesvári
Threads that pass through here
- Machines versus champions (step 5 of 7)
Sources
Original source
- Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games 2006, Lecture Notes in Computer Science 4630, pp. 72-83 (opens in a new tab). Rémi Coulom, 2006
- Bandit Based Monte-Carlo Planning. ECML 2006, Lecture Notes in Computer Science 4212, pp. 282-293 (opens in a new tab). Levente Kocsis and Csaba Szepesvári, 2006
How to cite
“Monte Carlo tree search.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/monte-carlo-tree-search
This entry was last reviewed on November 13, 2026.