企业官网建设流程全解析

我在伯克利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一共五个任务，覆盖面很清晰：

前两个任务是基础，第三个是性能优化，第四个改变了对对手的建模方式，第五个则是从搜索算法转向“如何定义状态好坏”的特征工程。

很多人觉得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号是Pacman，1号到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方法只需要调用一次value：

def 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 边界条件的处理顺序和返回值

边界条件的顺序很关键。正确顺序是：

1. 先判断是否到达指定深度。
2. 再判断是否终局（win或lose）。
3. 如果以上都不满足，再扩展子节点。

为什么终局判断不能放在最前面？因为深度判定和终局判定其实是并列的终止条件，谁先谁后都行。但有一种情况要注意：如果游戏在搜索中途已经结束，那么再调用getLegalActions就可能出问题。所以比较稳的写法是把“深度到了或终局了”合并成一个判断，提前返回评估值。

返回值方面，叶子节点的值一定来自evaluationFunction(gameState)，而不是gameState.getScore()。虽然scoreEvaluationFunction默认返回的就是getScore()，但你自己设计的betterEvaluationFunction会做更复杂的计算，如果写死成getScore()，后面Q5就废了。

3.3 我见过最多的四种错误

我在帮人调试时，Minimax的错误基本可以归为四类：

第一类：nextDepth永远不加。有人直接用depth + 1作为每次递归的深度，导致“一回合”的概念变成了“一层”。这样搜索树虽然会终止，但深度语义完全错了，Pacman会表现出一种奇怪的短视。

第二类：动作列表没取对。在getAction里，有人直接用gameState.getLegalActions()而不带智能体编号。这个项目里不同智能体的合法动作集是不一样的，必须传0（Pacman）或对应的agentIndex。

第三类：最大值初始值用0。当所有子节点的值都是负数时，用0做初始值会让结果错误。最大值初始值必须用float("-inf")，最小值初始值必须用float("inf")。

第四类：把max和min写反。Pacman是max，幽灵是min。这个看似简单，但状态多的时候容易晕。我一般会在注释里写清楚：agentIndex == 0表示Pacman节点，取max；agentIndex > 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节点，遍历子节点时更新alpha：alpha = max(alpha, childValue)；如果childValue >= beta，立刻剪枝返回。
• 在min节点，遍历子节点时更新beta：beta = 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 v

value函数要把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的适用边界

这两个算法没有绝对的谁优谁劣，关键看你对幽灵行为的建模假设：

我在实际测试中发现，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，你为什么会选这一步？然后去代码里找，哪个特征、哪一层搜索、哪个权重没有体现这个直觉。大多数情况下，问题都会自己浮出来。