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)
那么,无论我们以什么深度调用这个函数,它总是会返回一个正值吗?这里假设启发式值本身总是正的。
回答:
是的,如果叶节点的评估分数是正的,negamax将返回一个正值。这就是通过颜色值进行乘法的作用,它确保了如果递归的negamax调用次数为奇数时,会有一个反向的否定来抵消最终的否定。因为在奇数次递归调用中,颜色值总是等于-1。如果递归调用次数为偶数,所有否定都会相互抵消,颜色值将为1,这不会影响返回值。
请注意,如果你调用negamax时color == -1(轮到另一方移动),你必须对该调用进行否定以获得正确的值。即:
-negamax(origin, depth, -inf, +inf, -1)