Negamax总是应该返回正值吗？

Question

function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            val := -negamax(child, depth-1, -β, -α, -color)
            {the following if statement constitutes alpha-beta pruning}
            if val≥β
                return val
            if val≥α
                α:=val
        return α

因此，如果上面是我的negamax代码(从维基百科复制)，它的调用如下所示：

negamax(origin, depth, -inf, +inf, 1)

那么，无论我们调用函数的深度是多少，这个函数都会返回一个正值吗？这是假设启发式值本身始终是正的。

Answer 1

可以，如果叶子节点的评估得分为正，则negamax将返回正值。这就是颜色值的乘法所完成的，它确保了如果有奇数个递归的负极最大调用，总是有一个反否定来反转最终的否定。这是因为对于奇数个递归调用，color始终为-1。如果递归调用的次数为偶数，则所有的求反操作都会被取消，并且颜色将为1，这将使返回值不受影响。

请注意，如果您使用颜色== -1调用negamax (轮到另一方移动)，则必须取消该调用才能获得正确的值。这就是：

-negamax(origin, depth, -inf, +inf, -1)