AI Adversarial搜索
专家搜索是一种搜索，我们在其中研究尝试超前计划而其他代理商也计划与我们对抗时出现的问题。
在先前的主题中，我们研究了仅与单个代理相关联的搜索策略，该代理旨在查找通常以一系列动作形式表示的解决方案。
但是，在某些情况下，可能会有多个代理在同一搜索空间中搜索解决方案，这种情况通常发生在游戏中。
具有多个代理的环境称为多代理环境，其中每个代理都是其他代理的对手并相互竞争。每个代理都需要考虑其他代理的行为以及该行为对其绩效的影响。
因此，其中两个或两个以上目标相互冲突的玩家试图为解决方案探索相同搜索空间的搜索称为对抗搜索，通常称为"游戏"。
游戏被建模为搜索问题和启发式评估功能，这是有助于在AI中建模和解决游戏的两个主要因素。
完美的信息: 具有完美信息的游戏是代理商可以查看整个面板。特工拥有有关游戏的所有信息，并且他们也可以看到彼此的动作。例如国际象棋，跳棋，围棋等。
不完美的信息: 如果在游戏中代理商没有掌握有关游戏的所有信息并且不知道发生了什么，则此类游戏称为信息不完善的游戏，例如tic-脚趾，战舰，盲人，桥梁等。
确定性游戏: 确定性游戏是那些遵循严格的游戏规则和规则并没有随机性的游戏。例如国际象棋，跳棋，围棋，井字游戏等。
不确定性游戏: 不确定性是指那些发生各种不可预测事件并具有机会或运气因素的游戏。骰子或纸牌会引入这种机会或运气因素。这些是随机的，每个动作的响应都不是固定的。此类游戏也称为随机游戏。
示例: 西洋双陆棋，大富翁，扑克等。
注意: 在本主题中，我们将讨论确定性博弈，完全可观察的环境，零和以及每个代理交替执行的操作。
零和游戏
零和游戏是一种对抗性搜索，涉及纯粹的竞争。
在零和博弈中，每个代理的效用得失与另一代理的效用得失完全平衡。
游戏中的一个玩家尝试最大化一个单一值，而其他玩家尝试最小化一个值。
游戏中一位玩家的每步动作称为合股。
国际象棋和井字游戏是零和游戏的例子。
零和游戏: 嵌入式思维
零和游戏涉及一种嵌入式思维，其中一个特工或参与者试图弄清楚:
该怎么办。
如何决定举动
也需要考虑他的对手
对手也想做什么
每个玩家都在尝试找出对手对其动作的反应。这需要嵌入式思维或后向推理来解决AI中的游戏问题。
问题的形式化:
可以将游戏定义为AI中的一种搜索类型，可以将以下元素形式化:
初始状态: 它指定游戏一开始的设置方式。
玩家: : 它指定哪个玩家在状态空间中移动。
操作: 它返回状态空间中的合法移动集。
结果(s，a): 它是过渡模型，用于指定状态空间中移动的结果。
终端测试: 如果游戏结束，则终端测试为true，否则无论如何都为false。游戏结束的状态称为终端状态。
实用程序(s，p): 实用程序功能为游戏提供最终值，该游戏的最终结果以玩家p的终端状态s结束。也称为支付功能。对于国际象棋来说，结果是赢，输或平，其收益值为+ 1、0、1/2、对于井字游戏，实用程序值为+ 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玩井字游戏并交替轮流玩的可能性的整个搜索空间。
因此，对抗性搜索maxmax过程的过程如下:
旨在寻找MAX赢得比赛的最佳策略。
它遵循深度优先搜索的方法。
在游戏树中，最佳叶子节点可以出现在树的任何深度。
将minimax值传播到树，直到发现终端节点。
在给定的游戏树中，可以根据每个节点的minimax值确定最佳策略，可以将其写为MINIMAX(n)。然后，MAX希望移至最大值状态，而MIN希望移至最小值状态:
