Alpha-Beta 剪枝

• Alpha-beta 剪枝是 minimax 算法的修改版本。它是一种极小极大算法的优化技术。

• 正如我们在极小极大搜索算法中看到的那样，它必须检查的游戏状态数量在树的深度上是指数级的。由于我们无法消除指数，但我们可以将其减半。因此，有一种技术可以在不检查博弈树的每个节点的情况下计算正确的极小极大决策，这种技术称为剪枝。这涉及到两个阈值参数 Alpha 和 beta 用于未来扩展，因此称为alpha-beta pruning。它也被称为Alpha-Beta 算法。

• Alpha-beta 修剪可以应用于树的任何深度，有时它不仅修剪树叶，还修剪整个子树。

• 二参数可以定义为：

1. Alpha：到目前为止，我们在 Maximizer 路径上的任何一点找到的最佳（最高值）选择。alpha 的初始值为-∞。

2. Beta：迄今为止我们在 Minimizer 路径上的任何一点找到的最佳（最低值）选择。beta 的初始值为+∞。

• 标准极小极大算法的 Alpha-beta 修剪返回与标准算法相同的移动，但它删除了所有没有真正影响最终决策但使算法变慢的节点。因此，通过修剪这些节点，它使算法快速。

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

Alpha-beta 修剪的条件：

α-β 修剪所需的主要条件是：

α>=β

关于 alpha-beta 剪枝的要点：

• Max 播放器只会更新 alpha 的值。

• Min 玩家只会更新 beta 的值。

• 在回溯树时，节点值将传递给上层节点而不是 alpha 和 beta 的值。

• 我们只会将 alpha、beta 值传递给子节点。

Alpha-beta 剪枝的伪代码：

function minimax(node, depth, alpha, beta, maximizingPlayer) is  
if depth ==0 or node is a terminal node then  
return static evaluation of node  
  
if MaximizingPlayer then      // 用于Maximizer Player  
   maxEva= -infinity            
   for each child of node do  
   eva= minimax(child, depth-1, alpha, beta, False)  
  maxEva= max(maxEva, eva)   
  alpha= max(alpha, maxEva)      
   if beta<=alpha  
 break  
 return maxEva  
    
else                         // 用于最小化播放器  
   minEva= +infinity   
   for each child of node do  
   eva= minimax(child, depth-1, alpha, beta, true)  
   minEva= min(minEva, eva)   
   beta= min(beta, eva)  
    if beta<=alpha  
  break          
 return minEva

Alpha-Beta 剪枝的工作原理：

让我们以两人搜索树为例来了解 Alpha-beta 剪枝的工作原理

步骤 1：在第一步中，最大玩家将从节点 A 开始第一次移动，其中 α= -∞ 和 β= +∞，这些 alpha 和 beta 值向下传递到节点 B，其中 α= -∞ 和 β= + ∞，节点 B 将相同的值传递给它的子节点 D。

第 2 步：在节点 D 处，α 的值将在轮到 Max 时计算。α 的值先与 2 比较，然后与 3 比较，最大值 (2, 3) = 3 将是节点 D 处的 α 值，节点值也将是 3。

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

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

Step 4：在节点E，Max将轮到它，alpha的值会发生变化。alpha 的当前值将与 5 进行比较，因此 max (-∞, 5) = 5，因此在节点 E α= 5 和 β= 3，其中 α>=β，因此将修剪 E 的右后继，并且算法不会遍历它，并且节点 E 处的值将为 5。

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

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

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

Step 7:节点 F 将节点值 1 返回给节点 C，在 C α= 3 且 β= +∞ 时，这里 beta 的值将发生变化，它将与 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 剪枝的一个重要方面。

它可以有两种类型：

• 最差排序：在某些情况下，alpha-beta 修剪算法不会修剪树的任何叶子，并且与 minimax 算法完全一样。在这种情况下，它也会因为 alpha-beta 因素而消耗更多的时间，这种剪枝的动作称为最差排序。在这种情况下，最佳移动发生在树的右侧。这种订单的时间复杂度是 O(b ^m )。

• 理想排序： alpha-beta 修剪的理想排序发生在树中进行大量修剪时，并且最佳移动发生在树的左侧。我们应用 DFS，因此它首先搜索树的左侧，并在相同的时间内深入两倍于极小极大算法。理想排序的复杂度为 O(b ^m/2 )。

找到好的排序规则：

以下是在 alpha-beta 修剪中找到良好排序的一些规则：

• 从最浅的节点发生最好的移动。

• 对树中的节点进行排序，以便首先检查最佳节点。

• 使用领域知识，同时找到最佳举措。例如：对于国际象棋，尝试顺序：先捕获，然后威胁，然后向前移动，向后移动。

• 我们可以记录状态，因为状态可能会重复。