
Accession Number : AD0766293
Title : Analysis of the AlphaBeta Pruning Algorithm,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Fuller,S. H. ; Gaschnig,J. G. ; Gillogly,J. J.
Report Date : JUL 1973
Pagination or Media Count : 55
Abstract : Many gameplaying programs must search very large game trees. Use of the alphabeta pruning algorithm instead of the simple minimax search reduces by a large factor the number of bottom positions which must be examined in the search. An analytical expression for the expected number of bottom positions examined in a game tree using alphabeta pruning is derived, subject to the assumptions that the branching factor N and the depth D of the tree are arbitrary but fixed, and the bottom positions are a random permutation of (N sub D) unique values. A simple approximation to the growth rate of the expected number of bottom positions examined is suggested, based on a Monte Carlo simulation for large values of N and D. The behavior of the model is compared with the behavior of the alphabeta algorithm in a chess playing program and the effects of correlation and nonunique bottom position values in real game trees are examined. (Author)
Descriptors : (*COMPUTER PROGRAMMING, *GAME THEORY), (*SEARCH THEORY, ALGORITHMS), MINIMAX TECHNIQUE, GRAPHICS, DISTRIBUTION FUNCTIONS, RANDOM VARIABLES, ARTIFICIAL INTELLIGENCE
Subject Categories : Operations Research
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE