了解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 

声明.我的理解是,找到高于前一个call(?)中找到的最小值的第二个值,即使用的值.但由于这是函数的MAX部分,我们不想要HIGHEST值,而不仅仅是大于beta的任何值吗？

Answer 1

这是算法的修剪阶段,在MaxPlayer子句中(当检查此节点中播放器的最大值时):

Beta是函数的参数,即"修剪因子".它代表了迄今为止您找到的最低分数.这意味着当前节点的父节点(最小化节点)已经找到了一个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顶点中的修剪条件.