Informed Search & Game Trees: Heuristics, A, Minimax

TAKEAWAYS:

• Heuristic functions guide search by estimating cost-to-goal (e.g., Manhattan distance in grid-based pathfinding).
• A* combines uniform cost search with heuristics for optimal efficiency (used in Google Maps’ route optimization).
• Minimax assumes opponents play optimally, while Alpha-Beta pruning cuts unnecessary branches (used in chess engines like Stockfish).
• Game trees model adversarial decisions (e.g., Daraz’s dynamic pricing vs. customer bidding).
• Evaluation functions assign scores to game states (e.g., Ncell’s network congestion prediction).
• Trade-offs: Heuristic accuracy vs. computational cost; pruning vs. solution completeness.

1. Informed Search: Beyond Blind Search

Uninformed search (BFS/DFS) explores all possibilities without guidance. Informed search uses heuristics—rules of thumb—to prioritize promising paths. Key algorithms:

A. Greedy Best-First Search

• How it works:
  • Expands the node with the lowest heuristic estimate (h(n)) to the goal.
  • **Heuristic (h(n))**: Estimated cost from node n to the goal (must be admissible: never overestimates).
  • Example heuristic: Manhattan distance for grid-based problems (e.g., robot navigation).
• Visual: Heuristic Space as a Network

  graph TD
    A["Start"] --> B["B1\nh(n)=3"]
    A --> C["B2\nh(n)=1"]
    A --> D["B3\nh(n)=5"]
    C --> E["Goal\nh(n)=0"]

  Path taken: Start → B2 → Goal (greedy picks B2 first).
• Advantages:
  • Fast if h(n) is accurate.
  • No backtracking.
• Disadvantages:
  • May miss optimal path if heuristic is misleading (e.g., "shortcut" leads to dead ends).
• Real-world use:
  • eSewa’s service locator: Greedily selects the nearest ATM branch based on GPS distance (heuristic: straight-line distance).
  • Pathao’s driver assignment: Prioritizes drivers closest to pickup locations (heuristic: Euclidean distance).

B. Uniform Cost Search (UCS)

• How it works:
  • Expands the node with the *lowest total cost (g(n))* from the start (path cost).
  • Admissible (finds optimal path if one exists).
  • Example: Shortest path in a graph with weighted edges (e.g., traffic routes).
• Comparison with Greedy:

  Feature	Greedy Best-First	Uniform Cost Search
  Cost function	h(n) (heuristic)	g(n) (actual path cost)
  Optimality	No (unless h(n) perfect)	Yes
  Speed	Fast (if heuristic good)	Slower (explores all paths)
  Use case	Approximate solutions	Exact solutions (e.g., NTC’s fiber-optic route planning)

C. A Search: The Gold Standard*

• How it works:
  • Combines UCS and Greedy: expands node with the lowest f(n) = g(n) + h(n).
  • Admissible heuristic ensures optimality.
  • Example: Finding the fastest route in Kathmandu traffic (heuristic: time to destination via major roads).
• Visual: A Search Tree*

  graph TD
    A["Start\nf(n)=0+5=5"] --> B["B1\ng(n)=2\nh(n)=3\nf(n)=5"]
    A --> C["B2\ng(n)=1\nh(n)=4\nf(n)=5"]
    B --> D["Goal\ng(n)=4\nh(n)=0\nf(n)=4"]
    C --> E["Goal\ng(n)=5\nh(n)=0\nf(n)=5"]

  Path taken: Start → B1 → Goal (lower f(n)).
• Worked Example: Daraz Delivery Route
  • Problem: Deliver packages to 3 locations (A, B, C) with traffic weights:
    • Start → A: 4, A → B: 2, B → C: 3, C → Goal: 1.
    • Heuristic h(n): Straight-line distance (A:3, B:2, C:1).
  • A Steps*:
    1. Start: f(n) = 0 + 3 = 3 → Expand A (f(n) = 4 + 2 = 6).
    2. Expand B (f(n) = 6 + 1 = 7) → Reach Goal via B → C (f(n) = 6 + 3 + 1 = 10).
    3. Alternative path Start → A → B → C has f(n) = 10 (same cost).
  • Optimal path: Start → B → C (if heuristic for B is accurate).
• Advantages:
  • Optimal if h(n) is admissible.
  • Efficient with good heuristics (e.g., Google Maps uses A* with traffic data).
• Disadvantages:
  • High memory if branching factor is large (e.g., protein folding simulations).
• Real-world use:
  • Google Maps/Waze: A* with real-time traffic heuristics.
  • Ncell’s 5G tower placement: A* to minimize signal loss (heuristic: terrain elevation).

2. Game Playing: Adversarial Search

Games involve two players with opposing goals (e.g., chess, tic-tac-toe). Key concepts:

A. Game Trees

• Structure:
  • Nodes = game states.
  • Edges = possible moves.
  • Maximizing player (e.g., white in chess) wants to maximize score.
  • Minimizing player (e.g., black) wants to minimize score.
• Visual: Tic-Tac-Toe Game Tree (Simplified)

  graph TD
    A["Start"] --> B["X at top-left"]
    B --> C["O wins\nScore: -10"]
    B --> D["X at top-center"]
    D --> E["O at middle\nScore: 0"]
    E --> F["X wins\nScore: +10"]

• Depth-first expansion: Only explore moves up to a depth limit (e.g., 4 ply in chess).

B. Minimax Algorithm

• How it works:
  1. Assign terminal scores (e.g., +1 for win, -1 for loss, 0 for draw).
  2. Propagate scores up the tree:
     • Maximizer picks the highest child score.
     • Minimizer picks the lowest child score.
  3. Assumption: Opponents play optimally.
• Worked Example: Tic-Tac-Toe
  • Tree:

    graph TD
      A["Start"] --> B["X at center"]
      B --> C["O at top-left\nScore: -1"]
      B --> D["O at top-center\nScore: +1"]

  • Scores:
    • If O plays at top-center, X can force a win → Score = +1.
    • Minimax chooses the move that leads to the best worst-case outcome.
• Advantages:
  • Guarantees optimal play if the tree is fully explored.
• Disadvantages:
  • Combinatorial explosion: Chess has ~10^120 possible games.
  • Horizon effect: May miss long-term strategies.

C. Alpha-Beta Pruning

• How it works:
  • Alpha: Best score the maximizer can guarantee so far.
  • Beta: Best score the minimizer can guarantee so far.
  • Prune branches where:
    • Maximizer’s child ≤ current alpha (no better than existing options).
    • Minimizer’s child ≥ current beta (no better than existing options).
• Visual: Pruned Game Tree

  graph TD
    A["Max\nα=-∞"] --> B["Move 1\nβ=+∞"]
    B --> C["Min\nScore: 3\nPruned"]
    B --> D["Min\nScore: 1"]
    D --> E["Max\nScore: 5"]

  Pruned: Move 1’s first child (score 3 > alpha after Move 2).
• Worked Example: Chess Engine
  • Scenario: Stockfish evaluates a position to depth 4.
  • Before pruning: 7 branches at each ply → 7^4 = 2401 nodes.
  • After pruning: ~10% of nodes evaluated (e.g., 240 nodes).
• Advantages:
  • Reduces search time by ~60% (for chess).
• Disadvantages:
  • Still limited by tree depth.

D. Evaluation Functions

• Purpose: Assign scores to non-terminal states (e.g., material advantage in chess).
• Components:
  • Material: Piece values (pawn=1, knight=3, queen=9).
  • Position: Center control, king safety.
  • Heuristics: Mobility, pawn structure.
• Example: Evaluating a chess position:
  • White: Queen + Rook = 18.
  • Black: Bishop + Knight = 6.
  • Score: 18 – 6 = +12 (White is better).

In the Real World

1. eSewa’s Service Locator

   • Idea: A* search with GPS heuristics.
   • How: When you search for an ATM, eSewa uses:
     • g(n) = driving time from your location.
     • h(n) = straight-line distance to ATM (heuristic).
   • Result: Fastest route suggestion, even with traffic (dynamic g(n)).

2. Daraz’s Dynamic Pricing

   • Idea: Game theory (Minimax-like bidding).
   • How: Daraz’s algorithm models:
     • Maximizer: Seller trying to maximize profit.
     • Minimizer: Buyer trying to minimize cost.
   • Example: If you bid ₹500 for a product, Daraz’s system predicts the seller’s counter-offer using a game tree of possible bids.

3. Ncell’s Network Congestion Prediction

   • Idea: Heuristic search + evaluation functions.
   • How: Ncell uses A* to:
     • Predict congestion hotspots (heuristic: historical usage patterns).
     • Redirect traffic via alternative towers (minimizing latency).
   • Real output:

4. Pathao’s Driver Assignment

   • Idea: Uniform Cost Search (UCS).
   • How: When you request a ride, Pathao:
     • Assigns the driver with the lowest g(n) (time to reach you).
     • Uses real-time traffic data to update edge weights dynamically.
   • Example: If Driver A is 2 km away but stuck in traffic (g(n)=10 mins), and Driver B is 3 km away but on a clear road (g(n)=8 mins), Pathao picks Driver B.

5. NEPSE Stock Trading Bots

   • Idea: Minimax with evaluation functions.
   • How: Algorithmic traders model:
     • Maximizer: Buy low, sell high.
     • Minimizer: Market volatility (sudden drops).
   • Evaluation function: Combines volume, price trends, and news sentiment.

3. Key Comparisons and Trade-offs

*If h(n) is admissible.

4. Common Pitfalls and Exam Tips

Pitfalls

1. Non-admissible heuristics: If h(n) overestimates (e.g., Euclidean distance in a grid with obstacles), A* may not find the optimal path.
   • Fix: Use consistent heuristics (e.g., Manhattan distance for grids).
2. Ignoring g(n): Greedy search only considers h(n), leading to suboptimal paths.
   • Fix: Always use f(n) = g(n) + h(n) for A*.
3. Assuming perfect play: Minimax assumes opponents play optimally, which is rare in real life.
   • Fix: Use probabilistic models (e.g., expectimax for uncertain opponents).

Exam Tip

1. Always show the search tree:
   • For A*, label nodes with g(n), h(n), and f(n).
   • For Minimax, highlight pruned branches in Alpha-Beta.
2. Define terms precisely:
   • Admissible heuristic: Never overestimates the true cost.
   • Consistent heuristic: h(n) ≤ h(m) + cost(n→m) (ensures A* finds optimal path).
3. Real-world mapping:
   • Pathfinding: Relate to Google Maps, Daraz delivery, or NTC routes.
   • Games: Relate to chess engines, Pathao’s ride pricing, or NEPSE trading bots.
4. Calculate step-by-step:
   • For A*, expand nodes in order of increasing f(n).
   • For Minimax, alternate between max and min layers.
5. Common exam questions:
   • "Why is A* better than Greedy?" → Combines g(n) and h(n) for optimality.
   • "How does Alpha-Beta prune the tree?" → Cuts branches where alpha ≥ beta.
   • "Give an admissible heuristic for the 8-puzzle." → Manhattan distance (sum of row+col differences for misplaced tiles).

5. Worked Example: A in Kathmandu Traffic*

Problem: Find the fastest route from Thapathali to Koteshwor during rush hour.

• Graph:

  Edge	Cost (mins)	Heuristic h(n) (mins)
  Thapathali → Putalisadak	5	10 (direct distance)
  Putalisadak → Koteshwor	8	2
  Thapathali → Ringroad	7	8
  Ringroad → Koteshwor	6	4

Steps:

1. Start: f(n) = 0 + 10 = 10.
2. Expand Putalisadak (f(n) = 5 + 2 = 7).
3. Expand Ringroad (f(n) = 7 + 4 = 11).
4. From Putalisadak, expand Koteshwor (f(n) = 5 + 8 + 2 = 15).
5. From Ringroad, expand Koteshwor (f(n) = 7 + 6 + 4 = 17).
6. Optimal path: Thapathali → Putalisadak → Koteshwor (total cost = 13 mins).

Why not Thapathali → Ringroad → Koteshwor?

• Higher f(n) (17 vs. 15), even though g(n) is slightly lower (13 vs. 13). The heuristic h(n) for Putalisadak is more accurate in this scenario.

6. Visual Summary: Search Algorithms

flowchart LR
    A["Uninformed Search"] --> B["BFS"]
    A --> C["DFS"]
    D["Informed Search"] --> E["Greedy<br/>(h(n) only)"]
    D --> F["A*<br/>(g(n)+h(n))"]
    D --> G["Uniform Cost<br/>(g(n) only)"]
    H["Game Playing"] --> I["Minimax"]
    I --> J["Alpha-Beta<br/>Pruning"]

Exam Tip

• For search algorithms: Always draw the search tree and label g(n), h(n), and f(n).
• For games: Show the game tree with scores and highlight pruned branches.
• Real-world tie-ins: Relate A* to navigation apps (Google Maps) and Minimax to competitive strategies (chess, Pathao pricing).
• Heuristic design: Practice designing admissible heuristics for classic problems (8-puzzle, sliding tiles).