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

Key Concepts and Techniques

1. Informed Search: Heuristic Search Algorithms

Informed search algorithms use heuristics (rules of thumb) to guide the search toward the goal state more efficiently than uninformed search (BFS/DFS). The key idea is to estimate the cost to reach the goal from any given state.

Heuristic Function (h(n))

A heuristic function estimates the cost from a node n to the goal. It must satisfy:

• Admissibility: Never overestimates the true cost (h(n) ≤ actual cost).
• Consistency (Monotonicity): For any node n and successor n', h(n) ≤ c(n, n') + h(n').

A Search Algorithm*

A* combines the benefits of Dijkstra’s algorithm (optimal path) and Greedy Best-First Search (fast but not always optimal). It uses:

• f(n) = g(n) + h(n)
  • g(n): Cost from start to node n (known).
  • h(n): Heuristic estimate from n to goal (unknown but admissible).

How A Works:*

1. Start at the initial node, add it to the open list (priority queue).
2. While the open list is not empty:
   • Expand the node n with the lowest f(n).
   • If n is the goal, return the path.
   • Else, generate successors, calculate f for each, and add to open list.
   • Move n to the closed list (explored nodes).
3. If open list is empty, no solution exists.

Worked Example: Delivery Route Optimization (Like Pathao/Khalti)

Suppose a delivery agent must go from Kathmandu to Pokhara via Bhaktapur and Dhulikhel, with the following heuristic distances (in km):

• h(Kathmandu) = 200 (direct distance to Pokhara).
• h(Bhaktapur) = 150.
• h(Dhulikhel) = 120.

Graph:

graph TD
    A["Kathmandu"] -->|"10"| B["Bhaktapur"]
    A -->|"15"| C["Dhulikhel"]
    B -->|"20"| D["Pokhara"]
    C -->|"25"| D

Step-by-Step A Search:*

Optimal Path: Kathmandu → Dhulikhel → Pokhara (total cost = 40 km). Why? A* picks the path with the lowest f(n) at each step, ensuring optimality.

2. Game Playing: Minimax and Alpha-Beta Pruning

Games involve adversarial search, where two players (MAX and MIN) take turns. The goal is to maximize/minimize the outcome.

Minimax Algorithm

• MAX player tries to maximize the score.
• MIN player tries to minimize the score.
• The algorithm recursively evaluates all possible moves to the terminal state (end of the game) and backpropagates the best value.

Game Tree Example (Tic-Tac-Toe):

Worked Example: Tic-Tac-Toe (Simplified) Assume the following payoffs:

• X wins: +10
• Draw: 0
• O wins: -10

Minimax Evaluation:

1. Leaf Nodes (Terminal States):

   • X wins at (2,1): +10
   • Draw at (2,2): 0
   • O wins at (1,3): -10

2. Backpropagation:

   • For O at (1,3), MIN chooses the worst option for MAX → -10.
   • For O at (2,1), MAX chooses the best between +10 (X wins) and 0 (draw) → +10.
   • For O at (2,2), MIN chooses 0 (draw).

3. Final Decision:

   • MAX picks the move leading to the highest value: X at (1,1) (value = +10).

Alpha-Beta Pruning

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

• Alpha (α): Best value that MAX can guarantee so far.
• Beta (β): Best value that MIN can guarantee so far.
• If α ≥ β, prune the remaining branches.

Example with Pruning:

Steps:

1. Start with α = -∞, β = +∞.
2. Evaluate X at (1,1):
   • O at (2,1) → X wins (+10). Update α = max(-∞, 10) = 10.
   • Since α (10) ≥ β (∞) is false, continue.
   • O at (2,2) → Draw (0). No change to α.
3. Now, evaluate X at (1,2):
   • O at (1,3) → O wins (-10). Since α (10) ≥ β (-10) is true, prune the rest of the subtree under X at (1,2).

Result: Only the left subtree is explored, saving computation.

3. Comparison of Search Algorithms

4. Applications in the Real World

1. Pathao/Khalti Delivery Routing

• Idea Used: A Search*
• How? Pathao optimizes delivery routes by:
  • Using g(n) = distance traveled so far.
  • Using h(n) = estimated distance to destination (e.g., straight-line distance via Google Maps API).
  • Avoiding traffic-heavy routes (dynamic h(n)).

2. Ncell’s Network Optimization

• Idea Used: A Search*
• How? Ncell uses A* to:
  • Route calls through the least congested towers.
  • Minimize latency by choosing the shortest path with the best signal strength (h(n)).

3. Daraz’s Warehouse Inventory Management

• Idea Used: Minimax + Alpha-Beta Pruning
• How? Daraz uses game theory to:
  • Predict customer demand (MAX player).
  • Optimize stock levels (MIN player: cost of overstocking vs. understocking).
  • Prune irrelevant demand scenarios to speed up decisions.

4. Chess Engines (Stockfish, Leela Chess Zero)

• Idea Used: Minimax with Alpha-Beta Pruning
• How? These engines:
  • Evaluate board positions using heuristics (e.g., piece values, mobility).
  • Prune millions of irrelevant moves to focus on promising ones.
  • Use transposition tables to cache previously evaluated positions.

5. Self-Driving Cars (Tesla, Ncell’s Autonomous Vehicles)

• Idea Used: A Search + Game Trees*
• How? Tesla’s Autopilot:
  • Uses A* to plan the shortest path around obstacles (h(n) = distance to goal + safety margin).
  • Models pedestrian/car interactions as a game tree (pedestrian = MIN player trying to cross; car = MAX player avoiding collision).

5. Limitations and Challenges

Solutions:

• Iterative Deepening A* (IDA*): Combines A* with depth-limited search.
• Monte Carlo Tree Search (MCTS): Used in AlphaGo for better heuristic learning.
• Reinforcement Learning: Adjusts h(n) dynamically (e.g., Tesla’s self-driving updates route heuristics based on real accidents).

Exam Tip

1. For A Search:*

   • Always show the priority queue (open list) and closed list in your worked example.
   • Explain why a heuristic is admissible (e.g., "Manhattan distance is admissible for grid-based paths").
   • Compare A* with Greedy Best-First Search (Greedy ignores g(n); A* considers both g(n) and h(n)).

2. For Minimax/Alpha-Beta:

   • Draw the game tree and mark pruned branches in Alpha-Beta.
   • Memorize the order of evaluation: MAX → MIN → MAX (alternating).
   • For Alpha-Beta, highlight where α ≥ β causes pruning.

3. Common Pitfalls:

   • Forgetting to expand nodes in order of increasing f(n) in A*.
   • Misapplying admissibility (e.g., using Euclidean distance as h(n) in a grid with obstacles).
   • In games, not evaluating terminal states correctly (e.g., missing a forced win).

4. Real-World Links:

   • Expect route optimization questions (like Pathao/Khalti).
   • Expect game theory questions (like Chess engines or Poker bots).
   • Always relate heuristics to real-world constraints (e.g., "traffic slows down h(n)").