Alpha-Beta Pruning — Beginner-Friendly Notes

1. What It Fixes

Minimax visits all leaves — too many. Alpha-Beta skips branches that cannot affect the final decision, yielding same move much faster. It is an optimisation, not a different algorithm — result identical to Minimax.

2. Intuition in One Line

If you already have a move that guarantees score $X$, and opponent has a reply that limits another branch to $\leq X$, you don't need to examine other replies in that branch — they are irrelevant.

3. How It Works (two bounds)

• α (alpha): best value MAX can guarantee so far along the path to root (lower bound). Initial $-\infty$.
• β (beta): best value MIN can guarantee so far (upper bound). Initial $+\infty$.

During DFS traversal:

• At MAX node: update $α = max(α, value)$; if $α \geq β$ → β-cutoff (prune remaining children — MIN won't let MAX reach this node).
• At MIN node: update $β = min(β, value)$; if $β \leq α$ → α-cutoff (prune — MAX has a better alternative elsewhere).

AlphaBeta(node, α, β, isMax):
  if terminal: return utility
  if isMax:
    for child:
      α = max(α, AlphaBeta(child, α, β, false))
      if α >= β: break  # prune
    return α
  else:
    for child:
      β = min(β, AlphaBeta(child, α, β, true))
      if β <= α: break
    return β

4. Example That Clicks

MAX root (α=-∞,β=+∞)
 ├─ MIN A → returns 3 → α=3 at root
 └─ MIN B
     ├─ child 2 → β becomes 2 ≤ α(3) → prune!  (even without checking other children, B will be ≤2 <3, so root prefers A)

You saved exploring a whole subtree.

5. Properties

Property	Value
Correctness	Same result as Minimax (pruning is safe)
Best-case time	$O(b^{m/2})$ — effectively doubles searchable depth (perfect ordering)
Worst-case	$O(b^m)$ (bad ordering — no pruning)
Ordering matters	Sort children with best moves first → most pruning

6. Exam Tips

• Move ordering is key — use heuristic to order moves (e.g., captures first in chess).
• Alpha-Beta + evaluation function + cutoff depth = practical game AI (Deep Blue, chess engines).

7. One-Line Summary

Alpha-Beta prunes Minimax branches that cannot influence the root decision using α/β bounds, preserving optimal play while reducing best-case time to $O(b^{m/2})$.

8. Quick Self-Check

1. Why does α start at $-\infty$ and β at $+\infty$?
2. Give a state where pruning happens and where it doesn't.