Monte Carlo Tree Search
Monte Carlo tree search (MCTS) is a planning algorithm that decides what to do by growing a search tree of possible futures, guided by the results of many randomized simulations, rather than by exhaustively expanding every branch. Instead of requiring a hand-written evaluation of how good a position is, it estimates that quality by playing the position out to the end and averaging the outcomes, while steadily concentrating effort on the moves that look most promising. This made it the first approach to produce strong computer Go players, a game whose branching factor of roughly 250 moves per turn defeated the depth-limited alpha-beta search that had worked for chess.
Each MCTS iteration runs through four phases: selection, expansion, simulation and backpropagation. Selection walks down the existing tree from the root, at each node picking a child according to a rule that balances moves that have done well against moves that have been tried little. Expansion adds one or more new child nodes when the walk reaches the edge of the tree. Simulation, often called a rollout, plays from the new node to a terminal state using a fast, usually random or lightly informed policy and records win, loss or score. Backpropagation then updates the visit counts and average results of every node on the path back to the root. Repeating this thousands of times sharpens the estimates, and the move at the root with the most visits is chosen.
The method crystallized in 2006 through two independent contributions that arrived almost together. Rémi Coulom described "Monte-Carlo tree search" as a name and a framework in his paper on selectivity and backup operators, using it in his Go program Crazy Stone, which won the 2006 Computer Olympiad 9×9 Go event. In the same year Levente Kocsis and Csaba Szepesvári published "Bandit based Monte-Carlo planning", introducing UCT, upper confidence bounds applied to trees. UCT treats the choice at each node as a multi-armed bandit and uses the UCB1 rule of Auer, Cesa-Bianchi and Fischer from 2002, which adds a bonus for rarely tried moves, and the authors proved that it converges to the optimal choice given enough iterations. Earlier work such as Brügmann's 1993 Monte Carlo Go had used random playouts without the tree.
AlphaGo, from DeepMind in 2016, showed what happens when MCTS is paired with learned neural networks, and it remains the most famous application. Silver and colleagues described in Nature a system in which a policy network proposed promising moves, which narrowed the search, and a value network evaluated positions, which reduced reliance on long random rollouts. It defeated the European champion Fan Hui 5–0 in 2015, and in March 2016 beat Lee Sedol 4–1 in Seoul. AlphaGo Zero and AlphaZero (2017) dropped human game data and trained entirely by self-play, using the search's visit counts as the training target for the network, and MuZero (2019) learned its own model of the environment to search inside. In every case the search acts as a policy improvement operator: its output is better than the raw network's guess, and the network learns to match it.
MCTS is not magic, and its characteristic weaknesses explain where it is used and where it is not. It needs either a simulator or a model that can be stepped forward cheaply and often, so it suits games, planning and puzzles more than open-ended real-world control. Pure random rollouts can badly misjudge positions that hinge on a single forced tactic, since averages hide a refutation that only one reply finds. Win-rate averaging also assumes a roughly stationary opponent. The tree grows in memory with every iteration, and results depend on the constant balancing exploration and exploitation, which is tuned per domain. Search is also not the same as learning: MCTS by itself starts afresh each move and stores no lessons.
The same idea now appears in language-model reasoning, where nodes are partial chains of thought or candidate solutions rather than game positions. Methods in the style of tree-of-thoughts and search-based decoding sample several continuations, score them with a verifier or reward model, and expand the promising ones, spending extra computation at inference time to improve answers. This trades cost for accuracy, in the spirit of best-of-n sampling, and it works best where partial progress can be judged reliably, such as code with tests or math with checkable steps. It also inherits a risk from the learned scorer: searching harder against an imperfect reward model finds its blind spots, a form of reward hacking.
Read Monte Carlo tree search as asking a thousand quick what-ifs and then spending the next thousand where the answers looked best: it turns a hopelessly large game tree into a focused, anytime estimate, and its pairing with learned networks is what carried it from Go programs to modern reasoning systems.