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

Term	Meaning
Alpha (α)	Best value that the maximizer (AI) can guarantee so far
Beta (β)	Best value that the minimizer (opponent) can guarantee so far
Prune	Stop exploring a branch because it can't influence the outcome

---

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

Concept	Description
Alpha-Beta Pruning	Optimizes Minimax by eliminating branches that won’t affect the final decision
Alpha (α)	Best option so far for the maximizer
Beta (β)	Best option so far for the minimizer
Effect	Same result as Minimax, but faster
Best Case	Doubles depth of search vs. plain Minimax

---