Alpha-beta pruning

Alpha-beta pruning speeds up the search performed by a chess engine, a program that compares moves and replies. The search can be pictured as a tree: each node is a position and each branch is a legal move. Without pruning, the program would examine many continuations that eventually prove irrelevant.

The method maintains two bounds while searching. Alpha is the best result one side can already guarantee along the current path. Beta is a limit created by an alternative already available to the opponent. Once a continuation is so poor that a rational player would never choose it, searching it further cannot change the decision at the higher node.

The branch is stopped because of a logical bound in the tree, not merely because a move looks unattractive. At the same depth and with the same evaluations at the search limit, alpha-beta returns the same choice as a complete search that assumes both sides make their best replies.

The saving depends heavily on move order. Testing strong moves early establishes useful bounds sooner and lets more branches stop without deeper examination. An evaluation function, which assigns a numerical estimate to a position, supplies values where the finite search ends.