An optimization of the minimax search algorithm that skips over branches of the game tree that cannot possibly change the final decision, letting a game-playing program search substantially deeper in the same amount of time.
Facts
Partially Attested
Origin YearJohn McCarthy proposed the idea at the 1956 Dartmouth workshop and again to MIT students in 1961; Alexander Brudno independently conceived and published the algorithm in 1963, and Donald Knuth and Ronald Moore later refined and formally analyzed it in 1975, so the concept has more than one independent origin point. Core PrincipleAlpha-beta pruning is a tree search algorithm that decreases the number of nodes evaluated by the minimax algorithm in its search tree. 1 Connections
Associated With
Donald Knuth, Pioneers Donald Knuth and Ronald W. Moore published the definitive formal analysis of alpha-beta pruning in their 1975 paper An Analysis of Alpha-Beta Pruning.
In Field
Sources
1. Alpha-beta pruning - Wikipedia
History section
McCarthy proposed similar ideas during the Dartmouth workshop in 1956 and suggested it to a group of his students including Alan Kotok at MIT in 1961.
Lead section, opening sentence
Alpha-beta pruning is a tree search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.