1 
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)

次に、関数を呼び出す深さに関係なく、この関数は常に正の値を返しますか。これは、ヒューリスティック値自体が常に正であると想定しています。

4

1 に答える 1

1

はい、葉ノードの評価点が正の場合、negamax によって正の値が返されます。それが、カラー値による乗算によって実現されることです。これにより、再帰的な negamax 呼び出しが奇数回発生した場合に、最終的な否定を逆にするための対抗否定が常に存在することが保証されます。これは、奇数回の再帰呼び出しでは、色が常に -1 になるためです。偶数回の再帰呼び出しがある場合、すべての否定がキャンセルされ、色は 1 になり、戻り値は影響を受けません。

color == -1 で negamax を呼び出している場合 (反対側が移動する番です)、正しい値を取得するには、その呼び出しを無効にする必要があることに注意してください。あれは：

-negamax(origin, depth, -inf, +inf, -1)
于 2012-01-16T07:26:55.197 に答える