The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm

By Judea Pearl. 1981

Subfields: Game & Decision Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Game & Decision Theory

In Algorithms & Complexity

Citations in the corpus

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (2017, neutral): “For at least four decades the strongest computer chess programs have used alpha-beta search (19, 24).”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “In zero-sum perfect information games, minimax and alpha-beta search are classical search algorithms for making decisions using heuristic value functions [29].”
TreeQN and ATreeC: Differentiable Tree Planning for Deep Reinforcement Learning (2017, methodology): “One strategy for on-line planning is to use look-ahead tree search (Knuth & Moore, 1975; Browne et al., 2012).”
Deep Blue (2002, methodology): “The pseudo-code is based on a depth-limited version of alpha-beta using the negamax formulation [19].”
Learning to Search with MCTSnets (2018, background): “Many success stories in artiﬁcial intelligence are based on the application of powerful tree search algorithms to challenging planning problems (Samuel, 1959; Knuth & Moore, 1975; J¨unger et al., 2009).”
Automated Planning and Acting (2016, background): “2, except that the depth-first search is the well-known alpha-beta algorithm [338, 460, 517].”
Deep Blue system overview (1995, background): “The search control does not really implement the regular @ search algorithm [9].”
Computer poker: A review (2011, methodology): “A typical game tree search, such as minimax search with alpha-beta pruning [45], involves exhaustively searching the breath of a tree until a certain cut-off depth is reached.”
ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero (2019, background): “Many older AI players for board games use minimax search over a game tree, typically augmented with alpha-beta pruning (Knuth & Moore, 1975) and game-speciﬁc heuristics.”
Bonsai Trees in Your Head: How the Pavlovian System Sculpts Goal-Directed Choices by Pruning Decision Trees (2012, background): “There exist algorithmic solutions that ignore branches of a decision tree that are guaranteed to be worse than those already evaluated [1–3].”
Symbiotic Evolution of Neural Networks in Sequential Decision Tasks (1997, methodology): “The - pruning algorithm (Edwards and Hart 1963; Knuth and Moore 1975) is used as in a full-width search to prune irrelevant states.”
Deep Reinforcement Learning (2018, methodology): “One strategy for on-line planning is to use look-ahead tree search (Knuth & Moore, 1975; Browne et al., 2012).”
Autonomous Evolution of Topographic Regularities in Artificial Neural Networks (2010, background): “Alpha-beta pruning (Knuth and Moore, 1975) and iterative deepening (Russell et al.”
The *-Minimax Search Procedure for Trees Containing Chance Nodes (1983, methodology): “Readers familiar with studies of the alpha-beta procedure [2-5] will ap-”
A World Championship Caliber Checkers Program (1992, methodology): “The program uses all the standard computer chess search techniques: alpha-beta search [15] with the history heuristic [26], transposition tables and iterative deepening [29].”