对抗性搜索

对抗搜索是一种搜索，当我们尝试提前计划而其他代理针对我们进行计划时，我们会检查出现的问题。

• 在之前的主题中，我们研究了仅与单个代理相关联的搜索策略，旨在找到通常以一系列动作的形式表示的解决方案。

• 但是，可能存在多个智能体在同一个搜索空间中搜索解决方案的情况，这种情况通常发生在游戏中。

• 具有多个智能体的环境称为多智能体环境，其中每个智能体都是其他智能体的对手并相互对抗。每个智能体都需要考虑其他智能体的动作以及该动作对其性能的影响。

• 因此，两个或多个目标冲突的玩家试图探索相同的搜索空间以获取解决方案的搜索称为对抗性搜索，通常称为游戏。

• 游戏被建模为搜索问题和启发式评估函数，这是帮助在 AI 中建模和解决游戏的两个主要因素。

AI中的游戏类型：

• 完美信息：具有完美信息的游戏是代理可以查看完整版块的游戏。代理拥有有关游戏的所有信息，并且他们也可以看到彼此的动作。例如国际象棋、跳棋、围棋等。

• 不完全信息：如果在游戏中智能体没有关于游戏的所有信息并且不知道发生了什么，这种类型的游戏被称为不完全信息游戏，例如井字游戏、战舰、盲人、桥牌、等等。

• 确定性游戏：确定性游戏是那些遵循严格的游戏模式和规则的游戏，并且没有与之相关的随机性。例如国际象棋、跳棋、围棋、井字棋等。

• 非确定性游戏：非确定性是那些具有各种不可预测事件并具有机会或运气因素的游戏。这种机会或运气因素是由骰子或卡片引入的。这些是随机的，每个动作的反应都是不固定的。此类博弈也称为随机博弈。
  例如：西洋双陆棋、大富翁、扑克等。

注意：在本主题中，我们将讨论确定性博弈、完全可观察的环境、零和以及每个代理的交替行为。

零和博弈

• 零和博弈是对抗性搜索，涉及纯竞争。

• 在零和博弈中，每个代理人的效用收益或损失与另一个代理人的效用损失或收益完全平衡。

• 游戏中的一名玩家试图最大化一个单一值，而另一名玩家试图将其最小化。

• 游戏中一个玩家的每一步都称为 ply。

• 国际象棋和井字棋是零和游戏的例子。

零和游戏：嵌入式思维

零和游戏涉及嵌入式思维，其中一个代理或玩家试图弄清楚：

• 该怎么办。

• 如何决定搬家

• 也需要考虑他的对手

• 对手也想怎么办

每个玩家都试图找出对手对其行为的反应。这需要嵌入式思维或反向推理来解决 AI 中的游戏问题。

问题的形式化：

游戏可以定义为人工智能中的一种搜索，它可以由以下元素形式化：

• 初始状态：它指定游戏在开始时的设置方式。

• Player(s)：它指定哪个玩家在状态空间中移动。

• Action(s)：它返回状态空间中的合法移动集。

• Result(s, a)：它是转移模型，它指定了状态空间中移动的结果。

• 终端测试：如果游戏结束，终端测试为真，否则为假。游戏结束的状态称为终结状态。

• 效用(s, p)：效用函数给出以玩家 p 的终端状态 s 结束的游戏的最终数值。它也称为支付函数。对于国际象棋，结果是赢、输或平，其收益值为 +1、0、½。对于井字游戏，效用值为 +1、-1 和 0。

游戏树：

游戏树是一棵树，其中树的节点是游戏状态，树的边是玩家的移动。博弈树涉及初始状态、动作函数和结果函数。

示例：井字游戏树：

下图显示了井字棋游戏的游戏树的一部分。以下是游戏的一些关键点：

• 有两个玩家 MAX 和 MIN。

• 玩家有一个交替的回合并从 MAX 开始。

• MAX最大化博弈树的结果

• MIN 最小化结果。

示例说明：

• 从初始状态开始，MAX 有 9 种可能的走法。MAX 位置 x 和 MIN 位置 o，两个玩家交替玩，直到我们到达叶节点，其中一个玩家连续三个或所有方块都被填满。

• 两个玩家都将计算每个节点，minimax，minimax 值，这是对抗最佳对手的最佳可实现效用。

• 假设两个玩家都非常了解井字游戏并玩出最好的游戏。每个玩家都在尽最大努力阻止另一个玩家获胜。MIN 在游戏中与 Max 对抗。

• 所以在博弈树中，我们有一层 Max，一层 MIN，每一层都称为Ply。Max 放置 x，然后 MIN 放置 o 以防止 Max 获胜，这个游戏一直持续到终端节点。

• 在这种情况下，要么 MIN 获胜，要么 MAX 获胜，要么是平局。这个博弈树是 MIN 和 MAX 轮流玩井字游戏的可能性的整个搜索空间。

因此，对极小极大过程的对抗性搜索的工作原理如下：

• 它旨在为 MAX 找到赢得比赛的最佳策略。

• 它遵循深度优先搜索的方法。

• 在博弈树中，最优叶节点可以出现在树的任何深度。

• 将极大极小值传播到树，直到发现终端节点。

在给定的博弈树中，可以从每个节点的极大极小值确定最优策略，可以写成 MINIMAX(n)。MAX 更喜欢移动到最大值的状态，而 MIN 更喜欢移动到最小值的状态，然后：