对抗性搜索

对抗搜索是人工智能的一个子领域，旨在识别在个体或一群具有不同愿望的玩家在游戏、商业等过程中相互制衡的决策过程所涉及的算法和策略。因此，对抗搜索旨在识别玩家的合适走法，并考虑对手可能的反应。

对抗搜索的目的是制定策略，使代理能够在竞争或冲突的局面下选择最有效的行动，并预测对手的行动并预料反制措施。为了确定最佳的下一步走法或决策，大多数对抗搜索算法都会遍历一个定义了所有可能游戏状态及其转换的游戏树。

总的来说，对抗搜索可以被视为一个极具挑战性且充满前景的 AI 研究领域，它需要对博弈论以及决策和优化概念（如混合策略）有深入的了解。它在许多领域都有应用，并且在 AI 的背景下仍然是活跃的研究领域之一。

对抗搜索在 AI 中的重要性

分析对抗搜索概念时，需要注意的是它在人工智能中起着至关重要的作用。有趣的是，它在两个重要领域具有重要意义：

下棋：对抗搜索的一个关键应用领域是游戏。从国际象棋、跳棋到围棋以及复杂视频游戏，AI 代理利用对抗搜索来分析和决定在激烈的比赛中正确的走法。AI 在游戏中的一个有趣应用方面是击败对手的能力。例如，IBM 开发的能够与人类下国际象棋的计算机 Deep Blue，在 1997 年击败了世界国际象棋冠军 Garry Kasparov，这归功于所谓的对抗搜索。

决策制定：除了游戏之外，对抗搜索还应用于任何决策过程。当个体目标不同，并且他们必须找到最优化解决方案时，都可以应用它。它在经济学、机器人学，甚至军事规划和战略等其他领域都有用，因为代理必须根据对手的行动和目标来制定决策。对抗搜索为组织提供了AI 工具和方法论，以解决在复杂、动态、不确定甚至有时充满敌意的环境中的问题。

使用对抗搜索的不同游戏场景

完美信息：完美信息游戏是指代理能够查看整个棋盘的游戏。代理拥有关于游戏的所有信息，并且可以看到彼此的走法。例如国际象棋、跳棋、围棋等。

不完美信息：如果游戏中，代理没有关于游戏的全部信息，也不知道发生了什么，这类游戏就称为不完美信息游戏，例如井字棋、战舰、桥牌等。

确定性游戏：确定性游戏遵循严格的游戏模式和规则，没有任何随机性。例如国际象棋、跳棋、围棋、井字棋等。

非确定性游戏：非确定性游戏包含各种不可预测的事件，并涉及运气或偶然因素。骰子或纸牌引入了这种运气或偶然因素。这些是非随机的，并且每个行动的反应都不是固定的。这类游戏也称为随机游戏。例如双陆棋、大富翁、扑克等。

零和博弈：这是纯粹的竞争性游戏，其中一名玩家的地位提升等于另一名玩家地位的下降。在这些游戏中，每个玩家都有与对手不同的策略，净收益或损失为零。每个人总是试图在游戏情境下获得最大利润或最小化损失。国际象棋和井字棋是零和博弈的例子。

零和博弈：嵌入式思维

零和博弈涉及到嵌入式思维，即一个代理或玩家试图弄清楚

• 要做什么。
• 如何决定走法
• 还需要考虑对手
• 对手也在考虑要做什么
• 每个玩家都在试图找出对手对其行动的反应。这需要嵌入式思维或逆向推理来解决 AI 中的游戏问题。

问题的形式化

游戏可以被定义为 AI 中的一种搜索，涉及以下元素：

• 初始状态：它规定了游戏的初始设置。
• 玩家：它指定了在状态空间中轮到哪个玩家移动。
• 行动：它返回状态空间中的合法走法集合。
• 结果(状态, 行动)：这是转移模型，它指定了状态空间中行动的结果。
• 终止测试(状态)：如果游戏结束，终止测试为真；否则，无论如何都为假。游戏结束的状态称为终止状态。
• 效用(状态, 玩家)：效用函数为在终止状态 s 中结束的游戏为玩家 p 提供最终的数值。它也称为支付函数。对于国际象棋，结果是赢、输或平局，其支付值为 +1、0 和 ½。对于井字棋，效用值为 +1、-1 和 0。

游戏树

游戏树是一棵树，树的节点是游戏状态，边的节点是玩家的走法。游戏树包含初始状态、行动函数和结果函数。

它有几个节点，其中最高的是根节点。每个节点代表游戏的当前位置，后者由节点的边表示。在树的每一层上，两个玩家（称为最大化者和最小化者）的尝试是轮流进行的。最小化者会保留损失并最小化最大损失量，而最大化者会增加最小收益量。根据游戏的背景和其他玩家的走法，玩家会成为最大化者或最小化者。

示例：井字棋游戏树

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

• 有两个玩家，MAX 和 MIN。
• 玩家轮流进行，MAX 先开始。
• MAX 最大化游戏树的结果
• MIN 最小化结果。

示例说明

• 从初始状态开始，MAX 有九种可能的走法，因为它先开始。MAX 放置“X”，MIN 放置“O”，两个玩家轮流进行，直到达到一个叶子节点，其中一个玩家连成三子或所有方格都已填满。
• 两个玩家都将计算每个节点， minimax，minimax 值是针对最优对手可达到的最佳效用。
• 假设两个玩家都对井字棋了如指掌，并且正在尽力玩。每个玩家都尽最大努力阻止另一个玩家获胜。MIN 在游戏中扮演 MAX 的对手。
• 因此，在游戏树中，我们有 MAX 的一层和 MIN 的一层，每一层称为 Ply。MAX 放置“X”，然后 MIN 放置“O”以阻止 MAX 获胜，游戏一直持续到终止节点。
• 这是 MIN 获胜、MAX 获胜或平局的情况。这个游戏树是 MIN 和 MAX 玩井字棋并交替回合的所有可能性的搜索空间。

对抗搜索中的 Minimax 算法

它是对抗搜索中最核心的思想之一，因为它最适合两人游戏。它有助于决策，因为它假设每个玩家都在做出最佳决策。该算法的作用是确定在考虑的最坏情况下的最小损失量。

• 游戏树构建：该算法构建一个游戏树，其中节点表示游戏状态，边表示可能的走法。
• 最大化者和最小化者：该算法在两个玩家之间交替进行：最大化者试图最大化得分，最小化者试图最小化得分。
• 评估：在树的终止节点，效用函数评估游戏的结果。该算法从这些终止节点回溯，以确定当前玩家的最佳走法。

Alpha-Beta 剪枝简介

Alpha-Beta 剪枝是 Minimax 算法的一种搜索优化方法，有助于消除游戏树中的大部分节点。它通过移除所谓的“子树”（这些子树不需要进一步检查，因为它们下面的任何路径都无法使一个选择优于另一个）来优化算法。

• Alpha 和 Beta 值：Alpha 是对该级别及以上级别最大化者来说是最佳的值，而 Beta 是最小化者在该级别及以上级别可以提供的最佳值。
• 剪枝：如果一个节点的值小于 alpha 或 Beta，则无需继续评估该节点的后继节点，搜索将被剪枝。
• 速度：通过减少扩展的节点数量，Alpha-Beta 剪枝能够比简单的 Minimax 算法更快地找到最优解。

Alpha-Beta 剪枝如何减少节点探索？

Alpha-Beta 剪枝通过不扩展对结果没有影响的节点，大大限制了游戏树的使用。

• 提前终止：可以尽早剪除那些永远不会影响最终结果的分支，以节省不必要的计算。
• 降低复杂性：在许多情况下，搜索过程的复杂性从指数级降低到多项式级，从而提高了性能。
• 最优决策：尽管 Alpha-Beta 剪枝涉及删除某些节点，但仍然可以做出最优决策，因为只省略了不必要的计算。

对抗搜索在游戏之外的现实世界应用

因此，需要强调的是，Minimax 和 Alpha-Beta 剪枝不一定仅限于游戏，而是有更广泛的用途。

• 战略规划：这种规划在任何需要战略决策的地方都至关重要，例如军事或资源配置。
• 机器人学：可用于机器人领域，在竞争性领域进行路径规划和决策。
• 经济学：用于模型中，其中代理或参与者为资源或市场份额而斗争。
• 网络安全：应用于对抗场景，例如威胁检测和针对网络攻击的缓解策略。

对抗搜索的重要特征

对抗搜索是人工智能的一个重要领域。这是关于在敌对环境中做出决策。以下是对抗搜索的一些主要方面：

完美信息或不完美信息

在游戏中，玩家可以访问的信息主要有两种类别：完美信息和不完美信息。在完美信息游戏中，玩家都完全了解比赛的当前状态。然而，在不完美信息游戏中，玩家无法获得所有详细信息。

对抗搜索算法

在像国际象棋这样的任何竞技游戏中，参赛者都可以使用一种称为 min-max 策略或 alpha-beta 剪枝的技术来了解最佳走法。此类算法计算每次移动的可能结果，并提供提示，说明哪种平台适合玩家。

经验法则

树可能会变得非常大，因此可能无法完成对树的完整搜索。在这种情况下，算法使用启发式方法，即快捷规则，使其能够更快地遍历游戏树，跳过对所有可能走法的评估。这些小规则可以在不实际遍历整个游戏树的情况下，给出最佳走法的思路。

对抗搜索中的挑战

对抗搜索存在几个缺点：

计算复杂性

• 指数增长：问题还在于，随着移动次数的增加，游戏树的总大小也会增加，并且可能在实践中无法完成。
• 内存使用：它还有一个缺点，即需要大量内存来存储大型游戏树。

启发式评估

• 准确性：人们发现，即使设计了合适的启发式评估函数，它也可能无法真正反映真实的游戏状况。
• 可扩展性：特别是，启发式函数可能不太适合大型问题和复杂的问题空间。

对手建模

• 不可预测性：通常，很难对对手的行动进行建模和预测，尤其是在对手在复杂环境中运行时。
• 适应性：如果必须应对对手的打法，那么它会变得更具挑战性，因为这必须是实时进行的。

实时决策制定

• 时间限制：在广阔的搜索空间中进行实时决策可能非常困难，这取决于做出决策所需的时间，而这些问题又因时间相关的因素而加剧。
• 最优性与速度：因此，同时做出最佳决策并利用时间将是一个巨大的挑战。

结论

对抗搜索是人工智能中的一项基本技术，它在解决游戏和其他关键决策过程方面发挥了作用。AI 规划因此提供了一种系统有效的方式来与环境互动并在竞争场景中做出选择，同时预估对手的计划。从最基础的 minimax 算法到 alpha-beta 剪枝和启发式评估，由于高分支因子、视界效应和有限的计算能力，对抗搜索已经取得了长足的进步。