如果你刷过伯克利CS61B或者看过AI入门视频大概率见过那只黄色吃豆人在迷宫里被鬼追得满地图跑的画面。那个场景十有八九就来自CS188的Project 2: Multi-Agents。这个项目是所有CS188课程作业里最有“游戏感”的一个任务很直接——亲手写出一个能吃豆子、能躲鬼、甚至能反过来吃鬼的AI智能体。这个Project在AI课程体系里的地位很特殊。它不教神经网络也不涉及复杂的概率图模型而是把一个最经典的多智能体决策问题直接摆到你面前多个角色轮流行动目标互相冲突你该怎么选下一步这就是对抗搜索也就是博弈搜索。很多人做AI大作业时喜欢一上来就搞深度学习但CS188 Project 2会告诉你真正落到决策层面很多问题用搜索就能解决而且解决得很漂亮。本文适合正在做CS188大作业、复习人工智能导论博弈搜索、或者想找一个完整的AI练手项目的人。我会把项目任务、核心算法、代码实现、调参与调试经验全部过一遍尤其是那些课程网站上不会写、但你在debug时一定会遇到的坑。1. 项目全景Multi-Agent Pacman到底在做什么1.1 这不是单机吃豆人游戏很多人第一次打开Pacman项目时会觉得这不就是个吃豆子游戏吗我控制Pacman吃光所有豆子就赢了。但Project 2的Pacman和普通游戏有个本质区别Pacman不是由你手动控制的而是由你写的AI自动控制而且地图里还有若干个鬼魂Ghost在主动追你。整个场景是一个标准的零和博弈。Pacman的目标是吃光所有豆子并且不被鬼魂抓到鬼魂的目标则是尽快抓住Pacman。Pacman每走一步鬼魂也会走一步双方轮流行动。也就是说Pacman做的每一个决策都必须考虑到“我走完这步之后鬼魂会怎么走”而鬼魂同样也会考虑Pacman的反击。这种交替行动的结构天然形成了一棵博弈树。从单智能体搜索切到多智能体博弈很多人一开始会很不适应。Project 1里的BFS、DFS、A*都是一个人在地图里规划路径目标函数写清楚就行。但在Project 2里你写出的搜索不仅要“找路”还要“预测对手的动作”。这完全是两种思维模式。1.2 五个任务一条完整的进阶路线CS188 Project 2在官方代码里通常分为五个小任务每个任务都有自己的考察重点。我把它们整理成一张表题目核心考点大致分值Q1 Reflex Agent评估函数设计、基于当前状态选动作6分Q2 Minimax递归博弈树、MAX/MIN交替搜索5分Q3 Alpha-Beta Pruning剪枝逻辑、减少无效搜索5分Q4 Expectimax随机agent建模、概率期望5分Q5 Evaluation Function特征工程、多目标权衡6分很多人觉得Q1很简单随手写个“离豆子最近就走哪边”就交上去了。但Q1其实是整个项目的地基因为Q2到Q4写出的搜索树在叶子节点都依赖同一个东西——评估函数。Q1写的评估函数有多粗糙后面几个任务的上限就有多低。而Q5又把评估函数单独拎出来重点考察前后是呼应的。1.3 这个项目在AI知识体系里的坐标如果你把《人工智能导论》这门课的知识点列出来博弈搜索是搜索那一章的压轴内容。它前面是BFS、DFS、A*这些经典搜索算法后面往往会衔接强化学习、博弈论建模、多智能体系统。CS188 Project 2正好卡在这个位置。做完这个项目你应该能回答三个问题在多智能体环境下如何把一个决策问题形式化为博弈树搜索当对手是理性的时候用什么算法当对手行为不确定、甚至带随机性的时候又用什么算法这三个问题搞明白了后面学强化学习里的value iteration、policy iteration会发现思路是一脉相承的。2. 核心算法拆解Minimax、Alpha-Beta与Expectimax2.1 Minimax最朴素的理性对抗Minimax中文常译作极小极大搜索是零和博弈最基础的算法。它建立在两个假设之上第一双方轮流行动第二双方都是理性的。所谓理性就是Pacman在自己的回合会选择对自己最有利的动作鬼魂在自己的回合会选择对Pacman最不利的动作。具体到吃豆人游戏里Pacman的行动节点叫MAX节点因为Pacman想让评估分数最大化鬼魂的行动节点叫MIN节点因为鬼魂想让评估分数最小化。搜索从当前局面出发一层一层往下展开直到达到设定的深度上限或者游戏分出胜负。到了搜索树的叶子就用评估函数打一个分。然后从叶子往根回溯MAX层取所有子节点分数的最大值MIN层取所有子节点分数的最小值。用一个生活化例子类比就像两个人轮流从一堆数字里选数一个人想最后结果尽量大另一个人想结果尽量小。你每走一步都要把对手之后可能的所有走法都过一遍才知道这一步到底值不值。Minimax的复杂度是O(b^m)b是每个节点平均可选动作数m是搜索深度。吃豆人地图里一个位置通常有2到3个合法动作鬼魂也有类似数量所以每一个深度都会让搜索规模指数级膨胀。这也是为什么真实的项目里几乎不会用裸Minimax必须配合剪枝技术。2.2 Alpha-Beta剪枝砍掉注定没用的分支Alpha-Beta剪枝是在Minimax基础上的一个优化它不会改变搜索结果只是让搜索更快。核心思想是如果某个分支已经不可能影响最终决策就不需要继续往下搜索了。具体来说搜索过程中维护两个边界。alpha是MAX节点目前已经得到的最大下界意思是“Pacman至少能拿到这个分数”beta是MIN节点目前已经得到的最小上界意思是“鬼魂最多会让分数不超过这个值”。在MAX节点如果发现某个子节点的值已经大于等于beta那这个节点就没必要继续搜了因为鬼魂在一层一定不会让这个局面发生在MIN节点如果某个子节点的值小于等于alpha同样可以直接剪掉。很多人第一次写Alpha-Beta容易在“谁更新alpha、谁更新beta”上搞混。我提供一个记忆方法alpha跟着MAX走beta跟着MIN走。MAX层只更新alphaMIN层只更新beta剪枝判断则是MAX层看beta、MIN层看alpha。需要注意剪枝的效果和搜索顺序关系很大。如果先搜到足够好的分支alpha和beta的边界会收得很紧剪枝效率高如果搜索顺序很差Alpha-Beta可能退化成裸Minimax。为了提升剪枝效率可以对后继动作做一个简单重排比如越有希望的动作越先搜索。在吃豆人项目里这个优化不是必须的但理解这一点对以后做更复杂的搜索很有帮助。2.3 Expectimax对手不是一个“聪明”的玩家Minimax假设鬼魂每一步都极度理性会选择对Pacman最差的走法。但实际情况是CS188里的鬼魂虽然有一定追击逻辑但它的行为并不是完美理性甚至在某些地图中鬼魂的移动带有随机性。这时如果继续用MinimaxPacman会过度悲观白白错过一些成功概率很高的机会。Expectimax就是为这种情况设计的。它的搜索结构跟Minimax几乎一样唯一的区别是在鬼魂对应的MIN节点不再取最小值而是取所有子节点分数的平均值或者说期望值。这样一来Pacman的决策依据不再是“最坏情况下会发生什么”而是“平均情况下会发生什么”。打个比方Minimax像是你出门前假设必堵车所以提前三小时出发Expectimax则是你看了历史路况发现堵车概率才20%于是按正常时间出门。后者在不确定环境里往往更接近最优策略。实现Expectimax时平均值可以用子节点分数相加再除以动作数量也可以用sum(values) / len(values)。注意别在递归深度、动作索引哪里改动错了Expectimax和Minimax的框架是高度共享的。2.4 评估函数是所有搜索的地基Minimax、Alpha-Beta、Expectimax搜索到一个固定深度之后都必须对叶子节点打一个分这个分数就来自评估函数。评估函数的本质是把一个游戏局面映射成一个实数。分数越高代表局面越有利于Pacman分数越低越有利于鬼魂。在理想情况下如果搜索深度足够深能一直搜到胜负终局那评估函数只需要返回输赢分就行。但实际搜索深度通常只有3到5层远不足以看到终局所以评估函数必须间接刻画“这个局面未来有多大可能赢”。评估函数一般写成多个特征的线性加权和。举个最简单的例子score 当前游戏得分 - 2 * 到最近食物的曼哈顿距离 - 3 * 身边鬼魂的威胁程度。权重越大说明这个特征对决策的影响越大。设计评估函数是一项偏经验的工作也是Q5的重点考察内容后面我会详细展开。3. 实操过程重头代码逐一攻破3.1 环境准备与运行方式先从课程网站或项目仓库下载Pacman项目代码解压后你会看到pacman.py、game.py、multiAgents.py、graphicsDisplay.py等文件。我们几乎所有要写的代码都在multiAgents.py里文件里预先定义好了ReflexAgent、MinimaxAgent、AlphaBetaAgent、ExpectimaxAgent等类。运行项目有两种常用方式。一种是直接让AI在图形界面里玩python pacman.py -p ReflexAgent -l openClassic-p指定使用哪个Agent-l指定地图。想关闭图形界面、只看文字结果可以加--frameTime 0这样跑起来快很多调试时一定用得上。另一种是跑官方自带的自动评分脚本python autograder.py -q q2-q指定测试哪一道题。每次提交前都应该先用autograder跑一遍它会告诉你某个测试case是过了还是挂了以及耗时有多少。3.2 Q1 Reflection第一个能动的吃豆人Q1要求实现ReflexAgent也就是根据当前局面为每个可能动作算一个分数然后选分数最高的动作。核心在evaluationFunction这个方法它接收一个游戏状态和一个候选动作返回一个分数。我的实现思路分三步。第一步生成执行这个动作后的新状态第二步从新状态里提取自己关心的一系列信息比如Pacman的新位置、剩余食物位置、每个鬼魂的位置和scaredTimer鬼魂被吃豆人吃下能量豆后的虚弱倒计时第三步把这些信息组合成一个分数。一个非常基础但可用的评估函数长这样def evaluationFunction(currentGameState, action): successorGameState currentGameState.generatePacmanSuccessor(action) newPos successorGameState.getPacmanPosition() newFood successorGameState.getFood() newGhostStates successorGameState.getGhostStates() newScaredTimes [ghostState.scaredTimer for ghostState in newGhostStates] score successorGameState.getScore() foodList newFood.asList() if foodList: distToFood min(manhattanDistance(newPos, food) for food in foodList) score - 2.0 * distToFood for ghostState, scaredTime in zip(newGhostStates, newScaredTimes): distToGhost manhattanDistance(newPos, ghostState.getPosition()) if scaredTime 0: score 5.0 * max(0, 10 - distToGhost) else: if distToGhost 2: score - 1000.0 else: score - 3.0 / distToGhost return score这里有几个细节值得说。第一generatePacmanSuccessor会返回一个全新的状态原状态不会被修改所以可以放心调。第二鬼魂威胁用的是“距离越近惩罚越大”的非线性方式比一刀切更平滑。第三scaredTimer大于0说明鬼魂处于虚弱状态这时Pacman应该主动接近鬼魂把它吃掉加分。Q1不需要递归搜索但它能让你提前把所有游戏状态API摸熟。后面几个Agent虽然用的是递归搜索但叶子节点最终调用的还是这类评估函数。3.3 Q2 Minimax写一个能博弈的搜索框架Q2要求实现MinimaxAgent需要在multiAgents.py里补全Minimax搜索。这里最忌讳的是一上来就写一大堆代码我建议先理清状态流转。在CS188的设定里每个状态有一条行动链Pacman先行动然后1号鬼魂行动2号鬼魂行动依此类推所有鬼魂行动完算一个完整回合。用变量index表示当前轮到谁0代表Pacman1到numAgents - 1代表各个鬼魂。每轮鬼魂index都会递增最后一个鬼魂行动完后index回到0搜索深度减1。核心递归函数可以这样写def value(self, gameState, index, depth): if gameState.isWin() or gameState.isLose() or depth 0: return self.evaluationFunction(gameState) if index 0: return self.maxValue(gameState, index, depth) else: return self.minValue(gameState, index, depth) def maxValue(self, gameState, index, depth): v float(-inf) for action in gameState.getLegalActions(index): successor gameState.generateSuccessor(index, action) v max(v, self.value(successor, (index 1) % gameState.getNumAgents(), depth)) return v def minValue(self, gameState, index, depth): v float(inf) nextIndex index 1 nextDepth depth if nextIndex gameState.getNumAgents(): nextIndex 0 nextDepth depth - 1 for action in gameState.getLegalActions(index): successor gameState.generateSuccessor(index, action) v min(v, self.value(successor, nextIndex, nextDepth)) return v需要注意深度递减的时机。递减发生在最后一个鬼魂行动完、轮到Pacman再次行动的那一步而不是每个鬼魂行动后各减一次。很多同学在这里写错结果鬼魂数量一多实际搜索层数就莫名其妙地变少。getAction方法里还要处理一个边界情况如果当前Pacman没有合法动作直接返回Directions.STOP。虽然正常游戏里几乎不会出现但autograder有时会构造边界case来测试你的鲁棒性。3.4 Q3 Alpha-Beta在递归里剪枝Q3的AlphaBetaAgent和Q2基本同构只是要额外维护alpha、beta两个参数。注意搜索初始时alpha设为负无穷beta设为正无穷因为一开始我们对上下界一无所知。剪枝的核心代码如下def maxValue(self, gameState, index, depth, alpha, beta): v float(-inf) for action in gameState.getLegalActions(index): successor gameState.generateSuccessor(index, action) v max(v, self.value(successor, (index 1) % gameState.getNumAgents(), depth, alpha, beta)) if v beta: return v alpha max(alpha, v) return v def minValue(self, gameState, index, depth, alpha, beta): v float(inf) nextIndex index 1 nextDepth depth if nextIndex gameState.getNumAgents(): nextIndex 0 nextDepth depth - 1 for action in gameState.getLegalActions(index): successor gameState.generateSuccessor(index, action) v min(v, self.value(successor, nextIndex, nextDepth, alpha, beta)) if v alpha: return v beta min(beta, v) return v判断剪枝的时机可以记成一句话MAX节点发现自己已经比beta还大那这个节点对上层MIN节点没有价值剪掉MIN节点发现自己已经比alpha还小那这个节点对上层MAX节点没有价值剪掉。Alpha-Beta的结果必须和Minimax完全一致。如果跑autograder发现某个测试case结果对不上通常不是剪枝本身写错而是alpha、beta的传递位置搞错了。3.5 Q4 Expectimax把MIN节点换成平均值ExpectimaxAgent是这四个搜索算法里代码改动最少的一个。你甚至可以在Minimax的框架上把minValue的返回逻辑改成求平均值def expValue(self, gameState, index, depth): values [] nextIndex index 1 nextDepth depth if nextIndex gameState.getNumAgents(): nextIndex 0 nextDepth depth - 1 for action in gameState.getLegalActions(index): successor gameState.generateSuccessor(index, action) values.append(self.value(successor, nextIndex, nextDepth)) return float(sum(values)) / len(values)如果动作列表为空要小心除零错误不过游戏状态里一般不会让鬼魂陷入无路可走的境界。在Expectimax里随机节点没有alpha、beta剪枝的概念因为剪枝依赖的是“最坏情况”的边界推断而求均值时所有分支都会影响结果所以不能剪。我建议你实际运行一下同一个地图下Minimax和Expectimax的表现会发现Expectimax往往更“胆大”。在鬼魂其实并不完全理性的时候Expectimax的胜率通常会更高这也是为什么这个算法在实践里很有价值。4. 评估函数设计从能跑变成能赢4.1 评估函数的基本形式Q5要求你回过头来优化评估函数目标是让Pacman在更多地图里取得更高分。到这一步搜索算法本身已经写完了你能额外发挥的就是评估函数这一部分。绝大多数有效的评估函数都长这个样子score w1 * f1 w2 * f2 ...其中fi是某个特征的数值wi是权重。权重的正负代表特征的偏好方向绝对值大小代表重要程度。以Pacman为例比较有效的特征通常包括当前游戏得分直接反映局面好坏到最近未吃豆子的距离距离越短越好权重为负距离Pacman一定范围内、且未处于虚弱状态的鬼魂数量数量越多越危险权重为负附近虚弱鬼魂的距离离虚弱鬼魂越近越有机会反杀权重为正是否还有能量药丸capsule以及到最近能量药丸的距离。第一版评估函数可以先都设成差不多的权重然后跑几局看效果再单独调某一个权重的数值。4.2 特征选择与权重调整的经验我调参数时的一个核心方法是“控制变量法”。每次只调一个权重跑固定的几幅地图对比平均分和胜率再决定是增大还是减小这个权重。比如如果你发现Pacman经常在离豆子很近的时候被鬼魂抓住说明“鬼魂威胁”这一项的权重太小或者“食物距离”的权重太大导致Pacman为了吃豆子不惜冒险。反之如果Pacman经常在某些区域来回徘徊、迟迟不敢靠近豆子说明威胁项的权重过大Pacman过度保守了。这里给出一个我验证过很多次的基础配置思路当前游戏得分权重设为1.0保证优先保留已经获得的分数到最近食物的曼哈顿距离权重在-1.0到-2.5之间对非虚弱鬼魂的威胁惩罚采用分段函数距离小于某个阈值时给一个很大的负奖励比如-1000相当于“死亡禁区”距离稍远但可见时给一个随距离递减的负奖励对虚弱鬼魂的奖励设置为正的鼓励Pacman主动追击能量药丸的吸引力可以设为中等大小因为吃能量药丸本身需要绕过鬼魂风险高但收益高。注意评估函数不需要太追求把所有特征都塞进去。特征多了以后权重互相干扰反而不好调。宁可特征少而精只保留影响最大的三到五个特征。4.3 我调参时踩过的坑第一坑是距离计算用了欧几里得距离而不是曼哈顿距离。吃豆人地图是网格状Pacman只能上下左右移动欧氏距离会低估实际路程导致它判断“很近”的食物其实要绕一大圈。统一换成manhattanDistance会稳定很多。第二坑是忽略scaredTimer的变化。鬼魂被吃下能量药丸后会变成蓝色虚弱状态持续若干步。如果你只判断“它是不是虚弱”而不看还剩几步可能造成Pacman冲过去的时候鬼魂刚好恢复直接送命。所以对虚弱鬼魂要加一个时间衰减比如reward scaredTime * (接近程度)。第三坑是评估函数没有考虑“下一步会被夹击”的局面。比如前方通道有两个鬼魂一左一右堵过来单个鬼魂的威胁惩罚分别不高但合起来Pacman必死。要处理这种情况可以把周围一圈内的鬼魂威胁做累加或者对“两个以上鬼魂同时近距离出现”的情况加一个单独的惩罚项。5. 高频踩坑与调试技巧实录5.1 一定要先会读报错很多同学一看到KeyError或者AttributeError就懵其实报错信息已经把问题说得很清楚了。AttributeError: MinimaxAgent object has no attribute evaluationFunction说明你定义了evaluationFunction但是方法名拼错了或者写到了类外面。IndexError出现在gameState.getLegalActions(index)通常是把index传错比如对Pacman传了鬼魂的索引。我的建议是遇到报错先看两样东西一是报错发生在哪个文件哪一行二是报错信息里提到的是哪个变量或方法。用这两个信息去查代码绝大多数问题不需要问别人就能自己解决。5.2 递归深度与超时autograder对每个测试case通常有运行时间限制超时直接判挂。最容易导致超时的原因有两个一个是递归深度设置得太大另一个是在递归里做了大量重复计算。官方推荐的搜索深度一般很小比如-a depth4就算比较深了。不要贪心一上来就depth8普通笔记本跑起来会非常慢。如果确实想加大深度优先用Alpha-Beta剪枝并且对继任动作做排序让剪枝尽可能早发生。5.3 测小图不要一上来就跑大图调试时一定要用小地图。tinyMaze、openClassic、smallClassic这些地图规模小跑一局只要几秒方便快速观察Pacman的行为。我之前见过有人直接用originalClassic跑一次要几分钟改了一行代码又得重跑效率极低。先在小地图上确认“策略大方向正确”比如Pacman会主动吃豆子、会避开非虚弱鬼魂、会追击虚弱鬼魂再换大地图做性能测试。这样定位问题会快很多。5.4 常见问题速查表现象可能原因排查思路Pacman总往鬼魂脸上走鬼魂威胁项权重不足或漏算打印当前状态的威胁分数检查鬼魂位置读取Pacman原地转圈食物距离项权重太小周围食物吸引力不足增大食物距离权重或加入“未探索区域”特征鬼魂数量多时搜索结果突变深度递减时机错误检查最后一个鬼魂行动后是否depth减1剪枝后结果和Minimax不一致alpha/beta更新位置错误逐层打印alpha、beta值对比评估函数分数爆炸使用了较大权重直接相乘对距离等特征做归一化或分段处理时间超时depth过大或剪枝太少减小depth优化动作搜索顺序这个小表基本覆盖了我在做这个项目时遇到的绝大多数问题。如果你卡住了对着表格一项项排查大概率能解决。6. 项目之外这个Project能带给你的东西6.1 为什么懂了算法还是写不对很多同学在做Project 2之前已经看过Minimax、Alpha-Beta的教程觉得自己懂了。但一动手写代码还是会在状态索引、深度传递这些细节上卡很久。这说明“看懂”和“实现”之间有一道需要靠写代码来跨越的鸿沟。我的个人体会是博弈搜索最难的其实不是算法思想而是对“状态流转”的把控。你写的每个递归函数本质上都在回答一个问题当前这个局面是谁在行动、我能做什么、做完之后轮到谁、搜索深度还剩多少。把这条链路想清楚代码写起来会顺畅很多。这也是为什么我建议先把状态流转图在纸上画出来哪怕画得很潦草也比直接闷头写代码强。6.2 扩展方向从搜索到更现代的AI方法做完Project 2之后你可能会觉得Minimax这套方法有点“笨”只能看有限步。实际上Alpha-Beta剪枝至今仍是很多棋类AI的核心组件Deep Blue战胜卡斯帕罗夫时就用到了类似思想。后来出现的MCTS蒙特卡洛树搜索在AlphaGo里也扮演了重要角色它和Minimax一样都依赖对局面的模拟和评估。如果你对这个方向感兴趣接下来可以自己尝试几件事给Pacman加入MCTS策略看它和Minimax谁更抗随机鬼魂把评估函数换成一个小型神经网络用强化学习去训练权重或者把单Pacman扩展成多个Pacman合作吃豆体验一下 cooperative multi-agent 的建模复杂度。每一条路都能学到不少东西而且都会用到Project 2里打好的基础。6.3 最后分享一个小技巧项目做到最后很多人都只盯着autograder的分数觉得跑过测试就完事了。但我会建议你多做一步跑几局完整游戏用--frameTime 0.1看着Pacman的实际行为把速度放慢观察它在关键局面下是怎么决策的。你会发现光靠autograder里那几个测试case根本看不出Agent的“性格”差异。MinimaxAgent特别怂ExpectimaxAgent偶尔会犯险而一个好的评估函数能让Agent在“稳”和“浪”之间找到平衡。这些观察比拿到一个满分更有价值因为你真正理解了每种算法在真实决策中的样子。