CS188多智能体搜索实战：从Minimax到Alpha-Beta剪枝与评估函数

简介面向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 解包后先看这几个文件别急着写代码整个实验的代码量不大但第一次打开的人容易找错文件。常见做法是先解压然后按这个顺序读文件文件职责你要不要改pacman.py游戏主循环、键盘交互、局面渲染不改game.py状态、智能体、方向、Actions 等基础类不改multiAgents.py你的四个核心实现改这一个graphicsDisplay.py/textDisplay.py图形与文本渲染不改autograder.py本地判分入口只跑不改testParser.py/testClasses.py判分所用的测试框架不改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对应 ReflexAgentq2对应 Minimax等等。autograder.py里每个测试都包含一步步的搜索树展开过程它会检查你每一步返回的动作和期望动作是否一致而不是只检查最终局分。这意味着哪怕你最后赢了只要搜索过程不符合它预定的展开顺序一样会扣分。这一点很多人到了最后才意识到属于常见的翻车点。2.3 命令行参数里的隐藏信息pacman.py和autograder.py都支持-h查看全部参数常用参数归纳如下参数含义典型用法-p选择 Pacman 控制器类-p MinimaxAgent-l指定地图-l smallClassic/-l mediumClassic-a给控制器传入参数-a depth2-k幽灵数量-k 1只留一只幽灵调试用--numGames跑多少局--numGames10-q判分器只测指定题-q q2--no-graphics关图形跑批测试配合自动判分用-a depth2是后续调 Minimax 深度时最常用的参数。注意-a后面是键值对多个参数用逗号分隔-a depth2,evalFnbetterEvaluationFunction。初学时很容易把-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 一共需要考虑多少步自己的动作”。depth2在最小情况下意味着 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 加幽灵的总数agentIndex0代表 Pacman1..n-1代表各幽灵。depth只在 Pacman 行动时递减因为深度定义的是 Pacman 自己的思考步数。当agentIndex numAgents时把幽灵索引回到 0同时 depth 减一表示一轮完整回合结束。参数说明这里的depth和evalFn都是通过-a depth2注入的类初始化时从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 betaminValue里更新的是beta判断条件用best alpha。剪枝条件写反是经典错误如果你发现跑出来的动作和 Minimax 不一致先查这两行。另一个常见错误是把alpha max(alpha, best)写在if之后这样当前层后续动作拿到的 alpha 是旧值剪枝虽然可能不报错但剪枝率和 Minimax 结果都会异常。参数说明这两个边界值在value函数里逐层传递。初始调用value(successor, 1, self.depth, -inf, inf)也就是 max 层往下传 alpha-inf、betainfmin 层往下传时会带上上层更新后的 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函数在agentIndexnumAgents时同样要做索引回绕和 depth 递减。Expectimax 的深度和 Minimax 一样由-a depth2传入。我建议在调试时固定-k 1也就是只留一只幽灵能显著减少搜索分支更快确认期望值计算是否正确。4.2 评估函数别只看分数要看“到食物的距离”前四问里叶子节点都依赖evaluationFunction。默认版本通常会直接返回gameState.getScore()这个函数在叶子深度很浅时几乎没用Pacman 一步根本吃不到豆子分数全都是 0搜索退化成随机动作。因此实验的最后一问就是让你写一个更好的评估函数。评估函数的核心思想是“把未来的收益折现到当前状态”。我常用的组合包含四个因子因子含义权重经验值当前分数吃到食物和幽灵的累积分基础项到最近食物的距离越近越好鼓励向前推进10~30剩余食物个数越少越好20~50幽灵威胁幽灵是否处于 scared 状态、距离多远强惩罚不要试图用“所有食物平均距离”这种全局指标多智能体搜索的评估函数越局部越有效。基于曼哈顿距离的写法我一般这样组织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的判断写在depth0判定之前因为depth的递减依赖 agentIndex 回绕顺序反了会导致深度提前耗尽。5.3 现象Alpha-Beta 跑出的动作和 Minimax 不一样这是剪枝实现写错的最直接信号。剪枝优化理论上必须保证结果一致不一致只有两个原因第一alpha或beta没有在循环中即时更新而是用了递归返回前的旧值第二剪枝条件写反。排查方法是在本地写一个对照脚本随机生成 500 个浅层局面同时运行 MinimaxAgent 和 AlphaBetaAgent对比每个动作。如果有一个不一致打印出该局面的 alpha/beta 更新过程很快能看到问题出现在 max 层还是 min 层。5.4 现象Expectimax 在--numGames10下平均分波动巨大这个不是 bug是随机幽灵带来的天然行为。很多人会把“跑了几局分低”归结为评估函数差实际是运气问题。解决方法是比较两个 Agent 时用相同的随机种子或者干脆固定地图固定幽灵数量例如python pacman.py -p ExpectimaxAgent -l smallClassic -k 1 --numGames5。多智能体搜索的“强弱”必须用统计量判断单局翻车不说明任何问题。我以前在调第四问时连续三局 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 depth2 -l smallClassic -k 2 --numGames10 --no-graphics \ | grep Average Scorepython pacman.py -p ExpectimaxAgent -a depth2 -l smallClassic -k 2 --numGames10 --no-graphics \ | grep Average Score如果 Expectimax 的平均分低于 Minimax十有八九是幽灵配置被设成了非随机模式或者地图里没有胶囊随机游走的幽灵恰好避开了 Pacman。检查pacman.py中幽灵类型的参数确保用的是RandomGhost而不是固定的方向循环模式。最后一个可执行的进阶技巧是写一个几十行的“复盘器”把 Pacman 每一步的getAction输入输出记成 JSON回放时逐步打印评估值和搜索深度。这样既能看到决策边界又能回查某一步是不是被剪枝剪坏了。动手前先想清楚你希望验证什么如果只是验证“代码没写错”用autograder.py就够如果是验证“搜索策略真的有智能”就一定要带统计和可视化一起看。回到我做这个实验时的教训最快拿到满分的路径不是一上来调深评估函数而是先把每问的边界条件写对、把环境跑通、再谈权重。先把基线跑绿再一点一点加花活这个习惯后来帮我避开了无数次返工。希望帮到你。本文还有配套的精品资源点击获取