🌏 中文版
Video status: Checked: no corresponding recording link listed on the public official page. Source details
This is CMU 07-280 Spring 2026 Lecture 3: Adversarial Search. The previous lecture found a route through a fixed world. Here, an opponent or random event changes the next state. The answer is no longer one action sequence but a contingent plan: what to do after each possible response.
The inherited question: when you do not control the transition
A* assumes that after an action, the transition model determines the next state. Games alternate action choices between agents. MAX wants higher utility; MIN wants lower utility. In a stochastic world, a chance node produces outcomes according to a probability distribution.
The algorithm must therefore evaluate a strategy rather than a path. MAX's move must include what MIN can do next, just as an opening move in chess cannot be scored using only the immediate board change.
Full conceptual path: three backup rules
Minimax backs terminal utilities up the tree. A MAX node takes the maximum child value; a MIN node takes the minimum. Under zero-sum optimal play, the root value is what MAX can preserve even when MIN works against it. With branching factor b and depth m, exhaustive time is O(b^m). Real games require a limited horizon and an evaluation function for nonterminal states.
Alpha-beta pruning maintains two bounds. α is the best value MAX can already guarantee; β is the best upper bound MIN can already enforce. When a branch cannot change an ancestor's choice, expansion stops. Pruning does not change the minimax root value. Good move ordering simply makes more branches provably irrelevant earlier.
Expectimax changes the chance-node backup to an expectation:
V(s) = Σ P(s'|s,a) V(s')MIN deliberately chooses the worst result. Chance samples from a distribution. Treating an imperfect opponent as MIN can be overly conservative; treating a strategic opponent as random can overvalue risky moves.
A reproducible example: one tree, different choices
MAX has two actions:
Safe -> [4, 4]
Risky -> [0, 10]If the next layer is MIN, Safe has value 4 and Risky has value 0, so minimax chooses Safe. If it is an equal-probability chance node, their expected values are 4 and 5, so expectimax chooses Risky.
Now apply alpha-beta. Fully evaluating Safe sets root α=4. At Risky's MIN node, the first child gives 0, so β=0 ≤ α=4. The remaining 10 need not be read: MIN can already hold Risky to at most 0, and MAX will not abandon Safe's 4.
Recitation and homework connection
Recitation 2 first asks for alpha, beta, and pruned branches under left-to-right traversal. Its true/false questions then compare minimax and expectimax values and policies. The exercise forces a distinction between a higher expectation and a better worst-case guarantee.
HW2 places pruning inside iterative deepening: complete a shallow search, then use its information to improve move ordering in the next round. It also asks a precise question. Alpha-beta preserves the root value, but must it return the same move as full minimax? When several moves tie for the optimum, tie-breaking can still differ. The search-and-games programming tree is public, while its official grader and submission feedback are not.
Further comparison: an evaluation function is a compressed future
A depth limit does more than cut computation. It replaces terminal utility with an estimate of how good the current state looks. If that evaluation orders states incorrectly, deeper search often helps but is not a formal promise of monotonic improvement; the slides also discuss horizon effects and cases where additional depth does not improve play.
This returns to Lecture 1's representation problem. An evaluation function compresses an enormous future into one number. What it preserves determines which positions the search favors.
What to do tonight
- Compute the full minimax value of Recitation 2's first tree before pruning anything.
- Trace
αandβin the same order, writing why each pruned branch cannot change an ancestor's decision. - Build a three-action example in which minimax and expectimax choose different actions.
Course video sources
The official Spring 2026 schedule has been checked: it lists slides, notes and exercises, but no public recording link for the lectures covered here. This article therefore links to course materials and has no corresponding lecture player. Géron/Karpathy videos are supplementary readings; the CMU-Qatar NumPy recording is a separate Recitation 0, not the lecture covered here.
Official sources:
Checked on 2026-10-10.
Official materials and reading scope
I read the complete inked slides, Adversarial Search staff notes, Recitation 2 and solution, and checked HW2. No public recording link is listed in the official schedule. This article does not turn slide games or demos into unrecorded spoken commentary.
Update Log
- 2026-10-10: Added explicit video status and checked recording sources and access notes.
- 2026-10-10: Rechecked video status. Re-verified the live official course pages and public video sources; no public recording for this lecture was found, so the status stands.
References
Loading...