Empirical Exploration of the Performance of the Alpha Beta Tree-Searching Heuristic
- 1 January 1976
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-25 (1) , 6-11
- https://doi.org/10.1109/tc.1976.5009198
Abstract
The alpha beta heuristic has been used extensively as a means for reducing the tree-searching effort in computer game-playing programs. It is well known that if the number of terminal nodes in a tree is N, then under optimal circumstances the alpha beta heuristic reduces the actual number of nodes examined to about 2N ½ . This is a substantial reduction in the case that N is on the order of ten thousand to a million. Unfortunately these optimal conditions are equivalent, in the case of game playing, to having immediate knowledge for every position in the tree as to which alternative is the best one; and this amount of foreknowledge would make tree searching unnecessary in the first place! This paper explores quantitively the performance of the alpha beta heuristic under a wide variety of conditions other than the optimal one, including several situations occurring in actual game-playing programs.Keywords
This publication has 6 references indexed in Scilit:
- A comparison and evaluation of three machine learning procedures as applied to the game of checkersArtificial Intelligence, 1974
- Experiments with the M & N tree-searching programCommunications of the ACM, 1970
- Some Studies in Machine Learning Using the Game of Checkers. II—Recent ProgressIBM Journal of Research and Development, 1967
- The Greenblatt chess programPublished by Association for Computing Machinery (ACM) ,1967
- Some Studies in Machine Learning Using the Game of CheckersIBM Journal of Research and Development, 1959
- Chess-Playing Programs and the Problem of ComplexityIBM Journal of Research and Development, 1958