An analysis of the efficiency of the alpha-beta algorithm is carried out based on a probabilistic model in which terminal node scores depend on random branch values. Explicit expressions are derived for the expected number of terminal nodes scored for the cases of uniform trees of fanout N and of depths 2 and 3. For trees of depth 2, the expected number is of order O(NHN); for trees of depth 3, the expected number is of order O(N2). An upper bound on the expected number of terminal nodes scored for trees of depth 4 is shown to be no greater than O(N2HN2) and no less than O(N2).
See also:Monty Newborn and Monroe Newborn. 1997. Kasparov Vs. Deep Blue: Computer Chess Comes of Age. Springer-Verlag New York, Inc., Secaucus, NJ, USA.Monty Newborn. 2003. Computer chess. In Encyclopedia of Computer Science (4th ed.), Anthony Ralston, Edwin D. Reilly, and David Hemmendinger (Eds.). John Wiley and Sons Ltd., Chichester, UK 336-339.Recent Progress in Computer Chess. In ADVANCES IN COMPUTERS, Volume 18, edited by Marshall C. Yovits, Academic Press, 1980.Monty Newborn. 1990. The 20th annual ACM North American computer chess championship. Commun. ACM 33, 7 (July 1990), 92-104.Monroe Newborn, Computer Chess: Ten Years of Significant Progress, In: Marshall C. Yovits, Editor(s), Advances in Computers, Elsevier, 1989, Volume 29, Pages 197-250.New York: Academic Press