THE ALPHA-BETA PRUNING — a dart

THE ALPHA-BETA PRUNING skip the branches that cannot matter

Minimax explores every branch of a game tree; alpha-beta proves the same value while skipping branches it can already show are irrelevant. Once one reply is bad enough that a rational opponent would never allow the position, the rest of that subtree goes unexamined. With good move ordering it searches roughly the square root of the nodes — letting the same lookahead reach twice as deep.

THE TECHNIQUE same value as minimax, fewer nodes

The demo runs a tiny MAX-of-MIN tree and shows a beta cutoff pruning one leaf, value unchanged: live demo

HISTORY & CREDIT Knuth & Moore · 1975

“Alpha-beta might miss the best move to go faster.” — it returns the exact minimax value; it only skips branches that cannot change the result. cited

the window · carry α (best for MAX) and β (best for MIN); when they cross, cut.
the cutoff · a reply ≤ α means the opponent will avoid this line — stop searching it.
1975 · Knuth & Moore formalized it (roots in McCarthy, Samuel, the Newell-Simon-Shaw chess work).

Proving you need not look. algorithm

RECOMMEND FOR I-13 the cutoff, on the compiler

On i-13, the tree with leaves [3,5,2,9] returns 3 with only 3 leaves visited (the 9 is pruned):

$ i13 run gm_alpha-beta-pruning.i13 RUN OK · 55 step(s) value = 3 -- same as full minimax prune = 1 -- L2=2 <= alpha 3 -> beta cutoff visited_ab = 3 visited_full = 4

Recommend as a NULL — a resource win (B40) + coordinate-dependent order (B44). Alpha-beta returns the identical minimax value; it only saves node visits, and WHICH nodes it prunes depends on move ordering (a labeling of the tree). NULL — skip the branches that cannot matter.