简介：面向AI学习者与强化学习初学者的CS188实验二多智能体搜索（multiagent）完整资源包，聚焦多个智能体在共享环境中的协作与竞争，覆盖环境模拟、智能体建模、Q-learning与深度强化学习算法实现等关键环节。资源共228个文件，包含88个test与87个solution测试用例及参考答案、18个py源码、16个pyc编译文件，另有11个lay迷宫布局和7个config配置文件，压缩包仅236KB，目录结构清晰，便于对照调试、按需取用。已有470人学习下载。包内从经典迷宫布局到多智能体搜索完整代码框架一应俱全，并保留可运行示例与结果验证方案，既能帮助理解DQN、DDQN、马尔可夫博弈等核心概念，也可直接作为课程实验、面试复习或算法二次开发的起点。

1. CS188 多智能体搜索实验：这包代码到底要你做什么

打开multiagent.zip，里面不是一个完整游戏，而是一个装着吃豆人 Pacman 的“半成品”：你已经能跑、能看幽灵追杀，但吃豆人自己不会思考。CS188 实验二多智能体搜索的目标，就是让你在multiAgents.py里填出几个决策函数，让 Pacman 从“乱撞”变成“会绕着幽灵找食物”。很多初次接触对抗搜索的人，会把全部精力花在背 Minimax 公式上，结果卡在环境跑不通、递归写错、剪枝边界算错这三件事上，白白消耗大量调试时间。这篇笔记会按“跑通→实现→调参→避坑→验证”的顺序，把多智能体搜索这条线完整走一遍，适合正在做这个实验、想拿满 Autograder 分数的同学，也适合想用这个项目练对抗搜索落地的人。

2. 跑通 multiagent.zip：环境、命令行与测分套路

2.1 解包后先看这几个文件，别急着写代码

整个实验的代码量不大，但第一次打开的人容易找错文件。常见做法是先解压，然后按这个顺序读文件：

multiAgents.py里面有四个方法：ReflexAgent.getAction、MinimaxAgent.getAction、AlphaBetaAgent.getAction、ExpectimaxAgent.getAction，以及一个betterEvaluationFunction。这五个方法对应实验的五个问，前四个是“搜索器”，最后一个是“启发式评估”。刚开始可以先把每个方法的*** YOUR CODE HERE ***注释位找到，确认一下自己要在哪些位置动手。

2.2 最小可运行命令：先让随机吃豆人跑起来

解压后，在命令行里进入目录，先跑一个不需要写任何代码的基线：

cd multiagent python pacman.py -p ReflexAgent -l openClassic

这条命令表示：用ReflexAgent作为 Pacman 的控制器，在地图openClassic上跑一局。默认的 ReflexAgent 在 starter code 里是个占位实现，直接运行不会立刻报错，但你会看到 Pacman 基本不移动路线，这说明决策函数还没写。能正常启动、看到图形窗口，说明环境没问题；如果这一步都跑不起来，问题大概率出在 Python 版本上，见 2.4 节。

接着可以试文本模式，省掉图形窗口，适合在服务器上调试：

python pacman.py -p ReflexAgent -l openClassic --textGraphics

加--textGraphics后，地图和每一帧状态会打印在终端里。调试少量局面时特别好用，因为你能直接看到每次getAction被调用时 Pacman 眼里有哪些合法动作。

运行判分的命令是：

python autograder.py -q q1

-q指定要测的题目，例如q1对应 ReflexAgent，q2对应 Minimax，等等。autograder.py里每个测试都包含一步步的搜索树展开过程，它会检查你每一步返回的动作和期望动作是否一致，而不是只检查最终局分。这意味着哪怕你最后赢了，只要搜索过程不符合它预定的展开顺序，一样会扣分。这一点很多人到了最后才意识到，属于常见的翻车点。

2.3 命令行参数里的隐藏信息

pacman.py和autograder.py都支持-h查看全部参数，常用参数归纳如下：

-a depth=2是后续调 Minimax 深度时最常用的参数。注意-a后面是键值对，多个参数用逗号分隔：-a depth=2,evalFn=betterEvaluationFunction。初学时很容易把-a误写成--agentArgs，两者效果一样，但缩写写起来快很多。

2.4 Python 版本兼容：最容易被环境卡住的一关

这个项目包是按老版 Python 2 写的，直接用python3 pacman.py跑大概率在print语句上报语法错误。常见做法是优先找 Python 2 环境运行；如果手头只有 Python 3，可以分两步处理：

第一步，把multiAgents.py里你新增的代码全部写成 Python 3 兼容语法，print加括号、xrange改成range、.iteritems()改成.items()。

第二步，处理游戏框架本身的兼容问题。game.py和graphicsDisplay.py里也存在少量 Python 2 遗留写法，直接跑会报类型错误。我在 Python 3.10 下实测可行的最小改法是这样：

# 把 graphicsDisplay.py 里的 callable() 用法替换掉 python -c " import re s = open('graphicsDisplay.py').read() s = s.replace('callable(info)', 'hasattr(info, \"__call__\")') open('graphicsDisplay.py', 'w').write(s) "

上面这段是临时补丁思路，不要依赖它作为正式方案，更好的做法是直接找一个社区维护的 py3 兼容版本再动工。判断标准很简单：只要能执行python3 pacman.py -p ReflexAgent -l openClassic --textGraphics且不死循环，就是合格环境。

3. Minimax 与 Alpha-Beta：对抗搜索的递归骨架与剪枝边界

3.1 先把“多智能体”想成一层层的决策树

multiagent这个名字容易让人想复杂，其实它要处理的是轮流行动的博弈：Pacman 走一步，幽灵走一步，Pacman 再走一步，如此交替。每层节点的“玩家”不同，所以不能像普通搜索那样统一取最大值，而是要区分 max 层和 min 层：

• max 节点：Pacman 选择对自己评估值最大的动作。
• min 节点：幽灵选择让 Pacman 评估值最小的动作。
• 终止节点：游戏结束，返回gameState.getScore()或自定义评估值。

深度参数的含义是“Pacman 一共需要考虑多少步自己的动作”。depth=2在最小情况下意味着 Pacman 一步、所有幽灵各一步、Pacman 再一步。如果地图上有多只幽灵，幽灵的动作会连续出现在每层“幽灵回合”里。这个“一回合包含多只幽灵”的细节是后面实现中最容易写错的地方，很多人递归层数数错，导致幽灵被跳过。

minimax递归的核心结构，我的惯用写法是这样：

def value(self, gameState, agentIndex, depth): if gameState.isWin() or gameState.isLose(): return self.evaluationFunction(gameState) numAgents = gameState.getNumAgents() # agentIndex 超过总智能体数时，说明所有幽灵都动完了，进入下一轮 Pacman 决策 if agentIndex >= numAgents: agentIndex = 0 depth -= 1 if depth == 0: return self.evaluationFunction(gameState) if agentIndex == 0: return self.maxValue(gameState, agentIndex, depth) return self.minValue(gameState, agentIndex, depth)

逻辑说明：numAgents是 Pacman 加幽灵的总数，agentIndex=0代表 Pacman，1..n-1代表各幽灵。depth只在 Pacman 行动时递减，因为深度定义的是 Pacman 自己的思考步数。当agentIndex >= numAgents时，把幽灵索引回到 0，同时 depth 减一，表示一轮完整回合结束。

参数说明：这里的depth和evalFn都是通过-a depth=2注入的，类初始化时从self.depth读取。不要在getAction里硬编码深度，否则 Autograder 校验时会因为不匹配而扣分。

写getAction时只要记住一件事：你跟所有的递归层共享同一套状态，不要在递归内部去“模拟”状态变化之外的东西。例如：

def getAction(self, gameState): bestAction = None bestValue = -float('inf') for action in gameState.getLegalActions(0): successor = gameState.generateSuccessor(0, action) v = self.value(successor, 1, self.depth) if v > bestValue: bestValue = v bestAction = action return bestAction

这里getLegalActions(0)里的 0 表示 Pacman 的索引。循环每个合法动作，对后继状态调用value，从幽灵层开始算。注意初始bestValue用负无穷而不是 0，因为评估值可能是负数，用 0 会漏掉所有负分的最优动作。

3.2 Alpha-Beta 剪枝的改写：只加两个变量，维护好全局更新顺序

实验的第三个问题是在 Minimax 基础上加 alpha-beta 剪枝。很多人的误区是“剪枝就是提前 return”，但更准确地说，剪枝生效的前提是：父层已经维护了一个 alpha 或 beta 边界，而当前层的某个后继把这个边界击穿了。剪枝不是拦截遍历，而是“遍历过程中发现了不可能再影响上层决策的子树，直接放弃”。

我在AlphaBetaAgent里这样组织：

def maxValue(self, gameState, agentIndex, depth, alpha, beta): best = -float('inf') for action in gameState.getLegalActions(agentIndex): successor = gameState.generateSuccessor(agentIndex, action) v = self.value(successor, agentIndex + 1, depth, alpha, beta) best = max(best, v) alpha = max(alpha, best) if best > beta: return best return best def minValue(self, gameState, agentIndex, depth, alpha, beta): best = float('inf') for action in gameState.getLegalActions(agentIndex): successor = gameState.generateSuccessor(agentIndex, action) v = self.value(successor, agentIndex + 1, depth, alpha, beta) best = min(best, v) beta = min(beta, best) if best < alpha: return best return best

逻辑说明：maxValue里更新的是alpha，判断条件用best > beta；minValue里更新的是beta，判断条件用best < alpha。剪枝条件写反是经典错误，如果你发现跑出来的动作和 Minimax 不一致，先查这两行。另一个常见错误是把alpha = max(alpha, best)写在if之后，这样当前层后续动作拿到的 alpha 是旧值，剪枝虽然可能不报错，但剪枝率和 Minimax 结果都会异常。

参数说明：这两个边界值在value函数里逐层传递。初始调用value(successor, 1, self.depth, -inf, inf)，也就是 max 层往下传 alpha=-inf、beta=inf；min 层往下传时会带上上层更新后的 alpha/beta。注意每次递归调用返回后，要立刻把返回值和当前层的上下界做比较，因为剪枝只在“比较后”才有意义。

3.3 搜到同样的动作，判分却说错：顺序与平局

Autograder 对 Minimax 和 Alpha-Beta 的检查，不只是看最终动作，还会在若干固定测试里比对每一步的选择。如果它期望返回的动作有多个平局候选，而你写代码时用<而不是<=，或者维护 bestAction 的方式不同，就可能导致选出的动作和它预设的不一致。

这个问题的典型现象是：手动跑pacman.py时 Pacman 表现正常，一提交autograder -q q2就报 mismatch。解决方向不是改数值，而是检查动作遍历顺序里平局的处理规则。常见做法是只更新第一个达到最大值的动作，也就是说当v > bestValue时才替换bestAction，遇到相等时不变。这样的结果通常与测试预期一致，因为测试数据大多是按字典序、遍历第一个合法动作来构造的。

另外，gameState.getLegalActions(agentIndex)返回的列表不是固定的，不同版本的框架排序可能不同。如果你的实现依赖列表顺序来保证平局分支结果一致，尽量在循环里自行决定平局策略，例如只保留索引最小的动作。这里并没有绝对的最优解，但一旦选定，就不要再在代码里混用>=和>，否则同一局面会跑出两种结果。

4. Expectimax 与评估函数：把随机性揉进搜索树

4.1 幽灵的“随机”不是随机：求期望而不是求最小

第四问ExpectimaxAgent和 Minimax 的唯一区别是：幽灵节点不再取最小值，而是对所有后继的评估值取平均值。因为在RandomGhost模式下，幽灵的移动是均匀随机的，所以对抗搜索里那个“最坏情况假设”要改成“期望值假设”。

实现时可以直接复用 Minimax 的框架，只把minValue换成：

def expValue(self, gameState, agentIndex, depth): legalActions = gameState.getLegalActions(agentIndex) if not legalActions: return self.evaluationFunction(gameState) total = 0.0 for action in legalActions: successor = gameState.generateSuccessor(agentIndex, action) total += self.value(successor, agentIndex + 1, depth) return total / len(legalActions)

逻辑说明：这里有一个容易踩的边界，getLegalActions可能返回空列表，比如死亡后卡在某些状态，所以要先判空，避免除零。概率模型是均匀分布，所以等权平均；如果后续自定义幽灵概率，这里要改成带权累加。

参数说明：value函数在agentIndex>=numAgents时同样要做索引回绕和 depth 递减。Expectimax 的深度和 Minimax 一样，由-a depth=2传入。我建议在调试时固定-k 1，也就是只留一只幽灵，能显著减少搜索分支，更快确认期望值计算是否正确。

4.2 评估函数：别只看分数，要看“到食物的距离”

前四问里，叶子节点都依赖evaluationFunction。默认版本通常会直接返回gameState.getScore()，这个函数在叶子深度很浅时几乎没用：Pacman 一步根本吃不到豆子，分数全都是 0，搜索退化成随机动作。因此实验的最后一问，就是让你写一个更好的评估函数。

评估函数的核心思想是“把未来的收益折现到当前状态”。我常用的组合包含四个因子：

不要试图用“所有食物平均距离”这种全局指标，多智能体搜索的评估函数越局部越有效。基于曼哈顿距离的写法，我一般这样组织：

def betterEvaluationFunction(state): if state.isWin(): return 999999 if state.isLose(): return -999999 pacmanPos = state.getPacmanPosition() foods = state.getFood().asList() if not foods: return state.getScore() minFoodDist = min(manhattanDistance(pacmanPos, food) for food in foods) score = state.getScore() score += 15.0 / (minFoodDist + 1) score -= 4.0 * len(foods) ghosts = state.getGhostStates() for ghost in ghosts: dist = manhattanDistance(pacmanPos, ghost.getPosition()) if ghost.scaredTimer > 0: score += 200.0 / (dist + 1) else: if dist < 3: score -= 500 return score

逻辑说明：把到最近食物的距离放到分母里，能让 Pacman“越近越舍不得走”，这个方向比单纯加固定奖励更平滑。len(foods)乘一个负权重，让 Pacman 倾向吃掉更多食物；剩余食物少、距离近的状态评分会明显更高。幽灵部分分成 scared 和 normal 两种情况：scared 时幽灵是食物，靠近反而加分；normal 时距离小于 3 就要给强惩罚，避免 Pacman 撞枪口。

参数说明：15.0 / (minFoodDist + 1)里的 +1 是防除零的常规操作，也可以写成1.0 / (dist + 1)，再用大权重放大，两种方式等价。200.0和500这类数值是经验值，没有标准答案，Autograder 的第五问只要求你随机选择若干地图、跑若干局后平均分超过基线即可，所以不需要对着某个固定分数调参。

这里有个很隐蔽的坑：评估函数会在每一层叶子被调用，而不是只在搜索根节点调用。如果你的评估函数里有高开销的计算，比如遍历所有食物算两两距离，深度为 2 时还好，深度为 4 时会明显卡顿。血泪经验是：评估函数要能在一毫秒内完成，否则后面所有调参都会变成“改一次参数等三分钟”。

5. 多智能体搜索避坑：5 个常见问题定位与修复

5.1 现象：generateSuccessor之后状态没有变化

有人会写gameState = gameState.generateSuccessor(...)，然后发现无限循环或返回同一个状态。原因是没有意识到generateSuccessor在game.py里不修改原状态，而是返回新对象。这个误用很像“引用传递”的直觉，但这里状态对象是不可变的。解决方法是：在递归与循环里用新变量接收返回值，且不要覆盖参数gameState，否则后面的getLegalActions会基于错误状态计算。

5.2 现象：autograder -q q2报错但q1通过，Minimax 单独跑却正常

原因通常是MinimaxAgent.getAction里把self.depth用成了实例属性，但在getAction开头写死成 1。或者更常见的是：你只写了maxValue和minValue，少了value函数里的 agentIndex 回绕层。这类问题在singleAgent测试里看不出来，因为只有 Pacman 和一只幽灵时，回绕逻辑恰好不影响第一层。解决方法是把value里对agentIndex的判断写在depth==0判定之前，因为depth的递减依赖 agentIndex 回绕，顺序反了会导致深度提前耗尽。

5.3 现象：Alpha-Beta 跑出的动作和 Minimax 不一样

这是剪枝实现写错的最直接信号。剪枝优化理论上必须保证结果一致，不一致只有两个原因：第一，alpha或beta没有在循环中即时更新，而是用了递归返回前的旧值；第二，剪枝条件写反。排查方法是在本地写一个对照脚本，随机生成 500 个浅层局面，同时运行 MinimaxAgent 和 AlphaBetaAgent，对比每个动作。如果有一个不一致，打印出该局面的 alpha/beta 更新过程，很快能看到问题出现在 max 层还是 min 层。

5.4 现象：Expectimax 在--numGames=10下平均分波动巨大

这个不是 bug，是随机幽灵带来的天然行为。很多人会把“跑了几局分低”归结为评估函数差，实际是运气问题。解决方法是：比较两个 Agent 时用相同的随机种子，或者干脆固定地图固定幽灵数量，例如python pacman.py -p ExpectimaxAgent -l smallClassic -k 1 --numGames=5。多智能体搜索的“强弱”必须用统计量判断，单局翻车不说明任何问题。我以前在调第四问时，连续三局 Expectimax 分数低，换种子后立刻反超 Minimax，差点把正确实现改成错误版本。

5.5 现象：betterEvaluationFunction一加入，反而在跑步时被幽灵堵死

评估函数只考虑“当前局面的静态价值”，不会规划路径，所以 Pacman 可能为了吃一颗近处的豆子，主动走进死胡同。原因是你没有给“幽灵威胁”加足够强的负权重，或者权重只在距离小于 3 时生效，导致 Pacman 评估时觉得距离 4 的幽灵不构成威胁。解决方向是改用分段惩罚：距离 1 到 2 内是极高惩罚，距离 3 到 5 是中等惩罚，距离 5 以上才不惩罚。这样 Pacman 在两步前就会开始避让，而不是被逼到墙角才后悔。

此外还有一个和代码无关的陷阱：betterEvaluationFunction会被ReflexAgent复用。如果你只改了评估函数却没改 ReflexAgent，第五问的测试一样会失败。注意每个 Agent 的类层级关系，子类会继承父类的getAction，而evaluationFunction统一挂在类外。要确认ReflexAgent里调用的是不是同一个函数，最简单的方法是在函数入口加一行print(state.getScore())，跑一局看输出是否出现。

6. 用带球吃豆 Demo 验证整条链路：可视化胜率统计与最终检查

实验全部通过之后，我会额外做一次“肉眼验证”，目的是把 Autograder 之外的真实博弈能力也检查一遍。步骤是固定一张经典地图，分别跑 MinimaxAgent 和 ExpectimaxAgent 各十局，记录胜利局数和平均分：

python pacman.py -p MinimaxAgent -a depth=2 -l smallClassic -k 2 --numGames=10 --no-graphics \ | grep "Average Score"

python pacman.py -p ExpectimaxAgent -a depth=2 -l smallClassic -k 2 --numGames=10 --no-graphics \ | grep "Average Score"

如果 Expectimax 的平均分低于 Minimax，十有八九是幽灵配置被设成了非随机模式，或者地图里没有胶囊，随机游走的幽灵恰好避开了 Pacman。检查pacman.py中幽灵类型的参数，确保用的是RandomGhost而不是固定的方向循环模式。

最后一个可执行的进阶技巧是：写一个几十行的“复盘器”，把 Pacman 每一步的getAction输入输出记成 JSON，回放时逐步打印评估值和搜索深度。这样既能看到决策边界，又能回查某一步是不是被剪枝剪坏了。动手前先想清楚你希望验证什么：如果只是验证“代码没写错”，用autograder.py就够；如果是验证“搜索策略真的有智能”，就一定要带统计和可视化一起看。回到我做这个实验时的教训：最快拿到满分的路径不是一上来调深评估函数，而是先把每问的边界条件写对、把环境跑通、再谈权重。先把基线跑绿，再一点一点加花活，这个习惯后来帮我避开了无数次返工。希望帮到你。

本文还有配套的精品资源，点击获取