Artificial Intelligence : Unit - 2 Part - 15 : Alpha-Beta Pruning

 

UNIT - II

Alpha-Beta Pruning

---

Part A: Introduction

---

What is Alpha-Beta Pruning?

Alpha-Beta Pruning is an optimization technique used in the Minimax algorithm to reduce the number of nodes evaluated in a game tree.

It helps the AI agent make faster and smarter decisions by ignoring branches that will not affect the final result.

---

Why is it called Alpha-Beta?

• Alpha (α): The best (maximum) score that the MAX player can guarantee so far.
• Beta (β): The best (minimum) score that the MIN player can guarantee so far.

If at any point α ≥ β, the remaining branches don’t need to be explored — they’re pruned (cut off).

---

Part B: Need for Alpha-Beta Pruning

Problem with Minimax	Solution Provided by Alpha-Beta
Explores all nodes of the tree	Prunes unnecessary branches
High time complexity (O(b^d))	Reduces it to O(b^(d/2)) with good ordering
Slow decision-making in games	Makes real-time game AI faster and smarter

---

Part C: How Alpha-Beta Pruning Works

---

Step-by-Step:

1. Traverse the tree using Minimax (Depth-First).
2. Pass two values down the tree:
• Alpha: Best value that MAX can secure
• Beta: Best value that MIN can secure
3. At each node:
• If you find a value worse than alpha or beta, you can prune that branch.
4. Continue only with branches that might influence the final decision.

---

Part D: Alpha-Beta Pruning Conditions

Condition	Result
At MAX node: α ≥ β	Stop evaluating further children
At MIN node: β ≤ α	Stop evaluating further children

---

Pseudocode (Simplified)

function AlphaBeta(node, depth, α, β, maximizingPlayer):

    if node is terminal or depth == 0:

        return heuristic value of node

 

    if maximizingPlayer:

        value = -∞

        for each child of node:

            value = max(value, AlphaBeta(child, depth-1, α, β, False))

            α = max(α, value)

            if α ≥ β:

                break  # Beta cut-off

        return value

    else:

        value = +∞

        for each child of node:

            value = min(value, AlphaBeta(child, depth-1, α, β, True))

            β = min(β, value)

            if β ≤ α:

                break  # Alpha cut-off

        return value

---

Part E: Advantages of Alpha-Beta Pruning

Advantage	Description
✅ Faster than plain Minimax	Evaluates fewer nodes
✅ Same result as Minimax	Optimal result is preserved
✅ Supports deeper search	Saves time and space, allowing more depth
✅ Better for real-time games	Efficient decision-making under time constraints

---

Part F: Limitations

Limitation	Description
❌ Requires proper node ordering	Works best if best moves are checked first
❌ Still exponential in worst case	O(b^d), but greatly reduced with pruning

---

Applications

• Chess Engines (e.g., Stockfish)
• Checkers, Tic-Tac-Toe
• AI Bots in Strategy Games
• Decision Trees in Competitive Environments

---

Summary

• Alpha-Beta Pruning is an enhancement to the Minimax algorithm.
• It eliminates branches in the game tree that don’t affect the final decision.
• Uses two values, Alpha (max value) and Beta (min value), to prune unnecessary paths.
• It is widely used in game-playing AI to save time and compute deeper strategies.

"Alpha-Beta Pruning is like solving a puzzle faster — by skipping pieces that won’t fit!"