An Analysis of Alpha-Beta Pruning.
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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1974
- Accession Number
- ADA000284
Entities
People
- Donald Knuth
- Ronald W. Moore
Organizations
- Stanford University