Game Trees, Minimax, Alpha-Beta Pruning & Adversarial Search

TAKEAWAYS:

• Game trees model adversarial decision-making with alternating maximizer/minimizer players, where each node represents a game state and edges represent possible moves.
• Minimax assigns optimal values to states by recursively evaluating worst-case outcomes, but suffers from exponential time complexity in deep trees.
• Alpha-beta pruning optimizes minimax by cutting branches that cannot influence the final decision, reducing time complexity from $O(b^m)$ to $O(b^{m/2})$.
• Heuristic evaluation functions (e.g., material advantage in chess) guide search depth and improve efficiency, but may sacrifice optimality for speed.
• Iterative deepening combines depth-limited search with increasing depth bounds to balance completeness and efficiency, often used in time-sensitive games like Go.
• Real-world applications include ride-sharing algorithms (Pathao’s driver matching), financial arbitrage (NEPSE stock trading), and even traffic routing (NTC’s signal optimization).

1. Game Theory Basics: Players, States, and Moves

A game in AI is a formal framework with:

• Players: Alternating turns (e.g., MAX player vs. MIN player in chess).
• States: Configurations of the game (e.g., board positions, scores).
• Moves: Actions that transition between states (e.g., moving a pawn in chess).
• Terminal states: End conditions (e.g., checkmate, draw, or time limit).
• Utility values: Numerical outcomes (e.g., +1 for win, -1 for loss, 0 for draw).

State Space Graph for Tic-Tac-Toe

graph TD
    A["Start"] --> B["X's turn: 3 empty"]
    B --> C["X plays center"]
    B --> D["X plays corner"]
    C --> E["O's turn: 2 empty"]
    E --> F["O plays corner"]
    F --> G["X wins (terminal)"]
    D --> H["O's turn: 2 empty"]
    H --> I["O plays edge"]
    I --> J["X can win next move"]

Key Idea: Each node is a game state; edges are valid moves. Terminal nodes (e.g., G) have predefined utilities.

A terminal state in tic-tac-toe where X wins by three in a row. (Image: Ofek Gila, CC BY-SA 4.0, via Wikimedia Commons)

Why Model Games as Trees?

• Adversarial nature: Players act against each other (e.g., Pathao’s algorithm matches drivers to riders while minimizing wait times for both).
• Sequential decisions: Each move depends on previous states (e.g., NEPSE’s stock trading bots adjust bids based on real-time market states).
• Optimality: AI must choose moves that maximize its chance of winning, given the opponent’s optimal play.

2. Minimax Algorithm: Optimal Play with Perfect Information

Minimax assumes:

1. Perfect information: Both players know all past moves (e.g., chess, Go).
2. Alternating turns: Players take turns (no simultaneous moves).
3. Rational opponents: Players act optimally to maximize/minimize utility.

How Minimax Works

1. Assign utilities to terminal states (e.g., +100 for win, -100 for loss).
2. Recursively evaluate non-terminal states:
   • MAX player: Chooses the move with the highest child value.
   • MIN player: Chooses the move with the lowest child value.
3. Backpropagate values up the tree.

Worked Example: Matchstick Game

Rules:

• Two players alternately remove 1–3 matchsticks from a pile.
• Player to remove the last matchstick loses.

Initial state: 10 matchsticks. Terminal condition: 0 matchsticks (losing state).

flowchart TD
    A["10"] --> B["9"] --> C["6"] --> D["3"] --> E["0 (lose)"]
    A --> F["8"] --> G["5"] --> H["2"] --> E
    A --> I["7"] --> J["4"] --> K["1"] --> E

Minimax Trace:

1. MAX (current player) wants to force a win (i.e., leave MIN with a losing position).
2. From 10, possible moves: remove 1, 2, or 3 → states 9, 8, or 7.
   • If MAX removes 3 → state 7.
     • MIN’s turn: removes 1–3 → states 6, 5, or 4.
       • If MIN removes 3 → state 4.
         • MAX’s turn: removes 1–3 → states 3, 2, or 1.
           • If MAX removes 3 → state 1.
             • MIN removes 1 → state 0 (lose).
   • Optimal move: Remove 3 matchsticks first (leaving 7), forcing MIN into a losing path.

Real-World Tie-In:

• Pathao’s ride-matching: Think of riders as "MAX" (wanting shortest wait) and drivers as "MIN" (wanting highest pay). Pathao’s algorithm uses minimax-like logic to balance both objectives, even though it’s not a zero-sum game.

3. Alpha-Beta Pruning: Cutting the Tree

Minimax explores all possible moves, which is inefficient. Alpha-beta pruning eliminates branches that cannot affect the final decision.

How It Works

• Alpha (α): Best value that the MAX player can guarantee so far.
• Beta (β): Best value that the MIN player can guarantee so far.
• Pruning rule:
  • If a MAX node’s value ≤ α, prune its subtree (MIN will never choose worse).
  • If a MIN node’s value ≥ β, prune its subtree (MAX will never choose worse).

Example: Pruning in Tic-Tac-Toe

graph TD
    A["X's turn"] --> B["X plays center"] --> D["O's turn: corner"]
    A --> C["X plays edge"] --> E["O's turn: center"]
    D --> F["X wins (terminal, +1)"]
    E --> G["O wins (terminal, -1)"]

Trace:

1. Start at root (X’s turn). α = -∞, β = +∞.
2. Explore X plays center → O’s turn.
   • O plays corner → X wins (+1). Update α = max(-∞, +1) = +1.
   • Prune other O moves (e.g., O plays edge) because even if O chooses worst for X, X still wins.
3. Move to X plays edge → O’s turn.
   • O plays center → O wins (-1). Since -1 < α (+1), prune subtree.

Result: Only 3 nodes explored instead of 7 (50% reduction).

Time Complexity

Where $b$ = branching factor, $m$ = depth.

4. Heuristic Evaluation Functions

Minimax alone is infeasible for deep games (e.g., chess has ~10¹²⁰ possible games). Heuristics estimate state values without full expansion.

Common Heuristics

Example: Chess Heuristic

def evaluate(state):
    piece_values = {
        'pawn': 1, 'knight': 3, 'bishop': 3,
        'rook': 5, 'queen': 9, 'king': 0
    }
    score = 0
    for piece in state.white_pieces:
        score += piece_values[piece.type]
    for piece in state.black_pieces:
        score -= piece_values[piece.type]
    return score

Output: +3 if White has an extra knight and pawn.

Limitations

• Optimality trade-off: Heuristics may miss optimal moves for speed.
• Domain-specific: A chess heuristic won’t work for Go.
• Horizon effect: Short-term heuristics may overlook long-term strategies.

Real-World Use:

• NEPSE trading bots: Use heuristics like volume-weighted moving averages to predict stock trends, but may miss black swan events.
• Daraz’s recommendation: Uses collaborative filtering (a heuristic) to suggest products, but can’t guarantee optimal sales.

5. Depth-Limited Search and Iterative Deepening

Depth-Limited Search

• Problem: Minimax explores too deeply. Limit search to a fixed depth $d$.
• Solution: Evaluate states at depth $d$ using a heuristic.
• Limitation: May not reach a terminal state (incomplete).

Example: Limited Depth in Checkers

graph TD
    A["Depth 0"] --> B["Depth 1: 4 moves"]
    B --> C["Depth 2: 16 moves"]
    C --> D["Depth 3: 64 moves (heuristic applied)"]

• At depth 3, if no terminal state is reached, use heuristic to evaluate.

Iterative Deepening (IDA)*

• Idea: Run depth-limited search with increasing depth until solution is found.
• Advantages:
  • Complete: Will find solution if one exists.
  • Optimal: Uses heuristic to guide search (like A*).
  • Efficient: Avoids redundant work (shares computations between depths).

Trace for 8-Puzzle (Goal: Solve in ≤3 moves)

1. Depth 0: Check if initial state is goal. No.
2. Depth 1: Explore all 3 possible moves. None reach goal.
3. Depth 2: Explore deeper, but prune paths exceeding threshold $t_1$.
4. Depth 3: Find solution at move sequence [Down, Left, Up].

Real-World Tie-In:

• Pathao’s driver assignment: Uses iterative deepening to match riders to drivers within a time limit, balancing wait time and driver availability.

6. Comparing Search Strategies

*Optimal if heuristic is admissible.

7. Real-World Applications

1. Pathao’s Ride-Matching Algorithm

• Game: Rider (MAX: wants shortest wait) vs. Driver (MIN: wants highest pay).
• Minimax Variant: Pathao’s algorithm uses a bipartite matching approach (not pure minimax) but shares the idea of balancing two objectives.
• Alpha-Beta Pruning: Eliminates driver-rider pairs where wait time exceeds rider’s tolerance or driver’s pay is too low.

2. NEPSE Stock Trading Bots

• Game: Bot (MAX: maximize profit) vs. Market (MIN: adversarial trends).
• Heuristics: Use technical indicators (e.g., RSI, MACD) as evaluation functions.
• Iterative Deepening: Bots adjust bid/ask prices in real-time, increasing depth of analysis as time permits.

3. Kathmandu Traffic Signal Optimization (NTC)

• Game: Vehicles (MAX: minimize travel time) vs. Signals (MIN: minimize congestion).
• Minimax: Signals act as MIN players, adjusting timings to "minimize" overall delay.
• Real Picture:

4. WhatsApp’s Spam Filter

• Game: User (MAX: wants clean chat) vs. Spammer (MIN: wants to bypass filter).
• Alpha-Beta: WhatsApp’s ML model prunes messages with low spam probability early, reducing false positives.

Exam Tip

1. For minimax/alpha-beta:

   • Always draw the game tree and label MAX/MIN nodes.
   • Show pruned branches with alpha/beta values in the trace.
   • Example: In a tic-tac-toe exam question, assume X starts and show how alpha-beta reduces nodes.

2. For heuristics:

   • Define the evaluation function clearly (e.g., "material advantage + mobility").
   • Compare with/without heuristic in terms of completeness and optimality.

3. For iterative deepening:

   • Show depth-by-depth expansion and how thresholds $t_1,t_2,\dots$ guide search.
   • Link to real-time systems (e.g., "Pathao uses this to match rides within 5 seconds").

4. Common Pitfalls:

   • Forgetting to alternate MAX/MIN in minimax.
   • Misapplying alpha/beta values (e.g., updating α at MIN nodes).
   • Assuming heuristics are always admissible (they’re not!).

Pro Tip: Memorize the alpha-beta pruning formula:

If a MAX node’s value ≤ α, prune. If a MIN node’s value ≥ β, prune.

Final Visual Summary

mindmap
  root((Game Search Algorithms))
    Minimax
      "Recursive evaluation"
      "Optimal but slow"
      "Example: Tic-Tac-Toe"
    Alpha-Beta
      "Prunes branches"
      "Faster than minimax"
      "Example: Chess"
    Heuristics
      "Estimates state value"
      "Trades optimality for speed"
      "Example: Chess material count"
    Iterative Deepening
      "Increases depth gradually"
      "Complete and efficient"
      "Example: Rubik’s Cube"
    Real-World
      "Pathao: Ride matching"
      "NEPSE: Stock trading"
      "NTC: Traffic signals"