The History of AI

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

Sources

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.

Open in the interactive timeline