吃豆人项目是为加州大学伯克利分校的人工智能入门课程 CS 188 开发的。他们应用了一系列人工智能技术来玩吃豆人。
这些项目使学生能够直观地看到他们所实施的技术的结果。 它们还包含代码示例和明确的说明，但不会强迫学生费力地使用过多的脚手架。 最后，吃豆人提供了一个具有挑战性的问题环境，需要创造性的解决方案； 现实世界的人工智能问题具有挑战性，吃豆人也是如此。
实验介绍 原创网站：The Pac-Man Project
实验文件：下载吃豆人项目 (GitHub)
实验文件组成
下面简单说明一下实验文件的组成和使用方法。
文件名备注
多代理.py
唯一需要写入的文件，所有搜索代理都会在这个文件中
吃豆人.py
运行吃豆人游戏的主文件，包括GameState类等。
游戏.py
该文件实现了吃豆人游戏的运行逻辑，包含AgentState、Agent、Direction、Grid等几个支持类。
实用工具.py
该文件包含实现搜索算法所需的数据结构
幽灵特工.py
该文件控制幽灵的代理
图形显示.py
该文件实现了吃豆人游戏的图形界面
GraphicsUtils.py
该文件提供对吃豆人游戏图形界面的支持
键盘代理.py
该文件实现了通过键盘控制Pac-Man
布局.py
该文件包含读取游戏布局文件并保存布局内容的代码
文本显示.py
该文件为吃豆人游戏提供 ASCII 代码的图形。
打开 multiAgents.py，查看评论的问题 1-4 和大的“您的代码”，您就会知道该怎么做。
运行游戏的方式是：终端
打开终端的方式有无数种，比如用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模仿人类的操作来击败其他玩家。 现实中的很多游戏都符合以下属性：一定数量的玩家、一定的游戏步骤（不像飞棋这样大量的随机事件）、完整的游戏信息、对抗性（零和博弈）。 国际象棋、双陆棋、围棋等游戏都是典型的游戏游戏。 国际象棋虽然有“逼平”的结局，但其本质仍然是“生或死”的对抗性游戏技能特效，因此符合零和游戏的对抗性本质。
对抗性博弈可以粗略地定义为：两个具有完全信息、确定性、在一定规则下轮流进行的博弈者之间的零和博弈。
与过去一些常见的搜索问题如迷宫行走、八皇后、八个数字等不同，博弈问题的解决需要建立博弈树。 与普通搜索问题的搜索树不同，由于有两个玩家，并且每个玩家的动作对游戏状态和另一个玩家的决策都有重要影响，因此搜索树被扩展以反转每个动作。 对象的游戏树。 游戏树同时显示双方玩家的行动空间和利益。
为了更好地理解博弈树，它可以被认为是一种分析对抗性博弈的技术，它决定了玩家为赢得游戏而采取的行动。 在博弈论中，博弈树是一个有向图3D场景，其节点是游戏中的位置（例如，棋盘游戏中棋子的排列），其边是移动（例如，将棋子从棋盘上的一个位置移动到另一个位置） ）。
游戏的完整博弈树是从初始位置开始并包含每个位置的所有可能移动的博弈树； 完整的树与从扩展形式的博弈表示中获得的树是同一棵树。 更具体地说，完整博弈是博弈论中博弈的一个规范。 可以清楚地表达很多重要的方面。 例如，利益相关者可能采取的行动顺序、他们在每个决策点的选择、每个利益相关者做出决策时其他利益相关者采取的行动的信息，以及所有可能的博弈结果的收益。
——博弈树——维基百科
在游戏问题中，游戏搜索树太大，无法使用效率较低的普通搜索算法，例如A*搜索。 在博弈搜索算法中，我们必须学会使用剪枝算法（例如Alpha-beta剪枝）来去除许多未考虑的情况以及使用评价函数（Evaluation function）来估计每一步的评价。
极小极大算法
Minimax算法也称为极小极大算法。 作为对抗性搜索中的一种重要搜索方法，它可以在最大的失败可能性中找到最小值。
自然地，基于我们的AI想要击败其他玩家（或其他AI）的想法游戏开发中的人工智能 源码，我们认为Max是AI的最大利益，Min是玩家的最小利益。
该算法可以简化为以下数学形式：
对于Max层来说，它继承了下一层（Min层）的最大值；
对于Min层来说，它继承了下一层（Max层）的最小值；
直到终点，即游戏结束或人工深度。
因此，很明显Minimax算法是一种悲观博弈搜索。 它认为对手不会犯错误，并且对手会做出对对手最有利的操作（即对AI本身利益最小），因此它假设对手做出操作的集合，然后选择对您最有利的操作。
Minimax算法的搜索过程与DFS类似：
计算过程：
我强烈推荐 Minimax 算法的模拟网站。 尝试自己添加节点和值，一看就明白：
吃豆人 #1 反射器
说了这么多，让我们回到吃豆人。 吃豆人实验的第一个问题是编写一个简单的反射代理来替换原来的反射代理。 我们在 openClassic 布局上进行实验，默认情况下没有墙壁，只有一个幽灵。
运行代码：pacman.py -p ReflexAgent -l openClassic -g DirectionalGhost
我们的目标是：
寻路算法使用最简单的 BFS 来搜索距离吃豆人最近的豆子。
BFS算法原理请参考：数字八题-BFS解法，模板来自acwing-yxc。 值得注意的是，由于直接应用模板，所以没有使用一些面向对象的方法。 例如，判断操作是否合法，可以使用函数提供的getLegalActions方法。 以上代码仅供参考。
通过寻找最近的豆子，你可以在这张没有墙的地图上通过贪婪直接找到局部最优路线。 避鬼的方法也很简单。 计算吃豆人和幽灵之间的曼哈顿距离。 当距离小于等于1时，增加避鬼权重再增加：
在其他距离，你可以直接假装鬼魂不存在。
使用该方法编写的简单智能反射器，运行100次后，胜率100%，平均分1230左右：
吃豆人#2 极小极大
我们来说一下这个实验的难点之一，如何实现Minimax算法。 查找 MinimaxAgent(MultiAgentSearchAgent) 类的问题 2。
Minimax算法的设计可以通过两个函数之间互相调用来实现（上面的伪代码，max_value & min_value）； 它也可以写成一个统一的函数，在其中执行条件分支和递归。 我们选择后者来写。
我们首先想一下Minimax函数需要哪些参数，然后再想一下应该返回什么。 首先我们应该告诉函数当前的游戏状态，gameState。 游戏状态可以提供很多信息如下：
我们还需要告诉函数它正在对谁进行操作。 因为是写成函数的，所以你至少要告诉函数当前是谁在操作，否则函数本身就不知道是应该生成最大值还是最小值。 操作对象是index。
最后有一个参数作为当前深度。 严格来说，这个参数不必写在定义中。 可以在函数中写成局部变量，也可以像我一样写在定义中，方便递归。 当前深度允许函数知道何时停止，而不是无休止地递归搜索。
所以先写出函数的终止条件：
我们来谈谈最后返回什么。
接下来是实现max-min的重头戏。 如果直接用模拟DFS的过程，无疑会太痛苦。 这里我选择维护一个数组valNodes游戏开发中的人工智能 源码，记录了下一层所有节点的评估值（比如当前Pacman层，valNodes记录了Ghost1值的每个动作的评估值）。 我还需要遍历当前操作对象的合法动作，并为每个动作生成对应的后继（其实我们这里说的是同一件事。动作和后继是同一级别的不同数据结构。例如，如果动作是‘左’，则后继者是左走后的游戏状态）。 接下来我们必须向 valNodes 添加下一个级别的值。 怎么做？ 好答案！ 递归。 递归Minimax函数本身（注意参数要改为下一级的参数）可以返回下一级的值。
这可能会引起大家的疑问，Minimax函数到底返回什么？ 是返回评估值还是Pacman的动作？ 最后一段代码回答了这个问题。 如果已经是第一层（最顶层）并且操作对象是Pacman，那么毫无疑问该动作会被返回。 如果递归到下层或者对象不是Pacman，那么返回的值显然就是评估值。 毕竟行动不能用来计算。
如果你精通数据结构查找方法，你会发现这其实是一个DFS过程，只不过每次返回的东西都不一样。
接下来我们看一下算法的效果，使用代码：
python pacman.py -p MinimaxAgent -l minimaxClassic -a 深度=4
你会发现你的代理人有时会失败。 这是完全正常的。 更不用说深度为4的Minimax算法并没有很好的预测结果。 该算法本身具有一定的“自杀倾向”，即当吃豆子的人意识到自己不可避免地会死亡时，由于不断的生存惩罚，它会试图尽快结束游戏。 有时这是与随机性幽灵相关的错误，但 Minimax 代理总是假设最坏的情况，这就是为什么我们说它是“悲观的”。
即便如此，朴素的 Minimax 算法仍然有 60% 到 70% 的胜率。
我们稍后会在Alpha-beta剪枝和评估函数的设计中解决这个问题。
最后附上运行一百次的测试结果（深度为4）：
完整的multiAgents.py代码将在本系列结束后上传
参考文章：
文章来源:https://blog.csdn.net/Pericles_HAT/article/details/116901139
