1. An analysis of alpha-beta pruning
- Author
-
Ronald W. Moore and Donald E. Knuth
- Subjects
Linguistics and Language ,Correctness ,Theoretical computer science ,Negamax ,Computer science ,Alpha–beta pruning ,Language and Linguistics ,Expectiminimax tree ,Artificial Intelligence ,Principal variation search ,Game tree ,Algorithm ,Transposition table ,Killer heuristic - Abstract
The alpha-beta technique for searching game trees is analyzed, in an attempt to provide some insight into its behavior. The first portion of this paper is an expository presentation of the method together with a proof of its correctness and a historical discussion. The alpha-beta procedure is shown to be optimal in a certain sense, and bounds are obtained for its running time with various kinds of random data.
- Published
- 1975
- Full Text
- View/download PDF