Module 11 · AI/ML in games

Search and planning: minimax, αβ, MCTS

How an AI picks a move by looking ahead. Minimax assumes an optimal opponent; αβ pruning throws away branches that can't affect the result; MCTS samples when the tree is too large to enumerate. And the frontier is a hybrid: classical search with a learned evaluation inside it (AlphaZero, Stockfish NNUE).

~18 min🔬 search + ML hybrid🏠 lab

The gist in 30 seconds

Game tree search picks a move by looking ahead. Minimax (perfect information, zero-sum): you maximize, the opponent minimizes; evaluate the leaves, push the values up. That's exponential,

b^{d}

, so αβ pruning throws away branches that can no longer change the outcome — in the best case

b \to \sqrt{b}

(twice as deep for the same time; that's how Deep Blue beat Kasparov in 1997 + quiescence + transposition tables + a hand-written evaluation). When the tree is huge (Go:

b \approx 250

) or there's no good evaluation — MCTS samples: descend by UCB1 (exploit↔explore), simulate a rollout, backprop; anytime, parallelizable, needs no evaluation function. The frontier is the hybrid: AlphaGo/AlphaZero/MuZero = MCTS + a trained network (policy+value) instead of random rollouts; Stockfish = αβ + NNUE (a learned evaluation). The lesson for an ML engineer: search is the skeleton, ML goes in as a learned component inside it, and for most games classical search is enough (strategy isn't the bottleneck, reaction time is).

The mechanism: look ahead, prune, sample

Minimax

For zero-sum games with perfect information: on your moves you take the max over children, on the opponent's moves the min (they play optimally against you). Evaluate the leaves with an $eval$ function, push the values up from the bottom, pick the move at the root with the best guaranteed outcome:

Full enumeration costs $b^{d}$ (branching $b$ , depth $d$ ) — for chess that's $35^{8}$ positions. You can't go that deep. Pruning is what saves you.

αβ pruning

Carry two bounds: $α$ — the best MAX has already guaranteed, $β$ — the best MIN has guaranteed. As soon as $α \geq β$ , the node's remaining children can be skipped: they won't change the result (the parent will reject them). With perfect move ordering this cuts the branching down to its square root:

O (b^{d}) \to O (b^{d / 2}) = O (\sqrt{b^{d}})

That is, the same depth for the square root of the work — or twice the depth for the same time. For chess $35^{8} \approx 2.3 \cdot 10^{12}$ shrinks to $35^{4} \approx 1.5 \cdot 10^{6}$ — a million-fold cut. Move ordering is critical: look at the likely-best moves first → more pruning. Deep Blue (1997, beat Kasparov): αβ + quiescence search (keep looking until a "quiet" position, against the horizon effect) + transposition tables (a cache of positions) + a hand-written evaluation function.

MCTS: when enumeration is impossible

For Go $b \approx 250$ and there's no good hand-written evaluation — αβ is helpless. Monte Carlo Tree Search builds the tree asymmetrically, investing in promising lines, in four steps: select (descend by UCB1) → expand (add a child) → simulate (roll out to the end) → backpropagate (update the win statistics). Choosing a child balances exploitation and exploration:

UCB = \underset{exploit}{\underset{⏟}{\frac{w}{n}}} + C \underset{explore}{\underset{⏟}{\sqrt{\frac{\ln N}{n}}}}

( $w$ — the node's wins, $n$ — its visits, $N$ — the parent's visits, $C$ — the exploration weight). This is the same explore-exploit as in bandits. MCTS is anytime (run it longer, get a better move), parallelizes (independent rollouts) and needs no evaluation function (just the rules and the outcome).

The frontier: a learned function inside the search

The breakthrough wasn't replacing search with a network, it was a network inside the search. AlphaGo: MCTS + a CNN policy (which moves to look at) + value (how good the position is), replacing random rollouts with a learned evaluation. AlphaZero (2017): the same from self-play, with no human games, PUCT-MCTS — it mastered chess/shogi/Go. MuZero: dropped even the rules — it learns a model of the environment and plans inside it (generalizes to Atari). Stockfish 12 (Sep 2020): classical αβ + NNUE (a learned evaluation instead of a hand-written one) — it won ~10× more games against v11. The pattern is one and the same: a learned component (policy/value/model) slots into a classical search skeleton.

🕹 What to open — and what to notice

A chess engine minimax + αβ + NNUE, live

Any Stockfish client (Lichess "Analysis") shows an eval bar and a depth. The eval bar is exactly a minimax leaf value pushed up to the root; the depth is how many plies αβ got through.

🎮 Do: open a game analysis on Lichess, turn the engine on and watch the eval change as the depth grows (sometimes sharply — it found a tactic beyond the previous horizon). That's αβ digging deeper thanks to pruning, and NNUE evaluating the leaves. Notice: this is a turn-based game — nothing in an action game computes like this.

Go / AlphaGo MCTS + a network

Go can't be enumerated with αβ (b≈250, no simple evaluation). AlphaGo/KataGo use MCTS with a learned policy/value — intuition steers which lines get "imagined".

🎮 Notice: in a KataGo analysis look at the "visits" on candidate moves — those are MCTS visit counters; the policy network sets the prior (what to look at), rollouts/value refine it. More visits → a more confident evaluation. That's explore-exploit in action.

An action game why nobody searches here

A shooter or a hack-and-slash doesn't build a game tree every frame — it needs a reaction in 16 ms, not a strategy 20 moves out. This is FSM/BT territory, not minimax.

🎮 Notice: in any action game the enemy reacts instantly by rules (saw you → reacted), with no "thinking". Tree search here would be both expensive and pointless: the bottleneck is reaction time, not plan depth. That's why MCTS is rare in production.

🏠 Lab — minimax and αβ, live

An interactive lab with no code: a game tree with random leaves. Compute minimax bottom-up, turn on αβ pruning and watch which branches go dark (they never get looked at) and how far the visited-node count drops. Shuffle the move order — you'll see how "best first" multiplies the pruning. Open the lab →

The compression formula (b→√b) and UCB1 are in the text and the deep end; here it's about touching the pruning with your hands.

Deep end · αβ complexity, move ordering, MCTS/PUCTskippable

Why √b exactly, and what ordering has to do with it

Ideal αβ reaches $O (b^{d / 2})$ only under perfect ordering (the best move first at every node): then one maximizer child and all minimizer children suffice, and vice versa. In the worst ordering there's no pruning at all — back to $b^{d}$ . That's why engines invest in move ordering: the killer heuristic, the history heuristic, the best move from the transposition table, MVV-LVA for captures. Plus iterative deepening: a shallow search first provides the ordering for the deep one. Quiescence search follows forced lines (captures/checks) so the evaluation doesn't get cut off mid-exchange (the horizon effect).

MCTS: UCB1 → PUCT with a network prior

Vanilla UCB1 explores uniformly. AlphaGo/Zero replace it with PUCT: $Q + c \cdot P \cdot \sqrt{N} / (1 + n)$ , where $P$ is the policy network's prior: exploration shifts toward the moves the network thinks are promising rather than spreading uniformly. The value network replaces the random rollout with a position evaluation. That cuts the required simulations by orders of magnitude — intuition trims the width, search supplies the depth and the correction. MuZero goes further: it plans in a learned latent state space without knowing the true rules — MCTS on top of a learned dynamics model.

Deep end · search + learning and "when you don't need ML"skippable

Search is the skeleton, ML is the insert

The general pattern from 2016 on: a classical search algorithm + a learned component inside it. AlphaZero = MCTS + (policy, value); Stockfish = αβ + an NNUE eval; and the same thing in LLMs — inference-time search (tree-of-thought, verifier-guided decoding, self-consistency): you expand candidates, score them with a learned verifier/value, backtrack — an MCTS-shaped form. Learning it all end-to-end without a search structure is usually worse: search gives guarantees, interpretability and generalization by depth that a pure network doesn't. Knowing where to insert learning (the evaluation? the prior? the model?) and what to leave classical is the key engineering fork.

When you need neither search nor ML

For most shipped games nobody builds a tree at all: reactive FSM/BT/GOAP + scripts give predictable, debuggable, cheap AI, and strategic depth isn't the bottleneck (reaction and "fairness" matter more). Minimax/MCTS are justified where the game is about deep calculation (chess, Go, turn-based strategy) and there's time to think. Learning (NNUE/policy) gets added only when the space is too large for a hand-written evaluation (Go). The discipline of asking "do I need search here at all, and do I need a network inside it?" is exactly the classical vs ML judgment at the core of this whole module.

Analogy

Minimax is like planning an argument assuming your opponent will always give the answer that's worst for you: you pick the opening that leads to the least bad worst case. αβ pruning is not finishing a line once it's clear it's already worse than an option you have: you drop the branch the moment it can't beat your best. MCTS is for when the tree of replies is unmanageable: you mentally "play out" many random continuations of the most promising openings, keep score of which openings more often end well, and spend more imagination on the good-looking ones (explore vs exploit). AlphaGo is the same, but with a learned intuition that suggests which lines to imagine and how good a position is, instead of random playouts.

Why it matters

For you as an ML engineer this is a map of how learning and classical search combine in the strongest decision systems there are — from AlphaZero to inference-time search in LLMs: search gives the skeleton, the guarantees and the depth, the network gives the intuition and the evaluation. And it's a showcase for the course's central judgment: for most games you need neither search nor ML (reactive rules are more predictable and cheaper), and learning is justified only where the space is too big to cover by hand. Knowing where to insert learning, and when not to, is worth more than knowing how to train.

🔁 Where this leads — ties to your ML work

The lesson is about planning by search with a learned component inside and about the discipline of not training where structure is cheaper.

ML / AI (your domain): MCTS-with-a-learned-evaluation is the planning + learning template: AlphaZero/MuZero and all of model-based RL (Dreamer, planning in latent dynamics) are MCTS/trajectory optimization on top of a learned model. The same pattern has now arrived in LLMs as inference-time search: tree-of-thought, verifier/PRM-guided decoding, self-consistency, best-of-N — expand candidates, score them with a learned value/verifier, backtrack (an MCTS shape). αβ/minimax = the classical skeleton where ML slots in as the evaluation (NNUE) or the prior (policy) — the general "algorithm + learned component" pattern (RAG = retrieval + LLM; retrieval + reranker). UCB1/PUCT = the explore-exploit core, the same one as in bandits, RL exploration, A/B allocation and successive halving for HPO. And the honest note on "when ML isn't the answer": search/scripts without learning are usually enough (determinism, debuggability, cost); it's worth learning only the evaluation/model where a hand-written evaluation falls short (Go) — that's the very judgment this whole course exists for.

Algorithms: branch and bound, transposition tables = memoization, iterative deepening — the general technique of optimizing search.

Designing an AI opponent: search depth is a direct dial for difficulty (shallower search = a weaker and more "human" bot).

Principle: give the problem a search skeleton, insert learning surgically (evaluation/prior/model) and only where structure can't cope; don't train what's cheaper to program.

🔧 Run it and poke at it

🏠 The "minimax + αβ" lab in the browser

Open lab-minimax.html: compute minimax, turn αβ on, change the leaf order and the depth — watch which nodes get pruned and how far the counter drops. Push the pruning to "perfect" ordering and compare the node count with the √ of the full one.

🧪 Build a mini engine ~40 min, optional

Write minimax+αβ for tic-tac-toe or Connect 4 (a few dozen lines). Measure the number of eval calls with and without pruning → you'll see √b in practice. Then swap the hand-written evaluation for a trivial learned one (even a linear function of features) — feel the Stockfish/NNUE pattern in miniature.

Checklist: pushed αβ to perfect ordering in the lab and compared with the √ of the full count; understood UCB1 as explore-exploit; connected MCTS+network with AlphaZero/inference-time search; articulated when search/ML is NOT needed here.

Connections

foundation

Pathfinding: A* — also search, but single-agent and cooperative (A* = informed best-first); minimax is adversarial.

RL agents — self-play, which is what trains the policy/value inside AlphaZero; and why pure RL rarely ships.

summary

Classical vs ML — where to insert learning and what to leave to classical search.

Difficulty — search depth as a direct dial for bot strength.

Questions worth asking

Minimax or MCTS — when do you use which?

It depends on the branching factor, whether a good evaluation function exists, and whether the game is "tactical" or "strategic". Minimax + αβ is strong when branching is moderate (chess ~35), a decent positional evaluation function exists, and the game is tactical (short forced lines decide it) — αβ dominates because it calculates exactly to the horizon. MCTS wins when branching is enormous (Go ~250, where αβ can't get deep), there is no good hand-written evaluation (a Go position is hard to score statically), and/or the game is strategic (the general "feel" of the position matters more than forcing lines) — MCTS needs no evaluation function (rollouts give the estimate empirically) and it's anytime/parallel. In practice the strongest systems combine them: MCTS + a learned value/policy (AlphaZero) for Go; αβ + NNUE (Stockfish) for chess — meaning that in chess αβ still beats pure MCTS, and in Go it's the other way round. Rule of thumb: if you can evaluate a position cheaply and accurately — αβ; if you can't but you can simulate — MCTS.

How much does αβ actually speed things up, and why isn't it "just a constant"?

It's not a constant factor, it's a change of exponent: from

b^{d}

b^{d / 2}

under perfect ordering. In practice that means: in the same time αβ goes twice as deep as bare minimax, and every extra level of depth is a qualitative jump in strength (you see tactics one move further out). For chess the difference between

35^{8} \approx 2.3 \cdot 10^{12}

and

35^{4} \approx 1.5 \cdot 10^{6}

is a million-fold — the difference between "can't finish in an hour" and "a fraction of a second". The caveat:

b^{d / 2}

is the best case under perfect move ordering; in the worst ordering there's no pruning and you're back at

b^{d}

. Which is why real engines spend half their effort on move ordering (killer/history heuristics, transpositions, iterative deepening) to get close to the ideal √b. Without good ordering αβ is nearly useless.

Is AlphaZero "just" MCTS?

No — it's MCTS with the randomness cut out and learning inserted at two key points. Vanilla MCTS explores more or less uniformly (UCB1) and evaluates leaves with random rollouts to the end of the game. AlphaZero replaces both with a trained network: the policy head gives a prior over "which moves are worth looking at at all" (through PUCT it biases the search and trims the width), the value head scores the position directly (replacing the rollout — no need to play to the end). The network is trained from self-play: play games with the current version → the policy targets are the MCTS visit distribution, the value target is the outcome → retrain → stronger → repeat. So search and network improve each other in a loop. "Just MCTS" would play Go weakly; it's precisely the learned policy/value that make the search orders of magnitude more efficient (fewer simulations per move). MuZero drops the last assumption too — knowledge of the rules: it learns a model of the dynamics and plans inside it. The gist: MCTS is the engine, but the fuel is learned intuition.

How does this carry over to inference-time search in LLMs?

Almost word for word — it's a renaissance of the same "search + learned evaluation" idea. Expanding an LLM's reasoning as a tree (tree-of-thought) = expand in MCTS; scoring intermediate steps with a trained verifier/PRM (process reward model) = a value network scoring a leaf; choosing which branches to expand by those scores = select by UCB/PUCT; best-of-N and self-consistency are simplified forms (wide sampling + voting/scoring instead of a full tree). That's exactly the AlphaZero structure carried from games to reasoning: the base model gives the policy prior (which continuations are likely), the verifier gives the value (which is closer to correct), and the search spends inference compute to squeeze a better answer out of a fixed model — the way AlphaZero spends simulations to strengthen the network. And it has the same trade-off: more search = a better answer but a more expensive one (latency/compute) — hello, latency budget. Once you've got minimax/MCTS, you already understand the skeleton of modern test-time scaling.