简介CS188 吃豆人游戏 Project 2: Multi-Agent Search 项目包源自伯克利大学人工智能入门课程面向希望动手实践多智能体搜索算法的学习者。项目以经典吃豆人游戏为环境涵盖 Minimax、Expectimax 等对抗搜索思想并涉及 A*、Dijkstra、Q-learning 等路径规划与强化学习方法帮助理解多个角色在动态迷宫中的协同与对抗决策。压缩包共 60 个文件、350KB以 Python 源码12 个 .py和编译缓存20 个 .pyc为主另有 11 个 .lay 迷宫布局、工程配置.xml/.iml以及实验指引文档.docx便于直接导入 PyCharm 运行与调试。目前已有 5495 人学习下载资源包含完整游戏引擎、多智能体搜索算法实现、多张经典地图、测试用例和伯克利课程作业说明既能用于课程作业对照也可作为人工智能入门的实战练手素材。1. 从零手写对抗搜索这就是伯克利 CS188 的吃豆人 Project 2第一次跑通 CS188 的吃豆人 Project 2你会在终端里看到自己的 MinimaxAgent 被幽灵堵在角落里反复横跳最后 score 停在个位数。这个项目是伯克利 CS188 课程里最经典的 Multi-Agent Search 作业它让吃豆人在有多个幽灵同时追击的环境里自主决策吃豆子、躲幽灵、抢能量豆。别小看这个游戏它内部是一个完整的对抗搜索框架——每个幽灵都是一个独立的最小化玩家吃豆人是最大化玩家整个决策过程就是一个多智能体博弈树搜索。它的核心价值在于你能亲手把 Minimax、Alpha-Beta 剪枝、Expectimax 这些 AI 入门必学的算法从伪代码变成能实际跑分的 Python 代码同时评估函数的设计会逼着你思考「一个状态到底值多少分」。这个项目适合正在啃 Berkeley CS188 课程、准备算法面试、或者想搞明白对抗搜索落地细节的任何人。2. 先把博弈树立起来Minimax 搜索的递归实现与评估函数设计2.1 对抗搜索的基础为什么吃豆人游戏是个零和博弈吃豆人游戏里的对抗关系非常纯粹吃豆人得分越高幽灵的追捕就越失败幽灵抓住吃豆人游戏直接结束吃豆人分数归零。零和博弈的意思是一方的收益完全等于另一方的损失。在这个设定下多个幽灵可以被看作同一个最小化团队——每个幽灵都试图让吃豆人的得分最小化。这个视角是理解 Multi-Agent Search 的关键。传统 Minimax 是两人轮流走棋而这里是一个吃豆人对多个幽灵所以博弈树每一层交替出现吃豆人层最大化→ 幽灵1层最小化→ 幽灵2层最小化→ … → 吃豆人层。这个层级顺序直接决定了递归函数的调用方式每个幽灵都要单独占用一层最小化节点而不是把所有幽灵合并成一个节点。// 博弈树层级的伪代码 max_node (吃豆人回合): for each legal action: value min_node_ghost1(下一个状态) best max(best, value) min_node_ghostK (幽灵K回合): for each legal action: if K 幽灵总数: value min_node_ghost(K1)(下一个状态) else: value max_node(下一个状态) // 所有幽灵走完回到吃豆人回合 best min(best, value)这里有个很关键但容易忽略的设计幽灵回合之间是顺序执行的不是同时行动的。游戏里每个幽灵在每一轮都有自己独立的移动回合所以博弈树的深度是「吃豆人 1 步 幽灵1 1 步 幽灵2 1 步 …」这样累积下来的。如果你把递归写成「吃豆人 → 所有幽灵合并 → 吃豆人」那你的评估时机就错了跑分的时候会遇到幽灵明明还有行动机会、你的搜索却提前停在了不该停的深度上。2.2 从零实现 MinimaxAgent递归深度、终止条件与返回值约定CS188 项目 2 的骨架代码里已经给了MinimaxAgent类的框架你需要自己实现getAction和递归的value函数。先搞清楚骨架代码的输入输出约定getAction接收一个gameState返回一个合法的direction方向字符串而递归函数返回的是评估值数值不是动作。这个「返回数值」和「返回动作」的分离是搜索算法的标准套路。def getAction(self, gameState): # 返回能让状态评估值最大的动作 best_value float(-inf) best_action None for action in gameState.getLegalActions(0): value self.value(gameState.generateSuccessor(0, action), 0, 1) if value best_value: best_value value best_action action return best_action def value(self, gameState, agentIndex, depth): if gameState.isWin() or gameState.isLose() or depth self.depth: return self.evaluationFunction(gameState) if agentIndex 0: return self.max_value(gameState, agentIndex, depth) else: return self.min_value(gameState, agentIndex, depth)这段代码的每个参数都有明确含义。agentIndex0表示吃豆人1到numAgents-1表示各个幽灵depth是你从根节点向下的层数计数。这里有个常见的实现陷阱depth 什么时候自增。正确逻辑是「每完成一轮所有 agent 的行动」深度加一也就是说只有幽灵全部走完、再次轮到吃豆人的时候 depth 才应该加 1。如果你在每次递归调用时都加 depth那么搜索树的深度会比预期浅很多——因为吃豆人一层 幽灵一层就算了两层深度实际游戏里这才算半轮。继续看max_value和min_value的实现def max_value(self, gameState, agentIndex, depth): best float(-inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) best max(best, self.value(successor, 0, depth 1)) return best def min_value(self, gameState, agentIndex, depth): best float(inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) next_agent agentIndex 1 next_depth depth if next_agent gameState.getNumAgents(): next_agent 0 next_depth depth 1 best min(best, self.value(successor, next_agent, next_depth)) return best注意min_value里的关键差异当幽灵走完后下一个 agent 重新指向吃豆人next_agent 0同时 depth 加一而max_value里 depth 不变因为吃豆人走完就该轮到幽灵。很多刚上手的人在max_value里也写了 depth 1导致搜索深度翻倍运行时间呈指数级爆炸。我在调这个 bug 的时候花了一个晚上最后打印递归轨迹才发现是深度计算重复了。2.3 评估函数把游戏状态压成一个可比较的数搜索深度达到叶子节点时递归需要返回一个评估值这个值就是evaluationFunction干的事。项目骨架里给了一个简单的scoreEvaluationFunction它直接返回gameState.getScore()——也就是游戏本身的分数。这个函数不是不能用只是信息量太少它只能反映已吃豆子的数量完全没考虑幽灵距离、食物分布这些关键信息。如果你用这个评估函数跑深度为 4 的 Minimax跑出来的吃豆人大概率会一头撞进幽灵嘴里——因为「即将被抓」和「暂时安全」在分数上没有区别。评估函数设计的基本思路是把影响胜负的元素拆成特征再给每个特征配权重。我自己的实现里最有用的三个特征是食物距离离最近食物的距离越近越好幽灵距离离最近幽灵的距离越远越好能量豆状态吃豆人是否在能量状态、幽灵是否 scared此时幽灵越近反而越好项目里也允许你用一个自定义类BetterEvaluationFunction来实现这些逻辑后面第 6 章我会专门展开怎么调参。3. 剪枝省时间Alpha-Beta 剪枝的边界条件与剪枝顺序3.1 从 Minimax 到 Alpha-Beta剪枝的本质是给决策区间收束Alpha-Beta 剪枝是 Minimax 的优化版本核心思想一句话如果一个分支已经不可能影响根节点的决策就直接砍掉不再递归展开。它的实现是在递归过程中维护两个值——alpha当前最大化节点已经找到的最佳候选值和 beta当前最小化节点已经找到的最佳候选值。当某个最小化节点的值已经低于父级最大化节点的 alpha那就没必要再往下搜了因为父级已经有一个更好的选择同理当某个最大化节点的值已经高于父级最小化节点的 beta同样剪掉。这个算法在吃豆人项目里最大的收益是效率。无剪枝的 Minimax 复杂度是 O(b^d)其中 b 是分支因子吃豆人平均有 4 个合法方向d 是搜索深度加了剪枝后理想情况下复杂度能降到 O(b^(d/2))也就是同样的时间可以搜两倍深度。在实际运行中因为游戏状态分叉较多剪枝效率通常没那么理想但也能稳定提升 30%60% 的搜索速度。这个提升直接关系到你能不能把搜索深度从 2 提升到 4——深度每加一决策质量完全是两个级别。3.2 实现 AlphaBetaAgent参数传递、剪枝判断与边界条件def getAction(self, gameState): best_value float(-inf) best_action None alpha float(-inf) beta float(inf) for action in gameState.getLegalActions(0): successor gameState.generateSuccessor(0, action) value self.value(successor, 0, 1, alpha, beta) if value best_value: best_value value best_action action alpha max(alpha, best_value) return best_action def value(self, gameState, agentIndex, depth, alpha, beta): if gameState.isWin() or gameState.isLose() or depth self.depth: return self.evaluationFunction(gameState) if agentIndex 0: return self.max_value(gameState, agentIndex, depth, alpha, beta) else: return self.min_value(gameState, agentIndex, depth, alpha, beta)这里有一个增量更新的细节在getAction的循环里每算完一个动作就要更新 alpha这样后面动作的搜索能直接利用前面动作的结果做剪枝。如果你忘了这一行剪枝完全不生效跑分结果和普通 Minimax 一模一样但代码更复杂——纯属白忙活。再看max_value和min_value里的剪枝条件def max_value(self, gameState, agentIndex, depth, alpha, beta): best float(-inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) best max(best, self.value(successor, 0, depth 1, alpha, beta)) if best beta: return best # 剪枝这个值已经超过父层最小值节点的上限了 alpha max(alpha, best) return best剪枝方向是很多人绕不过去的坎max_value 里判断的是best betamin_value 里判断的是best alpha。把这两个条件搞反是最常见的错误——我见过很多版本的代码把写成结果搜索路径根本没剪或者更糟把不该剪的节点剪掉了导致决策质量下降。判断逻辑的核心是你要看的是当前节点的值会不会「越界」到父层已经确定的范围之外不是看它相对于自身层级的优劣。3.3 剪枝顺序的玄学为什么评估函数顺序决定效率Alpha-Beta 剪枝的效率非常依赖子节点的访问顺序。分类讨论如果你先访问的是最优移动方向剪枝率接近最大化可能砍掉 70% 以上的节点如果你先走的是最差方向剪枝几乎无效运行时间逼近朴素 Minimax。这意味着你在getAction里对动作列表做一个粗略排序能带来显著收益。常见做法是先按评估函数的值粗略排序动作吃豆人层按评估值降序先探索看起来最好的方向幽灵层按评估值升序先探索对吃豆人最不利的方向。这里的「粗略排序」可以在搜索前做一次快速评估不精确没关系只要方向大致正确就有效果。def getAction(self, gameState): actions gameState.getLegalActions(0) # 先粗排按当前状态的即时得分降序把可能更好的动作放前面 actions.sort( keylambda action: self.evaluationFunction( gameState.generateSuccessor(0, action) ), reverseTrue ) # 然后进入正常的带剪枝搜索循环 ...这里有个血泪经验排序本身也要花时间如果评估函数很重比如要扫描整张地图计算食物距离那排序开销可能抵消剪枝收益。实践里可以做一个简化——只按当前吃豆人位置与最近幽灵的距离排序或者干脆不排序直接用原始动作列表。我在项目中尝试过做完整评估排序跑分时反而变慢了 10%换成只有吃豆人距离的快速排序后剪枝效率上去了总运行时间降了一半还多。4. 不确定性与期望Expectimax 和概率评估模型4.1 从确定到随机幽灵行为的不确定性建模Minimax 假设幽灵每一步都会选择最优策略——也就是对吃豆人最不利的移动。但实际的吃豆人游戏里幽灵的行为并不完全是完美对抗它们有各自的追逐算法有的是随机移动的有的是按固定路线巡逻。如果你建的模型假设它们永远完美决策你的吃豆人会过于悲观错失很多本来可以安全吃豆子的机会。Expectimax 算法把 Minimax 中的最小化节点替换成了「期望节点」不取子节点的最小值而是取子节点的平均值或者按已知概率分布的加权平均。它表达的是这样一个决策逻辑你对手的行为不是完美的但你也不知道它会做什么此时最合理的假设是它的各种可能行为等概率发生你选择令期望收益最大的动作。在这个项目里Expectimax 通常能得到比 Minimax 更高的分数——因为吃豆人的目标本来就是最大化总得分而不是打败一个完美的幽灵理性玩家。4.2 实现 ExpectimaxAgent期望节点的差异与实现要点Expectimax 的实现与 Minimax 非常相似差别只在min_value的聚合逻辑上def exp_value(self, gameState, agentIndex, depth): legal_actions gameState.getLegalActions(agentIndex) if len(legal_actions) 0: return self.evaluationFunction(gameState) total 0.0 for action in legal_actions: successor gameState.generateSuccessor(agentIndex, action) next_agent agentIndex 1 next_depth depth if next_agent gameState.getNumAgents(): next_agent 0 next_depth depth 1 total self.value(successor, next_agent, next_depth) return total / len(legal_actions)注意total必须用浮点数整数除法在 Python 2 里会导致期望值被截断。CS188 项目环境虽然提供了 Python 3 版本但有的同学本地跑的还是 Python 2 的旧版环境这个坑真踩过的人才知道多隐蔽。还有个细节幽灵的行动概率在实际吃豆人游戏里不是均匀分布的。幽灵在岔路口有偏向性尤其是追击状态下的幽灵更倾向于选择「离吃豆人更近」的方向。项目本身允许你使用任意概率分布如果你想让模型更贴近真实可以把期望值改为加权平均——每个动作的权重由该动作导致的状态与吃豆人距离的倒数决定。但我一般建议先做好均匀版本因为加权版本容易引入额外的超参数调起来没完没了。4.3 评估函数的数值尺度为什么绝对值大小不重要Expectimax 和 Minimax 有一个微妙差异Minimax 只关心数值的相对大小最大对最小而 Expectimax 把数值直接做平均这就让评估函数的数值尺度开始影响决策。设想一种极端情况如果你的评估函数对「距离幽灵 1 步」返回 -100对「距离幽灵 2 步」返回 0那么在幽灵的期望节点里「幽灵可能走向你」这个分支会给期望值造成一个 -50 的打击如果同样的状态你用 -1000 和 0 来表示期望值就是 -500。这会影响吃豆人的决策倾向——数值尺度差距越大吃豆人对风险越敏感。我调参时发现一个实用规律评估函数最好让不同局面之间的差值保持在相对接近的数量级比如最大最小差值在 100 以内这样 Expectimax 的期望聚合不会因为个别极端值而扭曲决策方向。你可以采取特征归一化或者用 tanh 把数值压到 (-1, 1) 区间都可以获得更稳定的行为表现。5. 绕开隐藏的坑判分陷阱与常见翻车现场5.1 深度为 0 时的判断终止状态检测的顺序问题写终止条件时一个逻辑顺序上的坑很隐蔽先判断 game over还是先判断搜索深度到达极限。如果你把depth self.depth写在前面那么当游戏已经结束时你返回的是评估函数的估值而不是实际的胜负结果反过来如果isWin/isLose写前面深层搜索在碰到终局状态时会提前终止递归。这个顺序直接影响两个地方一是终局状态的精确性下沉的博弈树不会错误展开二是评估函数是不是会被应用到已经结束的状态上。用我自己的例子来看有一次测试里吃豆人只剩下最后一步就会被抓到搜索深度刚好还有剩余结果递归继续向下展开到了幽灵的几层最终返回的评估值是基于「假设吃豆人已经被抓但游戏还在继续」的非法状态。修正办法很简单——把两个条件放到同一行判断用or连接顺序不重要但代码可读性好很多if gameState.isWin() or gameState.isLose() or depth self.depth: return self.evaluationFunction(gameState)5.2 幽灵多步移动与吃豆人单步移动的不对称CS188 的吃豆人游戏规则是吃豆人每行动一次所有幽灵各行动一次。这意味着在你的博弈树里吃豆人走一步的「代价」是多个幽灵步搜索深度在幽灵层会被快速消耗。这会造成一个反直觉的行为看起来你搜索了深度为 4 的树实际上只覆盖了吃豆人 1 步 幽灵 3 步——吃豆人的决策粒度很粗。如果你想真正让吃豆人能看到自己未来 2 步的后果深度需要设到2 * (numAgents - 1) 2左右。但深度翻倍的代价是节点数指数级上升。一个替代方案是让深度不按 agent 层数累计而是按吃豆人的实际决策次数累计——也就是在幽灵层深度不变、只有回到吃豆人层才深加一。我遇到过不少同学在这个地方理解偏差导致深度设了 4 却只能看到吃豆人 1 步——期望的远期规划能力完全没体现出来。5.3 评估函数与吃豆人的位置权重越靠近幽灵越危险一个特别容易被低估的评估特征幽灵距离的权重。如果你只用「最近食物距离」作为评估特征吃豆人会一味冲向食物完全不理会路上的幽灵反过来如果幽灵距离权重太高吃豆人又会缩在原地一步都不敢动分数极低。测试时有一个典型现象吃豆人在地图中间食物在左下角一个幽灵在左边通道守着。如果幽灵距离权重小于某个阈值搜索树会判定「冲过去吃食物」的路径评分更高因为评估函数在终端状态时食物收集的加分盖过了幽灵逼近的减分但实际上冲过去的结果是在到达食物之前就被抓。解决手段是给幽灵距离加非线性惩罚——比如距离小于等于 2 时惩罚急剧增大而不是线性递减。我常用的实现是def ghost_penalty(dist): if dist 1: return -500 elif dist 2: return -100 else: return -dist * 2这比单一的线性权重稳定得多——因为幽灵的威胁本质上是「越近越危险」的非线性关系尤其在它的下一步就能抓到你的距离上惩罚必须远远超过其它所有特征的加权总和你的吃豆人才会长记性。5.4 迭代加深与超时机制怎么卡时间项目评测有运行时间限制如果你的搜索太慢会被判超时。想在固定时间内获得尽可能好的决策质量常见做法是实现迭代加深先搜深度 1再搜深度 2以此类推直到时间耗尽返回上一次完成搜索的决策结果。这需要你把getAction里的深度参数做成可变的在每次迭代前记录开始时间在每个动作计算前检查时间余量。import time def getAction(self, gameState): start_time time.time() best_action gameState.getLegalActions(0)[0] for depth in range(1, self.max_depth 1): current_best None current_value float(-inf) for action in gameState.getLegalActions(0): if time.time() - start_time 0.9: # 留下 0.1 秒余量给渲染 return best_action successor gameState.generateSuccessor(0, action) value self.value(successor, 0, depth, alpha, beta) if value current_value: current_value value current_best action best_action current_best return best_action这个版本的迭代加深有个小问题Alpha-Beta 剪枝需要在每次迭代时重置 alpha 和 beta否则上一次搜索的边界值会污染新一轮搜索。我在第一次实现时直接把 alpha、beta 定义在了循环外面结果后面轮次的剪枝条件完全错乱。迭代加深的最大好处是在时间受限时你一定能返回一个「上次已完成搜索」的结果——而不是强行中断当前搜索导致决策质量骤降。6. 把胜率从 60% 拉到 90%评估函数调参与对抗性测试技巧6.1 用吃豆人位置、食物距离和幽灵距离搭建评估基线基础评估函数我会从四个特征起步当前游戏分数、最近食物距离、最近幽灵距离、是否处于能量状态。能量状态是一个布尔值它可以让你主动追击幽灵而不用逃跑。把这四个特征线性组合成一个可调的评分函数def betterEvaluationFunction(currentGameState): pacman_pos currentGameState.getPacmanPosition() foods currentGameState.getFood().asList() ghosts currentGameState.getGhostStates() # 最近食物距离 if len(foods) 0: min_food_dist min( util.manhattanDistance(pacman_pos, food) for food in foods ) else: min_food_dist 0 # 最近幽灵距离 min_ghost_dist min( util.manhattanDistance(pacman_pos, ghost.getPosition()) for ghost in ghosts ) weight_food -2.5 # 距离食物越近越好 负权重 weight_ghost -4.0 # 距离幽灵越近越差 负权重 if currentGameState.isWin(): return float(inf) # 胜利直接给极大值 if currentGameState.isLose(): return float(-inf) score currentGameState.getScore() score weight_food * min_food_dist score weight_ghost * min_ghost_dist return score这段代码是评估函数的骨架取舍都在权重里。weight_ghost比weight_food更负这意味着吃豆人更优先保命而不是吃豆子——这个倾斜方向是我在多次测试后确认的保守策略通常比冒险策略的总分数更高因为死一次等于清零而慢一点吃豆子只损失一点增量分数。注意看isWin/isLose的返回终局状态返回float(inf)或float(-inf)能保证搜索树不会丢弃这些至关重要的节点。6.2 对抗自测用比你强的对手测试别只看总分项目自带的自动评测会跑一批固定布局每个布局有一个基准分数你的 agent 超过基准线才算通过。但仅仅过了基准线远远不够——我一般会把测试难度调高让幽灵采用比默认更聪明的追逐策略比如每次都直接朝吃豆人方向移动或者增大幽灵数量。拿我自己实践的结果举例默认稀疏地图上胜率 95%换到多幽灵的开放地图后胜率直接掉到 70% 以下原因就是评估函数的幽灵距离惩罚不够狠——只有当幽灵接近到 2 格内才产生高惩罚而开放地图上幽灵的接近速度更快导致吃豆人经常在惩罚生效前就被拦截。提高胜率的有效做法是给评估函数加一个「安全系数」当最近幽灵距离小于某个阈值时强制执行逃跑方向忽略食物的吸引力。很多同学不会做这个硬切换导致吃豆人在紧急情况下还在犹豫要不要绕路吃豆子。我的处理是设置一个逃生阈值常量ESCAPE_DIST 3在评估函数返回值里单独加一个惩罚项当距离小于阈值时把惩罚调到远高于所有食物收益的总和。6.3 调参的边界过度拟合局部地图的陷阱与最后检查调参最需要注意的是「过度拟合」——你在一张特定地图上把参数调得妙不可言但换一张地图就全线崩溃。比如我最早把幽灵距离权重调到-8.0在狭窄走廊地图上表现完美但在开阔地图上吃豆人过于保守宁可原地转圈也不愿意穿过危险区域去取食物——那张图上有充足的安全路线不需要这么极端的避险意识。正确做法是在多种布局上交叉测试至少用课程自带的若干张地图各跑一遍而不是死磕一张最难的地图。最后一轮验收前我习惯做一个快速检查清单深度设为 4 时单局运行时间是否在 2 秒内幽灵距离权重在-3到-5之间食物权重在-1.5到-3之间终局状态返回inf/-inf是否生效迭代加深的时间切断是否在 90% 时限左右触发。对着这四个维度逐项验完再跑一遍完整的官方评测脚本看是否所有布局都通过基准然后调一次随机种子多跑几遍——吃豆人游戏本身有随机性单次跑分波动很大不能只看一次结果定结论。从那以后我每次拿到一个新的搜索类作业或者真实项目里的博弈决策需求都会强制走一遍「先写朴素实现 → 加剪枝 → 换概率模型 → 设计评估函数 → 多地图交叉验证」这个流程包括在评估函数里预设逃生阈值这种小习惯都是从 CS188 吃豆人这项目里踩坑踩出来的。它不只是一份课程作业更是一套完整的对抗搜索落地方案——希望帮到你。本文还有配套的精品资源点击获取