Monte Carlo Tree Search

In 2016, AlphaGo defeated Lee Sedol — one of the strongest Go players in history — 4-1. Go had long been considered the last fortress where human intuition would outpace machines. The board is 19×19; the number of legal positions dwarfs atoms in the observable universe. Classic minimax search with alpha-beta pruning, the engine behind chess programs, simply cannot crawl that tree fast enough.

AlphaGo's foundation was Monte Carlo Tree Search (MCTS), an algorithm invented in 2006 by Rémi Coulom and developed independently by Levente Kocsis and Csaba Szepesvári. Instead of evaluating positions with a handcrafted heuristic, MCTS plays out random games from each candidate move, uses the win rate as a score, and spends more computation on moves that look promising — while never completely abandoning the rest.

That balance — between exploiting what looks best and exploring what might be better — is controlled by a formula called UCB1 (Upper Confidence Bound). It is the same principle used to decide which banner ad to show, which drug to test next in a clinical trial, and how a robot should map an unknown room. Understanding MCTS means understanding one of the most versatile ideas in all of computer science.

The demo below runs MCTS on a tiny game: two players alternately pick numbers from 1 to 5 (without repeats) and the first to hold three numbers that sum to 15 wins (this is equivalent to tic-tac-toe on a magic square). You play as Player 1 (blue); MCTS plays as Player 2 (red).

<div id="app">
  <div id="info-bar">
    <span id="turn-label">{{your_turn}}</span>
  </div>
  <div id="number-row">
    <button class="num-btn" data-n="1">1</button>
    <button class="num-btn" data-n="2">2</button>
    <button class="num-btn" data-n="3">3</button>
    <button class="num-btn" data-n="4">4</button>
    <button class="num-btn" data-n="5">5</button>
    <button class="num-btn" data-n="6">6</button>
    <button class="num-btn" data-n="7">7</button>
    <button class="num-btn" data-n="8">8</button>
    <button class="num-btn" data-n="9">9</button>
  </div>
  <div id="chosen">
    <div id="p1-chosen"><strong>{{label_you}}</strong> <span id="p1-nums">—</span></div>
    <div id="p2-chosen"><strong>MCTS:</strong> <span id="p2-nums">—</span></div>
  </div>
  <div id="tree-section">
    <div id="tree-title">{{tree_title}}</div>
    <div id="tree-bars"></div>
  </div>
  <div id="result-bar"></div>
  <button id="reset-btn" type="button">{{new_game}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
#app { padding: .6rem; max-width: 500px; margin: 0 auto; }
#info-bar { font-weight: 600; font-size: .95rem; margin-bottom: .5rem; }
#number-row { display: flex; gap: .3rem; margin-bottom: .6rem; flex-wrap: wrap; }
.num-btn { flex: 1; min-width: 42px; height: 44px; font-size: 1.15rem; font-weight: 700;
           border-radius: 9px; border: 2px solid #1d3557; background: #fff;
           color: #1d3557; cursor: pointer; transition: background .12s, color .12s; }
.num-btn:hover:not(:disabled) { background: #e8eef3; }
.num-btn:disabled { opacity: .38; cursor: default; }
.num-btn.taken-p1 { background: #3b82f6; border-color: #2563eb; color: #fff; }
.num-btn.taken-p2 { background: #ef4444; border-color: #dc2626; color: #fff; }
#chosen { display: flex; gap: 1.5rem; font-size: .9rem; margin-bottom: .6rem; }
#p1-chosen { color: #2563eb; } #p2-chosen { color: #dc2626; }
#tree-section { background: #f4f7fa; border-radius: 10px; padding: .5rem .7rem;
                margin-bottom: .5rem; min-height: 90px; }
#tree-title { font-size: .78rem; color: #666; margin-bottom: .3rem; }
.tree-row { display: flex; align-items: center; gap: .4rem; margin-bottom: .22rem; font-size: .82rem; }
.tree-label { width: 22px; text-align: center; font-weight: 700; color: #444; }
.tree-bar-wrap { flex: 1; background: #dde4ec; border-radius: 4px; height: 13px; overflow: hidden; }
.tree-bar { height: 100%; background: #ef4444; border-radius: 4px; transition: width .2s; }
.tree-stat { width: 74px; text-align: right; color: #555; font-size: .78rem; }
#result-bar { font-size: 1rem; font-weight: 700; min-height: 1.3em; margin-bottom: .4rem;
              text-align: center; }
.win { color: #15803d; } .lose { color: #dc2626; } .draw { color: #78350f; }
#reset-btn { display: block; margin: 0 auto; padding: .4rem 1.2rem; border-radius: 8px;
             border: 1px solid #1d3557; background: #1d3557; color: #fff;
             font: 600 .9rem system-ui; cursor: pointer; }

// Code not found

After each of your moves, the tree panel shows MCTS spending its simulation budget. Wider bars mean more visits; the score shows the win-rate estimate that UCB1 uses to direct future simulations. Notice how early in the game the tree explores broadly, then narrows onto promising continuations as evidence accumulates.

MCTS is not a complete or optimal algorithm in the traditional sense, but it comes with a powerful theoretical guarantee on how quickly it stops wasting simulations on bad moves.

Each iteration of MCTS has four phases:

• Selection: starting from the root, follow the child with the highest UCB1 score until you reach a node that has unvisited children.
• Expansion: add one unvisited child to the tree.
• Simulation (rollout): play the game randomly to the end from that new node.
• Backpropagation: walk back up the tree, updating each ancestor's visit count and win total.

The UCB1 formula for choosing a child node is: UCB1 = w/n + C · √(ln N / n), where w is wins, n is visits to that child, N is total parent visits, and C is an exploration constant (typically √2). The first term exploits what looks best; the second term, which grows as n stays small relative to N, pushes the algorithm to revisit under-explored branches.

Regret bound: Kocsis and Szepesvári (2006) proved that MCTS with UCB1 has logarithmic regret — after T simulations it misses the optimal move by at most $O(\log T / T)$ per node. That is as good as any algorithm can do without prior knowledge, matching the information-theoretic lower bound for bandit problems.

Limitations: MCTS is an anytime algorithm — it improves with more simulations but never guarantees finding the minimax-optimal move. In games with very deep forced lines (like chess endgames) or positions where the winning move is "quiet" (no immediate tactical threat), random playouts may never discover it. That is why AlphaGo combined MCTS with a deep neural network value function trained on human games: the neural net replaced the random rollout with a learned position evaluator, and a separate policy network guided the selection step. See neural network training for how that learning works.

The exploration-exploitation framework at the heart of MCTS appears everywhere a decision must be made under uncertainty with limited resources:

• Game AI: MCTS is the engine in AlphaGo (2016), AlphaZero (2017), and many open-source Go/chess engines. AlphaZero generalized the approach to chess and shogi with no domain knowledge beyond the rules.
• Drug discovery: clinical trials must allocate patients across drug candidates; UCB-style bandit algorithms assign more patients to drugs showing early promise while still testing alternatives — the same math, higher stakes.
• Robot exploration: a robot mapping an unknown environment must choose between revisiting known safe areas (exploitation) and venturing into unexplored territory (exploration). MCTS planners operate directly in this setting.
• Compiler optimization: choosing the order in which to apply code transformations is a combinatorial search problem; MCTS has been used to search this space faster than random or exhaustive methods.
• Procedural content generation: game designers use MCTS to generate levels, puzzles, and narrative branches that remain challenging but winnable.

Wherever you see a trade-off between "use what you know" and "learn something new," the math of UCB1 is likely nearby. The P vs NP problem reminds us that exhaustive search is often intractable — MCTS is one of the most elegant practical answers to that intractability.

Monte Carlo Tree Search starts with a disarmingly simple idea: when the tree is too large to search completely, play random games and let the statistics guide you. UCB1 turns that into something mathematically rigorous, guaranteeing that the algorithm stops wasting time on bad moves at a rate no algorithm could beat without more information.

The result powered machines to defeat world Go champions — and the same logic schedules clinical trials, plans robot paths, and optimizes compilers. The exploration-exploitation trade-off is one of the deepest recurring patterns in decision-making under uncertainty, and MCTS is its clearest algorithmic expression.

Next time you see an AI make a move that surprises you, it may well have arrived there through thousands of imagined random futures, each one nudging a score and quietly updating a tree — the same tree, grown one playout at a time, that AlphaGo used to change what we thought machines could do.