Negascout

Negascout

NegaScout or 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 move ordering to capitalize on this advantage.

NegaScout works best when there is a good move ordering. In practice, the move ordering is often determined by previous shallower searches. It produces more cutoffs than alpha-beta by assuming that the first explored node is the best. In other words, it supposes the first node is in the principal variation. Then, it can check whether that is true by searching the remaining nodes with a null window (also known as a scout window; when alpha and beta are equal), which is faster than searching with the regular alpha-beta window. If the proof fails, then the first node was not in the principal variation, and the search continues as normal alpha-beta. Hence, NegaScout works best when the move ordering is good. With a random move ordering, NegaScout will take more time than regular alpha-beta; although it will not explore any nodes alpha-beta did not, it will have to re-search many nodes.

In chess engines, NegaScout has typically given a 10 percent performance increase[citation needed].

Alexander Reinefeld invented NegaScout several decades after the invention of alpha-beta pruning. He gives a proof of correctness of NegaScout in his book.[1]

Another search algorithm called MTD(f) can theoretically result in even fewer nodes searched. However it has practical issues (in particular, it relies heavily on the transposition table) and nowadays most chess engines still use a form of NegaScout in their search. Yet another search algorithm which tends to do better than NegaScout in practice is the best-first algorithm called SSS*, although neither algorithm dominates the other. There are trees in which NegaScout searches fewer nodes than SSS* and vice-versa. However, note that SSS* is not a depth-first search and thus has larger memory requirements.

Pseudocode

function negascout(node, depth, α, β)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    b := β                                             (* initial window is (-β, -α) *)
    foreach child of node
        score := -negascout (child, depth - 1, -b, -α)
        if α < score < β and child is not first child      (* check if null-window failed high *)
            score := -negascout(child, depth - 1, -β, -α)  (* full re-search *)
        α := max(α, score)
        if α ≥ β
            return α                                   (* Beta cut-off *)
        b := α + 1                                     (* set new null window *)
    return α

References

  1. ^ A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN 3-540-50742-6

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Negascout — es una variante del algoritmo Minimax, es un algoritmo que combina la relación matemática del Negamax y el uso de ventana nula. También llamado búsqueda de la variante principal este algoritmo puede ofrecer rendimientos incluso mayores a la poda… …   Wikipedia Español

  • MTD-f — MTD(f), an abbreviation of MTD(n,f) (Memory enhanced Test Driver with node n and value f) is a minimax search algorithm better than the basic alpha beta pruning algorithm. Zero Window Searches MTD(f) efficiently does only zero window alpha beta… …   Wikipedia

  • Alpha-beta pruning — is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two player games (Tic tac toe, Chess, Go …   Wikipedia

  • Negamax — En este artículo sobre videojuegos y matemáticas se detectaron los siguientes problemas: Necesita ser wikificado conforme a las convenciones de estilo de Wikipedia. Carece de fuentes o referencias que aparezcan en una fuente acreditada …   Wikipedia Español

  • Minimax — This article is about the decision theory concept. For other uses, see Minimax (disambiguation). Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a… …   Wikipedia

  • Computer chess — 1990s Pressure sensory chess computer with LCD screen Chess+ For the iPad …   Wikipedia

  • Crafty — For the publisher of role playing games, see Crafty Games. Crafty Original author(s) Dr. Robert Hyatt Stable release 23.4 …   Wikipedia

  • Negamax — search is a slightly variant formulation of minimax search that relies on the zero sum property of a two player game. An animated pedagogical example showing the plain negamax algorithm (that is, without alpha beta pruning). The person performing …   Wikipedia

  • Fruit (chess engine) — Fruit is a chess engine developed by Fabien Letouzey. In the SSDF rating list released on November 24 2006, Fruit version 2.2.1 had a rating of 2842. In the CEGT rating list released on January 24 2007, Fruit version 2.2.1 had a rating of 2776.At …   Wikipedia

  • Alexander Reinefeld — (born 1957) is the head of computer science at Zuse Institute Berlin. His contributions to the field include the NegaScout algorithm.External links*Alexander Reinefeld s [http://www.zib.de/reinefeld/ personal homepage] …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”