Alpha–beta pruning

Alpha–beta pruning speeds up minimax search by skipping branches that cannot change the final decision. It preserves minimax’s result while often reducing the number of positions examined.

Minimax: A decision rule that chooses moves by assuming an opponent also chooses optimally. Alpha–beta pruning accelerates this search without changing its selected move.
Iterative deepening depth-first search: A search strategy that repeatedly runs depth-limited depth-first search with increasing limits. Its earlier searches can improve move ordering for later alpha–beta passes.
Expectiminimax: A game-tree algorithm that includes chance nodes and evaluates them using expected values. Chance outcomes require expectation calculations rather than ordinary alpha–beta comparisons.
Branching factor: The average number of successor states generated from each state in a search tree. Reducing the effective branching factor is the main source of alpha–beta’s speedup.
Alpha value: The best score MAX can guarantee along the path examined so far. This lower bound lets MAX-side search reject branches that cannot improve its choice.
Chess engine: A program that analyzes chess positions and selects moves. Chess engines combine alpha–beta pruning with evaluation and ordering to search far beyond shallow trees.
Monte Carlo tree search: A search method that estimates move values through repeated simulated play. Unlike alpha–beta, it samples selected paths instead of exhaustively bounding minimax branches.
Search depth: The number of successive moves or transitions explored in a search. Pruning can make deeper search feasible within a fixed computational budget.
Beta value: The best score MIN can guarantee along the path examined so far. This upper bound lets MIN-side search reject branches that cannot worsen its choice.
Negamax: A minimax formulation that uses score negation to handle alternating players symmetrically. Its compact implementation can use the same alpha–beta bounds at every ply.

Linked from 10 pages