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

The Model Workshop swaps the map for a chessboard. After you make a move, the world doesn't just keep going along fixed edges, instead, your opponent picks the response that's most harmful to you. Standard shortest-path algorithms only model environmental transitions; game-tree search must also model other agents' goals and information.

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 deep cutoff, evaluation function, and transposition;
• Distinguish adversarial nodes, random nodes, and hidden information.

1. The Recursive Meaning of Minimax

For MAX players:

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

For MIN players:

$$ V(s)=\min_{a\in A(s)}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.

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 of the current node cannot affect the ancestor's choice, so we can stop expanding. Pruning does not change the minimax value.

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

The value itself cannot move:

def choose_action(state, depth, game):
    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

A tie-breaking strategy should be clearly defined: stable selection, randomization to break ties, preference for winning sooner rather than failing later. It does not alter utility values but influences behavior and reproducibility.

4. Deep Truncation and Evaluation Function

The large board can't reach the endgame and must terminate at depth $d$, using evaluate(state) as an estimate. The evaluation function should:

• Consistent with the direction of final utility;
• Maintain symmetry in symmetric positions;
• Affordable to calculate;
• Has discernment in key tactics;
• Verify in independent mode and during gameplay.

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;
• captures/checks and other rule-related fields;
• 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.
• The evaluation function score is just win rate, unless properly defined and calibrated.
• 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

Opposition search transforms environmental state transitions into choices made by other decision-makers. Minimax's guarantees stem from the assumption of a clear game, alpha-beta pruning reduces unnecessary search expansions via upper and lower bounds; depth, evaluation function, caching, and uncertainty determine whether it can be deployed in real systems.

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.