Home/Game AI/Alpha-beta pruning
Search algorithmsCTRL K

Alpha-beta pruning

· minimax with cutoffs · same answer, fewer leaves
/gameai/alpha-beta-pruning
VISITED
1/ 40
nodes entered
LEAVES
0/ 27
positions scored
PRUNED
0
nodes never visited
ALPHA
−∞
best MAX can force so far
BETA
+∞
best MIN can force so far
currentevaluatedbest linepruned
b = 3 · depth 3 · 27 leaves · seed 7 · 117 steps
step 0 / 116
Depth3
alpha_beta.ts
1
function alphaBeta(node: Node, depth: number, alpha: number, beta: number, maximizing: boolean): number {
2
  if (depth === 0 || node.isLeaf) return node.value;
3
  let best = maximizing ? -Infinity : Infinity;
4
  for (const child of node.children) {
5
    const value = alphaBeta(child, depth - 1, alpha, beta, !maximizing);
6
    best = maximizing ? Math.max(best, value) : Math.min(best, value);
7
    if (maximizing) alpha = Math.max(alpha, best); else beta = Math.min(beta, best);
8
    if (beta <= alpha) break;
9
  }
10
  return best;
11
}
CURRENT STEP
line 1

Enter a MAX node at depth 0 with α = −∞, β = +∞.

// how it works

Understanding Alpha-beta pruning

alpha-beta · the branches you never needed to look at
01

The idea

Alpha-beta is minimax that remembers two bounds while it searches: α, the best value MAX is already guaranteed somewhere above, and β, the best MIN is guaranteed. When a node finds a child that makes its own value worse than what the opponent can already force elsewhere, the remaining children cannot change the result and are skipped.

The answer is exactly the minimax value; only the work changes. With children in random order it roughly halves the leaves; with the best move tried first it visits about b^(d/2) leaves, which doubles the depth an engine can reach in the same time.

02

The four stages

1
descendcarry α and β down
2
scoreleaf returns its evaluation
3
tightenMAX raises α, MIN lowers β
4
cutβ ≤ α: skip the remaining children
03

Complexity

best
O(b^(d/2))best move always tried first
average
O(b^(3d/4))random move order
worst
O(b^d)worst move first: no cut ever fires
space
O(d)one path plus two numbers
04

Versus its siblings

LEAVES SCORED · b = 3, d = 4
minimax
81
negamax
81
expectimax
81
alpha-beta
44
alpha-beta, ordered
17
same tree · ordered means the best move is tried first
05

Pseudocode

ALPHABETA(node, depth, α, β, maximizing)
  if depth = 0 or node is a leaf: return value(node)
  best ← −∞ if maximizing else +∞
  for each child of node
    value ← ALPHABETA(child, depth − 1, α, β, not maximizing)
    best ← max/min(best, value); α ← max(α, best) if maximizing else β ← min(β, best)
    if β ≤ α: break
  return best
06

When to use

Every minimax search in practice: chess, checkers, Othello, Connect 4. There is no reason to run minimax without it.
Whenever move ordering is possible: try captures, killer moves or the previous best first and the cuts multiply.
07

Pitfalls

Move ordering decides everything: with bad ordering it is plain minimax with extra bookkeeping.
Cuts make the search order-dependent, so caching node values in a transposition table needs the bound type (exact, lower, upper) too.
Mixing up when to update α versus β, or the strict versus non-strict cutoff, silently returns wrong values.
08

History

Alpha-beta was discovered several times: John McCarthy sketched it in 1956, Arthur Samuel used it in his checkers program, and Alexander Brudno published the first analysis in 1963. Donald Knuth and Ronald Moore proved its b^(d/2) bound in 1975, and every chess engine since has been built on it.

Back to Game AI