Alpha-Beta 剪枝

Alpha-Beta 剪枝是 Minimax 算法的改进版本。它是 Minimax 算法的一种优化技术。

正如我们在 Minimax 搜索算法中所看到的，它必须检查的游戏状态数量是树深度的指数级增长。由于我们无法消除指数，我们可以将其减半。因此，存在一种技术，通过该技术，我们可以在不检查游戏树的每个节点的情况下，计算出正确的 Minimax 决策，这种技术称为剪枝。它涉及两个未来扩展的阈值参数，Alpha 和 Beta，因此称为 Alpha-Beta 剪枝。它也称为 Alpha-Beta 算法。

Alpha-Beta 剪枝可以应用于树的任何深度，并且有时它不仅影响树叶，还会影响整个子树。这两个参数可以定义为：

1. Alpha： 在 Maximiser 的路径上的任何一点，我们迄今为止找到的最佳（最高值）选择。Alpha 的初始值为 -∞。
2. Beta： 在 Minimiser 的路径上的任何一点，我们迄今为止找到的最佳（最低值）选择。Beta 的初始值为 +∞。

Alpha-Beta 剪枝对标准 Minimax 算法返回的移动与标准算法相同，但它会删除所有不真正影响最终决策的节点，从而使算法变慢。因此，通过剪枝这些节点，它使算法更快。

注意：为了更好地理解这个主题，请学习 Minimax 算法。

Alpha-Beta 剪枝的条件

Alpha-Beta 剪枝需要的主要条件是

α>=β

Alpha-Beta 剪枝的关键点

• Max 玩家只会更新 alpha 的值。
• Min 玩家只会更新 beta 的值。
• 在回溯树时，节点值将被传递给上层节点，而不是 alpha 和 beta 的值。
• 我们只会将 alpha 和 beta 值传递给子节点。

Alpha-Beta 剪枝的伪代码

Alpha-Beta 剪枝的工作原理

让我们以一个双人搜索树的例子来理解 Alpha-Beta 剪枝的工作原理

步骤 1： 在第一步，Max 玩家将从节点 A 开始第一步，其中 α= -∞ 且 β= +∞；这些 alpha 和 beta 值将传递给节点 B，其中 α= -∞ 且 β= +∞，节点 B 将相同的值传递给其子节点 D。

步骤 2： 在节点 D，α 的值将根据其 Max 的回合进行计算。α 的值首先与 2 比较，然后与 3 比较，max (2, 3) = 3 将是节点 D 的 α 值，节点值也将是 3。

步骤 3： 现在算法回溯到节点 B，其中 β 的值将发生变化，因为这是 Min 的回合。现在 β= +∞ 将与可用的后续节点值进行比较，即 min (∞, 3) = 3，因此在节点 B，现在 α= -∞，β= 3。

在下一步，算法将遍历节点 B 的下一个后继节点，即节点 E，并且 α= -∞ 和 β= 3 的值也将被传递。

步骤 4： 在节点 E，Max 将轮到它，α 的值将发生变化。当前 α 的值将与 5 比较，因此 max (−∞, 5) = 5，因此在节点 E 处 α = 5 且 β = 3，其中 α>=β，因此 E 的右后继节点将被剪枝，算法将不会遍历它，节点 E 的值将是 5。

步骤 5： 在下一步，算法再次从节点 B 回溯到节点 A。在节点 A，alpha 的值将被更改为 3 的可用最大值，因为 max (-∞, 3)= 3，并且 β= +∞；这两个值现在传递给 A 的右后继节点，即节点 C。

在节点 C，α=3 且 β= +∞，并且相同的值将传递给节点 F。

步骤 6： 在节点 F，α 的值将再次与左子节点 0 进行比较，max(3,0)= 3，然后与右子节点 1 进行比较，max(3,1)= 3，α 仍然是 3，但 F 的节点值将变为 1。

步骤 7： 节点 F 将节点值 1 返回到节点 C，在 C 处 α = 3 且 β = +∞；在这里，β 的值将发生变化，它将与 1 进行比较，所以 min (∞, 1) = 1。现在在 C 处，α = 3 且 β = 1，并且再次满足条件 α>=β，因此 C 的下一个子节点 G 将被剪枝，算法将不会计算 G 的整个子树。

步骤 8： C 现在将值 1 返回给 A。在这里，A 的最佳值是 max (3, 1) = 3。以下是最终的游戏树，显示了已计算的节点和从未计算过的节点。因此，对于这个例子，最大化器的最优值是 3。

Alpha-Beta 剪枝中的移动排序

Alpha-Beta 剪枝的有效性高度依赖于检查每个节点的顺序。移动顺序是 Alpha-Beta 剪枝的一个重要方面。

它可以是两种类型

1. 最坏的排序： 在某些情况下，Alpha-Beta 剪枝算法不会剪枝树的任何叶子，并且其工作方式与 Minimax 算法完全相同。在这种情况下，由于 Alpha-Beta 因素（例如剪枝移动），它还会消耗更多时间，这称为最坏的排序。在这种情况下，最佳移动发生在树的右侧。这种排序的时间复杂度为 O(bm)。
2. 理想排序： Alpha-Beta 剪枝的理想排序发生在树中有大量剪枝，并且最佳移动发生在树的左侧时。我们应用DFS。因此，它首先搜索树的左侧，并在相同的时间内深入两次，就像 Minimax 算法那样。理想排序中的复杂度为 O(bm/2)。

查找良好排序的规则

以下是查找 Alpha-Beta 剪枝中良好排序的一些规则：

• 最佳移动出现在最浅的节点。
• 对树中的节点进行排序，以便首先检查最佳节点。
• 在查找最佳移动时使用领域知识。例如：对于国际象棋，尝试排序：先吃子，然后是威胁，然后是前进的移动，后退的移动。
• 我们可以对状态进行簿记，因为状态可能会重复。

Alpha-Beta 剪枝的应用

AI 在棋盘游戏中的应用

• 国际象棋： Stockfish 使用 Alpha Beta 剪枝等技术。这种剪枝可以消除不会影响最终决策的分支，因此可以在合理的时间内评估数百万个可能的棋盘配置。例如，如果提供了一系列已知会导致失败的移动，算法将跳过进一步的搜索。
• 跳棋： 在跳棋中，算法必须评估可能的移动，目的是最大化 AI 分数并最小化对手的机会。Alpha Beta 剪枝可以避免不必要的探索，从而减少深度策略的规划时间。
• Tic-Tac-Toe： 即使游戏简单得多，Alpha-Beta 剪枝也可以通过在达到决策过程结束之前剪枝导致平局或失败的路径来有效地找出哪些移动是最佳的。

对抗搜索问题中的决策制定

• 安全系统： 在网络安全领域，Alpha-Beta 剪枝用于入侵检测系统进行决策。因此，它可以作为对抗行为的模型，并确定应对威胁的最优策略，同时最小化系统漏洞。
• 经济建模： Alpha-Beta 剪枝技术可以帮助竞争性市场中的公司模拟对抗性场景，以制定最佳策略，最大化利润并降低竞争对手行动的影响。
• 机器人和自动化： 机器人使用这种剪枝来决定有效的路径和响应，当使用对抗性规划进行任务时，例如竞争性任务或在动态环境中导航。

实时策略游戏中的增强

• 战斗模拟： 例如，在最像《星际争霸》的 RTS 游戏中，使用 Alpha-Beta 剪枝来评估可能的攻击和防御策略。这使得 AI 能够预测对手的移动并采取最佳行动，从而获得相对于对手的优势。
• 资源管理： 在 RTS 游戏中，决策与资源分配有关；例如，我应该花时间积累更多资源还是建造军队？Alpha Beta 剪枝使 AI 能够以更经济的权衡方式找到平衡这些相互竞争的目标的方法。
• 动态场景： RTS 游戏与回合制游戏不同，因为在 RTS 游戏中，始终是连续进行的，并且玩家的决策必须实时更改。然而，Alpha Beta 剪枝的实时执行需要进行微调才能使其正常工作，并且对于剪枝其考虑的移动中不必要的选项至关重要，以保持计算效率。

Alpha-Beta 剪枝的优缺点

优点

• 与纯粹 Minimax 相比效率更高： Alpha-Beta 剪枝可以通过从越来越多的节点向下钻取决策树来显著提高 Minimax 算法的性能。效率来自于剪枝不影响结果的分支。这意味着算法只关注最有希望的路径，并且由于存在许多通往目标的路径，这可以加快在国际象棋或跳棋等情况下的决策制定。
• 适用于大型决策树： 该算法对于大型搜索空间游戏和决策问题尤其有用。移除不必要的树枝允许在相同的计算预算下对树进行更深的搜索。深度优势对于做出更好的决策非常重要，尤其是在需要精确预见的竞争环境中。

缺点

• 依赖于节点评估的顺序： 由于 Alpha Beta 剪枝中的节点顺序由顺序控制，因此其效率在很大程度上取决于该顺序。因此，如果算法首先处理最有希望的移动（所谓的“节点排序”），则剪枝效果最大。然而，如果节点排序导致次优剪枝，则节点排序也会对计算效率产生负面影响。因此，为了获得最佳性能，通常需要使用启发式方法或预处理进行正确实现。
• 深度和复杂树的计算开销： Alpha-Beta 剪枝减少了节点的探索，但在具有极高深度的复杂树上效率不高。特别是，如果没有良好的节点排序启发式方法，该算法的计算工作量可能至少与最坏情况一样高。然而，当问题域需要此类方法时，蒙特卡洛树搜索可能是解决此类问题的更合适的方法。

结论

在许多人工智能对抗性游戏中，将 Alpha-Beta 剪枝应用于 Minimax 算法是优化 Minimax 算法的最佳方法之一。它通过有效地剪枝不相关的分支并利用其减少的努力深入决策树来显著节省计算资源，从而实现更具策略性的探索。

它尤其适用于国际象棋和其他基于策略的游戏等复杂场景，因为它具有优势；它更高效，并且适用于大型决策空间。尽管它在依赖节点排序和深层嵌套树中可能出现的计算开销方面存在局限性，但已证明在一般树中可以实现低开销。