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
[modifica | modifica wikitesto]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.
