Monte Carlo Tree Search, Playable

EP 01

Grow a tree of futures — the four-beat loop

One MCTS "playout" has four beats: select a promising path down the tree, expand one new node at its edge, simulate the rest of the game with random moves, and back up the result along the path. That's it — repeated thousands of times. Below is a real tic-tac-toe position (X to move). Press the button and watch the tree grow: node size = visit count, the mustard trail = the path of the last playout.

Every playout finishes the game with purely random moves — no chess-master rules anywhere. The intelligence comes only from counting which starts led to wins.

The magic: visits pile up on good moves automatically, because paths that keep winning keep getting selected. AlphaGo's tree worked exactly like this one — just with a neural network instead of random moves for the "simulate" beat, and millions of playouts instead of hundreds.

EP 02

The exploration dial — one formula decides where to look next

Inside every tree node lives a tug-of-war: keep visiting the move that looks best (exploit), or give neglected moves another chance (explore)? MCTS settles it with the UCB score: average win rate + c·√(ln N / n). Below are five slot machines with hidden win rates. The white bar is what the algorithm has measured; the mustard cap is its exploration bonus, which shrinks as a machine gets pulled. Drag c and watch the strategy change character.

exploration c 1.4

c = 1.4 — the classic UCB1 balance: mostly exploit, but never let any arm's uncertainty grow unchecked.

Try to break it: set c = 0, reset, and pull 50 times — pure greed locks onto whichever arm got lucky on its first pull and never checks the others (✗). Set c = 3 and it wastes half its budget re-checking losers (✗). Around 1–1.5 it funnels most pulls to the truly best arm (✓). This exact formula runs at every node of the tree in EP 01.

EP 03

The move greedy can't see

Here's a position where X has a forced win — but only via a fork: a quiet move that creates two threats at once, two plies later. A greedy one-step evaluator ("win if you can, block if you must, take center, take a corner") sees nothing special and settles for a corner. MCTS, because it actually plays the futures out, piles its visits on the fork. Run both and compare — green dots mark the moves a perfect game-solver confirms as winning.

The greedy player here uses the standard hand-written tic-tac-toe heuristic. The green ground-truth dots come from an exact minimax solver running live in this page.

Why it matters: greedy evaluation only scores the next board; a fork's value lives two moves deeper. Search converts compute into depth. This is precisely why chess and Go engines search instead of just scoring — and why "let the model think longer" beats "make the model smarter" surprisingly often.

EP 04

Buy better moves with compute — the budget dial

MCTS has a beautiful property: its answer improves smoothly with compute. Same position as EP 03. Pick a simulation budget, then launch 12 independent runs from scratch and see where their recommendations land. Watch two things: how often runs agree with each other, and how often they pick a truly winning move.

budget 10 playouts per run

At 10 playouts each of the 5 legal moves gets ~2 visits — the "best" move is basically a coin flip, yet the search still reports a high win-rate for it. Confidence is not evidence.

The lesson: a starved search is worse than no search, because it still hands you a confident number. Real systems (AlphaGo, poker bots, planning agents) treat playout count as a quality dial: more compute per move, better move — the original "test-time scaling" curve.

EP 05

Trap states — when shallow optimism walks into a refutation

The nastiest failure mode: move A looks great to random playouts (it wins against a careless opponent) but has one killer reply that refutes it completely. Move B is honestly decent. Early in the search the opponent's refutation hasn't been discovered, so A's value starts inflated — only as the tree deepens does the in-tree opponent learn to punish it, and A's curve collapses. Run the impatient search, then the patient one, and watch the collapse live.

Abstract two-move game, real UCT search: under A the opponent has 8 replies, one of which wins 95% for them; under B every line gives you a solid 55%. Random rollouts see A at ~75% — a mirage.

Why it matters: this is why pure-rollout MCTS struggled at chess (full of sharp tactical refutations) and why AlphaZero replaced random rollouts with a learned value network — a stronger "simulate" beat finds refutations in far fewer playouts. Depth isn't a luxury; some truths only live deep.