Monte Carlo Tree Search (MCTS) picks a move the same way minimax does — by estimating how good each option is before committing to one — but it never visits the whole tree, and it never needs a hand-written evaluation function for positions that aren't finished games. Instead it runs many random playouts (finish the game with random moves and see who wins) and lets the statistics accumulate: a move that keeps winning its random playouts gets searched more, a move that keeps losing gets searched less. Four steps repeat, over and over — selection (walk down the tree favoring moves that have looked good, but not exclusively), expansion (add one new node the tree hasn't tried yet), simulation (finish that game with random moves), and backpropagation (carry the result back up, updating every node on the path) — and the move with the most visits when the budget runs out is the one it plays.
Same fixed board as the minimax page, O to move, so the two are
directly comparable: X X O / _ _ X / _ O _. Minimax proved cell 6 is a forced win for O.
This demo never gets told that — it only ever sees random-playout win/loss counts. Press
Step to run one simulation (selection → expansion → simulation → backpropagation) or
Run to play through all 200. Watch the bars: each is a candidate move for O, its width is
the share of simulations spent exploring it so far, and the label carries the exact visit count and win
rate. The random playouts use a seeded random number generator fixed at page load, not
Math.random() — see Pitfalls for why.
The move each root bar leads to is a child of the root node; every node the tree has created tracks
two numbers, visits N and accumulated wins W (a draw counts as half a win).
Selection needs to choose, at every node with more than one already-tried child, which child to descend
into — and the choice is a real tension: keep visiting the child that's won the most so far
(exploit), or spend a visit on a child that hasn't been tried much, just in case its true
win rate is actually better (explore). UCB1 resolves that tension with
one formula, computed for each child c of the node currently being descended from (whose own
visit count is N):
UCB1(c) = c.W / c.N + √2 · √(ln(N) / c.N)The first term is exploitation — c's own win rate. The second is exploration — it grows
whenever c is visited less than its siblings (small c.N relative to
ln(N) makes the fraction large), so a long-neglected child eventually looks attractive again
no matter how poorly it scored the one time it was tried. Selection always picks the child with the
highest UCB1 score; once a node has an untried move left, expansion adds it as a new child instead of
selecting among the existing ones. Simulation then plays uniformly random legal moves from that new
node to a finished game, and backpropagation adds one visit — and a win, for whichever node's own move
led to that outcome — to every node on the path back to the root.
Nothing here ever computes a full game tree, and nothing needs to know tic-tac-toe's rules beyond "is this move legal" and "who just won" — the same algorithm, unchanged, plays chess or Go by swapping in their legal-move and win-check functions, which is exactly why it scales to games too large for exhaustive search where minimax's own approach runs out of room (see Complexity below).
function ucb1(child, parentVisits) {
return child.wins / child.visits
+ Math.SQRT2 * Math.sqrt(Math.log(parentVisits) / child.visits);
}
function select(node) {
// descend while every legal move already has a child
while (!node.winner && node.untried.length === 0 && node.children.length > 0) {
node = node.children.reduce((best, c) =>
ucb1(c, node.visits) > ucb1(best, node.visits) ? c : best
);
}
return node;
}
function expand(node) {
if (node.winner || node.untried.length === 0) return node;
const move = node.untried.shift();
const child = makeChild(node, move); // applies move, records who made it
node.children.push(child);
return child;
}
function simulate(node, rng) {
const board = node.board.slice();
let mover = node.toMove;
let winner = winnerOf(board);
while (!winner) {
const moves = legalMoves(board);
if (moves.length === 0) break; // draw
board[moves[Math.floor(rng() * moves.length)]] = mover;
winner = winnerOf(board);
mover = other(mover);
}
return winner; // null means draw
}
function backpropagate(node, winner) {
for (let n = node; n; n = n.parent) {
n.visits++;
if (n.moveMark === winner) n.wins += 1;
else if (!winner) n.wins += 0.5;
}
}
function mctsSearch(root, iterations, rng) {
for (let i = 0; i < iterations; i++) {
const expanded = expand(select(root));
backpropagate(expanded, simulate(expanded, rng));
}
// "robust child": most-visited, not highest win rate — see Pitfalls
return root.children.reduce((a, b) => (b.visits > a.visits ? b : a));
}This demo's randomness is seeded, not real — worth being upfront about that. Every
playout draws from mulberry32, the same deterministic generator
skip list's preload uses, fixed to the same seed on
every page load and every Reset. That's what makes every number in this page reproducible and checkable —
a real MCTS implementation reseeds from actual entropy every run and will play out differently each time,
including sometimes picking a different move at low simulation counts (see the next Pitfall). Reproducibility
here trades away the "different every time" liveliness a production implementation would have.
With too few simulations, the visit leader can be the wrong move — and it isn't even a clean one-time flip. Checked directly on this page's own seed: after 20 simulations, cell 4 leads with 7 visits (cell 6, the actual forced win, has only 5). Cell 6 briefly takes the lead at simulation 25 (8 visits to cell 4's 7) — then loses it again, with cell 4 back in front for simulations 26 through 34, before cell 6 finally takes the lead for good at simulation 35. Run the demo with Step and watch it happen — this isn't a contrived worst case, it's exactly what the default seed does. Stop MCTS early — because of a time budget, say — and it can confidently recommend a move that isn't the best one, and even "it's been winning for a while" isn't a safe signal to stop on early, exactly the failure mode minimax's exhaustive search structurally cannot have (given enough time, minimax is always exactly right; MCTS given enough time converges to being right, but "enough" is a real, unbounded amount, not a guarantee at any fixed simulation count).
Visit count and win rate can disagree about which child is best — that's why the final answer
uses visits, not rate. At simulation 33 on this page's own seed, cell 4 has the most visits (11)
while cell 6 has the higher win rate (6/10 = 60% against cell 4's 6.5/11 ≈ 59%) — the two metrics point at
different cells. A node's visit count is indirect evidence of how much UCB1's own exploration term already
trusted it (a high-win-rate child with almost no visits hasn't been tested enough to trust yet); that's why
the standard final choice — the "robust child" — is most visited, not highest win rate,
and why this page's own mctsSearch above returns exactly that.
The exploration constant is a knob, not a law. √2 is the theoretically
motivated value for rewards scaled to [0, 1] (which win/loss/draw already are here) — this
page doesn't explore other values, but raising it searches more broadly at the cost of exploiting known-good
moves more slowly, and lowering it does the reverse; tuning it per-game is a real, common practice this
page doesn't demonstrate.
Time: each simulation costs O(d) — one pass down the tree, however deep
it currently is, plus one random playout to a finished game — so n simulations cost
O(n·d) total, with no dependence on the branching factor b the way minimax's
O(b^d) does. That's the entire point: MCTS's cost is a budget you choose (how many
simulations to run), not a size the game forces on you. Space: O(n) in the
worst case — one new tree node per simulation's expansion step, capped by the total number of reachable
positions, whichever is smaller.
Checked, not just claimed: an offline sweep ran this exact algorithm (same code as above, extracted
from the shipped page) across 200 different seeds, 200 simulations each, on this page's own board. The
most-visited child matched minimax's proven answer — cell 6 — in all 200 of 200 runs.
That's the empirical case for MCTS on a board small enough to check against a known-correct answer;
minimax itself remains the right tool whenever the tree is small enough to search exhaustively; MCTS earns
its keep on games where b^d is too large for that to ever finish — a 19×19 Go board's opening
branching factor is 361, deep enough that no computer has ever searched it exhaustively, and MCTS
(paired with a learned evaluation function, in modern engines) is the approach that made strong computer
Go possible at all.
This is the site's second Game Trees entry, alongside Minimax with Alpha-Beta Pruning — same adversarial two-player setting and the same question ("what should I play right now"), answered by exhaustive-but-prunable search in one case and by random sampling with a principled explore/exploit rule in the other. Neither one fits a game with no adversary at all, just plain chance — a die roll, a random tile spawn — which is what Expectimax is for. All three decide a position's value by search or sampling; Transposition Tables instead caches a value once it's been derived, so a repeated position never gets re-decided at all. A fifth entry, Principal Variation Search, doesn't touch sampling or chance either — it's a refinement of exhaustive minimax search specifically, restated in negamax's single-function form and given a cheap scout question to ask before every expensive one. A sixth, Iterative Deepening, sits closest to this page's own trade-off of all six: search cheaply and reuse what's learned — but across successive fixed-depth minimax passes instead of random playouts, always keeping a complete, usable answer on hand the instant time runs out, the same anytime guarantee MCTS makes by a completely different mechanism. A seventh, Zobrist Hashing, doesn't touch sampling, chance, or search depth either — it's the incremental-key technique behind Transposition Tables' own cache, irrelevant here since this page's random playouts never revisit or cache a position by design. See Choosing a Game Tree Search Algorithm for how all ten compare side by side, including when a lack of any reliable static evaluator is exactly what should send you here instead of Iterative Deepening's own heuristic-based fallback.