简介这是伯克利大学经典人工智能吃豆人项目的搜索算法完整解决方案使用Python实现面向学习搜索策略与人工智能原理的学生和开发者。资源完整覆盖吃豆人游戏中的基础搜索方法包括广度优先搜索、深度优先搜索、A星搜索、Dijkstra算法并延伸到极小极大搜索、Alpha-Beta剪枝和Q学习等进阶AI策略源码均配有注释与测试用例。包内共23个文件其中20个Python源文件构成核心算法与游戏框架另有说明文档、命令文件和许可证文件压缩包仅67KB轻量精简主模块与辅助工具齐全便于快速下载与部署。目前已有564人学习此资源。通过本套代码可对照标准实现深入理解各搜索算法在真实博弈场景中的编码方式也适合用于课程作业参考、算法对比实验或二次开发学习。1. AI-Pacman 搜索项目实战让吃豆人自己找路一份能跑通的完整解答你可能也遇到过这种情况学完搜索算法理论都懂一上手写代码就卡在状态怎么定义、返回值怎么组织、为什么 dfs 会绕路。这套 AI-Pacman 的 Search 解决方案正好解决这个问题。整个项目用纯 Python 实现覆盖 DFS、BFS、UCS、A* 四种经典搜索算法以及两个进阶场景Corners 问题和 Food 问题。最直观的感受是同一个 mediumMaze用 BFS 只要几十毫秒就能跑出最短路径但换 DFS 在 bigMaze 上就会明显绕远路而 A* 的扩展节点数只有 BFS 的大约一半。这份方案把搜索问题抽象成统一的 problem 接口适合刚入门 AI 算法、想动手验证一遍理论的人也适合做课程作业时被状态哈希、坐标系翻转这些细节卡住的同学直接对照参考。2. 项目结构拆解从命令行参数到图形界面的完整数据流拿到资源第一步不是打开代码就改而是先把文件分层看明白。这个项目的结构设计很典型底层游戏逻辑、中层搜索算法、上层 Agent 调度三层解耦得非常干净。知道每个文件负责什么后面改起来才不会被牵着鼻子走。2.1 文件布局框架文件、算法文件、评测文件各管什么整个项目按职责可以分成四类入口与游戏循环、搜索算法实现、问题定义、工具与评测。用一张表快速过一遍文件职责是否需要改pacman.py命令行入口解析参数并驱动游戏主循环不需要search.py四个搜索算法入口DFS、BFS、UCS、A*核心改造点searchAgents.py各类 Problem 的定义与启发式函数核心改造点game.py游戏底层状态、动作、Agent 基类不需要util.pyStack、Queue、PriorityQueue 等容器实现不需要graphicsDisplay.py图形界面渲染不需要layouts/迷宫地图文本文件可自行扩展autograder.py自动评测脚本不需要这里最值得学习的是 search.py 的设计它完全不依赖图形界面和 Pacman 的具体逻辑只用 problem 接口打交道。搜索算法只认四个方法——getStartState、isGoalState、getSuccessors、getCostOfActions。这种解耦带来的好处很实际换一个布局、换一个场景甚至换一个完全不同的游戏只要实现同样的接口四个搜索函数一个字都不用改这也是 autograder 能批量跑通所有问题的前提。2.2 启动链路一条命令行触发一次搜索的完整流程先看最常用的启动命令python pacman.py -l mediumMaze -p SearchAgent -a fnbfs命令行参数拆开看-l指定用 layouts 目录下的哪个地图-p指定用哪个 Agent 类-a是传给 Agent 的构造参数。这里的fnbfs意思是让 SearchAgent 内部调用 search.py 里的 breadthFirstSearch 函数。整个流程是SearchAgent 初始化时立即执行搜索把整条路径算好存起来游戏开始后每一帧调一次 getAction从路径里按顺序取一个动作返回。class SearchAgent: def __init__(self, fndepthFirstSearch, probPositionSearchProblem, heuristicnullHeuristic): self.searchFunction getattr(search, fn) self.heuristic getattr(search, heuristic) self.searchType globals()[prob] self.actionIndex 0 self.actions [] problem self.searchType(self) if fn ! aStarSearch: self.actions self.searchFunction(problem) else: self.actions self.searchFunction(problem, self.heuristic) def getAction(self, state): if self.actionIndex len(self.actions): action self.actions[self.actionIndex] self.actionIndex 1 return action return Stop逻辑说明getattr(search, fn)是在 search 模块里按名字找函数这就是为什么命令行里传入字符串bfs就能动态绑定到 breadthFirstSearch。A* 特殊处理是因为它比另外三个函数多一个启发式参数。游戏运行时 getAction 每次只返回一个动作动作序列用完了就返回Stop让吃豆人原地待着。参数说明prob默认是PositionSearchProblem它把迷宫抽象成一个单目标搜索问题heuristic默认是nullHeuristic恒返回 0如果跑 A* 不指定启发式效果就和 UCS 完全一致。所以测试 A* 时记得加heuristicmanhattanHeuristic。2.3 状态表示为什么 state 必须是一个不可变的 tuple搜索问题的状态定义直接决定能不能跑起来。PositionSearchProblem 返回的状态是一个三元组(x, y, direction)包含了坐标和朝向。四个方向移动后新状态就是一个新的三元组。这里有一个所有人都可能踩的坑visited 集合用来判重必须对状态做哈希所以状态必须是不可变对象。一旦有人图省事把状态存成[x, y, direction]这种 list程序直接抛unhashable type: list搜索根本跑不起来。另外注意图形层坐标和逻辑层坐标的差异。layout 文本文件里 y 轴是向下增长的图形渲染时会做翻转但你写搜索算法时完全不需要关心这些只认 problem 的 getSuccessors 返回的状态。我自己一开始就犯过这个错对着渲染画面里的坐标去推墙的位置结果进去之后全是墙。后来学乖了所有坐标都以搜索问题内部的接口返回值为准渲染层对你来说就是个黑匣子。3. 核心算法实现四个搜索函数从 DFS 到 A* 的一行差异这一章是整个资源的核心价值。四个算法放在一起看会发现它们的骨架几乎一样区别只在 frontier 用哪种数据结构栈、队列还是优先队列。理解了这一点四个函数就不用分开背了。3.1 统一搜索框架frontier 加 explored set 加路径累积通用的图搜索模板长这样把起始状态放入 frontier循环里从 frontier 取出一个状态如果是目标就返回路径没访问过就标记 explored再把所有后继状态连同路径一起压入 frontier。四个算法的差异百分之百集中在「取出哪个状态」这一步。这里有一个实现细节值得多说一句判重到底是 push 时做还是 pop 时做。我的习惯是 pop 时判重也就是先取出状态再看它是否已经在 explored 里。push 时判重能减小 frontier 的体积但在带权图上可能漏掉更优路径pop 时判重牺牲一点点内存换来的是正确性。像 UCS 场景下同一个状态可能以不同代价被多次压入队列pop 时判重才能保证最优的那一次被使用。3.2 DFS 和 BFS同样是几行代码差别只在容器DFS 用栈后进先出深度优先地往下钻。实现如下def depthFirstSearch(problem): frontier util.Stack() frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, path, cost frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: frontier.push((nextState, path [action], cost stepCost)) return []逻辑说明栈里存的是三元组path是从起点到当前状态的完整动作列表cost是累计代价。push 进去时把 path 一起带上省掉了用 parent 指针回溯的麻烦。找到目标直接返回当前 path这个 path 因为是 DFS 找出来的不保证最短。参数说明problem.getSuccessors返回的元组是(nextState, action, stepCost)其中 stepCost 在普通迷宫里恒为 1但接口保留了加权图的可能性。BFS 的代码和 DFS 几乎一样只换一个容器def breadthFirstSearch(problem): frontier util.Queue() frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, path, cost frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: frontier.push((nextState, path [action], cost stepCost)) return []逻辑说明Queue 是先入先出逐层扩展所以第一次到达目标状态时的路径就是最短路径前提是每步代价相同。在 maze 这种单位代价场景里BFS 能保证最短路径这是它对比 DFS 的最大优势。参数说明这两个函数都只接受 problem 一个参数不涉及启发式。它们的返回值和 SearchAgent 的预期一致是一个 action 字符串组成的列表。3.3 UCS把队列换成按累计代价排序的优先队列UCS 解决的问题是当每一步的代价不再恒等于 1BFS 的逐层扩展就失效了。UCS 把队列换成优先队列每次弹出累计代价最小的状态def uniformCostSearch(problem): frontier util.PriorityQueue() frontier.push((problem.getStartState(), [], 0), 0) visited set() while not frontier.isEmpty(): state, path, cost frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: newCost cost stepCost frontier.push((nextState, path [action], newCost), newCost) return []逻辑说明PriorityQueue 的 push 接收两个参数第二个是优先级这里直接传累计代价。每次弹出的都是当前 frontier 里代价最小的状态等价于把搜索过程按代价从低到高展开。第一次弹出目标状态时返回值就是最优路径。参数说明visited 的存在让算法不会重复扩展已经处理过的状态。注意旧条目留在队列里没关系因为它们弹出 时会因为state in visited被跳过不会影响正确性。3.4 A*在 UCS 上叠加启发式引导方向A* 的代码只比 UCS 多一行push 时的优先级从纯代价改成代加启发式。def aStarSearch(problem, heuristicnullHeuristic): frontier util.PriorityQueue() start problem.getStartState() frontier.push((start, [], 0), heuristic(start, problem)) visited set() while not frontier.isEmpty(): state, path, cost frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: newCost cost stepCost priority newCost heuristic(nextState, problem) frontier.push((nextState, path [action], newCost), priority) return []逻辑说明priority newCost heuristic(nextState, problem)前一半是已付出的代价后一半是对剩余代价的估计两者相加是对总代价的预估。启发式越接近真实剩余代价搜索越「聪明」扩展的无关节点越少。参数说明heuristic是一个接收 (state, problem) 并返回数字的函数。nullHeuristic恒返回 0所以不传启发式时 A* 退化成 UCS。注意启发式必须可采纳——估计值不能超过真实剩余代价——否则 A* 找到的路径不保证最优。提示调试启发式时先把heuristic换成nullHeuristic跑一遍再把自定义的换上对比扩展节点数。扩展节点数变少了说明启发式在起作用变多了说明估计值不可采纳A* 被带偏了。3.5 同一个迷宫上的实测对比在 bigMaze 布局上跑这四个算法路径长度和扩展节点数差异很明显。以我本地跑出来的数据为参考不同版本布局数据略有出入算法扩展节点数路径长度特点DFS约 390较长约 210 步找得快但不保证最优BFS约 620最短节点数多内存压力大UCS约 620最短单位代价下等价于 BFSA* (manhattan)约 450最短扩展节点少综合最优这个对比非常有说服力BFS 和 A* 都能找到最短路径但 A* 的扩展节点少了近三成。在实际项目中节点数直接对应内存和时间这也是为什么真实路径规划场景几乎不用纯 BFS而是用 A* 及其变体。4. 高级问题进阶Corners 和 Food 场景里的状态设计与启发式前四关是热身Corners 问题开始才是真正考验状态设计能力的地方。这里的目标从「到达一个点」变成「遍历一组点」状态空间一下子复杂起来。4.1 CornersProblem目标从单点变成四个角Corners 问题的难点不在算法而在状态定义。吃完四个角意味着 Pacman 有一组「已完成目标」的信息要携带。如果状态还只用坐标表示搜索会丢失关键信息从同一个位置出发可能已经吃掉两个角也可能一个都没吃这两种情况不能混为一个状态。解决方案是把状态扩成((x, y), visitedCorners)visitedCorners 记录已经到达过的角落。关键是 visitedCorners 也要塞进状态里而不是做成全局变量——搜索树里每个分支的访问历史不同全局变量会让不同分支互相污染。def isGoalState(self, state): x, y state[0] visitedCorners state[1] return len(visitedCorners) 4 def getSuccessors(self, state): successors [] x, y state[0] visitedCorners state[1] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: dx, dy Actions.directionToVector(action) nextx, nexty int(x dx), int(y dy) if not self.walls[nextx][nexty]: nextVisited set(visitedCorners) if (nextx, nexty) in self.corners: nextVisited.add((nextx, nexty)) successors.append(((nextx, nexty), tuple(sorted(nextVisited)), action, 1)) return successors逻辑说明isGoalState 检查 visitedCorners 的个数是否达到 4getSuccessors 里每次移动后判断新位置是否在四个角之一在的话就把该角加入集合。注意tuple(sorted(nextVisited))把集合转成排序后的元组是为了让状态可哈希这也呼应了第 2 章说的不可变状态要求。参数说明self.corners是 layout 里四个角的坐标列表Directions.NORTH等是常量字符串Actions.directionToVector 负责把方向映射成坐标增量。getSuccessors 返回的元组是(nextState, action, stepCost)stepCost 这里写死为 1。4.2 cornersHeuristic曼哈顿距离组合出来的可采纳启发式Corners 场景要找最短路径遍历四个角一个自然的想法是用曼哈顿距离组合出现状下的剩余代价。最简版本是当前位置到最近未访问角的距离这样估计明显偏乐观但满足可采纳性。实际效果更好的做法是不仅考虑当前点到最近角的距离还要考虑这些角彼此之间的连通代价。我的做法是取两个值的较大者当前点到最近未访问角的曼哈顿距离以及剩余未访问角彼此之间的最短连接距离的某种近似。取 max 是为了保住可采纳性因为启发式只要求不超过真实代价偏小的估算总是安全的。def cornersHeuristic(state, problem): corners problem.corners x, y state[0] visited state[1] unvisited [c for c in corners if c not in visited] if not unvisited: return 0 return min(manhattanDistance((x, y), c) for c in unvisited)逻辑说明这个版本只考虑第一步——到最近未访问角的距离。真实方案里通常会再加一层「剩余角之间的最小连接」比如把剩余角按曼哈顿距离贪心串成一条链把链总长的一部分并入估计值。加这一层后扩展节点数会显著下降但必须验证合并后的值仍然不超过真实代价。参数说明manhattanDistance接收两个坐标元组返回abs(x1-x2)abs(y1-y2)在 Pacman 项目里它默认忽略墙的存在所以一定是真实步数的下界这保证了可采纳性。4.3 FoodProblem状态包含食物集合搜索空间指数增长Food 问题比 Corners 更狠。Corners 只需要记四个角的状态Food 场景的地图里有几十个豆子每个豆子都可能被吃掉或没被吃掉状态组合数指数爆炸。FoodSearchProblem 的状态是(position, foodGrid)foodGrid 里记录了当前哪些位置还有豆子。给 Food 写启发式是最容易翻车的地方。一个合格的可采纳启发式思路是从当前位置出发至少要走一段路才能抵达某个剩余豆子吃完所有豆子还需要在豆子之间移动。可以用剩余豆子的最小生成树MST总长作为下界估计因为无论怎么走要经过所有剩余豆子路径长度不会小于连接这些点的最小生成树长度。def foodHeuristic(state, problem): position, foodGrid state foods foodGrid.asList() if not foods: return 0 def md(a, b): return abs(a[0] - b[0]) abs(a[1] - b[1]) h 0 for f in foods: h max(h, md(position, f)) return h逻辑说明这个实现只用当前位置到最远豆子的距离做估计是最保守的版本可采纳但偏弱。我一般会在h 0附近再加一层对剩余豆子集合构造带权完全图边权是曼哈顿距离求最小生成树总长把「当前点到最近豆子距离 MST 总长」和当前版本取 max。这样估计更紧但依然保持可采纳。参数说明foodGrid.asList()返回当前剩余豆子的坐标列表。md是局部的曼哈顿距离函数。注意 foodHeuristic 的 state 结构与 Corners 不同它的第一个元素是位置第二个是食物网格写自定义启发式时一定要先确认 state 的结构否则就是在盲猜。4.4 suboptimalSearch什么时候可以放弃最优解Food 场景规模一大A* 也很难在有限时间内找到严格最优路径。课程里有个子问题专门允许你返回一条非最短但足够好的路径这种「差不多得了」的思路在实际工程里很常见路径规划第一优先级是别撞墙、能到达其次才是绕路少。我的做法是每次从当前位置贪心选择最近的豆子走过去吃完再重新计算。这种方式扩展节点数极少路径长度比最优长一些但胜在快。5. 运行指南与避坑记录从 Python 2 到 tkinter 的五个深坑代码看懂了下一步是把项目跑起来。这个项目年代比较早运行环境有不少暗坑我把最常见的几个问题按「现象 → 原因 → 解决」整理出来照着排查基本能一次通过。5.1 跑起来的三种方式# 图形界面肉眼观察搜索路径 python pacman.py -l mediumMaze -p SearchAgent -a fnbfs # 指定 A* 和曼哈顿启发式 python pacman.py -l bigMaze -p SearchAgent -a fnastar, heuristicmanhattanHeuristic # 静默模式不开图形窗口适合调试 python pacman.py -l mediumMaze -p SearchAgent -a fnbfs --frameTime 0 -q # 跑自动评测中的第一道题 python autograder.py -q q1逻辑说明--frameTime 0把每帧间隔设为 0让它以最快速度跑完-q关闭图形界面只输出最终统计信息。自动评测是验证改动的唯一标准本地手动跑通不代表评分能过因为 autograder 会检查路径代价和启发式可采纳性。注意autograder 默认按 Python 2 语法解析代码。如果你用 Python 3 跑看到print相关语法错误优先考虑版本兼容问题而不是怀疑代码写错了。5.2 高频踩坑记录坑一Python 3 下直接报SyntaxError: invalid syntax。原因是项目底子是 Python 2 写的print还是语句不是函数。解决要么安装 Python 2 环境要么全局把print xxx替换成print(xxx)。我一般把 autograder 也一并转成 Python 3 语法方便统一调试。坑二图形窗口打开后秒退或者直接不显示。原因多半是系统里没有 tkinter 库或者当前环境不支持图形界面。解决在本地桌面环境安装 python3-tk 再重试如果用的是远程服务器直接走--frameTime 0 -q的静默模式完全不需要图形界面。坑三搜索卡住几分钟不结束。这个现象基本可以断定是状态哈希出了问题。比如把状态里的坐标用 list 保存list 不可哈希visited set 永远判重失败同一批状态被无限次重新扩展。解决所有进 visited 的状态一律转成 tuple 或 frozenset我在第 4 章的 Corners 代码里特意用了tuple(sorted(nextVisited))就是防这个。坑四DFS 跑出来的路径明显在绕远路甚至能看到回头路。原因是很多简化的 DFS 实现里在 push 时就标记 visited导致某些分支被过早剪掉路径质量更差。解决统一在 pop 时判重让 DFS 先把一条路探索到底再回头探索其他分支。这样能保证 DFS 至少返回一条可达路径虽然不一定最短。坑五自定义启发式之后A* 返回的路径不是最优的。原因是启发式不可采纳估计值高于真实剩余代价。解决验证「当前点到目标的最短距离」和「启发式返回值」的大小关系确保前者永远不小于后者。最简单的手法是对多个不同估计取 max得到的新函数通常更容易保持可采纳。5.3 验证不想玄学用 autograder 和自定义日志跑 autograder 并不是只看总分。我习惯在执行时加一个统计扩展节点数的计数器每 pop 一个状态就加一终局打印出来。同一个布局下比较 BFS 和 A* 的扩展节点数如果 A* 节点数反而更多那启发式大概率有问题。autograder 跑完会明确指出哪道题最优性失败那里就是启发式返回错误估计的位置可以先单独打印每次的 estimate 和真实距离比对几组数据就能定位到具体逻辑。6. 二次开发思路把搜索算法套到自己的场景里这个项目的接口设计有个很实用的特点搜索算法不关心你是迷宫还是别的什么图只要你实现四个方法四个搜索函数直接复用。这一章聊点改造技巧。6.1 换地图layout 文件就是你的实验场layouts 目录下的迷宫是纯文本%表示墙空格表示可走路径P是吃豆人起点。直接复制一个文件改几行就能造出一个新迷宫来验证你的启发式。我把 map 尺寸改大、把豆子位置摆出奇怪的形状专门用来测试启发式会不会在某些布局下崩掉。这个操作零成本却比在固定地图上调参更能暴露问题。class MyProblem: def __init__(self, start, goal, walls): self.start start self.goal goal self.walls walls def getStartState(self): return self.start def isGoalState(self, state): return state self.goal def getSuccessors(self, state): successors [] # 遍历四个方向返回 (nextState, action, stepCost) return successors def getCostOfActions(self, actions): return len(actions)逻辑说明这个自定义 Problem 骨架直接扔进 search.aStarSearch 就能用只要你把 getSuccessors 按实际场景填完整。参数说明walls只是一个示例字段实际场景里可能换成图、网格或者导航数据只要保证四个接口语义正确即可。这套东西最值得带走的经验是改完代码别只在一个地图上跑多换几个布局顺手把 autograder 全量跑一遍。我第一次改 foodHeuristic 时只在给定布局下调得飞快结果 autograder 随机布局一跑就挂原因就是我针对固定布局过拟合了。从那以后我每次改完都强制走一遍全量评测换三个不同 layout 各跑一次。希望帮到你。本文还有配套的精品资源点击获取
