cs188/proj2/README_CN.md

Project 2: Multi-Agent Pacman 实验报告

本实验旨在通过编写 Pacman 智能体来实践对抗搜索算法（Adversarial Search）。主要涉及 Reflex Agent（反射智能体）、Minimax（极大极小算法）、Alpha-Beta Pruning（Alpha-Beta 剪枝）以及 Expectimax（期望最大算法）和评估函数的设计。

实验环境

• 操作系统: Linux
• 语言: Python 3
• 文件: multiAgents.py (主要修改文件)

---

Q1: Reflex Agent (反射智能体)

任务描述

编写 ReflexAgent 类中的 evaluationFunction 方法。该智能体通过评估当前状态及其后续动作的得分来选择最佳动作。不仅要考虑吃豆子，还要避免碰到幽灵。

实现逻辑

我们在 evaluationFunction 中综合考虑了以下因素：

1. 当前分数 (successorGameState.getScore()): 基础得分。
2. 食物距离: 计算 Pacman 到最近食物的曼哈顿距离。距离越近，得分越高（使用倒数 1.0 / (distance + 1)）。
3. 幽灵距离:
   • 如果幽灵距离过近（小于 2 格）且处于非受惊状态，返回极低分（代表死亡风险）。
   • 如果幽灵处于受惊状态（Scared），则不用过于担心。

核心代码片段

# 计算到最近食物的距离
minFoodDist = min([util.manhattanDistance(newPos, food) for food in foodList])

# 避免幽灵
for i, ghostState in enumerate(newGhostStates):
    # ... (省略部分代码)
    if dist < 2 and newScaredTimes[i] == 0:
        return -999999

return successorGameState.getScore() + 1.0 / (minFoodDist + 1)

---

Q2: Minimax (极大极小算法)

任务描述

在 MinimaxAgent 类中实现 Minimax 算法。该算法假设对手（幽灵）也是最优的，即 Pacman 试图最大化分数，而幽灵试图最小化分数。

知识点讲解

Minimax 算法是一种递归算法，用于在两人零和博弈中找到最优策略。

• MAX 层 (Pacman): 选择能获得最大评估值的动作。
• MIN 层 (Ghosts): 选择会导致最小评估值的动作。
• 深度 (Depth): 搜索树的深度。本实验中，一层（Ply）包含 Pacman 的一步和所有幽灵的一步。

实现细节

我们实现了一个递归函数 minimax(agentIndex, depth, gameState)：

• 终止条件: 达到最大深度 self.depth 或游戏结束（胜/负）。
• Agent 轮转: agentIndex 从 0 (Pacman) 到 numAgents - 1。当 agentIndex 回到 0 时，深度 depth 加 1。
• 状态值传递: 递归向上层传递最优值（Max 或 Min）。

---

Q3: Alpha-Beta Pruning (Alpha-Beta 剪枝)

任务描述

在 AlphaBetaAgent 类中实现带有 Alpha-Beta 剪枝的 Minimax 算法，以提高搜索效率。

知识点讲解

Minimax 算法会搜索整个博弈树，计算量巨大。Alpha-Beta 剪枝通过维护两个值 alpha 和 beta 来忽略那些不需要搜索的分支：

• Alpha (α): MAX 节点目前找到的最好（最大）值的下界。
• Beta (β): MIN 节点目前找到的最好（最小）值的上界。
• 剪枝规则:
  • 在 MAX 节点，如果发现某分支的值 v > beta，则 MIN 父节点绝不会选择该分支（因为父节点已有更小的值 β），故剪枝。
  • 在 MIN 节点，如果发现 v < alpha，则 MAX 父节点绝不会选择该分支，故剪枝。

实现细节

在 alphaBeta 递归函数中增加 alpha 和 beta 参数，并在循环中动态更新它们。注意不要在剪枝时改变节点的访问顺序，以通过 Autograder 的严格检查。

---

Q4 (Optional/Part of Logic): Expectimax (期望最大算法)

虽然任务主要要求 Q1-Q3，但也实现了 Expectimax 以备不时之需。

知识点讲解

Expectimax 假设对手（幽灵）不一定是最优的，而是随机行动。MIN 节点变为 CHANCE 节点，计算所有可能动作的期望值（平均值）。这更符合随机幽灵的行为模式。

---

Q5: Evaluation Function (评估函数)

任务描述

编写 betterEvaluationFunction，用于评估非终止状态的好坏。这是实现高性能智能体的关键。

设计思路

我们需要根据当前状态特征给出一个数值评分，特征及其权重如下：

1. 基础分数: 游戏自带的得分。
2. 食物距离 (权重 +10): 鼓励吃掉最近的食物。
3. 胶囊距离 (权重 +20): 鼓励去吃能量胶囊。
4. 受惊幽灵 (权重 +100): 如果幽灵被吓坏了，鼓励去吃掉它们（距离越近分越高）。
5. 活跃幽灵 (权重 -1000): 如果幽灵正常且距离太近，给予极大的惩罚。
6. 剩余食物数量 (权重 -4): 剩余越少越好。
7. 剩余胶囊数量 (权重 -20): 剩余越少越好。

通过线性组合这些特征，Pacman 能够在复杂的环境中表现出色，既能躲避追捕，又能积极得分。

---

如何运行测试

可以使用 autograder.py 来验证各个问题的实现：

1. 测试 Q1 (Reflex Agent):

   python autograder.py -q q1
   

2. 测试 Q2 (Minimax):

   python autograder.py -q q2
   

3. 测试 Q3 (Alpha-Beta):

   python autograder.py -q q3
   

4. 测试 Q5 (Evaluation Function):

   python autograder.py -q q5
   

如果不希望显示图形界面（加快测试速度），可以添加 --no-graphics 参数。