Citizendia

An illustration of alpha-beta pruning. The grayed-out subtrees need not be explored (when moves are evaluated from left to right), since we know the group of subtrees as a whole yields the value of an equivalent subtree or worse, and as such cannot influence the final result.
An illustration of alpha-beta pruning. The grayed-out subtrees need not be explored (when moves are evaluated from left to right), since we know the group of subtrees as a whole yields the value of an equivalent subtree or worse, and as such cannot influence the final result.

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. In Computer science, a search algorithm, broadly speaking is an Algorithm that takes a problem as Input and returns a solution to the problem usually If you're looking for game tree as it's used in game theory (not combinatorial game theory please see Extensive form game. Minimax (sometimes minmax) is a decision rule used in Decision theory, Game theory, Statistics and Philosophy for mini mizing It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc. Chess is a recreational and competitive Game played between two players. ). It stops completely 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. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes.

Contents

History

Allen Newell and Herbert Simon who used what John McCarthy calls an "approximation"[1] in 1958 wrote that alpha-beta "appears to have been reinvented a number of times". Allen Newell ( March 19, 1927 - July 19, 1992) was a researcher in Computer science and Cognitive psychology at the Herbert Alexander Simon ( June 15, 1916 February 9, 2001) was an American Political scientist whose research ranged John McCarthy (born September 4, 1927, in Boston, Massachusetts) is an American Computer scientist and Cognitive [2] Arthur Samuel had an early version and Richards, Hart, Levine and/or Edwards found alpha-beta independently in the United States. Arthur L Samuel (1901 – July 29, 1990) was a pioneer in the field of computer gaming and artificial intelligence The United States of America —commonly referred to as the [3] McCarthy proposed similar ideas during the Dartmouth Conference in 1956 and suggested it to a group of his students including Alan Kotok at MIT in 1961. The Dartmouth Summer Research Conference on Artificial Intelligence was the name of a conference now considered the seminal event for Artificial intelligence as a This article is about Alan Kotok who was associate chair of W3C. [4] Alexander Brudno independently discovered the alpha-beta algorithm, publishing his results in 1963. Alexander Brudno ( Aleksandr L'vovich Brudno) (Александр Львович Брудно (born 1918 is a Russian computer scientist, best known for [5] Donald Knuth and Ronald W. Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer Moore refined the algorithm In 1975[6][7] and it continued to be advanced.

Improvements over naive minimax

The benefit of alpha-beta pruning lies in the fact that branches of the search tree can be eliminated. The search time can in this way be limited to the 'more promising' subtree, and a deeper search can be performed in the same time. Like its predecessor, it belongs to the branch and bound class of algorithms. Branch and bound (BB is a general Algorithm for finding optimal solutions of various optimization problems especially in discrete and Combinatorial The optimization reduces the effective depth to slightly more than half that of simple minimax if the nodes are evaluated in an optimal or near optimal order (best choice for side on move ordered first at each node).

With an (average or constant) branching factor of b, and a search depth of d ply, the maximum number of leaf node positions evaluated (when the move ordering is pessimal) is O(b*b*. In Computing, Tree data structures and Game theory, the branching factor is the number of children of each node. In two-player Sequential games a ply refers to one turn taken by one of the players In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments . . *b) = O(bd) – the same as a simple minimax search. If the move ordering for the search is optimal (meaning the best moves always searched first), the number of positions searched is about O(b*1*b*1*. . . *b) for odd depth and O(b*1*b*1*. . . *1) for even depth, or O(b^{d/2}) = O(\sqrt{b^d}). In the latter case, the effective branching factor is reduced to its square root, or, equivalently, the search can go twice as deep with the same amount of computation. In Mathematics, a square root of a number x is a number r such that r 2 = x, or in words a number r whose [8] The explanation of b*1*b*1*. . . is that all the first player's moves must be studied to find the best one, but for each, only the best second player's move is needed to refute all but the first (and best) first player move – alpha-beta ensures no other second player moves need be considered. If b=40 (as in chess), and the search depth is 12 ply, the ratio between optimal and pessimal sorting is a factor of nearly 406 or about 4 billion times.

Normally during alpha-beta, the subtrees are temporarily dominated by either a first player advantage (when many first player moves are good, and at each search depth the first move checked by the first player is adequate, but all second player responses are required to try and find a refutation), or vice versa. This advantage can switch sides many times during the search if the move ordering is incorrect, each time leading to inefficiency. As the number of positions searched decreases exponentially each move nearer the current position, it is worth spending considerable effort on sorting early moves. An improved sort at any depth will exponentially reduce the total number of positions searched, but sorting all positions at depths near the root node is relatively cheap as there are so few of them. In practice, the move ordering is often determined by the results of earlier, smaller searches, such as through iterative deepening. Iterative deepening depth-first search (IDDFS is a State space search strategy in which a Depth-limited search is run repeatedly increasing the depth limit with

The algorithm maintains two values, alpha and beta, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Initially alpha is negative infinity and beta is positive infinity. As the recursion progresses the "window" becomes smaller. When beta becomes less than alpha, it means that the current position cannot be the result of best play by both players and hence need not be explored further.

Pseudocode

function alphabeta(node, depth, α, β)             (* β represents previous player best choice - doesn't want it if α would worsen it *)    if node is a terminal node or depth = 0        return the heuristic value of node    foreach child of node        α := max(α, -alphabeta(child, depth-1, -β, -α))             (* use symmetry, -β becomes subsequently pruned α *)        if β≤α            break                             (* Beta cut-off *)    return α

Heuristic improvements

Further improvement can be achieved without sacrificing accuracy, by using ordering heuristics to search parts of the tree that are likely to force alpha-beta cutoffs early. Pseudocode is a compact and informal high-level description of a Computer programming Algorithm that uses the structural conventions of some Programming language heuristic (hyu̇-ˈris-tik is a method to help solve a problem commonly an informal method For example, in chess, moves that take pieces may be examined before moves that do not, or moves that have scored highly in earlier passes through the game-tree analysis may be evaluated before others. Iterative deepening depth-first search (IDDFS is a State space search strategy in which a Depth-limited search is run repeatedly increasing the depth limit with Another common, and very cheap, heuristic is the killer heuristic, where the last move that caused a beta-cutoff at the same level in the tree search is always examined first. In competitive two-player games the killer heuristic is a technique for improving the efficiency of Alpha-beta pruning, which in turn improves the efficiency of the This idea can be generalized into a set of refutation tables.

Alpha-beta search can be made even faster by considering only a narrow search window (generally determined by guesswork based on experience). This is known as aspiration search. In the extreme case, the search is performed with alpha and beta equal; a technique known as zero-window search, null-window search, or scout search. This is particularly useful for win/loss searches near the end of a game where the extra depth gained from the narrow window and a simple win/loss evaluation function may lead to a conclusive result. If an aspiration search fails, it is straightforward to detect whether it failed high (high edge of window was too low) or low (lower edge of window was too high). This gives information about what window values might be useful in a re-search of the position.

Other algorithms

More advanced algorithms that are even faster while still being able to compute the exact minimax value are known, such as Negascout and MTD-f. NegaScout or Principal Variation Search is a Negamax algorithm that can be faster than Alpha-beta pruning. MTD(f, an abbreviation of MTD(nf (Memory-enhanced Test Driver with node n and value f is a Minimax search algorithm better than the basic Alpha-beta pruning algorithm

Since the minimax algorithm and its variants are inherently depth-first, a strategy such as iterative deepening is usually used in conjunction with alpha-beta so that a reasonably good move can be returned even if the algorithm is interrupted before it has finished execution. Depth-first search ( DFS) is an Algorithm for traversing or searching a tree, Tree structure, or graph. Iterative deepening depth-first search (IDDFS is a State space search strategy in which a Depth-limited search is run repeatedly increasing the depth limit with Another advantage of using iterative deepening is that searches at shallower depths give move-ordering hints that can help produce cutoffs for higher depth searches much earlier than would otherwise be possible.

Algorithms like SSS*, on the other hand, use the best-first strategy. SSS* is a Search algorithm, introduced by Stockman in 1979 that conducts a State space search traversing a Game tree in a best-first fashion Best-first search is a Search algorithm which explores a graph by expanding the most promising node chosen according to some rule This can potentially make them more time-efficient, but typically at a heavy cost in space-efficiency.

See also

References

  1. ^ McCarthy, John (LaTeX2HTML 27 November 2006). Pruning is a term in Mathematics and Informatics which describes a method of Enumeration, which allows to cut parts of a Decision tree. Branch and bound (BB is a general Algorithm for finding optimal solutions of various optimization problems especially in discrete and Combinatorial Minimax (sometimes minmax) is a decision rule used in Decision theory, Game theory, Statistics and Philosophy for mini mizing Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of Feasible solutions is discrete or can be reduced Negamax search is a slightly variant formulation of Minimax search that relies on the Zero-sum property of a Two-player game. In Computer chess and other computer games transposition tables are used to speed up the search of the Game tree. MTD(f, an abbreviation of MTD(nf (Memory-enhanced Test Driver with node n and value f is a Minimax search algorithm better than the basic Alpha-beta pruning algorithm NegaScout or Principal Variation Search is a Negamax algorithm that can be faster than Alpha-beta pruning. In competitive two-player games the killer heuristic is a technique for improving the efficiency of Alpha-beta pruning, which in turn improves the efficiency of the Events 1095 - Pope Urban II declares the First Crusade at the Council of Clermont Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. Human Level AI Is Harder Than It Seemed in 1955. Retrieved on 2006-12-20. Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. Events 69 - Vespasian, formerly a general under Nero, enters Rome to claim the title of Emperor.
  2. ^ Newell, Allen and Herbert A. Simon (March 1976). "Computer Science as Empirical Inquiry: Symbols and Search". Communications of the ACM, Vol. 19, No. 3.  
  3. ^ Richards, D. J. and Hart, T. P. (4 December 1961 to 28 October 1963). "December 4th" redirects here For the song by Jay-Z, see December 4th (song. Year 1961 ( MCMLXI) was a Common year starting on Sunday (link will display full calendar of the Gregorian calendar. Events 306 - Maxentius is proclaimed Roman Emperor. 312 - Battle of Milvian Bridge: Constantine Year 1963 ( MCMLXIII) was a Common year starting on Tuesday (link will display full calendar of the Gregorian calendar. The Alpha-Beta Heuristic (AIM-030). Massachusetts Institute of Technology. Retrieved on 2006-12-21. Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. Events 69 - The end of the Year of the four emperors: Following Galba, Otho and Vitellius, Vespasian
  4. ^ Kotok, Alan (XHTML 3 December 2004). Events 1800 - War of the Second Coalition: Battle of Hohenlinden, French "MMIV" redirects here For the Modest Mouse album see " Baron von Bullshit Rides Again " MIT Artificial Intelligence Memo 41. Retrieved on 2006-07-01. Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. "July 1st" redirects here For the Ayumi Hamasaki song see H (song.
  5. ^ Marsland, T.A. (May 1987). Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor) 159-171. J. Wiley & Sons. Retrieved on 2006-12-21. Year 2006 ( MMVI) was a Common year starting on Sunday of the Gregorian calendar. Events 69 - The end of the Year of the four emperors: Following Galba, Otho and Vitellius, Vespasian
  6. ^ * Knuth, D. E. , and Moore, R. W. (1975). "An Analysis of Alpha-Beta Pruning". Artificial Intelligence Vol. 6, No. 4: 293-326.  
    • Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 1-57586-212-3.  
  7. ^ Abramson, Bruce (June 1989). "Control Strategies for Two-Player Games". ACM Computing Surveys, Vol. 21, No. 2.  
  8. ^ Russell, Stuart J. & Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed. Stuart Russell (born 1962) is a computer scientist known for his contributions to Artificial intelligence. Peter Norvig is an American computer scientist. He is currently the Director of Research (formerly Director of Search Quality at Google Inc Artificial Intelligence A Modern Approach (ISBN 0-13-790395-2 (AIMA is a college textbook on Artificial Intelligence, written by Stuart J ), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2, <http://aima.cs.berkeley.edu/> 

External links

Dictionary

alpha-beta pruning

-noun

  1. (computing theory) An algorithm for pruning a search tree by eliminating any branch that is demonstrably inferior to a branch previously encountered.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic