Negamax search is a slightly variant formulation of minimax search that relies on the zero-sum property of a two-player game. By definition the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value of the position resulting from the move: this successor position must by definition have been valued by the opponent.

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • Negamax search is a slightly variant formulation of minimax search that relies on the zero-sum property of a two-player game. By definition the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value of the position resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single computation can be used to value all positions. This is a coding simplification over minimax, which requires that A select the move with the maximum-valued successor while B selects the move with the minimum-valued successor. It should not be confused with negascout, which is a modern variation of alpha-beta pruning discovered in the 1980s, alpha-beta pruning itself being a more advanced form of minimax or negamax. Most adversarial search engines are coded using some form of negamax search. Pseudocode for depth-limited negamax search with alpha-beta pruning: 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 α := max(α, -negamax) {the following if statement constitutes alpha-beta pruning} if α≥β return α return α When called, the arguments α and β should be set to the lowest and highest values possible for any node and color should be set to 1. (* Initial call *) negamax(origin, depth, -inf, +inf, 1)
  • Il negamax è una piccola variante dell'algoritmo minimax che si basa sulle proprietà di gioco 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 di ricerca sono programmati utilizzando alcune forme dell'algoritmo negamax.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • Negamax search is a slightly variant formulation of minimax search that relies on the zero-sum property of a two-player game. By definition the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value of the position resulting from the move: this successor position must by definition have been valued by the opponent.
  • Il negamax è una piccola variante dell'algoritmo minimax che si basa sulle proprietà di gioco 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.
rdfs:label
  • Negamax
  • Negamax
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is dbpprop:redirect of
is owl:sameAs of