Adversarial Search (Minimax & Alpha-Beta Pruning)

Recursive definition of the minimax value: terminal states return their utility; MAX chooses the child with the maximum minimax value; MIN chooses the child with the minimum.

Minimax with depth tracking

def minimax(state, is_max_turn, game):
    if game.terminal_test(state):
        return game.utility(state)

    if is_max_turn:
        best = float('-inf')
        for action in game.actions(state):
            val = minimax(game.result(state, action), False, game)
            best = max(best, val)
        return best
    else:
        best = float('inf')
        for action in game.actions(state):
            val = minimax(game.result(state, action), True, game)
            best = min(best, val)
        return best

def best_action(state, game):
    """Return the action that maximizes minimax value from root (MAX turn)."""
    return max(game.actions(state),
               key=lambda a: minimax(game.result(state, a), False, game))

Alpha-beta pruning — same result as minimax, far fewer node expansions

def alphabeta(state, alpha, beta, is_max_turn, game):
    """Alpha-beta pruning. alpha=best for MAX so far, beta=best for MIN so far."""
    if game.terminal_test(state):
        return game.utility(state)

    if is_max_turn:
        v = float('-inf')
        for action in game.actions(state):
            v = max(v, alphabeta(game.result(state, action), alpha, beta, False, game))
            if v >= beta:
                return v        # beta-cutoff: MIN won't allow this path
            alpha = max(alpha, v)
        return v
    else:
        v = float('inf')
        for action in game.actions(state):
            v = min(v, alphabeta(game.result(state, action), alpha, beta, True, game))
            if v <= alpha:
                return v        # alpha-cutoff: MAX won't allow this path
            beta = min(beta, v)
        return v

# Initial call from root (MAX turn)
# result = alphabeta(root_state, float('-inf'), float('inf'), True, game)

UCB1 score for node i: w_i = wins from node i, n_i = visits to node i, N = total parent visits, C = exploration constant (√2 is standard). The first term exploits; the second explores.

1. What is the minimax algorithm and when does it guarantee optimal play? (Answer: Minimax: MAX player maximises value; MIN player minimises value. Algorithm recursively computes the value of each game state by assuming both players play optimally. Returns the move that leads to the best guaranteed outcome under adversarial play. Guarantees optimal play when: the game is deterministic, two-player, zero-sum, perfect information. Does not guarantee: anything for non-adversarial opponents, stochastic games (need expectiminimax), or imperfect information games (poker).)
2. What is alpha-beta pruning and by how much can it reduce minimax search complexity? (Answer: Alpha-beta pruning: maintain α (best MAX value) and β (best MIN value found so far). Prune a branch if its value cannot affect the parent's decision. Example: if MAX already found a move with value 5, any MIN branch that has a value ≤ 5 is irrelevant — prune it. Complexity: minimax is O(b^d) where b = branching factor, d = depth. Alpha-beta best case (optimal ordering): O(b^{d/2}) — doubles the searchable depth. Average case (random ordering): O(b^{3d/4}). With move ordering (killer heuristic, history heuristic): approaches best case in practice.)
3. What is iterative deepening minimax and why is it preferred over fixed-depth search? (Answer: Iterative deepening: run minimax to depth 1, then 2, then 3, ... until time runs out. Use the deepest completed search's result. Advantages: (1) Anytime algorithm — always has a valid move available. (2) Time management — stops at exactly the time limit. (3) Shallow searches are fast (total overhead: only 1/(b-1) × deepest search). (4) Move ordering improves: nodes found at shallow depth are ordered first at deep search — approaching alpha-beta best case. Used in virtually every competitive chess engine.)
4. What is the horizon effect in game tree search and how do extensions address it? (Answer: Horizon effect: a fixed-depth search misses consequences that happen just beyond the search horizon. Example: a chess engine at depth 10 captures a pawn (gaining +1), but at move 11 the opponent checkmates — the engine doesn't see the checkmate. Extensions: quiescence search — extend search at 'noisy' positions (captures, checks) until the board is 'quiet.' Singular extensions — extend search at positions where one move is clearly best. These ensure the evaluated position is a stable snapshot, not a position mid-battle.)
5. What is Monte Carlo Tree Search (MCTS) and why did it revolutionise Go AI? (Answer: MCTS: iteratively builds a search tree by: (1) Selection: navigate from root using UCB1 score balancing exploration and exploitation. (2) Expansion: add a new node. (3) Simulation: play random (or policy-guided) games to the end from the new node. (4) Backpropagation: update win statistics up the tree. Evaluation by simulation rather than hand-crafted evaluation function. Revolutionised Go: designing a heuristic evaluation function for Go's enormous state space was intractable. MCTS + neural network policies (AlphaGo) achieved superhuman play without hand-crafted evaluation.)