Minimax and Alpha-Beta Pruning

Game-tree search is an extension topic beyond most interviews; it pays off in rounds that ask you to decide who wins a two-player game when both play optimally, and in game-AI discussions (tic-tac-toe, Connect Four, chess engines), where alpha-beta pruning is the standard follow-up.

Intuition

In a two-player, zero-sum game with perfect information, one player (MAX) wants the final score as high as possible and the other (MIN) wants it as low as possible. Draw the game tree: positions are nodes, moves are edges, finished games are leaves with a score.

• Minimax: the value of a MAX node is the maximum of its children's values; the value of a MIN node is the minimum. Computing it bottom-up gives the result of optimal play by both sides.
• Negamax: score every position from the point of view of the player to move. Then a position's value is the maximum over moves of the negated value of the resulting position, because whatever is good for the opponent is bad for you. One function replaces the MAX and MIN cases. "Predict the winner" style questions use exactly this: the best achievable score difference for the player to move.
• Win/lose games: a position is winning if some move leads to a losing position for the opponent (or wins immediately), and losing if every move leads to a winning position for the opponent.
• Memoization: different move orders often reach the same position, so cache the value of each position. When the position is "which items are used", a bit mask is a natural key.

Alpha-beta pruning computes the same root value while skipping branches that cannot change it. Carry a window [alpha, beta]: alpha is the best score MAX is already guaranteed elsewhere on the path, beta the best score MIN is already guaranteed. If while exploring a node the window closes (alpha >= beta), stop: the player above has a better alternative and will never let the game reach this node. With good move ordering (best moves first), alpha-beta examines about b^(d/2) leaves instead of b^d, which lets a search go roughly twice as deep in the same time.

When to use it in interviews / OAs

• "Two players take turns ... both play optimally ... return whether the first player wins / the maximum score the first player can get": minimax or negamax, usually with memoization (an interval DP or a bit-mask DP).
• The state is small enough to enumerate (n up to about 20 items for bit masks, or O(n^2) intervals).
• Designing a game AI (tic-tac-toe, Connect Four): minimax with alpha-beta, a depth limit, and a heuristic evaluation at the cutoff.
• When the game has huge or infinite state spaces, look instead for a mathematical invariant (parity, XOR of pile sizes for Nim); that theory is beyond this article.

Template

Minimax and alpha-beta on an explicit tree

A node is either a number (a leaf, scored from MAX's point of view) or a list of children:

import math


def minimax(node, maximizing: bool) -> float:
    if not isinstance(node, list):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)


def alphabeta(node, maximizing: bool, alpha: float = -math.inf, beta: float = math.inf) -> float:
    if not isinstance(node, list):
        return node
    if maximizing:
        value = -math.inf
        for child in node:
            value = max(value, alphabeta(child, False, alpha, beta))
            alpha = max(alpha, value)
            if alpha >= beta:
                break  # MIN above already has a better option: prune the remaining children
        return value
    value = math.inf
    for child in node:
        value = min(value, alphabeta(child, True, alpha, beta))
        beta = min(beta, value)
        if alpha >= beta:
            break  # MAX above already has a better option
    return value

The root value is exact; values returned from pruned subtrees are only bounds, which is enough for the parent to discard them.

Negamax with memoization: score difference

Players alternately take a number from either end of an array; both play optimally. The best margin for the player to move on nums[i..j] is the better of taking the left or the right end, minus the opponent's best margin on what remains:

from functools import cache


def first_player_margin(nums: list[int]) -> int:
    """(first player's total) - (second player's total) under optimal play."""
    @cache
    def best(i: int, j: int) -> int:  # margin for the player to move on nums[i..j]
        if i > j:
            return 0
        return max(nums[i] - best(i + 1, j), nums[j] - best(i, j - 1))

    return best(0, len(nums) - 1)

"Predict the winner" is first_player_margin(nums) >= 0. There are O(n^2) intervals and O(1) work each.

Win/lose search over a bit mask

Players alternately pick an unused integer from 1 to max_choosable and add it to a running total; whoever brings the total to at least desired_total wins. The set of used numbers determines the remaining total, so it alone identifies a position:

def can_i_win(max_choosable: int, desired_total: int) -> bool:
    if desired_total <= 0:
        return True
    if max_choosable * (max_choosable + 1) // 2 < desired_total:
        return False  # the total can never be reached, so nobody wins

    @cache
    def wins(used: int, remaining: int) -> bool:  # does the player to move force a win?
        for x in range(1, max_choosable + 1):
            bit = 1 << x
            if not used & bit and (x >= remaining or not wins(used | bit, remaining - x)):
                return True  # win now, or leave the opponent in a losing position
        return False

    return wins(0, desired_total)

Complexity

• Plain minimax visits every node: O(b^d) for branching factor b and depth d.
• Alpha-beta: still O(b^d) in the worst case (bad move ordering), about O(b^(d/2)) with perfect ordering. Space is O(d) for the recursion.
• Memoized game DP: (number of distinct positions) × (moves per position). first_player_margin is O(n^2); can_i_win is O(2^m * m) for m = max_choosable.

Common pitfalls

• Mixing perspectives. Either score leaves from MAX's view and alternate max/min, or score from the mover's view and negate (negamax). Mixing the two flips signs in subtle places.
• Memoizing without the full state. The key must include everything that affects the future: whose turn it is (unless using negamax), the remaining resources, the used set.
• Caching alpha-beta results as exact values. A pruned search returns a bound, not the exact value; a transposition table must record whether a stored value is exact, a lower bound or an upper bound.
• Forgetting immediate wins and impossible games: check "this move reaches the target" before recursing, and handle "nobody can ever reach the target" separately.
• Ties. Decide whether a draw counts as a win for the first player ("predict the winner" treats an equal score as a win).
• Python recursion depth for long games; convert interval DPs to bottom-up loops if n is large.

Interview variations

• Predict the winner and Stone Game: interval negamax as above (for the even-length Stone Game, the first player can always win by a parity argument).
• Can I win: win/lose search over a bit mask of used numbers.
• Guess number higher or lower II: minimax cost DP over intervals (minimize over your guess, maximize over the adversary's answer).
• Flip game II, cat and mouse style games: win/lose memoized search (cat and mouse needs careful handling of draws via retrograde BFS).
• Tic-tac-toe AI: minimax with alpha-beta; the empty board is a draw under optimal play.
• Nim and its variants: winning iff the XOR of pile sizes is non-zero, a closed form that replaces search.