Do not enumerate the game — grow it. Try promising moves more, sample the rest just enough to be sure, and the tree bends toward the best play on its own. At every node the choice is a bandit: exploit the move that looks good, explore the one you have not tried — Q + c·√(ln Nparent / Nchild). Down the center, data flows: the tree goes in, thousands of guided simulations run, the chosen move comes out — and it matches full minimax exactly. The blue team builds and defends it; the red team tries to break it.
source L. Kocsis & C. Szepesvári, Bandit Based Monte-Carlo Planning (UCT), ECML 2006, LNCS 4212, pp. 282–293 — link.springer.com/…/11871842_29 (with R. Coulom, 2006, for MCTS). No stable arXiv — cited by venue+year, AMBER. Rendered, not quoted.
A move is chosen not by fiat but by an upper confidence bound. For each child of a node the score is:
Q is the exploitation term — the mean value backed up through that child. The second is the exploration bonus: large when Nchild is small, shrinking as the child is visited more. A never-tried child scores +∞ — so UCT visits every child before it commits. At a MAX node it maximises the score; at a MIN (opponent) node it minimises Q, so the tree is a live minimax.
Live bonus, Nparent=100, as a child's visits grow:
| Nchild | 1 | 4 | 16 | 64 |
|---|
MCTS is the-bandit run at every node of a game tree: each internal node is its own multi-armed bandit, and UCB1 becomes UCT. It is downstream of the-minimax — it computes the same answer but replaces full enumeration with guided sampling, so it survives game trees minimax cannot fit.
Paired with a learned value network, this exact planner became AlphaGo (2016). Each sphere is the next one's premise.
The blue team's live check: re-run the whole search over the fixed tree and confirm the chosen move against an independent brute-force minimax — and that every root child was explored. If red tampers, this badge is where it shows.
A fixed, deterministic two-player game. You (MAX) pick a move; the opponent (MIN) replies to hurt you most; the leaf is your final score. Three moves, three replies each — every leaf value known in advance, so the true answer is checkable:
| your move | opponent replies (leaves) | minimax = min reply |
|---|
The opponent takes the minimum of each row, so a move is worth its worst reply. MAX then wants the row whose minimum is largest. That value the machine must find — without reading every leaf every time.
Each simulation walks the tree by UCT to a new leaf, plays a fixed-seed rollout, and backs the value up. Visit counts pile onto the strongest move.
Every number is computed live from the UCT rule on a fixed-seed rollout policy — nothing is looked up. Turn simulations down to 20 and the search is unsure; turn it up and it locks onto minimax.
What the machine produces, proven: given enough simulations the root's most-visited child is the minimax-optimal move — matching the independent brute-force search exactly — and the backed-up value estimate converges to the true minimax value, while every child was explored at least once first.
The blue team's witness (left) re-derives this move live from scratch; the red team (right) tries to make the search commit to the wrong one.
It also assumes a rollout that is at least weakly informative and a value roughly bounded — reward it badly and it converges to the wrong tree. The AlphaGo leap was precisely to replace random rollouts with a learned value net; plain UCT rollouts are a crude stand-in for the value it cannot yet see.
"MCTS finds the best move." Cut. It finds it in the limit. At a finite budget it returns the most-visited child — usually, not always, the optimum. This panel proves it only for enough sims on this fixed tree.
"More exploration is always safer." Cut. Too large a c wastes the budget re-checking bad moves and can leave the true best under-visited; too small and it commits early. c is a real knob — change it above.
"The rollout must be random." Kept, corrected. Random is the baseline; a fixed seed makes it reproducible, and a learned policy makes it strong. The seed here is fixed so the witness is deterministic.
The red team's move: flip the sign of the UCT bonus — subtract c·√(…) instead of adding it — steering the search away from unexplored moves so it never leaves the first branch. The blue team's witness (window 7) is watching.
Flip the sign and unexplored moves score −∞: the search locks onto the first branch, its most-visited child is no longer the minimax move, and whole moves go unvisited. The witness recomputes, disagrees with brute-force minimax, and turns red. Nothing is faked; the attack is real and it is caught.