Depth-First Search (DFS): Going Deep

Imagine you're exploring a maze. Depth-First Search is like always taking the first path you see and following it as far as possible before backtracking.

How DFS Works:

1. Start at initial state
2. Pick a successor and go there
3. Keep picking successors and going deeper
4. If you hit a dead end, backtrack to the most recent choice point
5. Try the next unexplored option

The Algorithm (in simple terms):

Create a stack (like a stack of cafeteria trays)
Put the starting state on top
While the stack isn't empty:
    Take the top state off the stack
    If it's the goal, we're done!
    Otherwise, generate all its successors
    Put the new successors on top of the stack

DFS in Action - Simple Example:

    1
   / \
  2   3
 /   / \
4   5   6

Breadth-First Search (BFS): Going Wide

BFS is like exploring all rooms on the current floor before going upstairs.

How BFS Works:

1. Start at initial state
2. Explore ALL immediate successors first
3. Then explore all successors of those successors
4. Continue layer by layer

The Algorithm:

Create a queue (like a line at the bank)
Put the starting state at the back of the line
While the queue isn't empty:
    Take the front state from the line
    If it's the goal, we're done!
    Otherwise, generate all its successors
    Put the new successors at the back of the line

BFS on the same example:
BFS would explore: 1 → 2, 3 → 4, 5, 6

Which is Better?

BFS guarantees the optimal solution - it finds the goal that requires the fewest steps.

DFS is often more memory-efficient and can find solutions faster, but they might not be optimal.

The choice depends on your problem! For GPS navigation, you want the shortest route (BFS-style thinking). For exploring possibilities in a game, DFS might work fine.

The A* Algorithm: Best of Both Worlds

A* combines what we know (how far we've come) with what we estimate (how far we have to go):

A* Evaluation Function:

f(s) = g(s) + h(s)

Where:
- g(s) = sum of cost from initial state to reach state s
- h(s) = estimated cost from s to nearest goal  
- f(s) = estimated total cost of solution through s

A* Algorithm:

Create a priority queue (like an emergency room - most urgent first)
Add starting state with priority f(start)
While queue isn't empty:
    Remove state with lowest f value
    If it's the goal, we're done!
    For each successor:
        Calculate f = g + h
        Add to queue with this priority

The Power of Admissible Heuristics

A heuristic is admissible if it never overestimates the actual cost. Think of it as being "optimistically realistic" - you might underestimate how far you have to go, but you'll never overestimate.

Mathematical definition:
For all states s: 0 ≤ h(s) ≤ h*(s)

Where h*(s) is the true shortest distance to the goal.

Why this matters: If h(s) is admissible, A* is guaranteed to find the optimal solution!

A* in GPS Navigation

When your GPS calculates a route:

• g(s) = distance you've already traveled
• h(s) = straight-line distance to destination (admissible!)
• f(s) = estimated total trip distance

The GPS explores routes with the lowest f values first, ensuring you get an optimal path.

Minimax: The Foundation of Game AI

The core insight is simple:

• On your turn: Choose the move that maximizes your score
• On opponent's turn: They'll choose the move that minimizes your score

Minimax Algorithm:

If it's my turn (MAX):
    Pick the action with the highest value
    
If it's opponent's turn (MIN):  
    Opponent picks the action with the lowest value (for me)

Minimax in Action: Tic-Tac-Toe

       My Turn (MAX)
      /      |      \
   O's Turn  O's Turn  O's Turn
    (MIN)     (MIN)     (MIN)
   /  |  \   /  |  \   /  |  \
  +1  0 -1  +1 -1  0  -1 +1  0

Where: +1 = I win, 0 = draw, -1 = I lose

The algorithm works backwards:

1. Calculate values at terminal positions (+1, 0, -1)
2. MIN nodes: opponent picks lowest value
3. MAX nodes: I pick highest value
4. Propagate values up the tree

The Minimax Algorithm in Detail:

MaxTurn(state):
    If cutoff(state): return evaluation(state)
    value = negative infinity
    For each possible action:
        child_value = MinTurn(result of action)
        if child_value > value:
            value = child_value
            best_action = action
    return value, best_action

MinTurn(state):
    If cutoff(state): return evaluation(state)  
    value = positive infinity
    For each possible action:
        child_value = MaxTurn(result of action)
        if child_value < value:
            value = child_value
            best_action = action
    return value, best_action

Alpha-Beta Pruning: Making Minimax Efficient

The brilliant insight: you don't need to explore every branch!

Key Idea: If you find a move that's worse than something you've already found, stop looking at that branch.

Example:

        MAX
       /    \
    MIN      MIN
   /  |     /  |  \
  5   4    ?  ?  ?

Alpha-Beta Rules:

• Alpha (α): Best value MAX can guarantee so far
• Beta (β): Best value MIN can guarantee so far
• Prune when α ≥ β: No need to explore further

This can reduce the search tree dramatically while finding the exact same answer!

Real-World Impact: Deep Blue vs. Kasparov (1997)

Deep Blue's victory over world champion Garry Kasparov used minimax with alpha-beta pruning, plus many refinements:

• Sophisticated evaluation functions
• Move ordering to improve pruning
• Specialized hardware
• Opening books and endgame databases

The Four Steps of MCTS

1. Selection: Navigate down the tree using a smart formula that balances:

• Exploitation: Go toward moves that have worked well
• Exploration: Try moves that haven't been tested much

UCT (Upper Confidence bound applied to Trees) Formula:

Choose move i that maximizes:
[Wins_i / Plays_i] + c × √(ln(Total_Plays) / Plays_i)

Where:
- Wins_i / Plays_i = win rate for move i
- Second term = exploration bonus (larger for less-tried moves)
- c = exploration parameter (typically √2)

2. Expansion: When you reach a leaf node (a position with untried moves), add one new child node for an untried move.

3. Simulation: From this new position, play a complete random game to the end. This is called a "playout" or "rollout."

4. Backpropagation: Take the result (win/loss) and update statistics for every node on the path back to the root.

MCTS Algorithm:

While time remaining:
    # Selection: Navigate to leaf using UCT
    leaf = select_best_path_to_leaf(root)
    
    # Expansion: Add one new child
    child = add_new_child(leaf)
    
    # Simulation: Play random game to end
    result = play_random_game(child)
    
    # Backpropagation: Update all nodes on path
    update_path_statistics(child, result)

# Choose move that was simulated most often    
return most_simulated_move(root)

Why MCTS Works: The Multi-Armed Bandit Connection

MCTS treats move selection like a "multi-armed bandit" problem - imagine slot machines with different payout rates. You want to:

• Try each machine enough to estimate its payout
• Spend most time on the best machines
• Still occasionally try other machines in case you were wrong

The UCT formula solves this mathematically, with theoretical guarantees about minimizing regret!

MCTS Success Stories

AlphaGo (2016): Defeated Lee Sedol 4-1

• Combined MCTS with deep neural networks
• Neural networks guided both selection and evaluation
• Revolutionized computer Go

Beyond Go:

• Poker: Handle incomplete information through simulation
• Real-time strategy games: Manage complex state spaces
• General game playing: Works without game-specific knowledge

Benefits of MCTS:

1. No evaluation function needed: Just simulate to the end
2. Anytime algorithm: Can stop and make a decision whenever time runs out
3. Handles large branching factors: Naturally focuses on promising moves
4. Theoretically grounded: Mathematical guarantees about convergence