简介来自伯克利CS188课程的吃豆人多智能体搜索项目面向正在学习Python与人工智能算法的学生和开发者以经典游戏为载体集中实践Minimax、Expectimax以及Alpha-Beta剪枝等对抗搜索与概率决策方法。压缩包共60个文件涵盖12个Python源文件、20个编译缓存、11个迷宫布局文件以及项目配置、实验指引文档等整体大小仅350KB结构紧凑、方便直接运行调试。已有5495人学习下载。资源内除完整的Pacman游戏引擎含地图生成、角色移动、碰撞检测等核心模块外还提供multiAgents.py算法框架、多种经典与变体地图lay文件、docx实验指引和测试关卡可帮助读者快速复现课程实验逐层实现并对比不同搜索策略在幽灵追逐场景中的表现配套文档对项目背景和实现细节作了梳理既适合自学算法原理也可作为课程作业或教学参考深入理解多智能体环境中的博弈与决策逻辑。1. 为什么CS188吃豆人游戏Project 2: Multi-Agent Search是AI入门绕不开的一道坎CS188吃豆人游戏Project 2: Multi-Agent Search是伯克利CS188课程里最让人上头的第二个项目——它把对抗搜索、多智能体博弈和评估函数设计三件事一次性塞进吃豆人游戏。和Project 1的单智能体寻路不同这里的核心难点是你无法预知鬼的走位鬼不是静态障碍而是会反过来追你的对手。你要写的不是一条最优路径而是一套在对手干扰下依然能做出决策的搜索策略。这篇笔记按Reflex Agent、Minimax、Alpha-Beta、Expectimax到评估函数调参的顺序把实现步骤、参数选择和踩坑记录摊开讲。适合正在赶CS188作业的人也适合想搞懂博弈搜索在真实状态空间里怎么落地的工程师。2. 跑通Multi-Agent Search第一环从Reflex Agent到Minimax的手写实现2.1 先把GameState的输入输出摸清否则后面全白搭在CS188吃豆人框架里所有Agent只做一件事给定一个gameState返回一个合法动作。gameState不是普通的坐标快照它封装了一整套查询接口写Multi-Agent Search之前必须先把这几条命令背下来。# 常用GameState API一览 state.getLegalActions(agentIndex) # 返回某智能体的合法动作列表0是吃豆人1..N-1是鬼 state.generateSuccessor(agentIndex, action) # 模拟该智能体执行动作后的新状态 state.isWin() / state.isLose() # 终局判断 state.getScore() # 当前累计得分 state.getPacmanPosition() # 吃豆人坐标 (x, y) state.getGhostPosition(i) # 第i个鬼的坐标 state.getGhostState(i).scaredTimer # 鬼被胶囊吓到后的剩余时间0表示正常追捕状态 state.getFood() # 返回一个Grid用 food[x][y] 判断该格是否有豆 state.getNumAgents() # 总智能体数 1个吃豆人 鬼的数量常见做法是先把getLegalActions(0)打印出来走一步generateSuccessor再看score变化确认你理解的方向是对的。很多翻车现场都是因为把agentIndex从1开始当成吃豆人导致后面Minimax递归从第一层就错。这里的约定是agentIndex为0的一定是吃豆人MAX鬼从1开始编号MINgetNumAgents()返回的是总数而不是鬼数。把这个约定想清楚再看任何递归代码都不容易晕。2.2 Reflex Agent给吃豆人装一个条件反射评估器写Minimax之前课程先让每个人实现一个ReflexAgent。它的思路极度朴素对当前状态的每个合法动作生成后继状态然后用评估函数给后继状态打分选分数最高的动作。评估函数就是你手动设计的直觉这一步做不对后面Minimax再完美也会因为叶子节点的坏分数做出蠢事。class ReflexAgent: def getAction(self, gameState): legal gameState.getLegalActions(0) if not legal: return Stop # 对每个动作打分取最高分动作 scored [] for action in legal: nextState gameState.generateSuccessor(0, action) scored.append((self.evaluationFunction(nextState), action)) return max(scored)[1] def evaluationFunction(self, state): # 基础分游戏分数 score state.getScore() # 最近的豆子距离越近越好所以取负 pacman state.getPacmanPosition() foodList state.getFood().asList() if foodList: minFoodDist min(manhattanDistance(pacman, f) for f in foodList) else: minFoodDist 0 # 最近鬼的距离越远越安全 ghostDists [] for i in range(1, state.getNumAgents()): ghostDists.append(manhattanDistance(pacman, state.getGhostPosition(i))) minGhostDist min(ghostDists) if ghostDists else float(inf) # 组合打分 return score - 2.0 * minFoodDist 3.0 * minGhostDist这段代码的核心逻辑是吃豆人先走一步看新状态里豆子是不是更近了、鬼是不是更远了用这两个特征直接对动作排序。manhattanDistance来自框架自带的util.py不需要重新实现注意它和欧氏距离在带墙的迷宫里都不精确但胜在便宜做Reflex够用。分数项权重1.0minFoodDist权重-2.0minGhostDist权重3.0这是最常见的起点跑map01和mediumClassic都能过关但离聪明还很远。后面所有搜索算法的叶子节点评估本质上都是在ReflexAgent这个评估函数上做文章。2.3 Minimax递归MAX节点和MIN节点到底谁嵌套谁ReflexAgent只考虑了一步鬼一动就失效。Minimax把搜索树展开吃豆人是MAX节点在所有动作里选分数最高的鬼是MIN节点在所有动作里选让吃豆人最难受的。递归终止在终局win/lose或达到你设定的深度上限。实现时最容易搞混的是鬼的层数有2个鬼Minimax深度为2表示吃豆人走一次、鬼1走一次、鬼2走一次共三层决策。class MinimaxAgent: def __init__(self, depth2): self.depth depth def getAction(self, gameState): # 在根节点吃豆人MAX枚举所有动作 bestScore float(-inf) bestAction Stop for action in gameState.getLegalActions(0): nextState gameState.generateSuccessor(0, action) score self.minValue(nextState, 1, 0) if score bestScore: bestScore score bestAction action return bestAction def maxValue(self, state, depth): # 吃豆人节点取后继分数的最大值 if state.isWin() or state.isLose() or depth self.depth: return state.getScore() v float(-inf) for action in state.getLegalActions(0): nextState state.generateSuccessor(0, action) v max(v, self.minValue(nextState, 1, depth)) return v def minValue(self, state, agentIndex, depth): # 鬼节点取后继分数的最小值 if state.isWin() or state.isLose() or depth self.depth: return state.getScore() v float(inf) for action in state.getLegalActions(agentIndex): nextState state.generateSuccessor(agentIndex, action) if agentIndex state.getNumAgents() - 1: # 所有鬼都行动完吃豆人开始新一轮 v min(v, self.maxValue(nextState, depth 1)) else: # 还有下一个鬼继续在当前深度递归 v min(v, self.minValue(nextState, agentIndex 1, depth)) return v这里最关键的设计是agentIndex轮转逻辑当agentIndex走到getNumAgents()-1时说明所有鬼都行动过一轮下一次轮到吃豆人所以depth要加1。这个深度的单位不是一步动作而是一轮完整博弈吃豆人和所有鬼各动一次。把depth当成总动作步数来写是这章最常见的死法会导致递归深度虚高、搜索树爆炸。minValue里鬼是取minmaxValue里吃豆人是取max二者通过返回值互相嵌套构成完整的对抗搜索树。3. 搜索效率和不确定性Alpha-Beta剪枝与Expectimax的落地写法3.1 Alpha-Beta剪枝为什么能在吃豆人里省下大半时间Minimax的复杂度随深度和智能体数量指数增长分支因子约4两个鬼时一层就是4×4×464个节点深度4就是4096个节点每个节点还要跑一次评估函数。Alpha-Beta剪枝不改变结果只是把不可能影响决策的分支砍掉。核心是维护两个值alpha是MAX节点目前能保证的下界beta是MIN节点目前能接受的上界。当某个节点的值超出这个窗口剪掉后面的兄弟节点。class AlphaBetaAgent: def __init__(self, depth2): self.depth depth def getAction(self, gameState): bestScore float(-inf) bestAction Stop alpha float(-inf) beta float(inf) for action in gameState.getLegalActions(0): nextState gameState.generateSuccessor(0, action) score self.minValue(nextState, 1, 0, alpha, beta) if score bestScore: bestScore score bestAction action alpha max(alpha, bestScore) # MAX节点更新下界 return bestAction def maxValue(self, state, depth, alpha, beta): if state.isWin() or state.isLose() or depth self.depth: return state.getScore() v float(-inf) for action in state.getLegalActions(0): nextState state.generateSuccessor(0, action) v max(v, self.minValue(nextState, 1, depth, alpha, beta)) if v beta: return v alpha max(alpha, v) return v def minValue(self, state, agentIndex, depth, alpha, beta): if state.isWin() or state.isLose() or depth self.depth: return state.getScore() v float(inf) for action in state.getLegalActions(agentIndex): nextState state.generateSuccessor(agentIndex, action) if agentIndex state.getNumAgents() - 1: v min(v, self.maxValue(nextState, depth 1, alpha, beta)) else: v min(v, self.minValue(nextState, agentIndex 1, depth, alpha, beta)) if v alpha: return v beta min(beta, v) return v剪枝的触发条件要背熟MAX节点发现v已经比beta大说明对手在上一层MIN节点绝不会选这个分支直接returnMIN节点发现v已经比alpha小说明吃豆人在上一层MAX节点绝不会选这个分支直接return。getAction里更新alpha用的是bestScore而不是每一轮的v因为根节点也是MAX层它最终只选一个动作下界的含义就是我目前已经有一个必拿的分数。写完后记得跑一个断言相同深度下AlphaBetaAgent和MinimaxAgent每个动作的返回值必须完全一致。3.2 剪枝顺序决定速度先看谁的分支效果完全不同Alpha-Beta的剪枝效率不是恒定的最坏情况退化成普通Minimax最好情况只搜一半节点。吃豆人里有两个天然的排序启发式在MAX节点先探索能立即得分吃豆、吃胶囊的动作在MIN节点先探索能把吃豆人逼入死角的鬼动作。实际操作中可以在遍历之前对legalActions按一个简单启发排序比如吃豆人先走豆子更近的格子鬼先走距离更近的格子。我见过有人把排序逻辑写进评估函数里反而拖慢速度——排序必须用廉价特征不要为了排序重新跑一次完整评估。深度相同的情况下Alpha-Beta和Minimax返回的最优动作必须完全一致这是自检的硬标准。3.3 Expectimax把鬼是随机走建模成期望节点Minimax假设鬼是完美对抗者但CS188默认的鬼行为其实带随机性除非你主动换DirectionalGhost所以Minimax会过度悲观。Expectimax把MIN节点替换成期望节点对鬼的所有合法动作取平均分数而不是取最小。这样吃豆人能识别出虽然某个分支可能送死但概率很低的有利局面。class ExpectimaxAgent: def __init__(self, depth2): self.depth depth def getAction(self, gameState): bestScore float(-inf) bestAction Stop for action in gameState.getLegalActions(0): nextState gameState.generateSuccessor(0, action) score self.expectValue(nextState, 1, 0) if score bestScore: bestScore score bestAction action return bestAction def expectValue(self, state, agentIndex, depth): if state.isWin() or state.isLose() or depth self.depth: return state.getScore() total 0.0 actions state.getLegalActions(agentIndex) for action in actions: nextState state.generateSuccessor(agentIndex, action) if agentIndex state.getNumAgents() - 1: total self.maxValue(nextState, depth 1) else: total self.expectValue(nextState, agentIndex 1, depth) return total / len(actions)expectValue的核心是total除以动作数也就是均匀概率。这里有个重要的参数语义如果以后想模拟鬼更聪明的情况可以改成加权和比如给靠近吃豆人的动作更高权重但课程autograder的期望是按均匀分布算的不要擅自加权否则对不上标准答案。Expectimax的复杂度比Minimax更糟因为它无法剪枝——期望值必须算了所有分支才能平均——所以深度最多开到2到3。4. 评估函数决定胜负Multi-Agent Search的分数公式与调参心得4.1 特征选择食物、鬼距离、胶囊优先级怎么排很多人在Project 2里把精力全放在Minimax递归和剪枝条件上这是本末倒置。搜索算法只是把叶子节点打多少分这件事放大动作空间就那么大深度也就2到4真正决定吃豆人行为风格的是叶子节点分数公式。CS188的autograder覆盖了搜索逻辑是否正确但最后的胜率测试完全取决于评估函数质量。所以我一般建议先写好一个能用的评估函数再回头调搜索深度而不是反过来。一个能用的评估函数至少包含四类特征当前累计得分、最近食物距离体现前进性、最近鬼距离体现安全性、以及鬼是否在scared状态。def betterEvaluationFunction(state): pacman state.getPacmanPosition() foodList state.getFood().asList() if not foodList: return float(inf) # 所有豆子吃完直接视为必胜 score state.getScore() minFoodDist min(manhattanDistance(pacman, f) for f in foodList) avgFoodDist sum(manhattanDistance(pacman, f) for f in foodList) / len(foodList) ghostDists [] scaredTimes [] for i in range(1, state.getNumAgents()): gState state.getGhostState(i) ghostDists.append(manhattanDistance(pacman, state.getGhostPosition(i))) scaredTimes.append(gState.scaredTimer) minGhostDist min(ghostDists) maxScaredTime max(scaredTimes) features { score: score, minFoodDist: minFoodDist, avgFoodDist: avgFoodDist, minGhostDist: minGhostDist, maxScaredTime: maxScaredTime, } weights { score: 10.0, minFoodDist: -2.0, avgFoodDist: -1.0, minGhostDist: 3.0, maxScaredTime: 2.0, } return sum(weights[k] * features[k] for k in features)优先级排序上我的习惯是minGhostDist的权重必须高于minFoodDist否则吃豆人会在鬼脸上抢豆子maxScaredTime的权重是动态的——鬼被吓住时距离越大反而越吃亏但为了保持线性形式直接用scaredTimer本身做正特征让搜索自己在不同局面下权衡。注意这里没有用剩余胶囊数因为胶囊对非scared鬼的影响要隔一层才体现特征太间接反而干扰搜索。4.2 权重调参别让评估函数变成主动送死函数调权重的常见翻车现场是给了score过高的正权重吃豆人为了多吃一个豆冲进死角或者给了minFoodDist过大的负权重导致它在两个豆子之间反复横跳因为下一步离豆子更近的诱惑压过了鬼正在靠近的警报。我的调试方法是开一个终端跑无限对局另一个终端改权重把每个决策动作连同评估值打印出来看——如果某个动作的分数明显反直觉比如鬼就在隔壁还选往前冲先把所有权重缩到同一量级再逐个调。模型写吃豆人提示词这类思路我也试过让大模型直接生成评估函数它给的特征组合往往过于理论像剩余行动力未来可得分这些没法从GameState直接拿到最后还是得回到手动调参。权重调整我一般按安全类特征前进类特征约1.2:1起步再根据对局微调。特征权重起点作用方向score10.0鼓励吃豆子累积分数minFoodDist-2.0鼓励向最近食物前进距离越小分越高avgFoodDist-1.0鼓励整体清场防止只追最近豆minGhostDist3.0鼓励远离最近的鬼权重必须高于食物距离maxScaredTime2.0鼓励抓住鬼被吓住的窗口追击这个表里的起点是我试过的组合里最不容易出意外的。如果你想验证某个权重的作用不要一次改多个每次只动一个值跑十局看胜负。这样能清楚地知道是哪一项造成了行为改变。4.3 为什么最小鬼距离比当前分数更能反映局面如果你观察Minimax叶子节点的返回值就会发现getScore()本身只反映吃豆人吃到了什么完全不含鬼的位置信息。一个吃了很多豆但被鬼堵死的状态和一个豆子少但通道开阔的状态getScore可能一样但前者下一秒就死。所以评估函数必须把安全性显式放进去。这也是为什么ReflexAgent里纯score能过关、但Minimax里纯score必翻车搜索越深叶子节点越需要表达局势而不是账目。举个具体例子。状态A累计30分最近鬼距离1格状态B累计10分最近鬼距离4格。用特征权重score1、minGhostDist2算A得分32B得分18吃豆人选A宁可贴着鬼吃豆。把minGhostDist权重提到8A变成38B变成42决策就变成先保命。两个状态的分差只有20分而鬼距离差3格——权重8意味着鬼距离每格值8分安全收益24分正好压过分数差距。用minGhostDist做安全特征时注意它是个距离值越小越危险权重是正数才表示鼓励远离很多人写成负数结果吃豆人主动往鬼嘴里送。5. Multi-Agent Search常见问题避坑死循环、深度爆炸、结果对不上5.1 现象深度调到3以后游戏一局要跑几分钟这不是电脑慢是搜索树的节点数爆炸了。分支因子约4两个鬼时每层是4的3次方64个节点Minimax深度3就是64的三次方约26万次递归每次递归还要生成新状态再算评估函数。原因是对深度的理解错了深度3指吃豆人加每个鬼各行动3轮而不是3层动作。解决方法是先把depth降到1验证逻辑正确再用Alpha-Beta最后才考虑上ExpectimaxExpectimax本身没法剪枝深度3就是极限非要提速可以给评估函数加一个缓存用(状态哈希, 深度, agentIndex)做key同一局面不重复算。5.2 现象报错KeyError或者某个动作递归到None这种报错十有八九是legalActions里带了Stop而你把它当成正常动作传入generateSuccessor。Stop确实是一个合法动作但当你过滤掉某些动作后状态可能已经终局getLegalActions返回空列表此时继续递归就会在取action时报错。解决方法是递归入口先判断isWin和isLose再判断depth上限最后再取legalActionsgetAction里如果legal为空直接返回Stop保底。另外generateSuccessor返回的是新状态不要用它覆盖原来的state变量否则后续兄弟节点的遍历就乱套了。5.3 现象Alpha-Beta的结果和Minimax就是不一样Alpha-Beta剪枝在理论上应该与Minimax完全一致结果不同说明剪枝条件写错或alpha、beta的传递错位。常见错误有两个一是在getAction层用v更新alpha而不是用bestScore导致根节点下界失真二是MAX节点和MIN节点的剪枝条件写反把v大于beta和v小于alpha搞混。解决方法是写一个断言脚本在同一深度下把AlphaBetaAgent和MinimaxAgent跑在同一组固定地图上逐动作对比不一致就在两个类里同时打印alpha、beta和返回值找出第一个不一致的分支。绝大多数情况下问题出在alpha更新的位置而不是剪枝条件本身。5.4 现象Expectimax结果总是过于乐观胜率反而低于Minimax这不是bug是期望值本身的性质均匀分布的鬼动作里某些送死分支的概率可能是四分之一期望值会把这种风险稀释掉。Minimax眼里必死的分支Expectimax可能给出还能赌一赌的分数。原因在于评估函数的安全特征权重不够不足以抵消期望平均对风险的稀释。解决办法不是改搜索算法而是把minGhostDist的权重加大或者直接在评估函数里加一个截断如果minGhostDist小于某个阈值比如2把分数压成一个非常大的负数相当于在搜索树里手动标红危险区域。我见过有人试图给Expectimax加剪枝这是徒劳的——期望值必须看到全部分支才能平均剪枝只会算出错误结果。5.5 现象用scaredTimer做特征鬼被吓住时吃豆人反而乱跑原因scaredTimer变大时鬼的威胁降低但评估函数里minGhostDist权重是正的鼓励远离两者互相矛盾——鬼都吓跑了你还跑胶囊时间全浪费。解决在评估函数里区分状态当maxScaredTime大于0时把minGhostDist的权重反转成负数鼓励吃豆人主动贴近鬼去拿分或者更简单直接用scaredTimer和距离的乘积做特征让搜索自己权衡。这个坑在Q5的胜率测试里特别明显因为胶囊一出现吃豆人反而开始满图乱跑看似谨慎实则把大好的进攻窗口浪费掉了。6. 验证你的Multi-Agent Search成果从autograder过关到自定义对局6.1 用autograder和命令行对局做双重验证课程自带的autograder是第一个验收标准。常见做法是单独测每个question确认Minimax和Alpha-Beta在相同深度的返回动作完全一致再跑Expectimax看固定随机种子下的稳定性。但autograder只是保底我会额外跑几场固定地图的对局python pacman.py -p MinimaxAgent -k 2 -l mediumClassic -a depth3把鬼的数量从2加到4看吃豆人的存活时间和得分变化。注意-k参数控制鬼数-l指定地图-a传深度固定地图的胜率比随机地图更能暴露决策漏洞。6.2 进阶动态深度和缓存让吃豆人真正变强跑通基础版之后我会做三件事。第一把深度改成动态的——开局阶段分支多但危险小用depth2后期豆子少、鬼聚集用depth4因为分支因子大幅下降。第二给评估函数加一个上一步动作惩罚避免吃豆人在两个相邻格子反复横跳这属于时序特征能明显提升视觉效果。第三用状态哈希缓存已算过的Minimax值key是(state, agentIndex, depth, alpha, beta)在一局游戏里相同局部状态出现多次时能省不少时间。我第一次跑Expectimax时以为它一定全面碾压Minimax结果在openClassic上胜率反而掉了两成原因就是评估函数里安全权重太低期望值把送死分支稀释成了可冒险。后来把minGhostDist权重提到3.5再跑同一地图胜率才追回来。这个教训我一直记得搜索算法决定上限评估函数决定下限而评估函数永远是那个最需要耐心调的黑匣子。希望这些实现细节和调参经验能帮到你也祝你的吃豆人早日通关。本文还有配套的精品资源点击获取
