Technology Videos

Stanford CS221 | Autumn 2025 | Lecture 10: Games I

The lecture introduces game theory as the next step after Markov decision processes and reinforcement learning, focusing on two‑player zero‑sum games. It defines a game formally with start states, player‑turn functions, and successor mappings, and emphasizes that utility is realized only at terminal nodes, creating a sparse‑reward problem. Key concepts include the game tree representation, deterministic and stochastic policies, and the recursive evaluation of game value (V_eval). By summing over action probabilities at opponent nodes and taking expectations, the expected utility of a fixed policy pair can be computed exactly—though at exponential cost. The instructor demonstrates this with a simple bin‑selection game and a halving game, showing how Monte‑Carlo rollouts approximate the true value and how the expectimax recurrence replaces the opponent’s expectation with a max operator to derive optimal agent policies. Notable examples feature a poll where most students chose bin C, the calculation that the average utility of a random opponent policy converges to zero, and a step‑by‑step code illustration of V_eval and expectimax. The lecture also highlights that while exact evaluation mirrors policy evaluation in MDPs, practical AI systems rely on sampling or more sophisticated search techniques to avoid exponential blow‑up. The material underscores the bridge between reinforcement learning and adversarial decision making, preparing students to apply search algorithms, Monte‑Carlo methods, and expectimax in domains ranging from board games to real‑world competitive environments. Mastery of these concepts is essential for building agents that can reason about opponents and compute optimal strategies efficiently.