Introduction

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.

Try It: Watch the Tree Grow

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 (Player 1 โ€“ blue)</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>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">MCTS simulation budget (300 rollouts per move)</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Number-picking game equivalent to tic-tac-toe via a 3ร—3 magic square.
// Players alternate picking numbers 1-9 (no repeats).
// First player with THREE numbers summing to 15 wins.
//
// Magic square (every row/col/diag sums to 15):
//   2 | 7 | 6
//   9 | 5 | 1
//   4 | 3 | 8
//
// Win triples (all 8 lines of the magic square):
// [2,7,6],[9,5,1],[4,3,8],[2,9,4],[7,5,3],[6,1,8],[2,5,8],[6,5,4]
// โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const WIN_TRIPLES = [
  [2,7,6],[9,5,1],[4,3,8],
  [2,9,4],[7,5,3],[6,1,8],
  [2,5,8],[6,5,4]
];

function checkWin(nums) {
  for (const [a,b,c] of WIN_TRIPLES)
    if (nums.includes(a) && nums.includes(b) && nums.includes(c)) return true;
  return false;
}

function available(p1, p2) {
  const taken = new Set([...p1, ...p2]);
  return [1,2,3,4,5,6,7,8,9].filter(n => !taken.has(n));
}

// โ”€โ”€ MCTS โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const C_EXPLORE = Math.SQRT2;

function randomPlayout(p1, p2, turnIsP2) {
  p1 = [...p1]; p2 = [...p2];
  let avail = available(p1, p2);
  let t = turnIsP2; // true = MCTS turn (p2), false = human turn (p1)
  while (avail.length > 0) {
    const pick = avail[Math.floor(Math.random() * avail.length)];
    if (t) p2.push(pick); else p1.push(pick);
    if (checkWin(t ? p2 : p1)) return t ? 1 : 0; // 1=p2 wins, 0=p1 wins
    avail = available(p1, p2);
    t = !t;
  }
  return -1; // draw
}

// Returns { move, stats[] } where stats = array of { move, visits, wins }
function mcts(p1, p2, simulations) {
  const avail = available(p1, p2);
  if (avail.length === 0) return null;

  const nodes = avail.map(m => ({ move: m, visits: 0, wins: 0 }));

  for (let i = 0; i < simulations; i++) {
    const total = nodes.reduce((s, n) => s + n.visits, 0);
    let chosen;
    if (total < nodes.length) {
      // Initialise all nodes once before UCB
      chosen = nodes[i < nodes.length ? i : Math.floor(Math.random() * nodes.length)];
    } else {
      let best = -Infinity;
      for (const nd of nodes) {
        const ucb = nd.visits === 0
          ? Infinity
          : nd.wins / nd.visits + C_EXPLORE * Math.sqrt(Math.log(total) / nd.visits);
        if (ucb > best) { best = ucb; chosen = nd; }
      }
    }

    // Expand: p2 picks chosen.move
    const newP2 = [...p2, chosen.move];
    let result;
    if (checkWin(newP2)) {
      result = 1; // p2 wins immediately
    } else if (available(p1, newP2).length === 0) {
      result = -1; // draw
    } else {
      result = randomPlayout(p1, newP2, false); // next turn = p1
    }
    chosen.visits++;
    if (result === 1) chosen.wins++;
  }

  // Robust child: most visited
  const best = nodes.reduce((a, b) => b.visits > a.visits ? b : a);
  return { move: best.move, stats: nodes };
}

// โ”€โ”€ Game state โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let p1 = [], p2 = [], gameOver = false;
const SIMS = 300;

function renderBars(stats) {
  const barsEl = document.getElementById('tree-bars');
  barsEl.innerHTML = '';
  if (!stats) { barsEl.textContent = 'Pick a number to see MCTS think.'; return; }
  const maxV = Math.max(...stats.map(s => s.visits), 1);
  for (const nd of [...stats].sort((a,b) => b.visits - a.visits)) {
    const pct = (nd.visits / maxV * 100).toFixed(1);
    const wr = nd.visits > 0 ? (nd.wins / nd.visits * 100).toFixed(0) + '%' : 'โ€”';
    const row = document.createElement('div');
    row.className = 'tree-row';
    row.innerHTML =
      fmt('<span class="tree-label">%move%</span><span class="tree-bar-wrap"><span class="tree-bar" style="width:%pct%%"></span></span><span class="tree-stat">%visits%v / %wr%</span>', { move: nd.move, pct: pct, visits: nd.visits, wr: wr });
    barsEl.appendChild(row);
  }
}

function updateButtons() {
  document.querySelectorAll('.num-btn').forEach(btn => {
    const n = +btn.dataset.n;
    btn.disabled = gameOver || p1.includes(n) || p2.includes(n);
    btn.className = 'num-btn' +
      (p1.includes(n) ? ' taken-p1' : p2.includes(n) ? ' taken-p2' : '');
  });
  document.getElementById('p1-nums').textContent = p1.length ? p1.sort((a,b)=>a-b).join(', ') : 'โ€”';
  document.getElementById('p2-nums').textContent = p2.length ? p2.sort((a,b)=>a-b).join(', ') : 'โ€”';
}

function endCheck() {
  const res = document.getElementById('result-bar');
  const tl = document.getElementById('turn-label');
  if (checkWin(p1)) {
    res.textContent = 'You win! You found a winning sequence.'; res.className = 'win';
    gameOver = true; tl.textContent = 'Game over';
    return true;
  }
  if (checkWin(p2)) {
    res.textContent = 'MCTS wins! It navigated to a forced sequence.'; res.className = 'lose';
    gameOver = true; tl.textContent = 'Game over';
    return true;
  }
  if (available(p1, p2).length === 0) {
    res.textContent = 'Draw โ€” no player formed a sum-to-15 triple.'; res.className = 'draw';
    gameOver = true; tl.textContent = 'Game over';
    return true;
  }
  return false;
}

document.querySelectorAll('.num-btn').forEach(btn => {
  btn.addEventListener('click', () => {
    if (gameOver) return;
    const n = +btn.dataset.n;
    if (p1.includes(n) || p2.includes(n)) return;

    p1.push(n);
    updateButtons();
    if (endCheck()) { renderBars(null); return; }

    document.getElementById('turn-label').textContent = 'MCTS is thinkingโ€ฆ';
    setTimeout(() => {
      const res = mcts(p1, p2, SIMS);
      if (res) {
        p2.push(res.move);
        document.getElementById('turn-label').textContent = 'Your turn (Player 1 โ€“ blue)';
        updateButtons();
        endCheck();
        renderBars(res.stats);
      }
    }, 20);
  });
});

document.getElementById('reset-btn').addEventListener('click', () => {
  p1 = []; p2 = []; gameOver = false;
  document.getElementById('result-bar').textContent = '';
  document.getElementById('result-bar').className = '';
  document.getElementById('turn-label').textContent = 'Your turn (Player 1 โ€“ blue)';
  updateButtons();
  renderBars(null);
});

// โ”€โ”€ Self-test (runs silently in the console) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
(function selfTest() {
  // checkWin basics
  console.assert(checkWin([2,7,6]), 'row win OK');
  console.assert(checkWin([2,5,8]), 'diag win OK');
  console.assert(!checkWin([1,2,3]), 'no win OK');
  // available
  console.assert(available([1,2,3],[4,5,6]).join(',') === '7,8,9', 'available OK');
  // mcts from empty โ†’ 5 stats with visits
  const r0 = mcts([], [], 100);
  console.assert(r0 && r0.stats.length === 9, fmt('stats length 9: got %v%', { v: r0 && r0.stats.length }));
  // forced win: p2 has [2,7], avail includes 6; picking 6 wins (2+7+6=15)
  const fw = mcts([1,3], [2,7], 500);
  console.assert(fw && fw.move === 6, fmt('forced win move=6: got %v%', { v: fw && fw.move }));
  // forced block: p1 has [2,7], p2 must pick 6 to block
  const fb = mcts([2,7], [1,3], 500);
  console.assert(fb && fb.move === 6, fmt('forced block move=6: got %v%', { v: fb && fb.move }));
  console.log('MCTS self-test passed. Forced win:', fw.move, 'Forced block:', fb.move);
})();

updateButtons();
renderBars(null);
Result
Console

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.

The Real Complexity

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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/monte-carlo-tree-search/Content licensed under CC BY-NC 4.0.