I have an interesting story about trying to find a copy of the original paper describing alpha-beta search. Back in 1992 I was doing research on massively-parallel computer chess for my Ph.D. thesis, and I was trying to do a literature review. According to several sources, the paper was
- Timothy P. Hart and Daniel J. Edwards, "The Tree Prune (TP) Algorithm", Artificial Intelligence Project Memo 30, RLE And Computation Center, Massachusetts Institute of Technology, Cambridge, MA, USA, December 4, 1961. (Revised as D. J. Edwards and T. P. Hart, "The α-β Heuristic", AI Memo 30 (Revised), October 28, 1963.)
The history of alpha-beta search is murky. The rest of this post comprises an incomplete review of that history. (See Knuth and Moore for a more careful treatment.)
- Slagle and Dixon (1969) wrote that Hart and Edwards provided the first detailed description of alpha-beta search (in 1961) and the first published use of the term "alpha-beta" (in the 1963 revision). Slagel and Dixon provided the first proof about the effectiveness of alpha-beta search on best-ordered trees, whereas Hart and Edwards stated the theorem without proof.
- Nils J. Nilson's 1971 book Problem Solving Methods in Artificial Intelligence cites Hart and Edwards as having done extensive investigation of alpha-beta search. Nilson cites, on page V-49, a personal communication with A. L. Samuel who claimed that he had implemented alpha-beta search in his 1959 checkers program but that Samuel didn't realize the significance of the algorithm and hadn't included a description of it in his paper. Samuel's work was actually pretty amazing: The entire checkers program was written in only 6800 instructions on an IBM 704, and included a transposition table.
- Knuth and Moore (1975) is the standard reference for a mathematical treatment of alpha-beta pruning. Knuth and Moore also cite (on page 303) that Samuel stated that alpha-beta search was present in his checker-playing programs. Knuth and Moore state that McCarthy thought of alpha-beta search in 1956. Knuth and Moore say that the first published account of alpha-beta search appeared in Russia (Brudno 1963), based on the fact that the Hart and Edwards AI memo was "unpublished". Knuth and Moore note how early authors had a lot of trouble explaining alpha-beta search: the idea was difficult to express in the notation of the time.