| dbpedia-owl:abstract
|
- Negamax search is a slightly variant formulation of minimax search that relies on the zero-sum property of a two-player game. This algorithm heavily relies on the fact that max(a, b) = -min(-a, -b) to simplify the implementation of the minimax algorithm. More precisely, 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 procedure can be used to value both 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, an algorithm to compute the minimax or negamax value quickly by clever use of alpha-beta pruning discovered in the 1980s. Note that alpha-beta pruning is itself a way to compute the minimax or negamax value of a position quickly by avoiding the search of certain uninteresting positions. 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 α≥β break 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) What can be confusing for beginners is how the heuristic value of the current node is calculated. In this implementation, the value is always calculated from the point of view of the player running the algorithm because of the color parameter. This is the same behavior as the normal minimax algorithm. If this parameter was not present, the evaluation function would need to return a score for the current player, i.e. the min or max player.
- Negamax es una variante del algoritmo minimax donde cada nodo independientemente si fuese MIN o MAX toma el valor máximo de sus hijos (como si todos los nodo fueran MAX), solo que los valores de los nodos MAX se cambian de signo (de ahí su nombre, en vez de tomar máximos y mínimos toma siempre máximos pero con valores cambiados). De esta forma se logra el mismo efecto ya que tomar el mayor valor pero cambiado de signo es en realidad tomar el menor así cuando el algoritmo está en un nivel MIN cuando toma el mayor de sus hijos en realidad está tomando al menor. La función Negamax podría recibir como parámetro un signo, de esta manera se podría comenzar por niveles MIN o niveles MAX, pero no necesariamente ya se puede establecer niveles estáticos, donde cada nivel está definido por un signo distinto. Hablando del Minimax: Suponiendo que existe min que devuelve el menor y max que devuelve el mayor, Negamax se basa en la siguiente igualdad matemática: max(x, y)=-min(-x,-y) A este algoritmo también se le pueden aplicar podas y heurísticas para acortar su tiempo de ejecución, además existe una mejora de este algoritmo llamado negascout.
- 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 di ricerca sono programmati utilizzando alcune forme dell'algoritmo negamax.
|
| rdfs:comment
|
- Negamax search is a slightly variant formulation of minimax search that relies on the zero-sum property of a two-player game. This algorithm heavily relies on the fact that max(a, b) = -min(-a, -b) to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B.
- Negamax es una variante del algoritmo minimax donde cada nodo independientemente si fuese MIN o MAX toma el valor máximo de sus hijos (como si todos los nodo fueran MAX), solo que los valores de los nodos MAX se cambian de signo (de ahí su nombre, en vez de tomar máximos y mínimos toma siempre máximos pero con valores cambiados).
- 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.
|
