AlphaGo and Self-Play

In March 2016, a computer program called AlphaGo defeated the world champion Lee Sedol at the ancient board game of Go — four games to one. That result shocked even its creators.

Go had long been considered AI's last frontier in board games. Chess had fallen to Deep Blue in 1997, but Go's 19×19 board has roughly $10^{170}$ legal positions — more than atoms in the observable universe. Brute-force search is hopeless; expert evaluation is hard to encode; and the game's patterns defy simple rules.

AlphaGo's breakthrough came from combining two ideas: Monte Carlo tree search (MCTS), which samples promising lines of play by rolling games out to completion, and deep neural networks trained not on human games alone, but on millions of games the system played against itself. Self-play generated its own data, self-corrected its own mistakes, and gradually built an intuition that surpassed humanity.

This article explores how MCTS works, how self-play acts as an engine of improvement, and what the technique has unleashed beyond Go.

The demo below runs Monte Carlo tree search on a small number-picking game. Two players alternate picking a number from 1 to 3; the first to push the running total to exactly 15 wins. Watch MCTS explore moves, accumulate visit counts, and guide play.

<p class="hint">
  {{hint_text}}
</p>
<div class="scoreboard">
  <span id="total-label">{{running_total_prefix}} <b id="total">0</b> / 15</span>
  <span id="turn-label">{{your_turn}}</span>
</div>
<div id="bar-chart" class="bar-chart"></div>
<div class="move-row">
  <button id="btn1" class="move-btn" data-v="1">{{pick_prefix}} 1</button>
  <button id="btn2" class="move-btn" data-v="2">{{pick_prefix}} 2</button>
  <button id="btn3" class="move-btn" data-v="3">{{pick_prefix}} 3</button>
</div>
<div class="ctrl-row">
  <button id="run-mcts">{{run_mcts}}</button>
  <button id="make-move" disabled>{{make_ai_move}}</button>
  <button id="reset" class="ghost">{{reset}}</button>
</div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
.scoreboard { display: flex; justify-content: space-between; align-items: center;
              background: #e8eef3; border-radius: 8px; padding: .4rem .8rem;
              font-weight: 600; margin-bottom: .5rem; }
#turn-label { color: #1d3557; }
#turn-label.red { color: #c92f3c; }
#turn-label.done { color: #0a7d33; }
.bar-chart { display: flex; gap: 10px; align-items: flex-end; height: 90px;
             margin: .5rem 0; padding: 0 4px; }
.bar-wrap { display: flex; flex-direction: column; align-items: center; flex: 1; }
.bar { width: 100%; border-radius: 4px 4px 0 0; transition: height .25s;
       min-height: 2px; background: #1d3557; }
.bar.best { background: #e63946; }
.bar-label { font-size: .75rem; font-weight: 600; margin-top: 3px; }
.bar-visits { font-size: .7rem; color: #666; }
.move-row { display: flex; gap: .5rem; margin: .4rem 0; }
.move-btn { flex: 1; font: 700 15px system-ui; padding: .5rem;
            background: #1d3557; color: #fff; border: none; border-radius: 8px;
            cursor: pointer; transition: background .15s; }
.move-btn:hover:not(:disabled) { background: #16304a; }
.move-btn:disabled { opacity: .35; cursor: default; }
.ctrl-row { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .38; cursor: default; }
.log { font-size: .8rem; color: #555; margin-top: .4rem; min-height: 2.2em; line-height: 1.5; }

// Code not found

Notice how the visit counts concentrate on the best moves after many simulations. Each playthrough (rollout) is a fast self-play game to the end; the result propagates back up the tree, nudging the statistics toward stronger moves. With enough rollouts the most-visited child converges to the correct winning move — even though the program never received a hand-crafted evaluation function.

Why was Go so hard for machines for so long?

• The search space is astronomical. The average game lasts ~200 moves from ~250 legal options each, giving a game tree of roughly $250^{200}$ nodes. Even with perfect pruning, exhaustive search is out of reach.
• Go is EXPTIME-complete. Generalised Go — deciding if the first player wins on an n×n board — is EXPTIME-complete (Robson, 1983), placing it firmly beyond polynomial-time algorithms. See chess complexity for how game-tree hardness is classified.
• Classical evaluation fails. Chess engines lean on material counts and positional heuristics humans understand. Go's scoring depends on the whole board; no compact formula captures strong play.

AlphaGo attacked this with four components working together:

1. Supervised learning (SL) policy network — trained on 30 million positions from human expert games, it predicts the next move with ~57% accuracy.
2. Reinforcement learning (RL) policy network — the SL network plays against past versions of itself; moves that win more often get higher probability. This is self-play.
3. Value network — a separate network trained on RL self-play positions learns to estimate who is winning without completing the game.
4. MCTS — at decision time, the tree search uses both networks: the policy guides which branches to explore, the value (combined with rollouts) evaluates leaf nodes. The most-visited branch after the search budget is the chosen move.

AlphaZero (2017) went further: no human data at all. Starting from random play, pure self-play produced superhuman Go, chess, and shogi in under 24 hours of training each. See P vs NP for why finding optimal strategies in general-game settings remains wide open.

Self-play as a training paradigm — generating your own experience by playing against yourself — has spread far beyond board games:

• Protein structure prediction: AlphaFold 2 (2020) used iterative self-distillation on predicted structures to achieve near-experimental accuracy, winning the CASP14 competition and accelerating drug discovery across biology.
• Chip design: Google used reinforcement learning (partly inspired by AlphaGo) to place components on silicon chips, beating human engineers on some metrics in hours rather than weeks.
• Robotics and autonomous driving: agents trained by self-play in simulation generalise to the real world, accumulating experience faster than any human-curated dataset could provide.
• Game AI and testing: self-play generates endless, adaptive opponents for testing and training, replacing hand-scripted bots in everything from strategy games to trading simulations.
• Scientific search: MCTS guides molecule generation, chemical synthesis planning, and mathematical theorem proving — any domain where you can self-evaluate candidate solutions.

The key insight AlphaGo gave us: when the rules of a domain are known, self-play turns the problem of finding training data into the problem of running fast simulations. That shift unlocks scales of experience no human could ever annotate.

AlphaGo did something deeper than beating a Go champion: it demonstrated that a machine can surpass human expertise in an EXPTIME-hard domain without ever being told what good looks like — only what winning looks like.

The recipe — combine a fast self-play data generator with a neural network that learns to evaluate and a tree search that guides exploration — has proven surprisingly general. From proteins to chips, from chemistry to theorems, the same loop applies wherever you can simulate outcomes faster than humans can label them.

Self-play is, at its core, a way to bootstrap intelligence from the rules alone. And that may be one of the most important algorithmic ideas of the century. See P vs NP to understand why finding guaranteed optimal strategies in such domains remains one of the deepest open questions in computer science.