Catalogue of Artificial Intelligence Techniques
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( ) 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.
- Slate, D.J. and Atkin, L.R., Chess 4.5---the Northwestern University chess program, Chess Skill in Man and Machine (Frey, P.W.
, ed.), Springer-Verlag, Berlin, 1977, pp.82--118.