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

Move Ordering in Alpha-Beta

Improving pruning efficiency by evaluating promising moves first to trigger more cutoffs earlier.

Move Ordering in Alpha-Beta

What You'll Learn

You'll learn how evaluating the most promising moves first dramatically increases Alpha-Beta pruning efficiency by triggering earlier cutoffs.

The Problem with Random Move Order

Alpha-Beta pruning already reduces the nodes you explore compared to vanilla Minimax, but its effectiveness depends heavily on which moves you examine first. In the worst case (random ordering), Alpha-Beta prunes very few branches. In the best case (optimal ordering), it can reduce search time from O(b^d) to O(b^(d/2))—effectively doubling your search depth!

Why Move Ordering Matters

Think of Alpha-Beta like searching for the best restaurant deal. If you check the worst options first, you waste time before finding evidence that lets you skip bad neighborhoods entirely. But if you check the most promising areas first, you quickly establish bounds that eliminate whole districts.

When the maximizing player examines its best move first, it raises the alpha bound aggressively. When the minimizing player checks its best move first, it lowers beta quickly. Both situations create more opportunities for cutoffs in sibling branches.

Common Ordering Heuristics

Without fully evaluating every position, you can use lightweight heuristics:

  • Captures before quiet moves (taking pieces is often strong)
  • Checks and threats (forcing moves constrain opponents)
  • Previous best move from iterative deepening
  • Killer moves (moves that caused cutoffs at the same depth elsewhere)
  • History heuristic (moves that historically performed well)

The goal: spend a little time ordering to save massive time pruning.

Key Takeaway: Move ordering is the difference between Alpha-Beta being marginally better than Minimax and being exponentially better—good ordering can double your effective search depth by maximizing cutoffs.