algorithm - 无法将 Alpha Beta 修剪算法应用于此树

Question

我正在尝试将 alpha beta 修剪算法应用于这棵给定的树。

我遇到节点 C 时卡住了，因为展开 B 的所有子节点后，我给 A >= -4，然后我展开 C 得到 I =-3，它大于 -4 (-3 >= -4).因此，我是否将 A 更新为 -3？如果是这样，我之后会修剪 J 和 K 因为 -3 >= -3 吗？当我完成这个例子时，我修剪了 J、K、M 和 N。我真的不确定这个 =(

编辑:

另一个问题:在探索 B 并将 B 的值传递给 A 之后，我们是否将这个值传递给 C，从而传递给 I？我看到一个例子是这样的。这是:http://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf

但是，在这个例子中，http://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf ，它似乎并没有向下传递值，而是似乎只向上传播值。我不确定哪一个是正确的，或者它是否有所不同。

Answer 1

展开B的所有 child 之后, 然后 A有α=-4, β=∞ .

当您到达 I 时, 然后 α=-4, β=-3 . α < β所以J和 K没有修剪。需要对它们进行评估以确保它们不小于 -3，从而降低 C 的评估. A 的值更新为α=-3, β=∞在 C 之后被扩大。您不能使用更新后的 alpha 值 A在评估 J 时因为它还没有更新。

J和 K如果 I 将被修剪相反是-5。在那种情况下，什么都不重要J和 K是因为我们已经知道了C的评价比B差因为-5 < -4 , 和 J和 K只会让情况变得更糟。

每个节点将 alpha 和 beta 值传递给它的子节点。然后， children 将根据轮到谁来更新自己的 alpha 或 beta 值副本，并返回该节点的最终评估。然后用于更新父级的 alpha 或 beta 值。

参见 Alpha-Beta pruning例如:

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 β

// Initial call
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)