🌏 中文版
Video status: Videos included. Source details
Lectures 5–8 place two problem types together. CSPs use variables, domains, and constraints to reduce combinatorial search; game trees add other agents that respond. In Project 2, Pacman faces ghosts while you implement a reflex agent, minimax, alpha-beta pruning, expectimax, and an evaluation function.
CSPs: reduce choices before entering the game
The official CSP textbook chapter represents a problem through variables, each variable's domain, and constraints on compatible assignments. Basic backtracking assigns one variable at a time. Ordering heuristics choose the next variable and value; propagation removes candidates that can no longer participate in a solution. These techniques preserve the solution set while avoiding branches already known to fail.
For an executable exercise, open the official Discussion 2 CSP worksheet. Pick one problem and draw the first three levels of its backtracking tree. Apply minimum remaining values and forward checking separately, circling nodes each technique avoids. Check the official solution before moving to Project 2. This separates search ordering from inference-based pruning.
Three algorithms, three views of the world
Minimax assumes an opponent chooses the worst action for you. Alpha-beta preserves the minimax answer while pruning branches that cannot affect it. Expectimax replaces the always-adversarial opponent with a probability model. The official P2 specification explicitly notes that a correct agent still loses some tests; winning is not the sole proof of correctness.
Define a ply before coding. P2 counts one Pacman move plus every ghost response as one layer. Misreading depth can leave recursion looking plausible while producing completely wrong expansion counts.
The evaluation function is part of the model
With limited depth, leaf-state evaluation defines the world the agent can see. Combining food distance, ghost danger, and remaining goals is easy; putting them on coherent scales is harder. Use a fixed seed and multiple games to separate genuine improvement from luck.
First draw a small tree with two ghosts and mark when agent index and depth change. Implement minimax before pruning, then obtain expectimax by changing only the ghost-node aggregation rule. Each step should correspond to one explicit assumption.
Series navigation: Previous: Search and heuristics | Next: MDPs and reinforcement learning
Course video sources
The official Spring 2026 schedule and the official YouTube playlist ([CS188 SP26] Live Lectures, 28 videos) were checked live on 2026-10-10; the lecture recording embedded here is listed there as a “Recording”. No unverified timestamp is supplied.
Original videos: CS188 Spring 2026 Lecture 5: CSPs I
Course and recording entries:
Checked: 2026-10-10.
Content check: verified against the video transcript (2026-10-10): sampled check (only the first ~5,000 characters of the transcript were read): the embedded video is Lecture 5, on CSPs I (constraint satisfaction problems); the transcript first recalls the assumptions of search (single agent, deterministic, fully observed, discrete) and then introduces the CSP unit, previewing Project 4's invisible ghosts. The remaining sections of this article cover other lectures in the unit and the project, not this video.
Update Log
- 2026-10-10: Added explicit video status and checked recording sources and access notes.
- 2026-10-10: Rechecked video status. The official Spring 2026 schedule and YouTube playlist were checked live and list the embedded lecture recording, so the status is now Videos included.
- 2026-10-10: Checked the video content against its transcript. Confirmed the embedded video is Lecture 5 (CSPs I (constraint satisfaction problems)) and fits the article scope; no video claims needed correcting.
References
Loading...