Alpha-beta剪枝是minimax算法的修改版本。它是minimax算法的一种优化技术。
正如我们在minimax搜索算法中看到的那样，必须检查的游戏状态数量在树的深度上呈指数级。由于我们无法消除指数，因此可以将其减半。因此，存在一种无需检查游戏树的每个节点就可以计算出正确的minimax决策的技术，该技术称为剪枝。这涉及两个阈值参数Alpha和Beta用于将来扩展，因此称为 alpha-beta剪枝。也称为 Alpha-Beta算法。
Alpha-beta剪枝可以应用于树的任何深度，有时它不仅可以剪枝树叶，还可以剪枝整个子树。
两个参数可以定义为: Alpha: : 到目前为止，我们在Maximizer路径上的任何位置都找到了最佳(最高价值)选择。 alpha的初始值为-∞。 测试版: 到目前为止，我们在"最小化器"路径上的任何位置都找到了最佳(最低价值)选择。 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      // for 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                         // for Minimizer player
   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剪枝中移动顺序:

最差排序: 在某些情况下，alpha-beta剪枝算法不会剪枝任何树上的叶子，并且与minimax算法完全一样。在这种情况下，由于alpha-beta因素，它还会消耗更多的时间，这种剪枝动作被称为最差排序。在这种情况下，最佳移动发生在树的右侧。这样的订单的时间复杂度为O(b ^m )。
理想排序: 当在树中进行大量剪枝时，发生理想的alpha-beta剪枝顺序，并且最佳移动发生在树的左侧。我们应用DFS，因此它首先在树的左侧搜索，并且在相同的时间内经过两次最小深度算法。理想排序的复杂度为O(b ^m/2 )。

找到良好顺序的规则:

从最浅的节点获得最佳移动。
对树中的节点进行排序，以便首先检查最佳节点。
使用领域知识，同时找到最佳方法。例如: 对于国际象棋，请尝试顺序: 先捕获，然后威胁，然后向前移动，向后移动。
我们可以保留状态，因为状态可能会重复。