Minimax Algorithm Theory Guide

Rules & Common Mistakes

• Exam Trap: Never Trace Horizontally — Minimax Runs Depth-First

  The most common first mistake is trying to fill in an entire level before moving up. Students work across all the leaf nodes, then try to fill in every node on the next level up, and immediately get stuck. You cannot evaluate a parent until every one of its specific children is resolved — and those children may be on completely different branches. The only valid approach is vertical: plunge straight down the leftmost branch all the way to the leaves, resolve it fully, then move to the next branch. Treat it like a DFS call stack, not a spreadsheet you fill in row by row.
• Exam Trap: The Highest Number in the Tree Is Not Always $MAX$'s Score

  Scan any Minimax tree and your eye will jump straight to the biggest leaf value. Do not chase it. If a $MIN$ node sits directly above that leaf, $MIN$ is the gatekeeper — and $MIN$ will never hand $MAX$ the highest value on that branch. It will pick the lowest value available instead. You do not get the maximum number in the tree. You get the maximum value among the outcomes $MIN$ is willing to allow. Always ask who controls the node above a leaf before assuming $MAX$ can reach it.
• Exam Trap: Label Every Row Before You Write a Single Value

  By the time you reach depth 3 or 4, it is dangerously easy to forget whose turn it is and accidentally apply a $MIN$ operation at a $MAX$ node — or vice versa. One wrong assignment cascades up the entire tree and invalidates your root value. The physical fix: before touching any numbers, take your pencil and write $MAX$ or $MIN$ aggressively next to every single level of the tree. Do it first, do it clearly, and never skip it. It costs you ten seconds and saves you from throwing away correct leaf work on a labelling error.
• Pro Tip: Depth-Limited Heuristic Values Are Just Leaf Values — Treat Them Identically

  Exam trees rarely run all the way to an actual win or loss. Most are cut off at depth 3 or 4 and use heuristic scores — estimated values a professor assigned to represent how good a position looks. Students see these and freeze, unsure whether the game is over or whether they need to do something extra. The rule is simple: it does not matter. Whether the number at the bottom of the tree is a real terminal utility or a heuristic estimate, your job is identical — read it, write it on the node, and pass it up. The Minimax logic above it does not change.

Strengths, Weaknesses & When To Use It

When to use it:In the real world, pure Minimax is almost never used in production — Alpha-Beta Pruning is a strict upgrade that finds the identical answer with far less work, so there is no reason to run the unoptimized version on a real game. The one place Minimax still gets used is tiny, trivial games like Tic-Tac-Toe, where the tree is so small that the inefficiency does not matter. On an exam, use Minimax when the question explicitly asks for an unoptimized trace, when you need to count the exact number of nodes a full tree evaluation visits, or when you are being asked to establish the worst-case baseline before introducing Alpha-Beta as an improvement.

Standard Minimax vs. Alpha-Beta Pruning

You cannot fully understand Alpha-Beta Pruning without first mastering Minimax — because they are the same algorithm at their core. The alternating $MAX$ and $MIN$ recursion, the depth-first traversal, the value propagation from leaves to root — Alpha-Beta inherits all of it unchanged. The only thing Alpha-Beta adds is a memory of what has already been guaranteed on the current path. Minimax is the brute-force baseline that proves the logic works. Alpha-Beta is Minimax that learned to stop wasting time.

• Evaluation Strategy: Minimax is exhaustive by design — it visits every single node in the tree without exception, regardless of what it has already found. Alpha-Beta is selective — the moment it can prove a branch cannot change the root decision, it stops expanding it entirely. Minimax sees everything. Alpha-Beta only looks at what matters.
• Memory and State: Minimax is effectively memoryless — each node only cares about the values bubbling up from its immediate children, with no knowledge of what was secured higher up the tree. Alpha-Beta requires passing history downward — the $\alpha$ and $\beta$ bounds inherited from every ancestor on the current path. Minimax asks 'what do my children return?' Alpha-Beta asks 'what have my ancestors already guaranteed?'
• Sensitivity to Move Ordering: Minimax is completely indifferent to move ordering — best moves on the left or right, it evaluates everything and always takes exactly $O(b^m)$ time. Alpha-Beta's efficiency is entirely dictated by ordering. Perfect ordering halves the exponent to $O(b^{m/2})$; reverse ordering degrades it all the way back to $O(b^m)$. For Minimax, order is irrelevant. For Alpha-Beta, order is everything.
• What Your Exam Is Actually Testing: If a professor asks you to trace Minimax, they are testing whether you understand the alternating $MAX$/$MIN$ recursive logic and can correctly propagate values from leaves to root. If they ask you to trace Alpha-Beta, they are testing whether you understand the boundary math — when $\alpha$ and $\beta$ cross and why a branch becomes irrelevant. The mechanics differ, but both algorithms return the exact same final answer at the root.

Implementation Pseudocode

// Minimax evaluates every node in the tree — no shortcuts, no skipping
// isMaximizing: true means it is MAX's turn, false means it is MIN's turn
// The function recurses all the way down to the leaves before any value is returned

function minimax(node, depth, isMaximizing):

    // BASE CASE: Reached a leaf node or the depth limit
    // Return the node's utility value directly — no comparison needed, just read and pass it up
    if depth == 0 or node is a terminal node:
        return node.value


    // ── MAX'S TURN ──────────────────────────────────────────────────────
    if isMaximizing:

        // Start at absolute floor — so low that the very first child value will always beat it
        // This guarantees bestValue gets replaced on the first comparison, never stays at -Infinity
        bestValue = -Infinity

        for each child in node.children:

            // Recurse into the child — it is now MIN's turn, so pass false
            childValue = minimax(child, depth - 1, false)

            // max(a, b): returns whichever value is higher
            // Replaces bestValue only if this child returned something better for MAX
            bestValue = max(bestValue, childValue)

        // Return the highest value found across all children
        return bestValue


    // ── MIN'S TURN ──────────────────────────────────────────────────────
    else:

        // Start at absolute ceiling — so high that the very first child value will always beat it
        // This guarantees bestValue gets replaced on the first comparison, never stays at +Infinity
        bestValue = +Infinity

        for each child in node.children:

            // Recurse into the child — it is now MAX's turn, so pass true
            childValue = minimax(child, depth - 1, true)

            // min(a, b): returns whichever value is lower
            // Replaces bestValue only if this child returned something better for MIN
            bestValue = min(bestValue, childValue)

        // Return the lowest value found across all children
        return bestValue


// ── INITIAL CALL (root is always MAX's turn) ─────────────────────────
// minimax(rootNode, maxDepth, true)

Time & Space Complexity

Minimax Exam Questions Students Always Get Wrong

• I can already see the winning move on the right side of the tree. Why do I have to trace the entire left side first?

  Because your exam is not testing whether you can spot a good move — it is testing whether you can trace like a computer. Minimax is blind. It has no vision of the whole tree; it just follows DFS rules mechanically, left branch first, every time. Trace left-first on your exam paper, even if it feels wasteful. Skipping to the right side is an automatic mark loss.

• Why does $MIN$ always pick the most negative number? Does $MIN$ want a negative score?

  All scores in Minimax are calculated from $MAX$'s perspective — a high number means $MAX$ is winning, a low or negative number means $MAX$ is losing. $MIN$ does not 'want' a negative score for its own sake. It picks the lowest number because that number represents $MAX$'s worst possible outcome. $MIN$'s only goal is to make $MAX$'s life as difficult as possible.

• What happens if $MAX$ or $MIN$ has two children with identical values — which one does the algorithm pick?

  It picks the first one it found — which in a standard left-first DFS trace means the leftmost child. The final game score at the root will not change either way, since the values are identical. Stick to the leftmost path on your exam to match standard algorithm behaviour and avoid any ambiguity in your answer.

• The tree on my exam ends at depth 3 but the game is not actually over yet. What am I supposed to do with those leaf values?

  Treat them exactly like a real win or loss — because for the purposes of this trace, they are. The leaf values are heuristic estimates of how good each position looks at that depth. Minimax does not care whether the game is truly over. Read the number, write it on the node, and pass it up. The math is identical either way.