¿Se supone que Negamax siempre devuelve un valor positivo?

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 α

Entonces, si el anterior es mi código negamax (copiado de wikipedia), y se llama de la siguiente manera:

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

Entonces, esta función siempre devolverá un valor positivo independientemente de la profundidad con la que llamemos a la función.Esto supone que el valor heurístico en sí mismo siempre es positivo.

Answer 1

Sí, si la puntuación de evaluación del nodo hoja es positiva, negamax devolverá un valor positivo.Eso es lo que logra la multiplicación por el valor del color, asegura que siempre haya una negación contraria para revertir la negación final si hay un número impar de llamadas negamax recursivas.Esto se debe a que con un número impar de llamadas recursivas, el color siempre será -1.Si hay un número par de llamadas recursivas, todas las negaciones se cancelan y el color será 1, lo que no afectará al valor devuelto.

Tenga en cuenta que si está llamando a negamax con color== -1 (es el turno del otro lado para moverse), debe negar esa llamada para obtener el valor correcto.Eso es:

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