3

我无法理解我在维基百科上找到的用于 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 β

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

if β ≤ α
    break

陈述。我的理解是，找到比上一次调用（）中找到的最小值高的第二个值β，即使用的值。但是由于这是函数的 MAX 部分，我们不想要 HIGHEST 值，而不仅仅是大于 beta 的任何值吗？

4

1 回答 1

7

这是算法的修剪阶段，在MaxPlayer子句中（当检查此节点中玩家的最大值时）：

Beta是函数的参数，即“微调因子”。它代表您迄今为止找到的最低分数。这意味着当前节点的父节点（最小化节点）已经找到了一个 beta 解决方案。

现在，如果我们继续迭代所有孩子，我们将得到至少与当前 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 顶点中的修剪条件。

于 2012-10-20T17:37:13.913 回答