Informed Search & Game Trees: Heuristics, A, Minimax, Alpha-Beta

TAKEAWAYS:

• Heuristics guide search algorithms toward solutions by estimating cost (e.g., Manhattan distance in pathfinding).
• A* combines uniform-cost search with heuristics for optimal pathfinding, balancing exploration and efficiency.
• Game trees model adversarial decisions (e.g., chess, poker), where players alternate moves to maximize/minimize outcomes.
• Minimax ensures optimal play by assuming opponents act rationally, but suffers from exponential complexity.
• Alpha-Beta pruning cuts unnecessary branches in game trees, drastically improving efficiency (e.g., used in chess engines).
• Evaluation functions assign scores to game states (e.g., material advantage in chess) to guide decision-making.

1. Informed Search: Heuristic Search Algorithms

Informed (or heuristic) search algorithms use additional knowledge (heuristics) to guide the search toward the goal, unlike blind search (BFS/DFS). They are admissible (never overestimate cost) and consistent (heuristic h(n) ≤ estimated cost f(n) = g(n) + h(n)).

Key Heuristics

• Admissible Heuristic: Never overestimates the true cost to reach the goal. Example: Manhattan distance in grid-based pathfinding (sum of horizontal/vertical steps).
• Consistent Heuristic: Satisfies h(n) ≤ c(n, a, n') + h(n') for any successor n'. Example: Euclidean distance in continuous spaces.

A Search Algorithm*

A* is the most popular informed search, combining:

• g(n): Cost from start to node n (like uniform-cost search).
• h(n): Heuristic estimate from n to goal.
• f(n) = g(n) + h(n): Total estimated cost (priority for expansion).

How A Works*:

1. Start at the initial node, add to open list (priority queue).
2. Expand the node with the lowest f(n).
3. Generate successors, calculate g(n) and h(n), add to open list.
4. Repeat until goal is found or open list is empty.

Worked Example: Grid Pathfinding Scenario: Find the shortest path from (0,0) to (4,4) in a grid with obstacles. Heuristic: Manhattan distance. Assume no obstacles for simplicity.

Start: (0,0), g=0, h=8 → f=8
Expand (0,0) → successors:
- (1,0): g=1, h=7 → f=8
- (0,1): g=1, h=7 → f=8

Continue expanding nodes with lowest f until goal is reached.

Visual: A Search Tree*

graph TD
    A["(0,0)\nf=8"] --> B["(1,0)\nf=8"]
    A --> C["(0,1)\nf=8"]
    B --> D["(2,0)\nf=6"]
    B --> E["(1,1)\nf=6"]
    C --> F["(0,2)\nf=6"]
    E --> G["(2,1)\nf=4"]
    G --> H["(3,1)\nf=3"]
    H --> I["(4,1)\nf=2"]
    I --> J["(4,2)\nf=1"]
    J --> K["(4,3)\nf=0"]
    K --> L["(4,4)\nGOAL\ng=8"]

Path taken: (0,0) → (1,0) → (2,0) → (3,0) → (4,0) → (4,1) → (4,2) → (4,3) → (4,4).

Advantages of A*:

• Optimal if heuristic is admissible.
• More efficient than BFS/DFS for large spaces. Disadvantages:
• High memory usage (stores all nodes).
• Performance degrades with poor heuristics.

2. Game Playing: Adversarial Search

Games involve two or more players with opposing objectives (e.g., chess, tic-tac-toe). Game trees model possible moves and outcomes.

Game Tree Structure

• Nodes: Game states (board configurations).
• Edges: Legal moves.
• Terminal Nodes: End of game (win/lose/draw).
• Utility Values: Scores assigned to terminal nodes (e.g., +1 for win, -1 for loss).

Example: Tic-Tac-Toe Game Tree

graph TD
    A["Start"] --> B["X moves"]
    B --> C1["X wins"]
    B --> C2["O moves"]
    C2 --> D1["O wins"]
    C2 --> D2["X moves again"]
    D2 --> E1["X wins"]
    D2 --> E2["Draw"]

Depth: 9 (maximum moves in tic-tac-toe).

Minimax Algorithm

Assumes:

• Players alternate turns (maximizer/minimizer).
• Opponents play optimally (worst-case for you = best-case for them).

Steps:

1. Start from terminal nodes, assign utility values.
2. Propagate values up the tree:
   • Maximizer: Chooses the maximum child value.
   • Minimizer: Chooses the minimum child value.
3. Root node’s value = optimal outcome.

Worked Example: Tic-Tac-Toe Board after 2 moves (X and O):

X |   |
---------
  | O |
---------
  |   |

Possible moves for X (maximizer):

1. Top-right → leads to X win (utility = +1).
2. Middle-left → leads to draw (utility = 0).
3. Bottom-right → leads to O win (utility = -1). Minimax choice: Top-right (highest utility).

Visual: Minimax Tree

graph TD
    A["Root\n(X turn)"] --> B["Move 1\n+1"]
    A --> C["Move 2\n0"]
    A --> D["Move 3\n-1"]
    B --> E["X wins"]
    C --> F["Draw"]
    D --> G["O wins"]

Disadvantages of Minimax:

• Exponential time complexity (e.g., chess has ~10^120 possible games).
• Inefficient for deep trees.

3. Alpha-Beta Pruning

Optimization for Minimax that eliminates unnecessary branches by tracking:

• Alpha (α): Best value so far for the maximizer.
• Beta (β): Best value so far for the minimizer.

How it works:

1. Traverse the tree, comparing node values with α/β.
2. Prune a branch if:
   • Maximizer’s child ≤ α (no better than previous max).
   • Minimizer’s child ≥ β (no better than previous min).

Worked Example: Tic-Tac-Toe with Alpha-Beta Same board as above, but prune suboptimal branches.

• After evaluating Move 1 (utility = +1), set α = +1.
• For Move 2 (utility = 0), since 0 ≤ α, prune its subtree.
• Only Move 1 and Move 3 are evaluated fully.

Visual: Alpha-Beta Pruned Tree

graph TD
    A["Root\nα=-∞, β=+∞"] --> B["Move 1\n+1\nα=+1"]
    A --> C["Move 2\n0\nPRUNED"]
    A --> D["Move 3\n-1"]
    B --> E["X wins"]
    D --> G["O wins"]

Advantages:

• Reduces time complexity from O(b^m) to O(b^{m/2}) (b = branching factor, m = depth).
• Used in chess engines (e.g., Stockfish), Go (AlphaGo).

4. Evaluation Functions for Games

Not all games have terminal nodes (e.g., chess). Evaluation functions estimate state values:

• Material advantage: Piece values in chess (pawn=1, knight=3, queen=9).
• Positional factors: King safety, pawn structure.
• Heuristics: Distance to goal in racing games.

Example: Chess Evaluation State: White to move, material = +2 (extra pawn). Evaluation: +2 (simplified; real engines use hundreds of factors).

In the Real World

1. eSewa (Nepal):

   • Uses A* for optimal route planning in delivery logistics.
   • How: Heuristic = straight-line distance between delivery points, adjusted for traffic (real-time data).
   • Impact: Reduces fuel costs and delivery time by 20–30%.

2. Pathao (Ride-Hailing App):

   • Minimax-like bidding for driver assignments.
   • How: Drivers (maximizers) bid for rides; Pathao (minimizer) assigns to maximize profit while keeping wait times low.
   • Real Example: During peak hours, Pathao’s algorithm prioritizes rides with high surge pricing to balance driver earnings and user costs.

3. Ncell’s Network Optimization:

   • Alpha-Beta pruning in call-routing algorithms.
   • How: When a call is routed through multiple towers, the algorithm prunes suboptimal paths (e.g., towers with high latency) to ensure the fastest connection.
   • Real Example: During festivals (like Dashain), Ncell uses this to reduce call drops by dynamically rerouting calls away from congested towers.

4. Daraz’s Warehouse Robotics:

   • A* for autonomous forklifts in fulfillment centers.
   • How: Forklifts navigate aisles to pick orders, using Manhattan distance heuristics to avoid collisions and minimize travel time.
   • Worked Example: A forklift at (0,0) must pick items at (5,3) and (2,7). A* calculates the optimal path as (0,0) → (2,0) → (2,3) → (2,7) → (5,7) → (5,3), reducing travel by 30% vs. BFS.

5. NEPSE Stock Trading Bots:

   • Game-theory models (Minimax variants) for predicting market moves.
   • How: Bots treat other traders as adversaries, using historical data to estimate "utility" (profit/loss) of buy/sell decisions.
   • Real Example: During volatile trading days, bots prune low-probability scenarios (like sudden policy changes) using Alpha-Beta to focus on high-impact moves.

5. Comparing Search Algorithms

*Assumes admissible heuristic.

6. Practical Considerations

• Heuristic Design:

  • Too optimistic → suboptimal paths.
  • Too pessimistic → behaves like BFS.
  • Example: In traffic routing, underestimating congestion leads to failed deliveries.

• Game Complexity:

  • Chess: ~80 million possible positions after 4 moves.
  • Go: ~10^760 possible games (AlphaGo uses Monte Carlo Tree Search instead).

• Real-Time Constraints:

  • Robots: Must use A* with pruning to act within milliseconds.
  • Stock Trading: Alpha-Beta with time limits to avoid missing trades.

Exam Tip

1. For A*:

   • Always show g(n), h(n), and f(n) in worked examples.
   • Explain why a heuristic is admissible/consistent.
   • Common Pitfall: Forgetting to include g(n) in f(n) (just use h(n)).

2. For Minimax/Alpha-Beta:

   • Draw the game tree and label maximizer/minimizer levels.
   • Highlight pruned branches in Alpha-Beta and justify cuts.
   • Exam Question: "Why is Alpha-Beta better than Minimax?" → Answer: "It reduces time complexity by pruning branches that cannot influence the final decision."

3. Applications:

   • Link A* to route optimization (eSewa, GPS).
   • Link Minimax to strategy games (chess, poker).
   • Link Alpha-Beta to resource allocation (Ncell towers, Daraz robots).

4. Numerical Problems:

   • Practice calculating f(n) for A* and evaluating game trees.
   • Example Question:

     "In a grid with obstacles, calculate the path from (0,0) to (3,3) using A with Manhattan distance. Show the open list after 2 expansions."* Solution: Expand (0,0) → (1,0) and (0,1), then (1,0) → (2,0) and (1,1). Show f(n) values.

5. Short-Answer Tips:

   • Define admissible heuristic: "A heuristic that never overestimates the true cost to the goal."
   • Define Alpha-Beta pruning: "An optimization for Minimax that eliminates branches that cannot affect the final decision."
   • Fill-in-the-Blank: "A* is optimal if the heuristic is ___." → "admissible."