我在伯克利CS188这门课的历届作业里Project 2的返工率一直很高。前面第一项目大家还都在做单智能体搜索BFS、A*、启发式函数写得飞起一到Multi-agents画风突变Pacman面前多了几只幽灵你需要让它在一个持续对抗的环境里做决策。很多人第一次运行结果要么Pacman原地发呆要么一头撞进幽灵怀里要么Alpha-Beta和Minimax的输出对不上。这个项目的核心不是“找到一条路”而是“在对手也在行动的前提下选出每一步最优动作”。它要你亲手实现Minimax、Alpha-Beta剪枝、Expectimax最后再设计一个能打的评估函数。做完之后你会发现课程视频里那些抽象的对抗搜索概念全都变成了你手里可以运行的代码。这篇文章我会把整个项目从架构理解到每一步实现的关键细节都拆开讲包括我见过的各种翻车现场希望你能少走弯路。1. 项目定位多智能体搜索在CS188里的真实分量1.1 从“找路”到“博弈”第二项目想训练什么CS188的第一项目让你处理的是“静态环境下的路径规划”。地图不动终点不动你只需要找一条最优路径。但真实世界的决策问题几乎没有这么安静你动对手也动你规划路线对手也在想尽办法拦截你。Project 2正是为了补上这一课。多智能体搜索本质上是博弈树搜索。Pacman和所有幽灵被建模成轮流行动的智能体Pacman先走一步然后每个幽灵依次走一步这样构成一个完整的回合。Pacman的目标是最大化自己最终的累计得分幽灵的目标是让它撞上自己、降低得分也就是最小化同一个数值。于是整个游戏过程可以被抽象成一棵对抗搜索树树中的层由不同的智能体轮流扩展Pacman层取最大收益幽灵层取最小收益。这就是Minimax的由来。这里有一个很关键的思维转变你在递归里处理幽灵节点时并不是在“模拟幽灵真的会思考”而是Pacman在假设“幽灵总是会选择让我最难受的那步棋”。这是一种保守策略相当于假设对手永远完美。这个假设不一定在所有场景里都成立比如后面Expectimax就会换掉它但Minimax是最基础的出发点必须先吃透。1.2 任务版图Q1到Q5分别检验什么能力Project 2一共五个任务覆盖面很清晰任务核心内容检验能力Q1ReflexAgent写一个评估函数加一次决策逻辑让Pacman能即时避障吃豆Q2MinimaxAgent实现固定深度Minimax状态树上交替取max/minQ3AlphaBetaAgent在Minimax上加入剪枝结果必须与Q2完全一致Q4ExpectimaxAgent把幽灵节点的min换成期望值计算应对随机行为Q5betterEvaluationFunction设计一个更强的评估函数让Pacman在复杂布局里也能高分存活前两个任务是基础第三个是性能优化第四个改变了对对手的建模方式第五个则是从搜索算法转向“如何定义状态好坏”的特征工程。很多人觉得Q5不重要其实恰恰相反。Minimax和Alpha-Beta只是框架它们本身不会告诉你某个局面好不好给AI“眼光”的是评估函数。你搜索得再深评估函数一团糟Pacman照样是个方向感混乱的莽夫。我见过很多同学Q2到Q4都顺利通过结果卡在Q5的胜率测试上很久就是因为低估了评估函数的设计难度。2. 动工之前必须搞清楚的GameState与代理接口2.1 GameState提供了哪些关键信息写代码前我强烈建议先把gameState的接口读一遍。这个项目几乎所有的逻辑都建立在GameState之上不理解它的方法后面处处踩坑。常用方法就那么几个gameState.getPacmanPosition()Pacman当前坐标。gameState.getGhostStates()返回所有幽灵的状态对象里面包含位置、方向、scaredTimer惊吓剩余时间。gameState.getGhostPosition(agentIndex)指定某个幽灵的位置。gameState.getFood()返回一个Grid对象可以用hasWall一类的方式查询每个格子是否有豆子。gameState.getCapsules()胶囊位置列表。gameState.getLegalActions(agentIndex)返回某个智能体在当前状态的合法动作列表。gameState.generateSuccessor(agentIndex, action)模拟某个智能体做出某个动作后的后继状态。gameState.getNumAgents()智能体总数一般是Pacman加所有幽灵。gameState.isWin()/gameState.isLose()判断终局。gameState.getScore()当前得分。一个容易忽略的点是getLegalActions在终局状态下不一定有有效返回值。所以递归搜索里一定要先判断是否终局再取合法动作。这个顺序错了轻则报错重则出现诡异的逻辑错误。2.2 多代理轮转、深度计数与动作状态Project 2的多代理轮转是很多bug的源头。部分同学会把“深度”和“层数”混为一谈。这里我重新梳理一下智能体编号从0开始。0号是Pacman1号到numAgents-1号是幽灵。搜索树每一层由某一个智能体扩展。Pacman层取max幽灵层取min。所谓“一回合”是指Pacman和所有幽灵各走一步。也就是说当层数从幽灵节点回到Pacman节点时深度才加1。终止条件到达指定深度或者状态是win/lose。我用一个标准做法来跟踪轮转和深度。假设当前处理的是agentIndex号智能体下一个要扩展的智能体是nextAgent (agentIndex 1) % gameState.getNumAgents()如果nextAgent 0说明一轮完成了深度加1否则深度不变。这个设计很简洁能保证搜索在“回合”边界上推进深度。2.3 文件边界该改的和不该改的这个项目要改的文件非常明确multiAgents.py所有Agent类的实现都在这里Q1到Q5都改这个文件。pacman.py、game.py、graphicsDisplay.py等项目框架文件不要碰。有些同学喜欢在pacman.py里加辅助函数来调试我不建议这样做。项目自带的autograder会检查代码能否正常导入运行改动框架文件容易引发意外。调试用的输出放在multiAgents.py里或者单独写脚本都行。另外evaluationFunction和scoreEvaluationFunction两个函数名是有讲究的前者是通用评估函数接口供搜索算法在叶子节点调用后者是默认的评分函数直接返回state.getScore()Q5要求你写一个更好的betterEvaluationFunction最终会替换掉默认函数。注意ReflexAgent里用的评估函数和搜索深度为0时调用的评估函数是同一个机制想清楚这点对理解代码流程很有帮助。3. Minimax的完整实现递归设计与调试实录3.1 价值函数骨架从总入口到max/min的拆解Minimax的实现思路已经被说烂了但真正写起来总有人在某一步搞错。核心就三件事最大值节点、最小值节点、终止条件。我推荐把逻辑拆成value、maxValue、minValue三个方法。value做总调度根据当前agentIndex决定走max还是min分支同时处理终止条件。这样结构最清晰也方便后续加Alpha-Beta剪枝。一个典型的Minimax递归骨架是这样的以Python为例def value(self, gameState, agentIndex, depth): if depth self.depth or gameState.isWin() or gameState.isLose(): return self.evaluationFunction(gameState) if agentIndex 0: return self.maxValue(gameState, agentIndex, depth) else: return self.minValue(gameState, agentIndex, depth) def maxValue(self, gameState, agentIndex, depth): v float(-inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) nextAgent (agentIndex 1) % gameState.getNumAgents() nextDepth depth 1 if nextAgent 0 else depth v max(v, self.value(successor, nextAgent, nextDepth)) return v def minValue(self, gameState, agentIndex, depth): v float(inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) nextAgent (agentIndex 1) % gameState.getNumAgents() nextDepth depth 1 if nextAgent 0 else depth v min(v, self.value(successor, nextAgent, nextDepth)) return v然后getAction方法只需要调用一次valuedef getAction(self, gameState): bestAction None bestScore float(-inf) for action in gameState.getLegalActions(0): successor gameState.generateSuccessor(0, action) nextAgent (agentIndex 1) % gameState.getNumAgents() nextDepth 1 if nextAgent 0 else 0 score self.value(successor, nextAgent, nextDepth) if score bestScore: bestScore score bestAction action return bestAction有人说可以直接在maxValue里记录动作不单独写getAction。也可以但新手容易搞混“根节点”和“递归内部节点”的区别。我建议根节点单独处理因为根节点需要返回动作而内部节点只需要返回分值。3.2 边界条件的处理顺序和返回值边界条件的顺序很关键。正确顺序是先判断是否到达指定深度。再判断是否终局win或lose。如果以上都不满足再扩展子节点。为什么终局判断不能放在最前面因为深度判定和终局判定其实是并列的终止条件谁先谁后都行。但有一种情况要注意如果游戏在搜索中途已经结束那么再调用getLegalActions就可能出问题。所以比较稳的写法是把“深度到了或终局了”合并成一个判断提前返回评估值。返回值方面叶子节点的值一定来自evaluationFunction(gameState)而不是gameState.getScore()。虽然scoreEvaluationFunction默认返回的就是getScore()但你自己设计的betterEvaluationFunction会做更复杂的计算如果写死成getScore()后面Q5就废了。3.3 我见过最多的四种错误我在帮人调试时Minimax的错误基本可以归为四类第一类nextDepth永远不加。有人直接用depth 1作为每次递归的深度导致“一回合”的概念变成了“一层”。这样搜索树虽然会终止但深度语义完全错了Pacman会表现出一种奇怪的短视。第二类动作列表没取对。在getAction里有人直接用gameState.getLegalActions()而不带智能体编号。这个项目里不同智能体的合法动作集是不一样的必须传0Pacman或对应的agentIndex。第三类最大值初始值用0。当所有子节点的值都是负数时用0做初始值会让结果错误。最大值初始值必须用float(-inf)最小值初始值必须用float(inf)。第四类把max和min写反。Pacman是max幽灵是min。这个看似简单但状态多的时候容易晕。我一般会在注释里写清楚agentIndex 0表示Pacman节点取maxagentIndex 0表示幽灵节点取min。4. Alpha-Beta剪枝同等深度下把耗时砍掉大半4.1 剪枝到底剪掉了什么Alpha-Beta剪枝不是一个新的搜索算法它是在Minimax基础上加了一层“如果这个分支不可能影响最终决策就不继续展开”的优化。核心思想是维护两个值alpha在max节点已经找到的能保证的最大下界。beta在min节点已经找到的能接受的最小上界。当某个max分支的值已经大于或等于beta时说明当前min节点已经有了一个更小的选择这个max分支后续再怎么扩展也不会被min选中可以剪掉。反过来当某个min分支的值小于或等于alpha时说明当前max节点已经有了一个更大的选择这个min分支也可以剪掉。用一句大白话概括如果某个分支的最优结果都已经不如你已经找到的结果那它就没有继续搜索的价值了。4.2 alpha/beta的更新时机与传递方式实现Alpha-Beta时最容易出错的是参数的传递时机。记住这几条就不会乱在max节点遍历子节点时更新alphaalpha max(alpha, childValue)如果childValue beta立刻剪枝返回。在min节点遍历子节点时更新betabeta min(beta, childValue)如果childValue alpha立刻剪枝返回。alpha和beta要一路从父节点传给子节点子节点的返回值再用来更新父节点的alpha或beta。一个可运行的骨架def maxValue(self, gameState, agentIndex, depth, alpha, beta): v float(-inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) nextAgent (agentIndex 1) % gameState.getNumAgents() nextDepth depth 1 if nextAgent 0 else depth v max(v, self.value(successor, nextAgent, nextDepth, alpha, beta)) if v beta: return v alpha max(alpha, v) return v def minValue(self, gameState, agentIndex, depth, alpha, beta): v float(inf) for action in gameState.getLegalActions(agentIndex): successor gameState.generateSuccessor(agentIndex, action) nextAgent (agentIndex 1) % gameState.getNumAgents() nextDepth depth 1 if nextAgent 0 else depth v min(v, self.value(successor, nextAgent, nextDepth, alpha, beta)) if v alpha: return v beta min(beta, v) return vvalue函数要把alpha和beta原样往下传def value(self, gameState, agentIndex, depth, alpha, beta): if depth self.depth or gameState.isWin() or gameState.isLose(): return self.evaluationFunction(gameState) if agentIndex 0: return self.maxValue(gameState, agentIndex, depth, alpha, beta) else: return self.minValue(gameState, agentIndex, depth, alpha, beta)注意alpha和beta在递归过程中是不断收窄的。alpha只会变大beta只会变小。一旦出现alpha beta这个区间的搜索已经没有意义。这个性质也决定了剪枝的效率上限。4.3 一个显著提升剪枝效率的改动动作排序Alpha-Beta剪枝的效率高度依赖动作的遍历顺序。如果优先搜到“更好的分支”alpha和beta会更快收窄剪枝就更多。一个非常简单的做法在max节点先评估那些历史上看起来分高的动作在min节点先评估那些历史上看起来分低的动作。项目里没有强求但你自己测试的时候会发现同样的深度排序后的搜索速度可以快出好几倍。尤其是在深度较大的mediumClassic布局里不排序可能卡到让人怀疑人生排序之后流畅很多。当然动作排序不是Q3的必测点autograder只关心“结果和Minimax一致”。但如果你想在实际游戏里看到Pacman跑得更快这一步值得做。5. Expectimax给幽灵的随机行为建模5.1 从Min到Chance为什么有时不能假设对手完美Minimax假设对手总会选择最坏的分支这是一种稳健但保守的策略。但现实中的幽灵并不总是完美的它们会随机转向、会因为地图结构做出愚蠢动作甚至在某些测试场景里本身就是随机移动的。Expectimax的思路是在幽灵节点不取最小值而是计算所有子节点值的期望。换句话说用概率平均值替代最坏情况。如果你知道幽灵每个动作的概率就按概率加权如果不知道通常用均匀分布即所有动作的概率相同。这个改变会让Pacman的决策从“防备最坏对手”变成“追求整体收益最大化”。在某些场景下Expectimax的表现反而比Minimax更好因为Pacman不会被“幽灵万一做出极端完美动作”这种低概率事件吓到不敢前进。5.2 期望值节点的实现细节实现上与Minimax的唯一区别在于幽灵节点。原来求min的地方改成对所有子节点的值求和并除以动作数量def chanceValue(self, gameState, agentIndex, depth): v 0.0 actions gameState.getLegalActions(agentIndex) for action in actions: successor gameState.generateSuccessor(agentIndex, action) nextAgent (agentIndex 1) % gameState.getNumAgents() nextDepth depth 1 if nextAgent 0 else depth v self.value(successor, nextAgent, nextDepth) return v / len(actions)注意这里有个细节actions的长度可能为0吗理论上如果游戏没有结束且当前智能体无路可走会返回一个包含Stop的默认动作所以不会为0。但保险起见仍然建议先判终局再取合法动作。5.3 Minimax与Expectimax的适用边界这两个算法没有绝对的谁优谁劣关键看你对幽灵行为的建模假设场景推荐算法原因幽灵有明确策略、会追捕PacmanMinimax最坏情况防护更稳幽灵随机移动、行为不可预测Expectimax期望收益更符合实际地图开阔、幽灵数量多Minimax配合剪枝搜索深度更深决策更长远地图狭窄、幽灵容易堵路Expectimax避免因过度悲观而错过逃生窗口我在实际测试中发现Expectimax在minimaxClassic这类小地图上表现不错但在幽灵本身有追踪逻辑的默认布局里有时会显得“过于乐观”倾向于冒进。这时候可以适当增加评估函数中对幽灵距离的惩罚权重来平衡。6. 评估函数决定Pacman上限的特征工程与权重调优6.1 默认评估函数为什么“短视”默认的scoreEvaluationFunction直接返回gameState.getScore()。这个分数只反映当前吃到多少豆子、距离终点还有多少步完全不管幽灵位置、豆子分布、惊吓状态。在搜索深度有限的情况下Pacman只能看到几步后的分数变化很容易做出“只顾眼前”的决策。有一次我让一个只用默认评估函数的MinimaxAgent跑mediumClassic它的表现是看到不远处有一堆豆子就冲过去完全无视旁边就是幽灵。明明绕一下就能安全吃到结果一头撞上去。这就是评估函数缺失了“风险”信息导致的。6.2 一个能打的评估函数由哪些特征组成设计评估函数本质上是在回答一个问题从当前局面看Pacman到底处于多安全的优势地位我常用的特征有这么几个当前分数gameState.getScore()这是基础信息。剩余豆子数量gameState.getNumFood()或currentFood.count()豆子越少越接近通关应该给高权重。最近食物距离Pacman到最近一颗豆子的距离。这个距离越短越好能引导Pacman朝有食物的方向移动。通常用曼哈顿距离。最近幽灵距离Pacman到最近一只未受惊吓幽灵的距离。这个距离越远越好距离近时要有很强惩罚。惊吓时间ghostState.scaredTimer。幽灵处于惊吓状态时可以被吃掉这时候应该主动靠近而不是逃跑。胶囊距离胶囊能惊吓幽灵如果有胶囊没吃到可以适度引导Pacman去吃。终局标记isWin给超大正分isLose给超大负分。注意这只能在叶子节点靠搜索终止条件触发不能在普通评估里当作特征循环判断。把这些特征加权组合最简单的形式是score gameScore - significantWeight * nearestGhostDistance - weightFood * numFoodsRemaining - weightFoodDist * nearestFoodDistance weightScared * totalScaredTime注意“最近幽灵距离”这一项幽灵距离越近减分越多。但距离为0就代表Pacman已经撞上幽灵此时直接返回一个极大的负值更合理。6.3 权重的调整与验证方式权重要不要调整到非常精细不需要但也别太随意。我自己的做法是分两步第一步确定量级。比如最近幽灵距离在几个格子到几十个格子之间波动最近食物距离也是类似量级那两者的权重就可以设计成同数量级。如果某个特征的数值范围天然很大它的权重就可以小一些数值范围小但不重要的权重可以大一些。这本质上是在做特征缩放。第二步用项目提供的布局做实战测试。minimaxClassic、trappedClassic、mediumClassic、testClassic这几个布局的难度和场景差异很大。我一般让Pacman分别跑50盘统计胜率和平均得分然后手动调权重。不必追求每一步都最优只要大部分局面下Pacman看起来“思路清楚”就行。还有一个细节评估函数的计算量也要控住。搜索树越深评估函数被调用的次数越多。如果你在评估函数里跑了一个全图范围的最短路径计算那搜索速度会被拖到不可接受。用曼哈顿距离代替真实寻路虽然不完全准确但速度足够快而且对Pacman来说已经够用。7. 一些真实的调试心得与项目之外的想法7.1 我觉得最实用的五种调试手段做这个项目遇到问题时不要只盯着代码干瞪眼。下面几个方法帮我省了非常多时间第一先跑小地图。项目提供了tinyGrid之类的小图或者你可以直接改命令行参数指定一个很小的布局。小地图上动作少搜索树小输出每一步的决策过程很直观。在小地图上调通逻辑再换大地图验证性能。第二加日志打印搜索路径。在递归函数里打印agentIndex、depth、当前动作和返回值。不需要打印所有节点可以在根节点附近打印或者设定一个打印阈值。这样你能看到树是怎么扩展的哪里逻辑断了立刻能发现。第三用标准测试脚本对比结果。autograder本身会检查Minimax和Alpha-Beta的结果是否一致。如果两者输出有差异先别怀疑算法八成是某个分支的剪枝条件写错了。把剪枝开关关掉再跑一次看能不能复现Minimax结果。第四临时把评估函数换成“打分状态”。如果你发现Pacman行为诡异先在评估函数里只返回score再看看搜索是否正常。这能帮你区分“是搜索逻辑错了”还是“是评估函数引导错了”。这两个问题经常被混在一起不拆开很难定位。第五手动构造固定状态测试。你可以写一个脚本构造一个Pacman旁边就是食物、但幽灵马上要过来的局面然后观察Agent选择什么动作。如果它选了找死的那条路说明要么评估函数里风险权重太低要么搜索深度不够导致看不到幽灵下一步动作。手动构造极端情况是验证算法边界的好办法。7.2 这个项目带给我的启发做完Project 2再去回顾课程内容我最大的感受是对抗搜索不是一种“高级技巧”而是把“决策”这件事结构化的一种方式。Minimax逼你想清楚谁是决策方、谁是对手、我的目标函数是什么、我打算看多远的未来。Alpha-Beta告诉你很多信息在决策过程中其实不需要知道剪掉它们不会损失决策质量。Expectimax提醒你对手的行为模型决定了你的策略形态。而评估函数设计则是在说无论算法多强它最终衡量的是你对“好局面”的定义是否准确。这些思路放到真实项目里同样适用。比如做游戏AI、做自动谈判系统、做多智能体仿真甚至做推荐系统里的广告拍卖竞价底层都有这一套“预测对手、评估局面、滚动优化”的影子。我后来再去学强化学习的时候发现状态价值函数、策略梯度这些概念和写评估函数、调权重的直觉其实是相通的。最后分享一个小经验如果你在某一步卡住了别急着翻答案。先把自己对当前局面的“评估”写下来——如果你是Pacman你为什么会选这一步然后去代码里找哪个特征、哪一层搜索、哪个权重没有体现这个直觉。大多数情况下问题都会自己浮出来。