it Negamax

Il negamax è una piccola variante dell'algoritmo minimax che si basa sulle proprietà dei giochi a somma zero con due giocatori.

Per definizione, il valore della posizione del giocatore A in un certo gioco è la negazione del valore della posizione del giocatore B. Così, il giocatore che deve muovere cercherà una mossa che massimizzi la negazione del valore della posizione risultante dalla mossa: per definizione, questa posizione del successore deve essere stata valutata dall'avversario. La veridicità di questa affermazione si mantiene indipendentemente dal fatto che sia A o B a dover muovere. Ciò significa che un singolo calcolo può essere usato per dare valore a tutte le posizioni. Questa è una semplificazione rispetto al minimax, che richiede che A scelga la mossa con il massimo valore di successione mentre B con il minimo.

Il negamax non va confuso con il negascout, una moderna variante dell'agoritmo potatura alfa-beta scoperto negli anni '80, divenendo esso stesso una versione più avanzata del minimax o del negamax.

Molti motori per la ricerca di soluzioni con avversari sono programmati utilizzando alcune forme dell'algoritmo negamax.

Pseudocodice

Qui di seguito lo pseudocodice per una ricerca negamax a profondità limitata con l'uso della potatura alfa-beta.

function negamax(nodo, profondità, α, β)
    if nodo è un nodo terminale or profondità = 0
        return valore euristico del nodo
    else
        foreach figlio
            α := max(α, -negamax(figlio, profondità-1, -β, -α))
            {ciò che segue, se verificato, costituisce la potatura alfa-beta}
            if α ≥ β
                return β
        return α

Al primo richiamo, gli argomenti α e β dovrebbero essere posti rispettivamente ai valori più alti e più bassi possibili per ogni nodo.

Voci correlate

Portale Economia

Portale Matematica