多智能体搜索与博弈决策：吃豆人项目详解Minimax、Alpha-Beta和Expectimax

简介面向正在系统学习人工智能与机器学习的开发者CS188实验二多智能体搜索资源包聚焦多智能体协同与竞争环境中的搜索决策问题。实验内容涵盖环境模拟、智能体建模、协作与竞争机制、Q-learning及深度强化学习算法实现适合中级学习者循序渐进地拆解理论与实践。压缩包共228个文件以测试文件、解决方案文件、Python脚本、配置文件与地图布局文件为主整体约236KB轻量但结构完整测试与参考答案可对照验证脚本与地图布局可支撑多种场景复现。目前已有470人学习/下载。读者可获得完整实验代码、测试用例、参考解决方案及经典地图布局结合可视化实验理解多智能体在非平稳环境中的学习方法是巩固理论并提升工程实践能力的高质量备赛与自学资料。1. 多智能体搜索从吃豆人到博弈决策这份实验资源到底在练什么多智能体搜索Multi-Agent Search是 AI 课程里最容易被低估的一道坎。很多人以为它只是普通迷宫搜索的升级版结果跑起来才发现你要在同一个游戏状态里同时处理“我该往哪走”和“对手会怎么堵我”两层决策还要在有限时间内给出答案。CS188 实验二 multiagent.zip 正是这个关卡的标准配置它把吃豆人、幽灵、力量药丸和随机食物包装成一个完整的对抗搜索环境让你亲手实现 Minimax、Alpha-Beta 剪枝和 Expectimax 三种算法。适合正在学搜索算法、被多智能体概念绕晕、或者想复现经典实验的开发者。2. Minimax、Alpha-Beta 与 Expectimax多智能体对抗搜索的三种决策模型2.1 为什么单个搜索算法在吃豆人里不够用从 Maze 到双人博弈实验一里你面对的是一个静止迷宫每次只做一个决策找到一条路径就行。到了实验二吃豆人和幽灵同时移动你的决策会改变幽灵接下来的反应幽灵的反应又会反向影响你的下一步。这种双向耦合让普通 DFS、BFS、A* 全部失效原因很简单你无法预判对手的行为因为对手不是环境里固定的障碍而是有自己目标的智能体。因此实验二把决策问题建模成博弈树。每个回合把当前状态当作树的节点吃豆人可以选择上、下、左、右四个动作幽灵也有自己的动作集合。树的每一层轮流属于不同的玩家吃豆人层叫 Max 节点幽灵层叫 Min 节点。这就是 Minimax 的核心Max 节点选择让自己评估值最大的分支Min 节点选择让评估值最小的分支。评估值来自一个启发式函数比如“吃豆人与最近食物的距离”“幽灵离吃豆人是否太近”。一个容易踩的误区是把幽灵当成环境的一部分。如果你简单地用 A* 规划一条避开幽灵的路径那么当幽灵改变方向时你的规划立刻失效吃豆人会撞进鬼怀里。Minimax 之所以适合是因为它显式建模了对手的最优反应哪怕幽灵并没有真的按最优策略走你也能在最坏情况下保住一条活路。在博弈树的每个叶子节点需要返回一个数值代表这个终局对吃豆人来说是好是坏。胜利为正值失败为负值平局为 0。但吃豆人游戏通常不会真的下到终局因为状态空间太大所以实验里一般设定一个最大搜索深度比如 4 层到达深度上限就调用评估函数基于当前局面打分。深度每多一层计算量成指数增长但决策质量也会更好。深度和速度的权衡就是实验二最核心的调参。Minimax 的递归过程很直接对一个 state先判断是否到达终止条件吃到所有豆子、撞上没无敌的幽灵、或 depth 归零然后检查当前轮到谁行动。吃豆人回合遍历每个合法动作生成后继状态对每个后继递归调用最后返回最大值幽灵回合返回最小值。这里的“合法动作”必须从 gameState 的接口里取不能自己硬编码因为不同地图里墙的位置完全不同。递归函数返回值是浮点数评估值但 getAction 最终要返回的是一个动作字符串。评估函数的设计会显著影响 Minimax 的表现。最朴素的思路是看吃豆人到最近食物的曼哈顿距离距离越短分数越高但如果不把幽灵位置考虑进去吃豆人就会直冲食物然后被幽灵截杀。更稳的做法是同时计算“最近幽灵距离”把它作为正权重加进去。这个函数不需要很复杂三个特征已经能支撑 smallClassic 地图的完整一局。2.2 Alpha-Beta 剪枝和 Expectimax 的选型边界确定性对抗与随机环境Minimax 的问题在于效率。一个深度为 d、每个节点有 b 个可用动作的博弈树Minimax 需要访问 O(b^d) 个节点。在吃豆人地图上动作数约为 3 到 4搜索到第 6 层就是数千个节点纯 Python 跑到超时边界很正常。Alpha-Beta 剪枝通过记录当前路径上的 alpha 和 beta 上下界把无用的分支直接切掉在理想情况下能把复杂度降到 O(b^(d/2))同样的深度剪枝后访问节点数可以降一个数量级。这个优化不改变最终决策结果只减少搜索量。Alpha-Beta 适合确定性对抗环境也就是每个动作的结果是确定的没有随机因素。吃豆人游戏里幽灵的移动虽然有方向偏好但核心规则是确定的。不过一旦引入随机食物出现或幽灵按概率移动就需要用 Expectimax。Expectimax 把 Min 节点换成 Chance 节点不再取最小值而是计算子节点评估值的期望加权和。如果幽灵的每个动作概率相等那就取平均值如果概率不相等就按概率加权。选型边界要分清对手有明确对抗意图且环境确定用 Minimax Alpha-Beta对手行为随机用 Expectimax如果既想考虑最坏情况又想让计算量可控可以在 Alpha-Beta 基础上限制深度并用评估函数兜底。很多人在实验二里纠结“我该不该用 Expectimax”其实判断标准就一句话你的对手会不会主动坑你。幽灵会所以默认任务里 Minimax 是基线但后续扩展题会出现随机幽灵那时才需要处理概率节点。Alpha-Beta 的剪枝依赖 alpha 和 beta 两个边界值。Max 节点维护 alpha 表示当前已知的最大下限Min 节点维护 beta 表示当前已知的最小上限。如果某个 Max 分支的值已经大于 beta说明对手在上一层绝不会选择这条路径可以提前剪掉同理Min 分支的值小于 alpha吃豆人绝不可能走这里。注意剪枝条件不要写反写反了结果仍然正确但剪枝效率会下降甚至会退化成未剪枝的 Minimax。实际落地时我一般按这个顺序做选型决策第一步看实验要求里有没有随机性描述比如“幽灵每秒有 30% 概率随机转向”有就上 Expectimax第二步看运行时间预算如果地图大且深度要求高就优先实现 Alpha-Beta第三步写一个共享的评估函数先保证 Minimax 通过再给 Alpha-Beta 留出剪枝接口最后用同一组测试用例对比三种算法在相同深度下的得分和耗时数据会告诉你哪条路更稳。这种比较本身就是实验二最有价值的产出因为你要的不是某个算法“感觉好”而是能在一批布局上稳定不超时的决策方案。三种算法在相同深度下的表现差异值得记录。Minimax 得分最稳定Alpha-Beta 得分完全相同但耗时明显下降Expectimax 在随机环境下更贴合真实胜率但在纯对抗环境中反而可能选到一条“平均安全但某一步必死”的路径。把这些观察写到实验报告里比堆算法公式有用得多。3. multiagent.zip 结构与运行步骤拿到资源后先确认这几个文件3.1 资源包文件清单与角色划分哪些是改的哪些是跑的这份 zip 解压后是一个完整的实验工程常见文件分布如下文件角色需要改吗multiAgents.py学生实现文件包含多个 agent 类是pacman.py主程序加载地图、启动游戏、调用 agent否game.py / gameState.py游戏状态与状态转移逻辑否graphicsDisplay.py可视化窗口GUI 模式用否layouts/测试地图列表否autograder.py评分脚本跑测试用否资源包里 multiAgents.py 通常已经定义了多个类ReflexAgent、MinimaxAgent、AlphaBetaAgent、ExpectimaxAgent。每个类的 getAction 方法是入口。你的任务是补齐里面的递归函数而不是改变接口签名。autograder 会按类名导入并调用 getAction如果你把类改名或把方法名改成 get_action评分脚本直接报 ImportError 或 AttributeError。这是最常见的低级错误提交前先跑一条命令验证接口。拿到 zip 后第一步不是直接写代码而是先跑一个最简单的地图确认环境能启动。在解压目录下打开终端执行cd multiagent python pacman.py -p ReflexAgent -l testClassic这条命令会启动吃豆人游戏吃豆人使用 ReflexAgent地图是 testClassic。如果能看到界面和吃豆人移动说明环境安装正确。如果你在服务器或容器里没有图形界面可以加-n参数跳过渲染但要注意不同版本对-n的解释不一样有的版本靠--frame_time 0关闭帧动画。不确定时先跑python pacman.py -h看帮助。地图文件放在 layouts 目录里常见的布局有 testClassic、smallClassic、mediumClassic、originalClassic。不同布局范围大小差别很大直接决定搜索深度上限。我一般先用 testClassic 验证代码正确性再切到 mediumClassic 测性能最后用 originalClassic 跑完整回放。如果你发现某个地图加载失败检查 layouts 目录是否还在原路径zip 解压后有人会把 layouts 移走导致找不到地图。3.2 命令行运行与自动评判autograder 的三种启动方式autograder 是这份资源里最值得研究的东西它把每个问题拆成了若干小测试用例每个用例会模拟一局或多局游戏并统计胜率。常用启动方式python autograder.py -q q1 # 只测试 Minimax 部分 python autograder.py -q q2 # 只测试 Alpha-Beta 剪枝部分 python autograder.py # 跑全部分数-q 后面的编号对应实验说明中的 Question 1、2、3第一次跑会看到类似 “Passed 4/5 tests” 的输出告诉你哪个用例没过。注意 autograder 输出里会出现 “Pacman emerges victorious! Score: 1234” 之类的字样这是正常反馈只需要关注最后一行分数和失败用例的名称。如果说的是“测试失败超时”优先检查深度和剪枝如果说的是“吃豆人输给了幽灵”优先检查评估函数如果直接抛异常优先检查接口签名和返回值类型。这条排查路线能帮你省掉大量无效调参时间。autograder 本身也是一段 Python 代码你可以直接打开它看某个用例到底在测什么这是比反复瞎试更高级的调试方式。在无图形环境里跑 autograder 有时也会触发 GUI 初始化错误。这时候要么用python autograder.py --help看是否支持--no-graphics要么在导入 graphicsDisplay 前设置环境变量SDL_VIDEODRIVERdummy。曾经我在一台服务器上跑实验GUI 报错卡了两小时最后发现只是缺了一个库和算法没有任何关系。调试时不要用 GUI 回放GUI 会拖慢整个流程。我一般先用python autograder.py -q q1快速跑分数再用python pacman.py -p MinimaxAgent -l smallClassic -n无界面跑一局观察终端输出的得分和时间。在 getAction 里加几行临时 print 打印候选动作和评估值定位到具体哪个分支决策错了。记得提交前把 print 删掉否则 autograder 的 stdout 会被刷屏虽然不影响分数但容易干扰测试日志。资源包里还可能包含一个 README 或实验说明文档里面列出了每道题的具体要求。强烈建议把这份说明当作第一优先级阅读材料因为它明确了你需要实现的函数签名、返回类型和深度语义。很多时候 autograder 失败并不是算法错而是你没按文档约定把函数写对。4. 从骨架到完整实现Minimax、Alpha-Beta 与 Expectimax 代码落地4.1 实现 Minimax递归节点、终止条件与深度控制multiAgents.py 里 MinimaxAgent 的骨架通常已经给出了类和 getAction 的签名。我们需要补充的是递归函数。为了避免 getAction 和递归函数互相干扰我习惯把递归函数定义为内部方法名称带下划线例如_minimax。代码大致如下def _minimax(self, state, depth, agentIndex): if depth 0 or state.isWin() or state.isLose(): return self.evaluationFunction(state) numAgents state.getNumAgents() if agentIndex 0: value -float(inf) for action in state.getLegalActions(0): successor state.generateSuccessor(0, action) value max(value, self._minimax(successor, depth - 1, 1)) return value else: value float(inf) for action in state.getLegalActions(agentIndex): successor state.generateSuccessor(agentIndex, action) nxt agentIndex 1 if nxt numAgents: nxt 0 if nxt 0: depth - 1 value min(value, self._minimax(successor, depth, nxt)) return value这段代码的关键是 depth 的递减时机。吃豆人走一步之后所有幽灵还没有走完所以不能立刻把深度减一只有当一个完整的决策周期吃豆人加所有幽灵结束后深度才减一。我的写法里nxt 0表示已经轮到下一轮吃豆人了此时 depth 才减一。如果你在每次递归进入函数时都减一深层博弈会变成每层只考虑一个智能体评估函数过早触发吃豆人基本只能是“贪心”级别。getAction 需要额外一层循环因为递归函数返回的是数值而 getAction 要返回的是动作字符串def getAction(self, state): bestAction None bestValue -float(inf) for action in state.getLegalActions(0): successor state.generateSuccessor(0, action) value self._minimax(successor, self.depth - 1, 1) if value bestValue: bestValue value bestAction action return bestAction注意这里 self.depth 是类属性autograder 会传入不同的 depth 来测试不要写死成数字。如果没有 self.depth常见做法是在 getAction 里读取命令行参数或直接使用默认值 2。评估函数 evaluationFunction 可以由资源提供或自己实现通常接收当前 state 和动作返回一个可比较的数值。实现时还有一个隐藏参数需要处理幽灵数量。如果地图里有四个幽灵那么一个决策周期意味着吃豆人、幽灵0、幽灵1、幽灵2、幽灵3 依次各走一步。agentIndex 从 0 开始到 numAgents-1 是最后一个幽灵之后再回到 0 表示新一轮。如果你只处理了单幽灵的情况多幽灵地图上深度计数会乱套吃豆人看不到后面几个幽灵的行动。4.2 加入 Alpha-Beta 剪枝参数初始化和剪枝时机Alpha-Beta 剪枝是在 Minimax 递归里再加上 alpha 和 beta 两个参数。初始调用时 alpha 为负无穷beta 为正无穷。Max 节点更新 alphaMin 节点更新 beta剪枝条件分别是 value beta 和 value alpha。代码实现def _alphabeta(self, state, depth, agentIndex, alpha, beta): if depth 0 or state.isWin() or state.isLose(): return self.evaluationFunction(state) if agentIndex 0: value -float(inf) for action in state.getLegalActions(0): successor state.generateSuccessor(0, action) value max(value, self._alphabeta(successor, depth - 1, 1, alpha, beta)) if value beta: return value alpha max(alpha, value) return value else: value float(inf) for action in state.getLegalActions(agentIndex): successor state.generateSuccessor(agentIndex, action) nxt agentIndex 1 if nxt state.getNumAgents(): nxt 0 depth - 1 value min(value, self._alphabeta(successor, depth, nxt, alpha, beta)) if value alpha: return value beta min(beta, value) return value这里的 alpha 和 beta 是从父节点传下来的不是全局变量。如果你把它们作为函数参数传递每一层的递归都携带自己的边界剪枝判断才准确。如果你为了省事把 alpha 设为 self.alpha多个递归分支会互相污染结果看起来“偶尔正确”但剪枝数量不稳定甚至漏剪。剪枝的收益在深色地图上特别明显。同一个 mediumClassic 地图深度 4 的 Minimax 可能要跑 10 秒加上剪枝后可能 2 秒内完成而且最终决策完全一致。Alpha-Beta 的剪枝顺序也会影响效率如果先搜索评估值高的动作剪枝会更多。因此你可以把合法动作列表按当前 agent 的评估值排序优先搜索可能更好的分支这是一种常见的优化。但这个排序本身会增加额外计算小地图上不一定划算深度大时收益才明显。Alpha-Beta 剪枝要求递归过程中 alpha 和 beta 在兄弟节点之间共享。Max 节点返回前更新 alpha这个 alpha 会传给后续兄弟节点判断是否剪枝Min 节点同理。如果你把 alpha、beta 初始化放在 getAction 的循环内部而非递归入口会导致每个动作的剪枝边界都从负无穷开始剪枝几乎失效。初始化位置是剪枝效率的分水岭。4.3 期望最大化与随机幽灵Expectimax 的概率节点设计Expectimax 与 Minimax 唯一的区别在幽灵节点Minimax 返回最小值Expectimax 返回所有后继评估值的加权期望。在等概率假设下就是平均值。一个最小实现如下def _expectimax(self, state, depth, agentIndex): if depth 0 or state.isWin() or state.isLose(): return self.evaluationFunction(state) legal state.getLegalActions(agentIndex) if not legal: return self.evaluationFunction(state) values [] for action in legal: successor state.generateSuccessor(agentIndex, action) nxt agentIndex 1 if nxt state.getNumAgents(): nxt 0 values.append(self._expectimax(successor, depth - 1, nxt)) else: values.append(self._expectimax(successor, depth, nxt)) if agentIndex 0: return max(values) else: return sum(values) / len(values)注意事项Chance 节点不能用 Alpha-Beta 剪枝因为期望值不能像最值那样安全地剪掉分支。如果硬剪期望值计算失真结果大概率变差。Chance 节点也没有“最坏情况”保证如果你在一个需要对抗的布局里只用 Expectimax吃豆人可能在个别局里被幽灵堵死因为期望值允许“平均来看还行”但某条路很危险的分支。实验里如果要求随机幽灵才需要用它。深度参数方面Expectimax 因为展开的是概率节点信息密度比 Min 节点低同样计算预算下可以设置比 Minimax 大 1 的深度。我习惯在 getAction 里把 self.depth 加一层再传给递归函数同时把叶子评估阈值保持不变。你可以通过跑 autograder 的扩展题来对比深度 2 和深度 3 的胜率差异通常跑一局就知道。还有个容易被忽略的点Chance 节点的概率分布不一定是均匀的。如果实验文档里写了“幽灵以 0.6 概率朝吃豆人移动”那么期望值计算就要把不同动作的概率作为权重乘进对应后继的评估值。等概率版本只是最简单的情况不是唯一情况。5. 多智能体搜索避坑指南超时、撞墙、接口不匹配的常见原因5.1 运行超时与递归过深现象autograder 在 q1 上直接报 timeout或者本地跑 pacman.py 时吃豆人卡住超过 30 秒不动作。原因没有设置深度上限或者 depth 每层递归都减一导致搜索层数失控。在 mediumClassic 地图上合法的动作组合非常多深度 6 的未剪枝 Minimax 很轻松把 CPU 跑满。另一个常见原因是递归终止条件只判断了 isWin 和 isLose没有判断 depth 0而吃豆人地图很少能快速分出胜负递归永远在等终局。解决先把搜索深度固定为 2跑通后再往上加。在递归函数入口第一行就检查 depth 0确保任何情况下都能返回评估值。同时在 getAction 里读取 self.depth避免在递归内部写死数字。如果某个布局特别大深度 4 加 Alpha-Beta 仍然超时就把深度降到 3然后用更好的评估函数弥补效果。记住实验二的目标是“在时限内给出合理决策”不是“深度越深越好”。5.2 评估函数失效与接口签名错误现象代码能跑但吃豆人一局得分很低甚至原地打转或者 autograder 直接报 AttributeError提示 MinimaxAgent 没有 getAction。原因评估函数用了随机权重或只考虑了食物没有考虑幽灵威胁接口问题更常见把 getAction 改名、类名改动、或者在某个分支返回了 None。递归中如果合法动作列表为空你的value -float(inf)会直接返回负无穷getAction 可能返回 None于是吃豆人停住。解决先检查接口确保 multiAgents.py 里的类名和方法名与自动导入模块完全一致。如果某个分支没有合法动作直接返回 evaluationFunction 的结果作为兜底。评估函数建议用三个特征起步最近食物距离、剩余食物数、与最近幽灵的曼哈顿距离。初始权重设为 -1、-1、1跑一局看效果再逐步调整。如果出现原地打转很可能是两个方向的评估值完全相同给动作加一个小的随机干扰或按字典序打破平局即可。另一个高频现象是 autograder 提示 “Unexpected Error” 或递归深度超限maximum recursion depth exceeded。原因往往是递归终止条件写错了状态一直不满足 isWin 和 isLosedepth 又是 None于是无限递归。还有一种可能是 depth 在传参过程中变成了 NonePython 里depth - 1会直接抛 TypeError。解决方式是在 getAction 里打印 self.depth 的类型和值确认它不是 None。在递归函数入口加断言assert depth is not None同时检查所有递归调用里的 depth 表达式。5.3 环境与图形依赖的坑现象运行 autograder 时没问题但运行 pacman.py 时抛错 “libGL error: cannot open shared object file”或者无头服务器直接黑屏退出。原因代码依赖图形库初始化在没有显示环境的 Linux 服务器上图形窗口无法创建。这是环境问题不是算法问题。解决使用python pacman.py -p MinimaxAgent -l smallClassic -n开启非交互模式。如果资源包没有提供无头参数尝试在终端设置环境变量SDL_VIDEODRIVERdummy。还可以直接改用 autograder 的非交互测试绕过 GUI 层。注意-n在不同版本里可能是 no-graphics 也可能是 non-interactive先跑-h确认。现象Python 3.11 及以上环境里启动游戏时报错module time has no attribute clock甚至崩溃。原因老版 graphicsDisplay.py 调用了 Python 3.8 已移除的 time.clock() 方法而资源包没有做兼容。解决找到报错位置把time.clock()改成time.perf_counter()。这是通用替换不会影响逻辑。如果你不想改源码可以给解释器打一个兼容补丁但最简单的方法还是直接替换。这种坑会浪费不少时间建议拿到资源后先把 graphicsDisplay.py 的 time.clock 修掉再开始写算法。6. 评估函数与验证技巧让吃豆人在两个指标里稳定上分评估函数是整个多智能体搜索的“最后一根杠杆”算法框架相同的情况下评估函数的好坏能直接让胜率从 30% 拉到 80%。我一般用三个特征组合最近食物距离、剩余豆子数、与最近幽灵的曼哈顿距离。注意曼哈顿距离用绝对值计算别用欧氏距离因为吃豆人只能上下左右走。在代码里评估函数接收 state 和动作返回分数。一个简单的实现模板def evaluationFunction(self, state, action): successor state.generateSuccessor(state.getPacmanPosition(), action) newPos successor.getPacmanPosition() newFood successor.getFood() distToFood min([manhattanDistance(newPos, food) for food in newFood.asList()] or [float(inf)]) ghostDist min([manhattanDistance(newPos, g) for g in successor.getGhostPositions()]) foodLeft newFood.count() return -distToFood - foodLeft ghostDist这个函数有几个要点食物很多时计算 min 遍历会很快但如果食物列表为空用or [float(inf)]兜底。幽灵距离为正权重让吃豆人躲得远远的食物距离为负权重让吃豆人尽量靠近食物剩余食物数也为负权重鼓励快速吃光。力量药丸开启时幽灵会变成蓝色此时“靠近幽灵”反而是得分机会所以需要额外判断state.isRedGhost()之类的属性把幽灵距离权重改成负值。验证时不要只看一局结果。我习惯固定同一个布局跑 5 局记录平均分和最低分。平均分反映长期表现最低分反映风险。如果最低分是负数说明存在某条分支会让吃豆人瞬间暴毙即便平均分高也不安全。把跑分过程写成一条命令python autograder.py -q q3 --seed 42固定随机种子能让每局随机布局一致便于对比不同评估函数的胜负差异。不过 autograder 不一定支持 --seed这时候可以用环境变量设置 Python 随机种子但最简单的办法是手动跑多次取均值。从那以后我每次改完评估函数都会强制走一遍同样的流程先跑 autograder 对应问题再跑一场 GUI 回放看动作序列确认不是“纸面高分、实际智障”。这个习惯帮我排掉过很多权重陷阱尤其是幽灵距离权重给大了导致吃豆人满地图乱躲、豆子全被幽灵吃掉的情况。希望帮到你。本文还有配套的精品资源点击获取