Introduction

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 1017010^{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.

Try It: MCTS and Self-Play

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">
  Two players pick a number 1–3 in turns; first to hit <b>exactly 15</b> wins.<br>
      <b>You</b> are Player 1 (blue). MCTS chooses for Player 2 (red).<br>
      Press <b>Run MCTS</b> to watch it think, then <b>Make move</b> to play the top choice.
</p>
<div class="scoreboard">
  <span id="total-label">Running total: <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 1</button>
  <button id="btn2" class="move-btn" data-v="2">Pick 2</button>
  <button id="btn3" class="move-btn" data-v="3">Pick 3</button>
</div>
<div class="ctrl-row">
  <button id="run-mcts">Run MCTS (500 rollouts)</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// MCTS on the "sum-to-15" game.
// State: { total, turn }  turn=0 player, turn=1 AI
// Moves: pick 1, 2, or 3 (but cannot overshoot 15)
// Win: reach exactly 15. If no legal move exists (total > 12 and all moves overshoot) = loss.
const WIN_TARGET = 15;
const CHOICES = [1, 2, 3];

function legalMoves(total) {
  return CHOICES.filter(v => total + v <= WIN_TARGET);
}

// Check terminal: returns 1 if `turn` just won, -1 if stuck, 0 if ongoing
function terminalScore(total, justPlayed) {
  if (total === WIN_TARGET) return 1; // justPlayed wins
  if (legalMoves(total).length === 0) return -1; // no moves = loss for next player
  return 0;
}

// ─── MCTS ────────────────────────────────────────────────────────────────
const UCB_C = 1.41;
function ucb(node, parentVisits) {
  if (node.visits === 0) return Infinity;
  return node.wins / node.visits + UCB_C * Math.sqrt(Math.log(parentVisits) / node.visits);
}

function makeNode(total, turn, move) {
  return { total, turn, move, wins: 0, visits: 0, children: null };
}

function expand(node) {
  const moves = legalMoves(node.total);
  node.children = moves.map(v => makeNode(node.total + v, 1 - node.turn, v));
}

function rollout(total, turn) {
  // Random rollout from current state; returns 1 if AI (turn=1) eventually wins, else 0
  let t = total, p = turn;
  while (true) {
    const moves = legalMoves(t);
    if (t === WIN_TARGET) { return p === 0 ? 1 : 0; } // previous player won
    if (moves.length === 0) { return p === 1 ? 1 : 0; } // current player stuck = win for other
    const pick = moves[Math.floor(Math.random() * moves.length)];
    t += pick;
    p = 1 - p;
  }
}

function mcts(rootTotal, rootTurn, numRollouts) {
  const root = makeNode(rootTotal, rootTurn, null);
  expand(root);
  for (let i = 0; i < numRollouts; i++) {
    // Selection
    let node = root;
    const path = [node];
    while (node.children && node.children.length > 0 && node.visits > 0) {
      const best = node.children.reduce((a, b) => ucb(a, node.visits) >= ucb(b, node.visits) ? a : b);
      node = best;
      path.push(node);
      if (node.children === null) {
        if (node.visits > 0) expand(node);
      }
      if (node.total === WIN_TARGET || legalMoves(node.total).length === 0) break;
    }
    // Simulation
    const result = rollout(node.total, node.turn);
    // Backprop
    for (const n of path) {
      n.visits++;
      // AI is turn=1; store wins from AI perspective
      if (result === 1) n.wins++;
    }
  }
  return root;
}

// ─── UI ──────────────────────────────────────────────────────────────────
let state = { total: 0, turn: 0 }; // turn 0 = human, 1 = AI
let lastRoot = null;

function setLog(msg) { document.getElementById('log').textContent = msg; }
function setTurnLabel(txt, cls) {
  const el = document.getElementById('turn-label');
  el.textContent = txt; el.className = cls || '';
}

function renderBars(root) {
  const chart = document.getElementById('bar-chart');
  chart.innerHTML = '';
  if (!root || !root.children || root.children.length === 0) return;
  const maxV = Math.max(...root.children.map(c => c.visits), 1);
  const bestIdx = root.children.reduce((bi, c, i, arr) => c.visits > arr[bi].visits ? i : bi, 0);
  root.children.forEach((c, i) => {
    const h = Math.round((c.visits / maxV) * 70);
    const wrap = document.createElement('div'); wrap.className = 'bar-wrap';
    const bar = document.createElement('div'); bar.className = 'bar' + (i === bestIdx ? ' best' : '');
    bar.style.height = h + 'px';
    const lbl = document.createElement('div'); lbl.className = 'bar-label';
    lbl.textContent = fmt('Pick %move%', { move: c.move });
    const vis = document.createElement('div'); vis.className = 'bar-visits';
    vis.textContent = fmt('%visits% visits', { visits: c.visits });
    wrap.appendChild(bar); wrap.appendChild(lbl); wrap.appendChild(vis);
    chart.appendChild(wrap);
  });
}

function updateUI() {
  document.getElementById('total').textContent = state.total;
  const isDone = state.total === WIN_TARGET || legalMoves(state.total).length === 0;
  const isHumanTurn = state.turn === 0 && !isDone;
  document.querySelectorAll('.move-btn').forEach(b => {
    const v = +b.dataset.v;
    b.disabled = !isHumanTurn || state.total + v > WIN_TARGET;
  });
  document.getElementById('run-mcts').disabled = isDone || state.turn !== 1;
  document.getElementById('make-move').disabled = true;
  if (isDone) {
    if (state.total === WIN_TARGET) {
      setTurnLabel(state.turn === 0 ? 'AI wins! Reset to play again.' : 'You win! Reset to play again.', 'done');
    } else {
      setTurnLabel('No legal moves — other player wins! Reset.', 'done');
    }
  } else if (state.turn === 0) {
    setTurnLabel('Your turn (Player 1)', '');
  } else {
    setTurnLabel('AI thinking… (run MCTS)', 'red');
  }
}

function humanMove(v) {
  if (state.turn !== 0) return;
  state.total += v;
  if (state.total === WIN_TARGET) { updateUI(); setLog('You reached 15 — you win!'); return; }
  if (legalMoves(state.total).length === 0) { updateUI(); setLog('No moves left after your pick.'); return; }
  state.turn = 1;
  lastRoot = null;
  renderBars(null);
  updateUI();
  setLog(fmt('You picked %v%. Total = %total%. Now run MCTS for AI.', { v: v, total: state.total }));
}

document.querySelectorAll('.move-btn').forEach(b => {
  b.addEventListener('click', () => humanMove(+b.dataset.v));
});

document.getElementById('run-mcts').addEventListener('click', () => {
  if (state.turn !== 1) return;
  const root = mcts(state.total, 1, 500);
  lastRoot = root;
  renderBars(root);
  document.getElementById('make-move').disabled = false;
  const bestChild = root.children.reduce((a, b) => a.visits >= b.visits ? a : b);
  const winRate = root.visits > 0 ? Math.round((root.wins / root.visits) * 100) : 0;
  setLog(fmt('MCTS ran 500 rollouts. Best move: Pick %move% (%visits% visits)). AI win-rate from here: %winRate%%.', { move: bestChild.move, visits: bestChild.visits, winRate: winRate }));
});

document.getElementById('make-move').addEventListener('click', () => {
  if (!lastRoot || state.turn !== 1) return;
  const bestChild = lastRoot.children.reduce((a, b) => a.visits >= b.visits ? a : b);
  const v = bestChild.move;
  state.total += v;
  lastRoot = null;
  if (state.total === WIN_TARGET) {
    state.turn = 0; updateUI(); renderBars(null);
    setLog(fmt('AI picked %v%. Total = %total%. AI wins!', { v: v, total: state.total })); return;
  }
  if (legalMoves(state.total).length === 0) {
    state.turn = 0; updateUI(); renderBars(null);
    setLog(fmt('AI picked %v%. Total = %total%. No moves left.', { v: v, total: state.total })); return;
  }
  state.turn = 0;
  renderBars(null);
  updateUI();
  setLog(fmt('AI picked %v%. Total = %total%. Your turn!', { v: v, total: state.total }));
});

document.getElementById('reset').addEventListener('click', () => {
  state = { total: 0, turn: 0 }; lastRoot = null;
  renderBars(null); updateUI(); setLog('Game reset. You go first.');
});

updateUI();
setLog('Pick a number to start. The AI uses MCTS to plan its replies.');
Result
Console

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.

The Real Complexity

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 250200250^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/alphago-self-play/Content licensed under CC BY-NC 4.0.