1.3 Minimax, Alpha-Beta, and Uncertainty: Opponents Are Also Making Choices

Path planning on a board has an extra complication: the opponent has plans too. Each move must account for possible responses. Game-tree search therefore represents other decision-makers' goals and information to evaluate the consequences of an action.

Minimax is suitable for deterministic, alternating-move, fully observable, zero-sum games. Beyond these assumptions, chance nodes, belief states, game solving, or sampling methods are needed, and the recursive approach cannot be mechanically applied.

This lesson's objectives

• Define minimax values using a terminal utility;
• Explain the bounds, correctness, and move ordering of alpha-beta pruning;
• Handle depth cutoffs, evaluation functions, and transpositions;
• Distinguish adversarial nodes, random nodes, and hidden information.

1. The Recursive Meaning of Minimax

For MAX players:

$$V(s)=\underset{a\in A(s)}{max}V(Result(s,a)).$$

For MIN players:

$$V(s)=\underset{a\in A(s)}{min}V(Result(s,a)).$$

Return a utility from a fixed perspective, such as win +1, draw 0, and loss -1. MIN is not "randomly choosing a suboptimal move," but rather knowing the position and minimizing MAX's outcome.

The Python 3 examples are interface fragments (partial). The caller implements legal actions, transitions, terminal checks, and scores on game. They assume alternating turns, at least one legal action in every nonterminal state, and scores from MAX's perspective throughout.

def minimax_value(state, player, game):
    if game.is_terminal(state):
        return game.utility(state)  # Always start from MAX Viewpoint

    children = [
        minimax_value(game.result(state, action), game.next_player(player), game)
        for action in game.actions(state)
    ]
    return max(children) if player == game.max_player else min(children)

In a finite tree, it gives the value under optimal play from both sides. When real opponents don't play optimally, minimax can be overly conservative, but "opponent modeling" should rely on verification rather than hope.

2. Alpha-Beta Pruning Eliminates Branches That Can't Affect the Final Decision

• $\alpha$: the best (lower) bound guaranteed by the current path for MAX;
• $\beta$: The best (tightest) upper bound guaranteed by the current path in MIN.

When $\alpha \ge \beta$, the remaining subtree cannot change the ancestor's choice, so expansion stops without changing the root minimax value. Suppose MAX already has an option worth 4. At another MIN child, a successor worth 2 establishes an upper bound of 2, so the remaining successors can be skipped. See Berkeley CS 188 on alpha-beta pruning for this bound.

def alpha_beta(state, depth, alpha, beta, player, game):
    if game.is_terminal(state):
        return game.utility(state)
    if depth == 0:
        return game.evaluate(state)

    if player == game.max_player:
        value = float("-inf")
        for action in game.ordered_actions(state):
            child = game.result(state, action)
            value = max(value, alpha_beta(
                child, depth - 1, alpha, beta,
                game.next_player(player), game,
            ))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value

    value = float("inf")
    for action in game.ordered_actions(state):
        child = game.result(state, action)
        value = min(value, alpha_beta(
            child, depth - 1, alpha, beta,
            game.next_player(player), game,
        ))
        beta = min(beta, value)
        if alpha >= beta:
            break
    return value

The worst-case order still approaches $O(b^d)$; the ideal order can get close to $O(b^{d/2})$. Pruning isn't just "adding two lines at zero cost": sorting, caching, and implementation overhead all come with costs.

3. The root node also needs to return an action

A score alone cannot select a move:

def choose_action(state, depth, game):
    if game.is_terminal(state):
        return None, game.utility(state)
    if depth < 1:
        raise ValueError("choose_action requires depth >= 1")
    best_action = None
    best_value = float("-inf")
    alpha, beta = float("-inf"), float("inf")

    for action in game.ordered_actions(state):
        value = alpha_beta(
            game.result(state, action), depth - 1,
            alpha, beta, game.min_player, game,
        )
        if value > best_value:
            best_value, best_action = value, action
        alpha = max(alpha, best_value)

    return best_action, best_value

This root function assumes MAX is to move. It returns no action at a terminal state and requires depth at least 1 otherwise: starting recursion at negative depth would miss the depth == 0 cutoff. Define tie-breaking too: stable selection, random choice, or a preference for earlier wins or later losses among equal-utility actions.

4. Depth cutoffs and evaluation functions

Searching a large game tree to terminal states is usually impractical. Stop at depth $d$ and estimate the value with evaluate(state). The evaluation function should:

• Use the same score direction as terminal utility;
• Give equal values to symmetric positions;
• Be cheap enough to compute during search;
• Distinguish relevant tactical positions;
• Be evaluated on held-out positions and in games.

Fixed depth leads to a horizon effect: a disaster occurs just beyond the visible range. Use quiescence search to continue exploring in unstable positions, or iterative deepening to gradually increase search depth within a time budget.

5. Move ordering determines pruning efficiency

Prioritize searching for the potentially best move that can tighten alpha/beta earlier:

• The principal variation from the previous round of iterative deepening;
• Domain rules such as captures and checks;
• killer/history heuristic;
• Lightweight evaluation function or learning model.

A bad ordering doesn't change the final alpha-beta value, it only reduces pruning; but at time cutoff, the order does affect the final answer.

6. Transposition table

Different move orders can lead to the same position. Caching search results using a position key can avoid redundant calculations, but the cache entries need:

state key (including whose turn it is, rule state)
searched depth
value
bound type: EXACT / LOWER / UPPER
best move

The values returned by pruning are sometimes just bounds and shouldn't always be treated as exact. Compact keys like Zobrist hashes still need to handle collision risks.

7. Random Events: Expectiminimax

Rolling dice, random drops, and similar events are not player choices, they should be added to the chance node:

$$V(s)=\sum _{o}P(o\mid s,a)V(Result(s,a,o)).$$

Letting MIN incorrectly choose the worst dice outcome is overly pessimistic; relying solely on expectations depends on the correctness of the probability model. Risk-sensitive tasks may also care about tail losses, rather than the expected value alone.

8. Hidden information is not a regular chance node

In incomplete-information games like poker, players don't know the true state. We need to model information sets and beliefs, consider strategy randomization, and have opponents infer information from actions. Treating unknown hands as if they're randomly redrawn at each step violates information consistency.

Monte Carlo Tree Search (MCTS) focuses on promising branches through selection, expansion, simulation, and backup, making it well-suited for large search spaces or scenarios with generative models; however, its performance depends on exploration policies, simulation strategies, and computational budget, it does not automatically replace minimax.

9. Test a game searcher

You must choose a winning move when you win immediately
We must stop our opponent from winning the next move.
Symmetric positions have equal values
Alpha-beta and complete minimax yield the same value on small trees
Different move orderings do not affect the final search value.
A transposition switch doesn't change the outcome.
The time limit always returns a valid action at the depth of completion

Common Misconceptions

• Minimax works for all competitive scenarios: it assumes zero-sum, alternating turns, deterministic, and complete information.
• Alpha-beta is always $O(b^{d/2})$: This is the ideal time complexity for action ordering.
• An evaluation score is a win probability: only if it has been defined and calibrated that way.
• Cached values can all be directly reused: Pruning values might just be bounds.

Practice

1. Implement utility and state key for tic-tac-toe termination, and verify rotational symmetry.
2. Compare the number of expanded nodes for the three move ordering methods.
3. Add a chance node to the dice-based game and compare it with the worst-case strategy.
4. Add a transposition table to alpha-beta search and correctly store bound types.

Summary

Adversarial search accounts for other decision-makers' choices. Minimax depends on explicit game assumptions; alpha-beta uses bounds to skip branches that cannot affect the root value. Depth limits, evaluation quality, caching, and uncertainty determine its practical usefulness.

The next chapter addresses knowledge representation and reasoning: when agents don't just need to search through states, but also express facts, constraints, and uncertain relationships, the representation method determines what can be inferred.