Monte Carlo Tree Search: The Randomness Strategy Behind AlphaGo's Historic Win

In March 2016, a machine made a move that no human had ever seriously considered — and the world's best Go players sat in stunned silence trying to figure out if it was a mistake. It wasn't. Move 37 of Game 2 between AlphaGo and 9-dan champion Lee Sedol would later be described by Fan Hui, Europe's reigning Go champion, with a single, quiet verdict: "It's not a human move. I've never seen a human play this move." AlphaGo won that game, and three days later it clinched the match 4 games to 1.

The algorithm that found move 37 wasn't magic, and it wasn't even new. It was a 2006 idea called Monte Carlo Tree Search, bolted onto neural networks and run billions of times over. It's a strategy for making good decisions when you can't possibly check every option — and it quietly powers far more than board games.

The Concept

Imagine you're playing chess and it's your move. In principle, you could try to calculate every possible sequence of moves to the end of the game and pick the best one. In practice, that's impossible — Go has roughly 10^170 possible board positions, vastly more than the number of atoms in the observable universe. No computer, no matter how fast, can brute-force its way through that.

Monte Carlo Tree Search (MCTS) solves this with a clever compromise: instead of exhaustively checking everything, it plays out a huge number of random, fast simulated games — rollouts — from the current position to the end, and keeps track of which early moves tended to lead to wins. The name borrows from the Monte Carlo casino, a nod to randomness as the engine of insight, a tradition started in the 1940s by physicists Stanislaw Ulam and John von Neumann for calculating neutron diffusion.

MCTS runs in four repeating steps:

Selection — starting from the current position, walk down the game tree, at each step picking the child move that best balances two things: moves that have looked promising so far (exploitation), and moves that haven't been tried enough yet to know (exploration).
Expansion — once you reach a position that hasn't been explored, add a new node to the tree representing a move from there.
Simulation — play out a random (or guided) game from that new node all the way to an outcome — a win, loss, or draw.
Backpropagation — take that result and propagate it back up through every node visited on the way down, updating each one's win/loss statistics.

Run this loop thousands or millions of times, and the tree naturally grows deeper in the branches that keep winning, while still occasionally sampling the long-shot branches in case they turn out to be secretly brilliant. The selection step typically uses a formula called UCT (Upper Confidence bounds applied to Trees), introduced by Levente Kocsis and Csaba Szepesvári in 2006, which borrows from the mathematics of multi-armed bandit problems — the same math casinos and clinical-trial designers use to decide, with limited information, which slot machine (or drug, or ad) is worth trying next.

Why It Matters

MCTS was formalized by French computer scientist Rémi Coulom in a 2006 paper, "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search," which he used to build Crazy Stone, a 9x9 Go program that went on to win the 10th KGS computer-Go tournament. Before this, Go had stubbornly resisted the techniques — like the minimax search with alpha-beta pruning — that let IBM's Deep Blue beat Garry Kasparov at chess in 1997. Go's branching factor is so enormous, and its positions so hard to evaluate numerically, that traditional search choked on it. MCTS, with its ability to make reasonable guesses without fully understanding a position, was the first approach that actually worked.

A decade later, DeepMind combined MCTS with deep neural networks to build AlphaGo. Instead of running purely random rollouts, AlphaGo used a "policy network" (trained on human expert games and refined through self-play) to suggest which moves were worth exploring, and a "value network" to estimate how good a position was without even finishing the simulated game. MCTS supplied the search structure; the neural networks supplied the intuition. In October 2015, AlphaGo beat European champion Fan Hui 5 games to 0 — the first time a program had beaten a professional Go player on a full-size board without a handicap. The result made the cover of Nature in January 2016. Two months later, AlphaGo faced a far tougher test: Lee Sedol, widely considered one of the greatest Go players of the preceding decade, in a five-game match in Seoul. AlphaGo won 4-1, in a result that stunned a field of AI researchers who had, only a year or two earlier, predicted Go-playing AI capable of beating top humans was still a decade away.

What made Move 37 remarkable wasn't that a computer calculated it — it's that no one, including AlphaGo's own creators, had taught it that move. It emerged from the tree search genuinely exploring a region of possibility space that centuries of human Go theory had passed over. Commentators initially estimated that a human professional would play that move roughly 1 in 10,000 times. It turned out to be winning.

The Details

The exploration-versus-exploitation tension at the heart of MCTS is worth sitting with, because it shows up everywhere decisions have to be made under uncertainty. Picture a gambler at a row of slot machines (the actual "multi-armed bandit" of the math) with no idea which machine pays out best. Playing only the machine that's paid out so far might mean missing a better one you've barely tried. But spending all your time trying new machines means never cashing in on the one that's actually good. UCT's formula for picking which branch to explore next balances the two with a term that rewards a move's average performance so far, plus a bonus that grows the less that move has been tried — so neglected branches eventually get another look, but the balance always tilts back toward what's working.

Visually, if you could watch an MCTS search tree grow in real time, it would look less like a balanced, symmetric tree and more like a sprawling root system — a few thick, deeply explored branches running fifty moves deep, surrounded by a dense fuzz of shallow, barely-touched offshoots, each one a move the algorithm glanced at, decided wasn't promising, and left behind. The "thickness" of a branch corresponds to how many simulations have run through it; the thickest path is, roughly, the algorithm's current best guess at the right move.

MCTS's real trick is that each individual rollout is cheap and dumb — a fast, rough simulation to a conclusion rather than a careful, exhaustive evaluation — but in aggregate, across millions of them, something close to genuine judgment emerges. This is a pattern that recurs throughout both AI and statistics: large numbers of simple, biased-but-noisy estimates, averaged correctly, outperform a single expensive attempt at perfect calculation.

That generality is why MCTS escaped the Go board entirely. DeepMind's AlphaZero used the same MCTS-plus-neural-network formula to master chess and shogi from scratch in 2017, with no human game data at all — just the rules and self-play. Chemists have used MCTS to plan retrosynthesis routes — working backward from a target molecule to figure out which sequence of simpler, buyable chemical reactions could build it, the way AlphaChem and its successor AiZynthFinder do. Researchers have applied it to scheduling problems like forest-harvest planning and vehicle routing, where the "moves" are decisions about what to do next and the "win" is an efficient, low-cost plan. In each case, the common thread is the same: a space of choices too large to search exhaustively, and a way to simulate an outcome if you commit to a path.

Takeaways

Monte Carlo Tree Search makes intractable decision problems tractable by trading exhaustive certainty for many cheap, randomized simulations — the law of large numbers does the real work.
It was formalized by Rémi Coulom in 2006 for the Go program Crazy Stone, built on the UCT algorithm from Kocsis and Szepesvári, itself borrowed from multi-armed bandit theory.
AlphaGo paired MCTS with deep neural networks to beat Fan Hui (5-0, October 2015) and then world-class champion Lee Sedol (4-1, March 2016) — a result researchers hadn't expected for another decade.
"Move 37" became famous precisely because it emerged from genuine search rather than imitation of human play — a rare, verifiable instance of a machine finding a strategic idea humans had collectively missed.
The same explore-versus-exploit logic now shows up well outside of games — in drug trials, chemical synthesis planning, and vehicle routing — anywhere decisions have to be made by simulating ahead under uncertainty.

Resources: - Monte Carlo tree search — Wikipedia - Coulom, "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search" (2006) - AlphaGo versus Lee Sedol — Wikipedia