Accession Number : AD0766293

Title :   Analysis of the Alpha-Beta Pruning Algorithm,

Corporate Author : CARNEGIE-MELLON 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 game-playing programs must search very large game trees. Use of the alpha-beta 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 alpha-beta 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 alpha-beta algorithm in a chess playing program and the effects of correlation and non-unique 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