对抗性搜索

对抗性搜索是一种搜索，在此检查当尝试在世界范围内进行计划而其他代理正在计划针对
时出现的问题。

• 在之前的主题中，我们研究仅与单个代理相关联的搜索策略，该代理旨在找到通常以一系列动作的形式表达的解决方案。
• 但是，可能存在多个代理在同一搜索空间中搜索解决方案的情况，这种情况通常发生在游戏中。
• 具有多个代理的环境被称为多代理环境，其中每个代理是其他代理的对手并且彼此竞争。每个代理都需要考虑其他代理的操作以及该操作对其性能的影响。
• 因此，搜索两个或更多具有相互冲突目标的玩家试图探索解决方案的相同搜索空间的搜索称为对抗搜索，通常称为游戏。
• 游戏被建模为搜索问题和启发式评估功能，这些是有助于在AI中建模和解决游戏的两个主要因素。

AI中的游戏类型

• 完美信息：拥有完美信息的游戏是代理可以查看整个电路板的游戏。代理商拥有关于游戏的所有信息，他们也可以看到彼此的动作。例如Chess，Checkers，Go等。
• 不完美的信息：如果在游戏中代理商没有关于游戏的所有信息并且不知道正在发生什么，这种类型的游戏被称为具有不完全信息的游戏，例如井字游戏，战舰，盲人，桥，等等
• 确定性游戏：确定性游戏是那些遵循严格模式和游戏规则的游戏，并且没有与之相关的随机性。例如国际象棋，Checkers，Go，tic-tac-toe等。
• 非确定性游戏：非确定性游戏是那些具有各种不可预测事件且具有机会或运气因素的游戏。这个机会或运气因素是由骰子或卡片引入的。这些是随机的，每个动作响应都不是固定的。这种游戏也被称为随机游戏。
  示例：步步高，垄断，扑克等

注意：在本主题中，将讨论确定性游戏，完全可观察的环境，零和，以及每个代理交替行动的位置。

零和博弈

• 零和游戏是对抗性搜索，涉及纯粹的竞争。
• 在零和游戏中，每个代理人的效用收益或损失都与另一个代理人的效用损失或收益完全平衡。
• 游戏中的一个玩家尝试最大化单个值，而其他玩家尝试最小化它。
• 游戏中一个玩家的每次移动都被称为ply。
• Chess和tic-tac-toe是零和游戏的例子。

零和游戏：嵌入式思维

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

• 该怎么办。
• 如何决定行动
• 需要考虑他的对手
• 对手也认为该怎么做

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

问题正式化

游戏可以定义为AI中的一种搜索，可以通过以下元素形式化：

• 初始状态：它指定游戏在开始时的设置方式。
• Player(s)：它指定哪个玩家在州空间中移动。
• Action(s)：它返回状态空间中的合法移动集。
• Result(s，a)：它是转换模型，它指定状态空间中移动的结果。
• 终端测试：如果游戏结束，终端测试为真，否则无论如何都是假的。游戏结束的状态称为终端状态。
• Utility(s，p)：效用函数给出游戏的最终数值，该游戏以玩家p的终端状态s结束。它也被称为支付功能。对于国际象棋，结果是胜利，损失或平局，其支付值为+1,0，½。对于井字游戏，效用值为 +1，-1和0。

游戏树

游戏树是树的节点是游戏状态的树，树的边缘是玩家的移动。游戏树涉及初始状态，动作功能和结果功能。

示例：Tic-Tac-Toe游戏树：
下图显示了tic-tac-toe游戏的游戏树的一部分。以下是游戏的一些关键点：

• 有两个玩家MAX和MIN。
• 玩家有另一个转弯，从MAX开始。
• MAX最大化游戏树的结果
• MIN最小化结果。

示例说明：

• 从初始状态开始，MAX首先开始时有9次可能的移动。MAX放置x和MIN位置o，两个玩家交替播放，直到我们到达一个叶子节点，其中一个玩家连续三个或所有方格都被填充。
• 两个玩家都将计算每个节点，minimax，minimax值，这是针对最佳对手的最佳可实现效用。
• 假设两位球员都非常了解井字游戏并且发挥出最好的发挥。每个球员都在尽力防止另一个球员获胜。MIN在比赛中对阵Max。
• 所以在游戏树中，有一层Max，一层MIN，每层都称为Ply。最大位置x，然后MIN放置o以防止Max获胜，并且此游戏继续直到终端节点。
• 在这里MIN赢，MAX赢，或者是平局。这个游戏树是MIN和MAX正在玩tic-tac-toe和轮流交替的可能性的整个搜索空间。

因此，对抗极小极大程序的搜索工作如下：

• 它旨在找到MAX赢得比赛的最佳策略。
• 它遵循深度优先搜索的方法。
• 在游戏树中，最佳叶节点可以出现在树的任何深度。
• 将minimax值传播到树，直到发现终端节点。

在给定的游戏树中，可以根据每个节点的最小极大值来确定最优策略，其可以写为MINIMAX(n)。MAX更喜欢移动到最大值状态，MIN更喜欢移动到最小值状态，然后：