Pacman项目实战：从搜索算法到强化学习的AI大作业全解析

简介伯克利大学人工智能课程的 Pacman 吃豆人 Python 作业源码面向学习搜索算法、强化学习与自动决策的 AI 初学者也适合高校学生对照课程实验或复现经典赛题。zip 压缩包内共 204 个文件主要包含 62 个 solution 与 62 个 test 文件、38 个 .lay 迷宫地图、20 个 .py 脚本、9 个 config 配置以及少量缓存与版本说明文件整体大小约 252KB目录结构适合按模块拆解学习下载后即可按需取用。已有 5581 人学习下载。代码覆盖状态空间搜索、A*/Dijkstra 路径规划、启发式评估和动作选择等核心环节并提供 Q-learning/SARSA 等强化学习实现配合 38 张地图如 bigMaze.lay和配套 solution/test 文件可直观验证不同算法在吃豆人场景中的表现帮助理解 AI 从环境感知到策略优化的完整链路。对想做课程设计、算法对比或伯克利作业参考的读者这份紧凑的源码包具有很高复用价值是一份难得的 AI 实践样例。1. 为什么AI课的大作业偏偏选吃豆人你可能在网上搜过“人工智能作业 pacman python源代码”然后看到一堆GitHub仓库和课程页面。没错这就是加州大学伯克利分校CS188那门经典AI导论课的项目现在国内不少高校的人工智能导论、机器学习基础课程也直接拿它当大作业。一个游戏demo能被这么多学校同时选中本身就能说明很多问题。吃豆人这个游戏外壳特别适合做AI算法试验场。游戏规则足够简单——吃豆人要在迷宫里吃掉所有豆子同时躲开四只巡逻的幽灵。但简单规则之下它天然涵盖了AI领域的几大经典问题路径搜索、对抗博弈、不确定性推理、强化学习。一个Pacman项目做下来等于把AI导论课的核心知识点全部实战了一遍。更妙的是这个项目的难度梯度设计得非常好。第一次接触的人可以从最基础的深度优先搜索DFS和广度优先搜索BFS写起几个小时就能跑通但如果你想在对抗搜索和强化学习部分拿高分又需要真正吃透Minimax、Alpha-Beta剪枝、Q-learning这些算法甚至还有Approximate Q-learning这种偏工程化的变体。所以不管你是刚学Python的本科生还是想深入理解AI算法原理的研究生这个项目都有值得你研究的地方。我在带学生做这个作业的时候发现大多数人的问题不是“不会写代码”而是“不知道代码应该怎么写才符合这个项目的架构”。项目框架给了你一堆现成的类和方法但算法的核心逻辑需要你自己填充很多人卡在第一步不知道从哪个文件下手不知道函数签名里的参数是干嘛的更不知道测试脚本会怎么调用你写的代码。这篇文章就是来解决这些问题的我会从项目结构、核心算法的实现思路、以及我实际跑代码时踩过的坑一条条讲清楚。2. 先把代码骨架摸透再谈写算法2.1 五个核心文件的职责划分Pacman项目的文件结构乍一看有点吓人一大堆.py文件堆在目录里。但其实你真正需要动手修改的只有五个文件其他的都是框架代码看都不用看当然前提是你只想完成作业而不是想做二次开发。这五个文件分别是search.py搜索算法模块实现DFS、BFS、UCS一致代价搜索和A*。这是第一个作业的核心。searchAgents.py搜索问题的建模把“吃豆人找豆子”这个具体问题转换成搜索问题的抽象表示包括状态定义、目标测试、代价函数、启发函数。multiAgents.py多智能体对抗搜索实现Minimax、Alpha-Beta剪枝、Expectimax还要写一个评估函数Evaluation Function。这是第二个作业。qlearningAgents.py强化学习模块实现Q-learning和Approximate Q-learning。analysis.py几个分析题通常是用文字回答算法相关的问题。弄清这五个文件的分工你就知道作业的边界在哪里了。search.py里的算法是通用的不应该依赖任何具体问题searchAgents.py里的问题建模才是跟吃豆人游戏挂钩的地方。这种分层设计本身就是一种很好的工程范式算法逻辑和业务逻辑解耦。你以后写代码也会遇到类似的场景比如你写一个通用的排序函数不应该关心调用方传进来的是学生成绩还是商品价格。2.2 框架代码的调用约定很多人拿到项目后第一反应是打开pacman.py看游戏逻辑这其实是个误区。你应该先看测试文件比如project1/test_cases目录下的测试用例或者直接跑一下官方给的自动评分脚本autograder.py看看它到底在测什么、怎么测。以Project 1为例自动评分脚本会调用search.py里的solve()函数传入一个SearchProblem对象返回一个动作列表比如[West, North, West]。你写DFS还是BFS评分脚本不关心它只关心你返回的路径是否合法、是否最优。这种“黑盒测试”的思路意味着你完全可以自己设计内部实现只要对外接口符合约定就行。这里有一个特别容易忽略的细节search.py里的算法函数接收的problem参数是一个实现了getStartState()、isGoalState(state)、getSuccessors(state)、getCostOfActions(actions)这四个方法的对象。你在写graphSearch图搜索的时候只需要跟这四个方法交互绝对不要直接去访问什么迷宫地图、豆子坐标之类的内部数据。很多学生代码跑不过测试就是因为在这个地方开了小差试图绕过问题抽象直接改游戏状态。3. 搜索算法模块一个函数吃遍四种策略3.1 通用图搜索框架的设计思路Project 1的四个算法DFS、BFS、UCS、A*其实可以写成一个通用函数只是边界数据结构不同。DFS用栈BFS用队列UCS和A*用优先队列。这也是我强烈推荐的做法比每个算法单独写一个函数要干净得多而且不容易出bug。核心框架是这样的def graphSearch(problem, frontier): closed set() startState problem.getStartState() startNode (startState, [], 0) frontier.push(startNode) while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in closed: continue closed.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in closed: newActions actions [action] newCost cost stepCost frontier.push((nextState, newActions, newCost)) return []注意一个细节每次从frontier弹出节点后要先用closed集合判断是否已经访问过如果访问过就直接跳过。这个“延迟判断”的做法比“入队时判断”更通用因为它能同时兼容DFS和BFS/UCS的策略差异。另一方面这个项目里默认要求返回动作列表actions所以每个节点要保存完整的动作序列而不是只保存父节点指针。虽然这样空间复杂度高一些但对作业场景没问题代码也更直观。3.2 为什么BFS能找到最短路径而DFS不能这个问题在作业里是必考的也是很多学生第一次接触图搜索时最困惑的地方。BFS按层扩展节点同一层的节点先入队先出队所以第一次到达目标状态的路径一定经过了最少的边数。在Pacman项目中每个动作的代价是1所以最少的边数就是最短路径。DFS则是沿着一条路走到黑它不保证第一次找到目标时经过的路径是最短的。你可能在迷宫里绕了一大圈才找到豆子而这条路径可能有20步但实际最短路径只要4步。在自动评分脚本里DFS通常只能拿到部分分数因为它能找到一条可行路径只要不做死循环但路径不最优。UCS就是把BFS的队列换成按累计代价排序的优先队列这样每次弹出的都是当前代价最小的节点。当所有动作代价相同时UCS和BFS等价。A则更进一步按f(n) g(n) h(n)排序g是已花费代价h是启发函数估计的剩余代价。只要h是可采纳的不会高估到达目标的实际代价A就能保证最优性同时比UCS高效得多。3.3 启发函数的设计从零到满分的实践A*的性能完全取决于启发函数。Project 1里最容易拿满分的方式是在searchAgents.py里实现一个叫foodHeuristic的函数它接收一个食物的坐标列表状态里包含这些信息返回一个估计值。最朴素的选择是曼哈顿距离即abs(food.x - pacman.x) abs(food.y - pacman.y)。但如果你把所有食物的曼哈顿距离加起来这个启发函数是不可采纳的——它会高估实际代价导致A*失去最优性。正确且简单的可采纳启发是“离最近一个食物的曼哈顿距离”。这个虽然单调但能保证最优性而且比BFS/UCS快不少。想要压榨性能可以尝试“第二个最近的食物距离”这类组合启发或者做一次简化问题的预计算。我个人的经验是先用曼哈顿距离拿基础分再逐步优化。不要一上来就追求复杂启发函数因为复杂意味着出错概率高一旦启发函数设计得不可采纳A*就退化成类似贪心的算法测试点很可能直接挂。4. 对抗搜索模块让吃豆人学会“怕鬼”4.1 Minimax的递归建模过程Project 2的multiAgents.py是很多人第一次接触多智能体博弈的地方。这里的核心思想是吃豆人是一个智能体四只幽灵是另外一个智能体虽然可以拆成多个但通常当作一个整体来建模。吃豆人每走一步都要考虑幽灵下一步会怎么走幽灵又会考虑吃豆人会怎么应对幽灵的应对……这就是Minimax算法的递归结构。实现时你需要写一个递归函数getAction(state, agentIndex, depth)它的逻辑是如果是吃豆人的层agentIndex 0取所有子节点中的最大值。如果是幽灵层取所有子节点中的最小值。到达叶节点游戏结束或深度上限时返回评估函数的得分。这里有三个容易出错的地方。第一深度depth的递增逻辑每轮是“吃豆人走一步、所有幽灵各走一步”完整的一轮结束才算depth1。但幽灵之间是顺序行动的幽灵0先走幽灵1再走……所以getAction里要根据agentIndex判断是加depth还是保持depth不变。第二评估函数返回的是分数不是动作。最大值层要记录的是哪个动作产生了最大的子节点分数而不是直接返回最大分数。第三合法动作可能为空比如吃豆人被四只幽灵团团围住没有出路这时候要让程序返回一个默认动作通常是Stop否则会索引越界。4.2 Alpha-Beta剪枝的边界条件写对了吗Alpha-Beta剪枝是在Minimax基础上的优化核心是维护两个值alpha最大值层已知的下限和beta最小值层已知的上限。当某个子节点的返回值导致alpha beta时就可以剪掉后续分支不影响最终结果。实现在逻辑上不复杂但边界条件很容易写错。我见过最多的bug是Python里递归函数的alpha和beta参数在返回值上处理不对。比如在最大值层你用value max(value, result)之后要alpha max(alpha, value)然后判断if alpha beta: return value在最小值层则是value min(value, result)、beta min(beta, value)、if beta alpha: return value。注意是大于还是大于等于不同写法对最终结果的正确性没有影响但会影响剪枝效率。另外ExpectimaxAgent期望最大化搜索是Project 2的一个选做题它的思路是幽灵不是恶意对抗的而是按一定概率随机行动所以取平均值而不是最小值。如果你想拿高分这个也值得一做。它会让你更直观地理解最小化和期望在博弈树上的区别。4.3 评估函数贪吃和保命怎么平衡评估函数evaluation function是Project 2的另一个大坑。它的输入是一个游戏状态或者能获取游戏状态的GameState对象输出是一个实数表示这个状态对吃豆人有多“好”。Minimax树的叶节点返回的就是这个值所以评估函数的质量直接决定AI的智商。一个简单但有效的评估函数我建议从这几个特征入手当前状态是否赢/输赢了返回一个大正数比如10^6输了返回一个绝对值很大的负数。离最近食物/豆子的距离越近越好。离最近幽灵的距离如果幽灵处于惊吓状态Scared那距离越近越好因为可以反吃幽灵得分如果幽灵是正常状态距离越近越危险要惩罚。剩余豆子数量豆子越少越好因为快赢了。具体数值怎么配比没有标准答案。我的经验是先让“输赢判断”的权重压过一切否则AI为了吃一个豆子直接送命。然后调距离惩罚项让AI在没幽灵时积极吃豆、有幽灵靠近时果断逃跑。你可以开着可视化界面python pacman.py -p ReflexAgent -l mediumClassic反复调权重观察AI的行为是否符合直觉。5. 强化学习模块不写规则也能学会策略5.1 Q-learning的状态抽象与更新公式Project 3的qlearningAgents.py算是整个项目里最有“机器学习味道”的部分。在这里AI不再靠人写规则比如“幽灵在附近就跑”而是通过与环境的试错互动自己学会一套策略。核心算法就是Q-learning维护一张Q表记录在状态s下执行动作a的长期回报期望。更新公式是这样的Q(s,a) Q(s,a) alpha * (r gamma * max(Q(s,a)) - Q(s,a))其中alpha是学习率gamma是折扣因子r是即时奖励s是执行动作a后到达的新状态max(Q(s,a))是下一状态的最大Q值。关键难点在于状态空间的定义。Pacman游戏的状态包括吃豆人位置、所有幽灵的位置和状态、所有豆子的分布。直接把这些全部塞进状态特征里状态空间巨大无比Q表根本存不下。项目框架给了一个简化的方法在qlearningAgents.py中状态通常被定义为“吃豆人的坐标位置 当前到最近豆子的方向 是否有幽灵在附近”这类离散特征。你要仔细看框架给的getState()是怎么写的、getFeatures()返回什么字典然后在此基础上实现更新。5.2 学习率、探索率和奖励设计的调参心得Q-learning要跑起来不难但要跑出好的策略调参和奖励设计缺一不可。我踩过的坑主要有这几个。第一探索率epsilon的衰减。一开始不能让智能体直接选择最大Q值exploitation否则它会一直重复第一次碰巧成功的路径永远探索不到更优策略。通常的做法是前期用高epsilon比如0.3随机探索随着episode数增加epsilon逐渐减小到0.1以下。项目框架里已经有epsilon参数但默认的衰减策略可能不够你可以在每次episode结束后手动乘以一个衰减系数。第二奖励的稀疏性问题。如果只有吃到豆子才给1奖励、被幽灵抓才给-1惩罚那在中等地图上AI很长一段时间都学不到东西因为大多数动作都是“什么都没发生”。这时候可以引入势能奖励potential-based reward shaping比如状态变好后给一个小正奖励变差给一个小负奖励。但注意直接添加和“吃豆子”无关的奖励会改变最优策略所以要用基于势能的形式F(s) gamma * phi(s) - phi(s)这样可以保证不改变最优动作。对于课程作业更简单粗暴的办法是在getReward()里把“靠近食物”或“远离普通幽灵”编码成小的即时奖励。第三训练episode的数量。很多学生发现AI训练了1000个episode还是像个无头苍蝇。我的经验是先在小地图比如testClassic上验证Q-learning能否收敛再放到mediumClassic上跑。小地图跑出合理策略后再加大地图这种从简到繁的process在强化学习里特别重要。Approximate Q-learning是把Q值写成特征的线性组合Q(s,a) w1*f1(s,a) w2*f2(s,a) ...更新时对权重向量做梯度下降。这比查表法更省空间也能泛化到未见过的新状态。框架里已经给了featureExtractor的接口你要做的就是定义特征并在更新公式里用weights[feature] alpha * difference * value来调权重。6. 从零跑通这个项目的实战经验6.1 环境配置和测试命令先说明运行环境这个项目官方支持Python 2但现在的学生大多用Python 3。好消息是伯克利官方已经更新了Python 3的版本GitHub上的Py3分支可以正常跑。配置环境时记得把项目目录加入Python路径否则导入模块会报No module named pacman之类的错误。跑通一个简单测试的指令是python pacman.py -l tinyMaze -p SearchAgent -a fnbfs这条命令用BFS在tinyMaze上跑搜索。如果你的算法实现正确应该能看到吃豆人走到豆子附近停下并打印出路径长度。自动评分则用python autograder.py --project1如果发现某个测试点过不了先把对应的test_cases目录下的测试文件读一遍里面会写清楚期望的输出和你的输出哪里不一致。这个项目的测试文本格式很清晰通常能直接看出来是路径不最优还是非法动作。6.2 三个最容易翻车的实现细节细节一闭包和变量污染。Python的列表默认是引用传递。如果你在getSuccessors里返回的子节点复用了父节点的actions列表后面又用append去扩展它那么所有子节点都会共享同一个列表结果就是路径越积越长。解决办法是创建新列表newActions actions [action]或者actions.copy()。细节二判断是否访问过的时机。我前面提到过“延迟判断”即节点弹出时才检查closed集合。有些人图省事在push之前就判断if nextState not in closed这在DFS下没问题但在A*下可能导致次优解。因为同一个状态可能被不同的路径以不同的代价访问多次你先入队的是代价较大的路径如果入队时就标记为已访问后面代价更小的路径就被错误地挡掉了。标准做法是维护一个“代价字典”而不是单纯的集合或者统一用“弹出时判断”。细节三幽灵的合法动作里有个Stop。幽灵的getLegalActions可能包含Stop动作在Minimax的递归里如果不对这个动作做处理幽灵可能会原地不动看起来像卡住了。通常的策略是过滤掉Stop除非没有其他合法动作。吃豆人的动作里也有Stop但搜索项目里通常要求排除它。6.3 关于“抄源代码”这件事我的建议很多人上网搜“pacman python源代码”是想直接拿到一份答案。我的态度是代码可以看但一定要自己理解之后再写否则后续课程会非常难受。因为Pacman项目里的搜索算法、Minimax、Q-learning是AI课的核心基础如果这份作业你是抄的后面学贝叶斯网络、粒子滤波、神经网络的时候你会发现自己连“状态”“动作”“奖励”这些词都听不懂在说什么。如果实在卡住了我建议的求助顺序是先跑官方给的autograder看错误信息再读test_cases里的具体测试描述然后画图/打印中间状态来debug最后再去看GitHub上的参考实现。而且看参考实现不要直接复制看懂思路后合上代码自己写一遍。这个过程虽然慢但比你期末考前突击一整周要有效得多。从我做助教和带项目的经验来看认真做完Pacman全部项目搜索、对抗搜索、强化学习的人对AI基础概念的理解深度跟只看教程不动手的同学完全不是一个层次。相信我这份努力是值得的。本文还有配套的精品资源点击获取