吃豆人实验（The Pac-Man Project）简介

The Pac-Man projects were developed for UC Berkeley’s introductory artificial intelligence course, CS 188. They apply an array of AI techniques to playing Pac-Man.
The projects allow students to visualize the results of the techniques they implement. They also contain code examples and clear directions, but do not force students to wade through undue amounts of scaffolding. Finally, Pac-Man provides a challenging problem environment that demands creative solutions; real-world AI problems are challenging, and Pac-Man is too.

• 吃豆人实验（The Pac-Man Project）是由加利福利亚大学伯克利分校的 John DeNero 和 Dan Klein 设计并开源给学习者使用。实验的初衷是使学生能在有趣的图形化可视化游戏界面中编写他们的AI。

• 如果你去Google本实验，你会发现本实验还包括两个前置任务：设计基本游戏逻辑和实现简单的走迷宫搜索（如BFS、DFS、A star等）。然而本实验将不聚焦于游戏主体（图形界面和游戏逻辑）的设计，毕竟这是人工智能导论（ Introduction to Artificial Intelligence）的课程实验而不是Python程序设计或者游戏设计的课程，我们将仅仅聚焦于吃豆人本身的智能反射体的设计和编写。

• 本实验包括四个部分：

  1. Reflex Agent
  2. Minimax
  3. Alpha-Beta Pruning
  4. Evaluation Function

• 本实验基于Python编写。

实验简介原址：The Pac-Man Project
实验文件：Download The Pac-Man Project （GitHub）

---

实验文件组成

下面简单讲解一下实验文件组成和用法。

文件名称	备注
multiAgents.py	唯一需要编写的文件，所有的搜索智能体都将在此文件中
pacman.py	运行吃豆人游戏的主文件，包含了GameState类等
game.py	该文件实现了吃豆人游戏的运行逻辑，包含了像AgentState，Agent，Direction，Grid等几个起到支持作用的类
util.py	该文件包含了实现搜索算法需要的数据结构
ghostAgents.py	该文件控制幽灵的智能体
graphicsDisplay.py	该文件实现吃豆人游戏的图形界面
graphicsUtils.py	该文件为吃豆人游戏的图形界面提供支持
keyboardAgents.py	该文件实现通过键盘控制吃豆人
layout.py	该文件包含了读取游戏布局文件和保存布局内容的代码
textDisplay.py	该文件为吃豆人游戏提供ASCII码形式展现的图形

打开multiAgents.py，看到注释的question1 - 4和大大的YOUR CODE HERE就知道该怎么做了。

运行游戏的方法是：终端

你有无数种方法打开终端，比如用Pycharm或者Vscode打开文件夹，直接用底下的终端。如果你是Mac/Linux用户还可以直接终端cd进入这个文件夹。

输入 python pacman.py -h 以查看所有运行命令的帮助：

在这里列举几个常用的命令：

python pacman.py // 开始游戏
python pacman.py -p ReflexAgent // 简单的反射智能体
python pacman.py -p ReflexAgent -l openClassic // 在开放布局测试反射智能体
......

默认情况下幽灵位置随机；为了获得乐趣，你可以使用命令 -g DirectionalGhost 使游戏中的幽灵更聪明和有方向性；你也可以通过命令 -n 来让游戏运行多次；使用命令 -q 关闭图形化界面使游戏更快运行；用–frameTime 0加速游戏画面。

看来我们已经了解了整个Pacman实验的操作方法，就让我们开始吧。

---

对抗搜索（博弈搜索）

我们设计游戏AI的初衷是让AI模仿人的操作去击败其他玩家。在现实的许多游戏都符合以下的性质：有确定的玩家数目，有确定的游戏步骤（不像飞行棋那样有大量随机事件），有完整的游戏信息，具有对抗性（零和游戏）。象棋、五子棋、围棋等游戏就是典型的博弈游戏，尽管象棋有“逼和”这一种结局，但是其本质仍是一种“你死我活”的对抗游戏，故符合零和游戏的对抗性质。

对抗性博弈可以粗略地定义如下： 一定规则下，具有完备信息的、确定的、轮流行动的、两个游戏者的零和游戏

区别于以往的一些类似于走迷宫、八皇后、八数码等普通搜索问题，博弈问题的解决需要建立博弈树（Game Tree）。不同于普通搜索问题的搜索树，由于有两个游戏者，而每一个游戏者的行动都对游戏状态和另一位游戏者的决策起到重要影响，因此搜索树扩展成每一行动都对调对象的博弈树。博弈树同时展示了对于两个游戏者的行动空间和利益。

To better understand the game tree, it can be thoughts of as a technique for analyzing adversarial games, which determine the actions that player takes to win the game. In game theory, a game tree is a directed graph whose nodes are positions in a game (eg, the arrangement of the pieces in a board game) and whose edges are moves (eg, to move pieces from one position on a board to another).
The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation. To be more specific, the complete game is a norm for the game in game theory. Which can clearly express many important aspects. For example, the sequence of actions that stakeholders may take, their choices at each decision point, information about actions taken by other stakeholders when each stakeholder makes a decision, and the benefits of all possible game results.
——Game tree - Wikipedia

在博弈问题中，博弈搜索树实在太大，无法使用较低效率的普通搜索算法如A*搜索。在博弈搜索的算法中，我们要学会使用剪枝算法（如Alpha-beta剪枝）去除很多不考虑的情况和评估函数（Evaluation function）来估计每一步的评价。

Minimax算法

Minimax算法又称极小化极大算法。作为对抗搜索中的重要搜索方法，它可以找出失败的最大可能性中的最小值。

自然地，本着我们AI要去击败其他玩家（或其他AI）的想法，我们考虑Max作为AI的最大利益，Min作为Player的最小利益。

算法可以简单化为以下数学形式：

对于Max层，它继承下一层（Min层）的最大值；
对于Min层，它继承下一层（Max层）的最小值；
直到端点为止，端点是游戏结局或者是人为设置的深度。

因此，很显然，Minimax算法是一种悲观的博弈搜索，它认为对手不会犯错，对手会做出对于对手而言的最大利益操作（即对于AI自己的最小利益），因此它假设了一个对手做出的操作集合，然后选出了其中对于自己的最大利益操作。
Minimax算法的搜索过程类似于DFS：

计算过程：

在此强烈推荐一个Minimax算法的模拟网站，自己试试添加节点和值，一看便懂：Minimax Simulator

---

Pac-Man #1 反射体

说了这么多，我们来回归吃豆人吧。吃豆人实验第一题是写一个简单的Reflex Agent替代原有的。我们在openClassic布局上进行实验，默认情况下没有墙，只有一个幽灵。

运行代码：pacman.py -p ReflexAgent -l openClassic -g DirectionalGhost

我们的目标是：

• 用寻路算法吃掉所有豆子
• 躲避幽灵
• 尽可能高分

寻路算法采用最简单的BFS，搜索距离吃豆人最近的豆子

BFS算法原理可以参考：八数码难题-BFS解决，模板来自acwing-yxc。值得注意的是因为直接套用了模板没有采用面向对象的一些方法，比如判断操作是否合法完全可以采用函数提供的 getLegalActions 方法，以上代码仅供参考。

通过找到最近的豆子，在这种没有墙的地图直接通过贪心来找局部最优路线即可。躲避幽灵的方法也很简单，计算吃豆人和幽灵的曼哈顿距离，当距离小于等于1时，将躲避幽灵的权重加大加大再加大即可：

其他距离下，直接可以当幽灵不存在。

利用本方法写出来的简单智能反射体，运行一百次的胜率为100%，平均得分大约1230：

Pac-Man #2 Minimax

下面来讲讲本次实验的难点之一，如何实现Minimax算法。找到 class MinimaxAgent(MultiAgentSearchAgent) 的question 2处。

设计Minimax算法的可以通过两个函数（如上的伪代码，max_value & min_value）的互相调用实现；也可以统一写成一个函数，其中进行条件分支和递归。我们选择后者来编写。

先让我们想想Minimax函数需要什么样的参数，然后再想想应该返回什么样的东西。首先我们应该告诉函数当前游戏的状态gameState，游戏状态能提供大量信息如下注释：

我们还要告诉函数操作对象是谁。因为统一写成了一个函数，因此至少要告诉函数目前实在操作谁，不然函数自己都不知道应该生成最大值还是最小值。操作对象就是index。

最后还有一个参数作为当前深度。这个参数严格意义上并不算是必需写在定义中的，你可以写成函数中的局部变量，也可以像我一样写在定义上方便递归。当前深度能让函数知道什么时候停止而不是无止尽地递归搜索下去。

因此先写出函数的终止条件：

返回什么东西我们最后讲。

接下来是实现max-min的重头戏了。如果直接采用模拟DFS的过程无疑会过于痛苦，这里我选择维护一个数组valNodes，该数组记录了下一层所有节点的评价值（如当前是Pacman层，则valNodes记录了Ghost1的每种行动的评价值）。我还需要遍历当前操作对象的合法actions，对每个action生成对应的successor（这里实际上是在说同一件事，action和succeesor是同级别的不同数据结构，比如action是’Left‘，则successor是向左走后的游戏状态）。紧接着我们就要往valNodes里添加下一层的值了，怎么操作呢？答得好！递归。递归Minimax函数本身（注意参数要改成下一层的）可以返回下一层的值。

这里可能会引起大家的疑惑，Minimax函数到底返回的是什么东西？是返回评价值还是Pacman的action？最后一段代码解答了这个疑惑。如果当前已经是第一层（最上面）且操作对象是Pacman，毫无疑问返回的就是action。如果是递归到了底下的层或者对象不为Pacman，那返回的显然是评价值，毕竟action不能用来计算。

如果你精通数据结构的搜索方法，你会发现这其实还是个DFS过程，只不过每次返回的东西有差异。

接下来我们来看看算法的效果，使用代码：
python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4

你会发现你的智能体有时候会输，这是完全正常的情况，先不说深度为4的Minimax算法本身预测结果并不好，算法本身就有一定的“自杀倾向”，即当吃豆人发现它将不可避免地死亡时，它会尝试尽快结束游戏因为不断的存活罚分。有时候，这个是跟随机幽灵有关的错误做法，但Minimax智能体一直都假定最坏情况，这就是我们为什么说它是“悲观的”。

即使这样，朴素Minimax算法仍然会有六七成的胜率。

这个问题我们将在后面的Alpha-beta剪枝和评估函数设计中解决。

最后附上运行一百次的测试结果（深度为4）：

完整multiAgents.py代码会在这个系列完结后上传

---

参考文章：
https://en.wikipedia.org/wiki/Minimax
http://ai.berkeley.edu/multiagent.html