简介面向高校AI课程学习者与算法爱好者这份UC Berkeley经典吃豆人项目完整解决方案基于Python实现系统覆盖BFS、DFS、A*、Dijkstra等基础搜索方法并引入Minimax、α-β剪枝与Q学习等进阶博弈与强化学习策略可用于完成CS188作业或自主探索游戏AI设计并附带完整可运行的项目框架。包内共23个文件以20个py脚本为主体涵盖search.py、searchAgents.py、pacman.py、layout.py、graphicsDisplay.py等核心模块另配README说明、commands命令文档与LICENSE整体压缩仅67KB轻量且结构清晰。已有561人浏览学习是同类资源中比较精简实用的参考实现。透过autograder测试逻辑与源码注释能快速掌握状态空间建模、启发式评估函数设计、对抗搜索剪枝的实际写法还可借助游戏图形界面观察算法效果从而把抽象AI原理落地到可运行项目中。附带eightpuzzle.py、solveEightQueens.py等辅助实验脚本便于交叉验证不同搜索策略的适用场景。1. AI Pacman 的 SearchUC Berkeley 这道题到底在考什么UC Berkeley 的 AI Pacman Project 是很多学校《人工智能导论》的标准编程作业而 Search 是它的第一个模块。这个模块不要求吃豆人多聪明只要你能用 DFS、BFS、UCS、A* 四种搜索算法在给定迷宫里找到一条从起点到终点的动作序列并让自带的评分器按“正确性 扩展节点数”给你打分。它的价值在于把课本上的伪代码变成能在真实状态空间里跑的工程代码状态怎么判断、节点怎么判重、代价怎么累计、启发式怎么设每一步都是在为后面的 Multi-Agent、强化学习项目打地基。适合刚学完搜索理论但没写过完整实现的人也适合想回头补一遍状态搜索基本功的从业者。2. 把项目跑起来Pacman 环境、文件结构与最小命令2.1 先搞清目录里有什么search.py、pacman.py 与 autograder 的关系拿到 UC Berkeley AI Pacman 项目后目录里通常是一组相互引用的 Python 文件不会有人替你写好search.py里的核心函数你需要自己填空。第一次打开的人最容易犯的错是盯着pacman.py和动画界面看半天却没弄明白真正的入口和评分链路在哪。我一般会先用表格盘一遍文件角色再决定从哪个文件下手文件角色search.py你要实现 depthFirstSearch、breadthFirstSearch、uniformCostSearch、aStarSearch 的地方searchAgents.py把算法返回的动作序列包装成吃豆人策略同时提供启发式函数pacman.py主程序负责加载迷宫、驱动游戏循环、渲染界面game.py定义 GameState、Agent、Actions 等基础类状态转移的底层逻辑都在这util.py提供 Stack、Queue、PriorityQueue 等数据结构autograder.py评分脚本按 q1-q6 逐题跑测试统计正确性和扩展节点数这个结构本身就是一个“可复现的搜索系统”模板算法层只管“给定状态返回动作序列”Agent 层负责把动作序列翻译成吃豆人的行为渲染层完全不参与搜索。实际做的时候你的工作边界应该严格锁在search.py和searchAgents.py里尽量不要改game.py否则后面的项目会跟着翻车。2.2 跑通最小命令先能看见吃豆人再谈算法很多教程会让你一上来就写代码但我的建议是先把环境跑通用课程自带的测试迷宫验证渲染和 Agent 调用链路是否正常。最常见的最小验证命令是python pacman.py -l mediumMaze -p SearchAgent -a fndfs这段命令的意思是用mediumMaze这个迷宫布局加载SearchAgent这个策略并把dfs作为搜索函数传给 Agent。如果环境正常你会看到吃豆人直接穿墙走到出口——因为此时search.py里的depthFirstSearch还是空实现SearchAgent找到的路径是预设的兜底结果。命令里值得注意的参数有三个-l指定布局-p指定 Pacman 的决策类-a传给 Agent 的参数。fn是核心参数它决定调用search.py里的哪个函数后面接aStar、uniformCostSearch都是同样的套路。参数大小写必须严格一致否则searchAgents.py里getattr(search, fn)会直接抛 AttributeError这是新手遇到的第一个高频报错。2.3 autograder 才是真正的评分标准不要凭感觉判断算法写得好不好这门课的黑匣子评分器autograder.py会告诉你答案。最小评分命令是python autograder.py -q q1其中q1对应 DFS后面还可以替换成q2到q6。跑完以后评分器会输出每个测试点的 pass/fail、路径是否合法、扩展节点数量和时间。这里有个很容易被忽略的细节扩展节点数不仅影响性能分有时还会决定这个测试用例是否超时。所以你在写代码时就要养成记录“当前实现扩展了多少节点”的习惯而不是只看路径对不对。3. 四个搜索算法的标准解法DFS、BFS、UCS 与 A* 的参数与边界3.1 先搞清楚状态、行动、代价和判重键Pacman 的搜索问题和课本例题最大的不同是状态不是一个坐标点而是一个完整的GameState对象。在每个状态上你要用三个固定接口获得“下一步”的信息actions state.getLegalActions() # 当前状态可执行的行动含 STOP next_state state.generateSuccessor(0, action) # 执行 action 后的新状态 done state.isWin() # 是否吃完全部食物generateSuccessor的0表示 Pacman 的 agent index这个参数在 Search 部分永远填 0。四个搜索算法的共同骨架是从初始状态出发不断枚举getLegalActions用generateSuccessor生成后继直到isWin()返回 True。这里最需要注意的是判重。很多人直接拿GameState对象放进 set运气好能跑运气不好就遇到 unhashable 报错即使不报错状态对象里包含的信息太多做 key 既不安全也不高效。我一般用一个轻量快照作为判重键def state_key(state): return (state.getPacmanPosition(), tuple(state.getFood().asList()))这个 key 把“吃豆人当前位置”和“剩余食物坐标集合”作为唯一标识。因为在 Search 关卡里没有鬼魂两个状态只要这两项相同未来可做的决策就完全一样。至于剩余食物数量为什么不够严谨因为它无法区分“同样数量但位置不同”的豆子分布用完整坐标集合才没有歧义。3.2 DFS 与 BFS显式栈、显式队列和状态快照课程里 DFS 的标准测试目标是mediumMaze它不要求最短路径只要求能走出去。但是如果你用递归写很容易在深迷宫里触发 Python 的递归上限更稳妥的做法是用显式栈维护待搜索路径。我保留并测过的最小实现如下from util import Stack def depthFirstSearch(state): start state if start.isWin(): return [] frontier Stack() frontier.push((start, [])) # (当前状态, 已走动作序列) visited set() while not frontier.isEmpty(): node, actions frontier.pop() if node.isWin(): return actions key (node.getPacmanPosition(), tuple(node.getFood().asList())) if key in visited: continue visited.add(key) for action in node.getLegalActions(): successor node.generateSuccessor(0, action) frontier.push((successor, actions [action])) return []这里actions [action]会产生新列表代价是 O(路径长度)但这个项目里迷宫规模很小完全可接受。判重用state_key而不是状态对象能避开哈希问题。注意visited.add放在 pop 之后而不是 push 之前这样能保证同一个状态第一次弹出时才展开避免“已入栈但未访问”的状态被重复处理。BFS 的实现几乎一样只是把Stack换成课程提供的Queue或者 Python 标准库的dequefrom collections import deque def breadthFirstSearch(state): frontier deque() frontier.append((state, [])) visited set() while frontier: node, actions frontier.popleft() if node.isWin(): return actions key (node.getPacmanPosition(), tuple(node.getFood().asList())) if key in visited: continue visited.add(key) for action in node.getLegalActions(): successor node.generateSuccessor(0, action) frontier.append((successor, actions [action])) return []用popleft()而不是pop(0)是因为 list 的pop(0)会把后面所有元素往前挪复杂度是 O(n)在bigMaze上会明显变慢。这是 BFS 最容易踩的性能坑后面专门讲。3.3 UCS 与 A*把代价和启发式统一进优先队列UCS 要解决的问题是最短路径所以优先队列的键是“从起点到当前状态的累计代价”。在这个项目里默认每个移动的代价是 1所以累计代价就是len(actions)。A* 只是把键换成g h其中h是启发式函数。下面这段是我在本地反复验证过的 UCS 实现from util import PriorityQueue def uniformCostSearch(state): frontier PriorityQueue() frontier.push((state, []), 0) # (状态, 动作序列) 以累计代价为优先级 visited {} while not frontier.isEmpty(): node, actions frontier.pop() if node.isWin(): return actions key (node.getPacmanPosition(), tuple(node.getFood().asList())) if key in visited and visited[key] len(actions): continue visited[key] len(actions) for action in node.getLegalActions(): successor node.generateSuccessor(0, action) frontier.push((successor, actions [action]), len(actions) 1) return []这里visited不再是一个 set而是一个 dictvalue 记录到达该状态的历史最小代价。原因很简单UCS 可能先通过一条代价较大的路径到达某个状态再通过一条代价较小的路径到达同一个状态后者不能因为“已经访问过”就被剪掉。只有在新代价不小于历史最小代价时才允许跳过。A* 和 UCS 的差异只在优先键上核心结构完全复用def aStarSearch(state, heuristicnullHeuristic): frontier PriorityQueue() frontier.push((state, []), heuristic(state, None)) while not frontier.isEmpty(): node, actions frontier.pop() if node.isWin(): return actions key (node.getPacmanPosition(), tuple(node.getFood().asList())) if key in visited and visited[key] len(actions): continue visited[key] len(actions) for action in node.getLegalActions(): successor node.generateSuccessor(0, action) new_cost len(actions) 1 priority new_cost heuristic(successor, None) frontier.push((successor, actions [action]), priority) return []heuristic是第二个参数课程默认传入nullHeuristic它返回 0此时 A* 会退化成 UCS扩展节点数明显变多。把它换成searchAgents.py里提供的manhattanHeuristic同样的迷宫扩展节点数会下降一个数量级。这就是启发式质量最直观的体现。4. 核心考点启发式函数怎么设计才能少扩展节点4.1 启发式为什么是 Search 项目里的分水岭Pacman 项目的前四个搜索算法只要数据结构用对基本都能过。真正的分水岭在 q5 和 q6一个是cornersHeuristic一个是foodHeuristic它们直接决定你能不能拿到加分项。评分器会记录 A* 扩展节点的个数同样的迷宫启发式从 0 到曼哈顿距离再到位移下界扩展数目能差几十倍。这就是为什么我说这个项目表面上是写搜索实际上考的是“对状态空间的建模能力”。很多同学的误区是认为启发式越“聪明”越好于是绞尽脑汁算一个看起来很准的估计值结果 A* 返回的路径不是最优反而被扣分。这里必须钉死一个概念A* 保证最优解的前提是启发式可采纳即 h(n) 不能大于从 n 到目标的真实代价。一旦启发式高估A* 就失去了最优性保证路径错了评分器直接判 fail。4.2 曼哈顿距离在迷宫里是可采纳的searchAgents.py里默认提供的是manhattanHeuristic它的定义是两个点的横向距离加纵向距离。在 Pacman 的网格迷宫里曼哈顿距离永远不会大于真实路径长度因为真实路径要绕过墙绕路只会让距离变长。所以它是严格可采纳的。这里有个很容易混淆的点很多人担心“有墙时曼哈顿距离比实际短会不会导致找不到路”其实 A* 只需要启发式不大于真实代价低估只会增加扩展节点数不会导致错误答案。如果你把启发式换成欧几里得距离在网格图里它同样可采纳但扩展节点数通常会比曼哈顿距离略多因为它的估计值更小、更不紧。调启发式时可以对比这两者的扩展节点数和运行时间这是评估启发式质量最直接的实验。4.3 cornersHeuristic 与 foodHeuristic用最小生成树下界逼近真实代价q5 的完整任务是让吃豆人访问四个角落。最简单的可采纳启发式是“到最近角落的曼哈顿距离”虽然可采纳但太松。想要在扩展节点数上拿高分需要把问题看成一个“多目标访问问题”从当前位置出发要覆盖所有未访问角落。这个问题的真实代价下界可以用最小生成树来逼近。常见做法是先把每个角落之间的两两迷宫距离算出来然后以“当前位置到最近角落的距离 剩余角落的最小生成树权值”作为启发式。代码如下def cornersHeuristic(state, problem): corners problem.corners visited state.getCornersVisited() unvisited [c for c in corners if c not in visited] if not unvisited: return 0 pos state.getPacmanPosition() # 当前位置到任一未访问角落的最小曼哈顿距离 start_dist min(manhattanDistance(pos, c) for c in unvisited) # 未访问角落之间的最小生成树权值 mst_cost mst_cost(unvisited, lambda a, b: manhattanDistance(a, b)) return start_dist mst_cost注意这里manhattanDistance用于计算两两距离是可采纳的因为墙的存在只会让真实距离更大。MST 权值本身是“连接所有角落的最小代价”任何一条从当前位置出发、覆盖所有角落的真实路径其代价都不可能小于“走到最近角落 连接所有角落的最小代价”所以整个启发式是可采纳的。q6 的 foodHeuristic 是加分题难度更高因为剩余食物可能非常多。我的经验是先对每个食物算一个“到最近其他食物的迷宫距离”作为边权再对当前位置加所有未吃食物做 MST 下界。如果食物数量太大可以退化成“到最近食物的距离”代价是可采纳但扩展节点数偏高。扩充时务必保持“不大于真实代价”的原则否则就是给自己挖坑。5. Search 项目常见问题排查从爆栈到启发式高估5.1 现象递归 DFS 在 mediumMaze 上报 RecursionError第一次做 DFS 的人习惯用课本上的递归写法结果在迷宫稍深一点的地方直接崩掉或者程序不返回看起来像死循环。原因是 Python 默认递归深度限制大概是 1000而迷宫路径可能绕几百步递归栈很容易触顶再加上没有判重搜索可能反复绕同一个环。解决换成显式栈的迭代写法把“待扩展的状态”放在util.Stack里用while循环展开。这样完全没有递归深度问题也方便在 pop 时统一做判重。如果实在想保留递归也可以sys.setrecursionlimit(10000)但这不是好习惯后面 Multi-Agent 项目里状态更深递归会继续成为隐患。5.2 现象判断重复状态时出现 TypeError: unhashable type直接拿GameState对象放进 set 或 dict有时会得到这样的报错即使不报错某些课改版本里GameState自带__eq__导致哈希行为变得难以预测。这类问题最大的麻烦是你可能只在某个测试用例上报错换个迷宫又能跑非常玄学。原因GameState是自定义类内部包含 Grid、AgentState 等可变对象默认情况下不可哈希或被改写过__eq__导致__hash__失效。解决永远不要拿状态对象本身做判重键改成像前面写的(position, tuple(food.asList()))这样的快照。如果后面做带鬼魂的 Multi-Agent就把鬼魂位置和方向一并加进 key规则是“只要两个状态未来决策完全一致就可以共用同一个 key”。5.3 现象BFS 在 bigMaze 上慢得离谱甚至被评分器判超时路径是正确的但跑大迷宫时耗时会突然增加。很多同学以为是数据规模的问题其实是用list.pop(0)实现了队列每次弹出队首元素Python 都要把后面的所有元素整体前移一位代价是 O(n)。在迷宫大、节点多的情况下总操作量变成 O(n²)。解决换成from collections import deque用popleft()实现出队或者直接用util.py里提供的Queue。换完以后 bigMaze 的运行时间通常能降一个数量级。这个细节也提醒我写 BFS 时第一反应不是“用队列”而是“用高效的队列”。5.4 现象A* 返回的路径不是最短路径评分器报错算法写得没问题但结果偏偏不是最优。问题几乎都出在启发式高估上。最典型的高估写法是把到两个目标的曼哈顿距离直接相加比如cornersHeuristic里这样写return sum(manhattanDistance(pos, c) for c in unvisited)这等于认为吃豆人能同时走两条路必然高估真实代价A* 的最优性保证立刻失效。解决回到可采纳性定义逐项检查启发式是否“不大于真实代价”。多目标问题时优先用“到最近目标的距离 目标集合的最小生成树权值”不要用求和。修完后可以在同一个迷宫对比 A* 路径长度是否和 UCS 的结果一致如果一致说明启发式没有破坏最优性。5.5 现象同样代码跑两次扩展节点数不一样结果难以复现你可能会遇到这样的情况本地运行一切正常换台机器或在同一台机器上重跑评分器给的扩展节点数变了甚至路径都不同。这种“黑匣子”式的波动多半是代码里用了 set 或 dict 做遍历而遍历顺序受哈希随机化影响另一部分原因是测试本身引入了随机迷宫默认种子没固定。解决开发和调试阶段固定随机种子命令里显式设置python pacman.py -l mediumMaze -p SearchAgent -a fnaStar里的-l参数保证每次都跑同一个布局代码里如果依赖集合遍历尽量改成按坐标排序后再处理。稳定复现是调试任何搜索算法的第一步。6. 验证与进阶用 autograder、可视化与后续 Project 收尾6.1 逐题跑 autograder不要等写完所有算法再验证我习惯写完一个函数立刻跑一个评分项。先python autograder.py -q q1验 DFS再python autograder.py -q q2验 BFS依此类推。不要等四个算法全写完再一起测否则一个低级错误会污染所有结果排查起来很痛苦。评分输出里可以重点看两项路径是否通过以及扩展节点数是否在预期范围。6.2 用可视化确认路径质量评分器只能告诉你对错不能告诉你“为什么不好看”。我会再用可视化命令观察路径python pacman.py -l mediumMaze -p SearchAgent -a fnaStar,heuristicmanhattanHeuristic如果路径存在明显绕路、来回折返说明判重键或代价累计有问题如果路径正常但扩展节点数偏高说明启发式还可以再收紧。-l换成bigMaze、openMaze可以覆盖不同形态的地图越早暴露边界问题越好。6.3 Search 是后续 AI 项目的地基做完 Search 后最好趁热把state_key、generateSuccessor的调用方式记牢因为 Multi-Agent、Reinforcement Learning 项目全都复用这套状态转移机制区别只是代价函数和决策目标的复杂度变了。我当年做完 Search 后最大的教训是把“能用”和“能拿满分”混为一谈四个基础算法跑通只是及格线把启发式从曼哈顿距离迭代到 MST 下界才是真正理解搜索的地方希望帮到你。本文还有配套的精品资源点击获取
