Newborn, M.


An upper bound on the time complexity of iterative-deepening-A*

Classics

This paper establishes an upper bound on the time complexity of iterative-deepening-A* (IDA*) in terms of the number of states that are surely-expanded by A* during a state space tree search.


The efficiency of the alpha-beta search on trees with branch-dependent terminal node scores

Classics

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).


Computer chess

Classics

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