Stanford CS221 | Autumn 2025 | Lecture 11: Games II — Annotated Lecture Notes & Key Takeaways

Course Information

Institution: Stanford

Original Course: Stanford CS221 | Autumn 2025 | Lecture 11: Games II

Instructor Bio: This lecture is delivered by Percy Liang, Associate Professor of Computer Science at Stanford University and core faculty of the Stanford Institute for Human-Centered Artificial Intelligence (HAI). Percy Liang leads the Stanford Natural Language Processing Group and the Center for Research on Foundation Models (CRFM). His research spans the theoretical foundations and practical systems of artificial intelligence, including machine learning, natural language processing, AI alignment, and rigorous model evaluation. He received his PhD in Computer Science from the University of California, Berkeley and his BA in Mathematics from Harvard University. His work has been recognized with the NSF CAREER Award, Google Faculty Research Award, and multiple best paper awards at top-tier AI conferences. He has taught CS 221 at Stanford for over a decade, shaping foundational AI education for thousands of students.

Course Description: This second game theory lecture extends to more complex multi-agent settings and repeated interactions. It covers extensive-form games with imperfect information, mixed strategy equilibria, and repeated game dynamics including the folk theorem. The lecture also introduces cooperative game theory concepts, mechanism design basics, and modern AI applications in multi-agent systems and strategic AI deployment.

If you missed this session, the short version is that it's really two lectures stapled together. The first chunk answers a question left dangling at the end of last week: if hand-written board evaluation is the weak link in a game-playing program, can we learn it instead? The last twenty-odd minutes throw away the turn-based setup entirely and ask what happens when both players commit at the same instant. The two halves share almost no machinery, and the second one stops before it finishes.

Where Games II Picks Up: Minimax, Alpha-Beta, and the Hand-Coded Ceiling

He opens with a quick rehash of two-player zero-sum games. The structural fact that matters is that control changes hands depending on where you are in the tree. Different states belong to different players, so you can't sweep a single max operator across everything, and you can't average either — you alternate, taking a minimum at the levels the opponent controls and a maximum at your own.

The example tree carries over from last lecture: a maximizing root, a minimizing level beneath it, and a game value of one, reached by the agent taking action B and then action one. I'd pull up the slides for this bit. The numbers are in the audio but the picture isn't, and without the tree the sequence "B, then one" is just a pair of labels.

Then two speed-ups. Alpha-beta pruning if you want to stay exact: you carry lower and upper bounds on the values your ancestors could still take, and the moment the intervals stop overlapping you stop expanding. In his example one branch is already known to be worth at least one, another is capped at minus five, and that's enough to never look at the fifteen. What I appreciate is how explicitly he marks this as exact — pruning here costs you nothing in answer quality.

Evaluation functions are the opposite trade. You give up exactness and in exchange you get to pour domain knowledge into a single number. The chess version he reviewed blends material count with mobility and control of the center, weights and all.

And that's the hinge, around 2:44. Every one of those terms was a human guess. So: can the evaluation function be learned instead, and would a learned one beat a hand-tuned one? That's the day's program — reinforcement learning, TD learning specifically.

The Long Detour Through Q-Values, and Why It Earns Its Time

A solid stretch of this lecture is review, and I don't think it's padding. He rebuilds the two objects you've been carrying around all quarter: state values, which score how good it is to be somewhere under a fixed policy, and action values, which score how good it is to do a particular thing from there and then keep following the policy.

SARSA comes back next, with its two defining features. It's on-policy — you're scoring the policy you're actually running, not the best one you could conceivably run. And it bootstraps: the update target is assembled from your own current estimate rather than from playing the episode out to the end. Concretely, each time you see a state, act, collect a reward, land somewhere new and act again, you shift your old action-value estimate a small step toward reward-plus-discounted-next-estimate, step size controlled by a learning rate. In code it's an alternation between two methods — one that asks for an action, one that absorbs what the environment did about it.

The point he's driving at is the marriage between action values and policies. An action value already has the action baked into the number, so a policy falls out of it for free: pick whichever action scores highest. He describes that as a single step of policy improvement — commit myopically to the best immediate move, then lean on your estimates for everything downstream.

Then a genuinely good question, around 9:16. Suppose I only hand you state values. Can you act? In an MDP, yes in principle: push the values through the one-step Bellman recurrence to manufacture action values, then take the best. But that expansion needs the transition model. If you don't have it, being told that this state is wonderful and that state is awful tells you absolutely nothing about which lever to pull. Action values are what tie states to actions. That, he says, is why the course opened with SARSA and Q-learning rather than anything value-only.

Games are the exception, and the turn comes at 11:14. In a game you know the rules. Transitions are usually deterministic, the board is fully observed, there's no hidden state. So given state values you can just enumerate your moves, run each one through the successor function, read off the resulting values and go. No model learning required.

Which invites the obvious heckle, and someone makes it at 12:25: if you have the model, why are we doing reinforcement learning at all? Run value iteration and be done. His answer is the sharpest thing in the first half. Value iteration scales with the number of states, and outside of tic-tac-toe the number of states is exponential. Reinforcement learning is being recruited here for its function approximation, not for its model-free properties. I found that reframe worth the price of admission on its own — RL as a compression tool for state spaces you can never enumerate.

A follow-up at 13:20 asks why the general one-step expansion simplifies so aggressively. Because in a deterministic game exactly one successor carries probability one, so the sum collapses, and because all the payoff sits at the end, so every intermediate reward is zero. You're left with the value of the successor and nothing else.

TD Learning, Shared Value Functions, and a Lot of Backgammon

The relationship is a one-liner around 13:60: TD learning stands to state values as SARSA stands to action values. That's the entire delta. Same bootstrapping, same on-policy flavor, one fewer argument.

In games that's a real simplification, because knowing which move leads where means scoring states is the same as scoring moves, and you're now fitting a function of the board alone.

With function approximation, the table of per-state numbers gets replaced by a parameterized function — weights in, value estimate out. He notes in passing that in deep RL this object is called a value network. The mechanics per experience: you're in some state, you act, you get a reward, you land in a successor. Your prediction is the current estimate at the first state. Your target is the reward plus a discounted estimate at the successor, computed with the same weights. Square the difference, take a gradient step on the weights.

There's a subtlety he stops to flag. The target also depends on the weights, and he chooses to ignore that: detach it, treat it as a constant, backpropagate only through the prediction. He points back to the computation-graph material from the second lecture of the course for the detach operation. The instruction is right, but I wanted one sentence about the price. Once you detach, you're no longer following the true gradient of any fixed loss, and that's the seed of most of the instability stories people tell about deep RL. The lecture never circles back.

The code walkthrough uses the tram MDP. Exploration is epsilon-greedy, and to choose an action you first reconstruct action values from your state values — sum over successors, weight by transition probability, add reward to discounted future value — then take the best. Worth noticing that this is exactly the model-based expansion that was declared impossible twenty minutes earlier; it's legal here purely because the model is being handed to you.

Summary of character: on-policy, because you only ever roll out the one policy and there's no max anywhere in the update; bootstrapping, because the target is partly made of the model's own output. His rule of thumb is a decent exam heuristic — see a max over actions and you're probably in off-policy Q-learning territory; don't see one and you're probably on-policy.

Adapting it to games (24:16) turns out to hinge on one thing. Deterministic transitions and end-only payoff are conveniences, not the interesting part. The interesting part is that there are two players who want opposite outcomes. The fix is self-play: maintain a single value function and let both sides consult it. The agent walks toward the highest-valued successor; the opponent walks toward the lowest. Swap the argmax for an argmin and you have the opponent's policy. If you know what's good and what's bad, you can steer toward either.

Here's where I got stuck, and I don't think the lecture resolves it. A state value is defined relative to a fixed policy. In self-play, both sides are being revised continuously while learning runs, so the thing you're estimating keeps moving underneath you. He doesn't raise it. Probably out of scope for this course, but don't file it away as settled theory.

Backgammon is the worked example, described from scratch at 27:05. Triangular points around the board, two colors running in opposite directions, goal is to get every piece home and off. You roll two dice and the two numbers are move lengths you may spend on one piece or split across two. Landing on a single enemy piece knocks it to the bar to start over. You may not land on a point held by two or more enemy pieces, so clumping is defense, though clumping too hard slows the race down.

Chance is handled by treating the dice as another player with a fixed policy that moves immediately before whoever is acting on the roll. The ordering matters because your legal moves depend on what came up. He jokes that dice playing adversarially would be a much harder game, and leaves it at that.

Feature construction starts around 31:30. You turn a board into a vector, and the examples he lists are mostly indicator-style: does column zero hold exactly one of your pieces, how many of yours are stuck on the bar, what fraction you've already borne off, how many enemy pieces sit in a given column, whose turn it is. On top of that vector you can fit a linear function, or an MLP, or anything else.

Three Old Programs, Read as a Story About Feature Engineering

He flags this stretch as reflection rather than technique, and it works best if you read it as a single trend line.

Samuel's 1959 checkers player (33:14) learned by playing itself — he calls it perhaps the earliest self-play system. Scarcity dictated the design: nine kilobytes of memory meant the human effort went into features rather than into search or capacity. Linear evaluation function, hand-added intermediate rewards because win-or-lose at the end of a game is a brutally delayed signal, alpha-beta layered on top with domain heuristics. It reached amateur strength, and he reckons it would beat him. (Small stumble in the delivery: he introduces it as checkers and then calls it a chess program. He means the checkers one.)

TD-Gammon, Tesauro, 1992 (34:55): the same recipe with roughly a million self-play games and a neural network instead of a linear map. Simple features, no shaped rewards. Expert-level play. And it returned something to humans — it had views about how the opening should be played.

AlphaGo, and more pointedly AlphaGo Zero (36:06): about five million self-play games, raw stone positions as the input representation, no crafted features at all, no intermediate rewards, and Monte Carlo tree search on top — which he characterizes as a less greedy way to act than grabbing the best-looking immediate value. It beat the 2016 AlphaGo that beat Lee Sedol, and Go programs now sit far above people.

The arc is explicit: as data and compute grow, you buy your way out of feature engineering. I'd add the corollary he leaves unsaid — the search component didn't get bought out. Learning replaced the evaluator, not the search.

Simultaneous Moves, Two-Finger Mora, and a Derivation That Gets Cut Off

At 37:45 he announces two extensions, simultaneous games and going beyond zero-sum. Only the first one arrives.

Rock-paper-scissors sets up the hook: can you play optimally if your opponent knows your strategy? Obviously not if your strategy is "rock." But if your strategy is a coin flip, announcing it costs you nothing at all. That's the doorway into mixed strategies.

The old machinery breaks because a game tree needs exactly one mover per node. With simultaneous moves you can't label a node as maximizing or minimizing. So the scope narrows: single move, zero-sum, no state, one shot.

Two-finger Mora (40:30) is the running example. Each player shows one or two fingers. Both show one, B pays A two dollars. Both show two, B pays A four. Mismatch, A pays B three. A wants agreement and would rather agree on two.

Formally: a payoff matrix over action pairs holding A's utility, with B's utility its negation. He names it V, which collides head-on with the value function from the first half of the lecture — keep those separate in your head. Strategies come in two flavors, pure (one action, probability one) and mixed (a distribution), written as probability vectors: always-one is [1, 0], always-two is [0, 1], a coin flip is [½, ½]. The value of the game under a pair of mixed strategies is the double sum over action pairs of the product of the two probabilities times the matrix entry. The independence of the two randomizations is doing quiet work in that factorization.

The arithmetic he works through: coin flip against coin flip averages to zero. Always-one against a coin flip gives minus one-half. Always-two against a coin flip gives plus one-half, and the mirrored cases come out symmetric. So against a naive opponent two is where the money is — which is precisely the trap, since a thinking opponent will start playing one.

He has the room pair off and play a few rounds (48:34), then admits it's subtle and adds a caveat worth remembering: repeated play isn't the same game, because the history of what the other person did becomes state. Everything in the formalism assumes one shot.

Solving it means breaking a deadlock. A wants the value high, B wants it low, and neither can wait for the other. So let one side commit first. With pure strategies: A commits, B mismatches, minus three. B commits, A matches, and B — foreseeing this — picks one, since conceding two hurts less than conceding four, giving a value of two.

Out of that comes a general principle at 51:54. Maximizing your move first and then letting the opponent minimize never beats the reverse order. Going second can't hurt you, and usually helps. The intuition is clean: with no state, the second mover hasn't been deprived of any option — same action set, same matrix — they've simply been handed information.

For mixed strategies the picture sharpens. A announces a coin rule without announcing the outcome. Expanding into four terms, B's expected value is minus one-half from playing one and plus one-half from playing two. At this point the lecturer briefly inverts himself and says B should play two; a student pushes back; he recovers out loud — B is the minimizer, so B loads everything onto one. If you were confused reading along, that's because it was confusing in the room.

What survives the stumble is the durable fact: B's expected payoff is linear in B's mixing weights, so the best response to anything is to put all the mass on one action. The second mover never needs to randomize.

The full solution then treats A's mixing probability p as a continuum of choices, with B's response restricted to two pure actions. B plays one, the value is 5p − 3. B plays two, it's 4 − 7p. The game value is the maximum over p of the minimum of those two. He starts sketching the two lines on the board and the recording ends at the hour mark.

Carrying his algebra two steps further myself, the min is maximized where the lines cross: 5p − 3 = 4 − 7p gives p = 7/12, and the value comes out to −1/12, about eight cents against A per game. So a game that looks tilted toward A — matching on two pays four — is actually slightly losing for A under optimal play. Verify that against the posted slides, because I'm completing a derivation he didn't.

Two things are left hanging: he promises a theorem that settles this whole class of games and never states it, and the non-zero-sum generalization he announced never appears. Both presumably land next time.

Stepping back, Games II places two bets side by side — that self-play can replace decades of human board intuition with a fitted function, and that the tidy minimax tree from last week is a special case that dissolves the moment both players move at once. The historical examples make the first bet look safe. The second argument is only half made when the tape runs out, which is its own kind of summary.