Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Alpha/Beta Pruning

Keywords: Trans-Ref hash tables, games

Categories: Game Theory , Search

Author(s): Hans Berliner

The Minimax procedure need not be applied to every branch of the Search Tree. Newell first observed that once a branch of a tree has been refuted, it need not be refuted again. The alpha-beta procedure was first formalised by McCarthy. Its properties are such that it is highly dependent on the order of presentation of alternatives. When alternatives are presented in the best order, it is possible to save O(n12 ) of the total effort, where n is the number of leaf nodes in the tree. Recent advances in game searching, such as Iterative Deepening and the use of Trans-Ref hash tables, have improved the performance of the alpha-beta search beyond the above specified bound. This is due to the fact that near perfect ordering can be achieved when the tree has many identical nodes in it, but in this case it can be more properly analysed as a graph.



Add Comment

No comments.