algorithm - 了解 alpha-beta 剪枝算法中的截止条件

Question

我无法理解我在维基百科上找到的关于 alpha beta 剪枝的伪代码:

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 β

令我困惑的是 if Player = MaxPlayer 条件。我理解整个递归调用函数 not(Player) 以获得最小值，然后递归调用 Player 函数，重复直到达到深度限制或已找到目标状态。但是，我不明白

if β ≤ α
    break 

声明。我对此的理解是，找到第二个高于上一次调用中找到的最小值 (β) 的值，即使用的值。但是因为这是函数的 MAX 部分，难道我们不想要 HIGHEST 值，而不仅仅是大于 beta 的任何值吗？

Answer 1

这是算法的修剪阶段，在 MaxPlayer 中子句(检查此节点中玩家的最大值时):

Beta 是函数的参数，即“微调因子”。它代表您到目前为止找到的最低分数。这意味着当前节点(最小化节点)的父节点已经找到了 beta 解。

现在，如果我们继续迭代所有 child ，我们将得到至少与当前 alpha 一样好的东西。自 beta <= alpha - 父节点 - 正在最小化节点 - 永远不会选择这个 alpha(或任何大于它的值) - 它会选择一个 beta 或更低的值 - 当前节点没有机会找到这样的值，所以我们可以修剪计算。

示例:

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

当评估 MAX 节点时，如果我们应用普通的 min-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 顶点中的修剪条件。