This algorithm relies on the fact that 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 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 selects 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.
Negamax base algorithm
An animated pedagogical example showing the plain negamax algorithm (that is, without alpha–beta pruning). The person performing the game tree search is considered to be the one that has to move first from the current state of the game (player in this case)
NegaMax operates on the same game trees as those used with the minimax search algorithm. Each node and root node in the tree are game states (such as game board configuration) of a two player game. Transitions to child nodes represent moves available to a player who is about to play from a given node.
The negamax search objective is to find the node score value for the player who is playing at the root node. The pseudocode below shows the negamax base algorithm,[1] with a configurable limit for the maximum search depth:
function negamax(node, depth, color) isif depth = 0 or node is a terminal node thenreturn color × the heuristic value of node value := −∞ for each child of node do value := max(value, −negamax(child, depth − 1, −color)) return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, 1)
(* Initial call for Player B's root node *) negamax(rootNode, depth, −1)
The root node inherits its score from one of its immediate child nodes. The child node that ultimately sets the root node's best score also represents the best move to play. Although the negamax function shown only returns the node's best score, practical negamax implementations will retain and return both best move and best score for the root node. Only the node's best score is essential with non-root nodes. And a node's best move isn't necessary to retain nor return for non-root nodes.
What can be confusing is how the heuristic value of the current node is calculated. In this implementation, this value is always calculated from the point of view of player A, whose color value is one. In other words, higher heuristic values always represent situations more favorable for player A. This is the same behavior as the normal minimax algorithm. The heuristic value is not necessarily the same as a node's return value due to value negation by negamax and the color parameter. The negamax node's return value is a heuristic score from the point of view of the node's current player.
Negamax scores match minimax scores for nodes where player A is about to play, and where player A is the maximizing player in the minimax equivalent. Negamax always searches for the maximum value for all its nodes. Hence for player B nodes, the minimax score is a negation of its negamax score. Player B is the minimizing player in the minimax equivalent.
Negamax variant with no color parameter
Negamax can be implemented without the color parameter. In this case, the heuristic evaluation function must return values from the point of view of the node's current player (Ex: In a chess game, if it is white's turn and white is winning, it should return a positive value. However if it is black's turn, it should return a negative value).
function negamax(node, depth) isif depth = 0 or node is a terminal node thenreturn evaluatePosition() // From current player's perspective value := −∞ for each child of node do value := max(value, −negamax(child, depth − 1)) return value
// Example picking best move in a chess game using negamax function above function think(boardState) is allMoves := generateLegalMoves(boardState) bestMove := null bestEvaluation := -∞ for each move in allMoves board.apply(move) evaluateMove := -negamax(boardState, depth=3) board.undo(move) if evaluateMove > bestEvaluation bestMove := move bestEvaluation := evaluateMove return bestMove
Negamax with alpha beta pruning
An animated pedagogical example showing the negamax algorithm with alpha–beta pruning. The person performing the game tree search is considered to be the one that has to move first from the current state of the game (player in this case)
Algorithm optimizations for minimax are also equally applicable for Negamax. Alpha–beta pruning can decrease the number of nodes the negamax algorithm evaluates in a search tree in a manner similar with its use with the minimax algorithm.
The pseudocode for depth-limited negamax search with alpha–beta pruning follows:[1]
function negamax(node, depth, α, β, color) isif depth = 0 or node is a terminal node thenreturn color × the heuristic value of node childNodes := generateMoves(node) childNodes := orderMoves(childNodes) value := −∞ foreach child in childNodes do value := max(value, −negamax(child, depth − 1, −β, −α, −color)) α := max(α, value) if α ≥ β thenbreak(* cut-off *)return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, −∞, +∞, 1)
Alpha (α) and beta (β) represent lower and upper bounds for child node values at a given tree depth. Negamax sets the arguments α and β for the root node to the lowest and highest values possible. Other search algorithms, such as negascout and MTD(f), may initialize α and β with alternate values to further improve tree search performance.
When negamax encounters a child node value outside an alpha/beta range, the negamax search cuts off thereby pruning portions of the game tree from exploration. Cut offs are implicit based on the node return value. A node value found within the range of its initial α and β is the node's exact (or true) value. This value is identical to the result the negamax base algorithm would return, without cut offs and without any α and β bounds. If a node return value is out of range, then the value represents an upper (if value ≤ α) or lower (if value ≥ β) bound for the node's exact value. Alpha–beta pruning eventually discards any value bound results. Such values do not contribute nor affect the negamax value at its root node.
This pseudocode shows the fail-soft variation of alpha–beta pruning. Fail-soft never returns α or β directly as a node value. Thus, a node value may be outside the initial α and β range bounds set with a negamax function call. In contrast, fail-hard alpha–beta pruning always limits a node value in the range of α and β.
This implementation also shows optional move ordering prior to the foreach loop that evaluates child nodes. Move ordering[2] is an optimization for alpha beta pruning that attempts to guess the most probable child nodes that yield the node's score. The algorithm searches those child nodes first. The result of good guesses is earlier and more frequent alpha/beta cut offs occur, thereby pruning additional game tree branches and remaining child nodes from the search tree.
Negamax with alpha beta pruning and transposition tables
Transposition tables selectively memoize the values of nodes in the game tree. Transposition is a term reference that a given game board position can be reached in more than one way with differing game move sequences.
When negamax searches the game tree, and encounters the same node multiple times, a transposition table can return a previously computed value of the node, skipping potentially lengthy and duplicate re-computation of the node's value. Negamax performance improves particularly for game trees with many paths that lead to a given node in common.
The pseudo code that adds transposition table functions to negamax with alpha/beta pruning is given as follows:[1]
function negamax(node, depth, α, β, color) is alphaOrig := α (* Transposition Table Lookup; node is the lookup key for ttEntry *) ttEntry := transpositionTableLookup(node) if ttEntry is valid and ttEntry.depth ≥ depth thenif ttEntry.flag = EXACT thenreturn ttEntry.value else if ttEntry.flag = LOWERBOUND then α := max(α, ttEntry.value) else if ttEntry.flag = UPPERBOUND then β := min(β, ttEntry.value) if α ≥ β thenreturn ttEntry.value if depth = 0 or node is a terminal node thenreturn color × the heuristic value of node childNodes := generateMoves(node) childNodes := orderMoves(childNodes) value := −∞ for each child in childNodes do value := max(value, −negamax(child, depth − 1, −β, −α, −color)) α := max(α, value) if α ≥ β thenbreak(* Transposition Table Store; node is the lookup key for ttEntry *) ttEntry.value := value if value ≤ alphaOrig then ttEntry.flag := UPPERBOUND else if value ≥ β then ttEntry.flag := LOWERBOUND else ttEntry.flag := EXACT ttEntry.depth := depth ttEntry.is_valid := true transpositionTableStore(node, ttEntry) return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, −∞, +∞, 1)
Alpha/beta pruning and maximum search depth constraints in negamax can result in partial, inexact, and entirely skipped evaluation of nodes in a game tree. This complicates adding transposition table optimizations for negamax. It is insufficient to track only the node's value in the table, because value may not be the node's true value. The code therefore must preserve and restore the relationship of value with alpha/beta parameters and the search depth for each transposition table entry.
Transposition tables are typically lossy and will omit or overwrite previous values of certain game tree nodes in its tables. This is necessary since the number of nodes negamax visits often far exceeds the transposition table size. Lost or omitted table entries are non-critical and will not affect the negamax result. However, lost entries may require negamax to re-compute certain game tree node values more frequently, thus affecting performance.
Related Research Articles
Minmax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.
Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Computer chess applications that play at the level of a chess master or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, GNU Chess, Fruit, and other free open source applications are available for various platforms.
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player combinatorial games. It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
In competitive two-player games, the killer heuristic is a move-ordering method based on the observation that a strong move or small set of such moves in a particular position may be equally strong in similar positions at the same move (ply) in the game tree. Retaining such moves obviates the effort of rediscovering them in sibling nodes.
In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha–beta pruning algorithm.
A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position. Transposition tables are primarily useful in perfect-information games. The usage of transposition tables is essentially memoization applied to the tree search and is a form of dynamic programming.
The horizon effect, also known as the horizon problem, is a problem in artificial intelligence whereby, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of them, typically a few plies down the game tree. Thus, for a computer searching only five plies, there is a possibility that it will make a detrimental move, but the effect is not visible because the computer does not search to the depth of the error.
In the context of combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, checkers, Go, and tic-tac-toe. This can be used to measure the complexity of a game, as it represents all the possible ways a game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minimax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.
The expectiminimax algorithm is a variation of the minimax algorithm, for use in artificial intelligence systems that play two-player zero-sum games, such as backgammon, in which the outcome depends on a combination of the player's skill and chance elements such as dice rolls. In addition to "min" and "max" nodes of the traditional minimax tree, this variant has "chance" nodes, which take the expected value of a random event occurring. In game theory terms, an expectiminimax tree is the game tree of an extensive-form game of perfect, but incomplete information.
Principal variation search is a negamax algorithm that can be faster than alpha–beta pruning. Like alpha–beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree. It dominates alpha–beta pruning in the sense that it will never examine a node that can be pruned by alpha–beta; however, it relies on accurate node ordering to capitalize on this advantage.
MTD(f) is an alpha-beta game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for Memory-enhanced Test Driver with node ‘n’ and value ‘f’. The efficacy of this paradigm depends on a good initial guess, and the supposition that the final minimax value lies in a narrow window around the guess (which becomes an upper/lower bound for the search from root). The memory structure is used to save an initial guess determined elsewhere.
In game theory, a null move or pass is a decision by a player to not make a move when it is that player's turn to move. Even though null moves are against the rules of many games, they are often useful to consider when analyzing these games. Examples of this include the analysis of zugzwang, and the null-move heuristic in game tree analysis.
Quiescence search is an algorithm typically used to extend search at unstable nodes in minimax game trees in game-playing computer programs. It is an extension of the evaluation function to defer evaluation until the position is stable enough to be evaluated statically, that is, without considering the history of the position or future moves from the position. It mitigates the effect of the horizon problem faced by AI engines for various games like chess and Go.
SSS* is a search algorithm, introduced by George Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm.
A variation can refer to a specific sequence of successive moves in a turn-based game, often used to specify a hypothetical future state of a game that is being played. Although the term is most commonly used in the context of Chess analysis, it has been applied to other games. It also is a useful term used when describing computer tree-search algorithms for playing games such as Go or Chess.
In computer science, B* is a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node. First published by Hans Berliner in 1979, it is related to the A* search algorithm.
Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. It is also known as Reversi for Microsoft Windows and Classic Mac OS.
In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree.
Best node search (BNS), originally known as fuzzified game tree search, is a minimax search algorithm, developed in 2011. The idea is that the knowledge that one subtree is relatively better than some other(s) may be propagated sooner than the absolute value of minimax for that subtree. Then a repetitive search narrows until a particular node is shown to be relatively best.
References
George T. Heineman; Gary Pollice & Stanley Selkow (2008). "Chapter 7:Path Finding in AI". Algorithms in a Nutshell. Oreilly Media. pp.213–217. ISBN978-0-596-51624-6.
John P. Fishburn (1984). "Appendix A: Some Optimizations of α-β Search". Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. pp.107–111. ISBN0-8357-1527-2.
↑ Schaeffer, Jonathan (1989). "The History Heuristic and Alpha–Beta Search Enhancements in Practice". IEEE Transactions on Pattern Analysis and Machine Intelligence. 11 (11): 1203–12. doi:10.1109/34.42858.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
