α-β剪枝算法

Question

我无法理解这种伪我发现α+β修剪维基百科：

function alphabeta(node, depth, α, β, Player)   
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    if Player = MaxPlayer 
     for each child of node 
      α := max(α, alphabeta(child, depth-1, α, β, not(Player)))  
      if β ≤ α 
       break        (* Beta cut-off *) 
     return α 
    else 
     for each child of node 
      β := min(β, alphabeta(child, depth-1, α, β, not(Player)))  
      if β ≤ α 
       break        (* Alpha cut-off *) 
     return β 

什么是困惑我的是，如果玩家= MaxPlayer条件。我理解整个递归调用not（Player）函数来获取最小值，然后递归调用带有Player的函数，直到达到深度限制或找到目标状态。但是，我不明白

if β ≤ α 
    break 

声明。我的理解是，第二个数值高于前一次调用（beta）中找到的最小值，即使用的值。但是由于这是函数的MAX部分，我们是不是想要HIGHEST值，而不是ANY值大于beta？

Answer 1

这是该算法的修整阶段，MaxPlayer子句中（当检查最大值为此节点中的播放器）：

贝塔是作为微调因子的函数的参数。它代表您迄今为止发现的最低分数。这意味着当前节点的父节点是一个最小化节点 - 已经找到了一个解决方案，它是beta。

现在，如果我们继续迭代所有的儿子，我们会得到至少和当前alpha一样好的东西。由于beta <= alpha - 父节点 - 这是最小化节点 - 将永远不会选择此alpha（或任何值大于它） - 它会选择一个值是beta或更低 - 并且当前节点没有机会找到这样的，所以我们可以修整计算。

例子：

    MIN 
       / \ 
       / \ 
       /  \ 
      /  \ 
       5   MAX 
         /| \ 
         /| \ 
        / | \ 
         6 8  4 

当评估MAX节点，我们将回到正常最小 - 最大8。然而，我们知道，MIN功能是要干什么min(5,MAX(6,8,4))。
由于我们要读6，我们知道max(6,8,4) >= 6后，我们就可以不继续计算返回6，因为上层的MIN计算将是min(5,MAX(6,8,4)) = min(5,6) = 5

（这是一个级别的直觉，当然递归做的“流“到具有相同想法的所有级别）。

同样的想法适用于MIN顶点中的修剪条件。