THE MONTE CARLO TREE SEARCH the bandit that learned Go
When a game tree is too vast to search, MCTS grows a lopsided tree by playing random games and following the results. Each node balances exploitation (its average outcome) against exploration via the UCB1 formula x̄ + c√(ln N / n) — try the promising, but do not neglect the untested. Four steps, repeated: select, expand, simulate, back-propagate. It is the engine that, with a neural net, beat the world at Go.
THE TECHNIQUE UCB1 = mean + c√(ln N / n)
The demo computes UCB1 for three children; the least-visited wins the exploration bonus: live demo
HISTORY & CREDIT Coulom / Kocsis-Szepesvári · 2006
“AlphaGo was pure deep learning.” — it married a neural net to MCTS; the tree search chose the moves, the net guided it. cited
select · descend by max UCB1 until a leaf. expand, simulate, back-propagate · add a child, play out at random, push the result up. 2006 · Coulom (MCTS) and Kocsis & Szepesvári (UCT), on Auer’s UCB1 — the core of AlphaGo.
Randomness, aimed by a bandit’s regret. algorithm
RECOMMEND FOR I-13 UCB1, on the compiler
On i-13 (ln via series, sqrt via Newton), the least-visited child’s UCB1 exceeds the best-mean child — exploration wins:
$ i13 run gm_monte-carlo-tree-search.i13
RUN OK · 3332 step(s) · call depth 42
lnN = 2.197 (ln 9)
ucb0 = 1.737 (mean .8, n5) ucb2 = 2.096 (mean 0, n1)
explore_wins = 1 -- the untested child is tried
Recommend as a NULL — a policy + resource (B40/B41). UCB1 is a selection rule with a regret bound (an adversary/bandit argument, B41); its value is pinned by the statistics. A heuristic, not a same-function structural DOF. NULL — the bandit that learned Go.