Table of Contents
🌏 中文版
The opening unit of CS188 asks how an agent should expand possible states when it does not know the solution path. The Lectures 1–4 schedule covers agents, uninformed search, A*, and local search. Project 1 turns that sequence into implementations of DFS, BFS, UCS, and A*, followed by heuristic design for corners and food search.
Fix the common skeleton first
All four graph-search methods share a loop: remove a node from the frontier, test the goal, expand successors, and avoid repeated states. DFS and BFS change frontier order; UCS orders by accumulated cost; A* adds an estimate of remaining cost. Four largely duplicated implementations usually mean the shared abstraction has been missed.
State is harder than the formula
P1 explicitly warns against using the entire GameState as the corners search state. Two positions can be identical while differing in which corners were visited, which changes the future objective. Ghost data and irrelevant food, however, should not inflate the state. A useful representation retains exactly what affects future legal actions and goal tests.
Heuristics must balance speed with correctness. The official P1 specification requires a consistent food heuristic. An impressive-looking estimate that overreaches can remove A*'s guarantee. Begin with a lower bound you can justify, then use the autograder to inspect expansions rather than reverse-engineering a score threshold.
A practical order
- Write the frontier rule for all four algorithms before coding.
- Implement DFS and BFS; observe how expansion order changes the path.
- Implement UCS and A*; test path cost separately from the heuristic.
- Describe in one sentence what your corners-state tuple predicts.
- Run one question or test case at a time. The local autograder is enough; Gradescope is not required.
After P1, retain three questions: does the state preserve necessary information, what preference does the frontier encode, and does the heuristic provide only a safe directional estimate? Those questions return in MDPs, Bayes nets, and planning.
Series navigation: Previous: Course overview | Next: CSPs and multi-agent search
References
Loading...