Alpha-Beta Pruning Algorithm

AKA: Alpha-Beta Technique.
Context:
- It usually applies a branch-and-bound technique.
- …
Example(s):
- an Alpha-Beta pruning algorithm written in pseudo-code (Wikipedia),
- …
Counter-Example(s):
See: Pruning Algorithm), Search Algorithm, Brute-Force Search Algorithm, Expectiminimax Algorithm, Negamax Algorithm, Branch and Bound Algorithm, Combinatorial Optimization Algorithm, Principal Variation Search, Transposition Table.

References

(Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Alpha–beta_pruning Retrieved:2021-12-15.
- Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.^[1]

↑ Russell, Stuart J.; Norvig, Peter (2010). Artificial Intelligence: A Modern Approach (3rd ed.). Upper Saddle River, New Jersey: Pearson Education, Inc. p. 167. ISBN 978-0-13-604259-4.

(ChessPrograming.org, 2021) ⇒ https://www.chessprogramming.org/Alpha-Beta Retrieved:2021-12-15.
- QUOTE: The Alpha-Beta algorithm (Alpha-Beta Pruning, Alpha-Beta Heuristic ^[1] ) is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of the game tree applying a branch-and-bound technique. Remarkably, it does this without any potential of overlooking a better move. If one already has found a quite good move and search for alternatives, one refutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and beta. They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively(...)

↑ Arthur Samuel (1967). Some Studies in Machine Learning. Using the Game of Checkers. II-Recent Progress. pdf, IBM Journal - November 1967, on the name Alpha-Beta Heuristic pp. 602: So named by Prof. John McCarthy. This procedure was extensively investigated by Prof. John McCarthy and his students at M.I.T. but it has been inadequately described in the literature. It is, of course, not a heuristic at all, being a simple algorithmic procedure and actually only a special case of the more general "branch and bound" technique which was been rediscovered many times and which is currently being exploited in integer programming research.

(GeeksforGeeks, 2021) ⇒ https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/ Last Updated : 18 Aug, 2021.
- QUOTE: Prerequisites: Minimax Algorithm in Game Theory, Evaluation Function in Game Theory.
  Alpha-Beta pruning is not actually a new algorithm, rather an optimization technique for minimax algorithm. It reduces the computation time by a huge factor. This allows us to search much faster and even go into deeper levels in the game tree. It cuts off branches in the game tree which need not be searched because there already exists a better move available. It is called Alpha-Beta pruning because it passes 2 extra parameters in the minimax function, namely alpha and beta.
  Let’s define the parameters alpha and beta.'Alpha is the best value that the maximizer currently can guarantee at that level or above. Beta is the best value that the minimizer currently can guarantee at that level or above.