Alpha-beta pruning

📘 Problem Solving by Searching: Alpha-Beta Pruning

1. What is Alpha-Beta Pruning?

Alpha-Beta Pruning is an optimization technique for the Minimax algorithm used in two-player adversarial games (like Chess or Tic-Tac-Toe). It reduces the number of nodes evaluated in the search tree without affecting the final result.

💡 Goal: Skip unnecessary branches that cannot influence the final decision.

2. Why Use Alpha-Beta Pruning?

• Minimax explores every node to find the best move.
• In complex games (like Chess), the search tree is too large.
• Alpha-Beta Pruning helps cut off parts of the tree that don’t affect the decision, making it much faster.

3. Key Terms

4. How It Works (Conceptually)

• Traverse the tree depth-first, just like in Minimax.

• At each Max node:

  • Update Alpha if a better value is found.
  • Prune if Alpha ≥ Beta.

• At each Min node:

  • Update Beta if a lower value is found.
  • Prune if Beta ≤ Alpha.

🧠 Pruning condition: If a move is worse than what we've already seen, don’t explore it further.

5. Visual Example

           MAX
         /     \
       MIN     MIN
      /  \     /  \
     3    5   2    9

• Without pruning, all 7 nodes are evaluated.
• With Alpha-Beta, some branches (like the "9" under the second MIN) can be skipped because they cannot improve the final decision.

6. Effectiveness

• Time Complexity (best case): O(b^(d/2))

  • b = branching factor
  • d = depth of tree

• This means it can double the depth that can be explored compared to basic Minimax.

✅ Summary