Monte Carlo Tree SearchMonte Carlo Tree Search

Around 2006, computer Go was stuck. The game's branching factor is so large that the tree-search methods which had conquered chess simply drowned. The breakthrough came from an unlikely direction: randomness.

Monte Carlo Tree Search, named by Remi Coulom in 2006 as he built the Go program Crazy Stone, evaluates a position not with a handcrafted scoring function but by playing many fast, random games to the finish and seeing who tends to win.

The method grows a search tree selectively. It spends its effort on the most promising lines while still occasionally exploring neglected ones, a balance formalized that same year by Levente Kocsis and Csaba Szepesvari in an algorithm called UCT, borrowed from the mathematics of slot-machine gambling.

The four repeating steps, select a path, expand a new node, simulate a random playout, and back up the result, let the search improve its estimates the more it thinks, without needing expert knowledge of the game baked in.

It transformed computer Go and board-game AI generally, and it became a central component of DeepMind's AlphaGo, combined there with deep neural networks to defeat the world's best human players in 2016.

The same planning-by-sampling idea now appears well beyond games, from robotics to scheduling to guiding the reasoning of large models, wherever the space of possibilities is too vast to enumerate.