Course contentsShow
← Computer Science
Lesson 2768 of 2,87261. AI and Search AlgorithmsFree lesson

Alpha-Beta Pruning

Optimizing minimax by eliminating branches that cannot affect the final decision, reducing nodes explored.

Alpha-Beta Pruning

What you'll learn: How to drastically reduce the number of game-tree nodes minimax needs to explore without changing the final decision.


The Core Idea

After learning the minimax algorithm, you know it explores every possible move to find the optimal play. But here's the insight: you don't always need to look at every branch. If you already know one move is terrible, why waste time proving just how terrible it is?

Alpha-beta pruning optimizes minimax by maintaining two values as you traverse the tree:

  • Alpha (α): The best score the maximizer can guarantee so far
  • Beta (β): The best score the minimizer can guarantee so far

When exploring a node, if you discover that the current branch can't possibly affect the final decision (because it's provably worse than an alternative you've already found), you prune that entire subtree—you stop evaluating it.

How It Works

Imagine you're the maximizer evaluating two moves. You fully explore the first move and find it guarantees you a score of 5. Now you start exploring the second move. The minimizer's first response gives a score of 3. Since the minimizer will choose the lowest score for that branch, and they've already found 3, you know the second move can't possibly be better than 5—so you stop exploring the rest of that branch.

The algorithm still returns the same answer as full minimax; it just skips evaluating nodes that can't change the outcome. In the best case, this cuts the effective branching factor from b to √b, meaning you can search roughly twice as deep in the same time.

Key Takeaway: Alpha-beta pruning eliminates provably irrelevant branches during minimax search, dramatically reducing computation while guaranteeing the same optimal result.