Negamax est-il toujours censé renvoyer une valeur positive?

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 α

Donc, si ce qui précède est mon code Negamax (copié à partir de Wikipedia), et il est appelé comme suit:

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

Ensuite, cette fonction renverra toujours une valeur positive quelle que soit la profondeur avec laquelle nous appelons la fonction. Cela suppose que la valeur heuristique en soi est toujours positive.

Answer 1

Oui, si le score d'évaluation du nœud feuille est positif, une valeur positive sera renvoyée par Negamax. C'est ce que la multiplication par la valeur de la couleur accomplit, il garantit qu'il y a toujours une négation contre-une négation pour inverser la négation finale s'il y a un nombre impair d'appels récursifs Negamax. En effet, avec un nombre impair d'appels récursifs, la couleur sera toujours -1. S'il y a un nombre uniforme d'appels récursifs, toutes les négations annulent et la couleur sera 1, ce qui laissera la valeur renvoyée non affectée.

Notez que si vous appelez Negamax avec Color == -1 (c'est le tour de l'autre côté pour bouger), vous devez annuler cet appel afin d'obtenir la bonne valeur. C'est-à-dire:

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