Minimax Search Algorithm: Two Worked Game Trees, an Alpha-Beta Trace and Exam Traps

Many students can recite that MAX chooses the largest value and MIN chooses the smallest, yet still propagate a value in the wrong direction. The usual mistake is to pick the most attractive leaf as though the opponent will cooperate. Start with the model from zero, fix every payoff in MAX's perspective, and work through numerical trees, an alpha-beta trace, and a compact routine for exam questions. A fixed payoff perspective and bottom-up evaluation prevent both errors.

Minimax search algorithm: the game model and its assumptions

A state is a complete game position. A legal action produces a successor state, and reachable successors form a game tree. One player's move is a ply. A terminal state ends the game and receives a utility.

Classical minimax assumes two players who alternate turns, perfect information, deterministic moves, zero-sum utilities, and optimal play. MAX seeks a larger utility; MIN seeks a smaller one because every number uses MAX's perspective. Thus +10 is strong for MAX, 0 is a draw, and -10 is strong for MIN. These are utilities, not probabilities or percentages. Do not add them along a path unless the question defines cumulative rewards.

The GATE CS Exam Preparation collection connects minimax to other search and game-playing problems.

Minimax recurrence: evaluate leaves and back values up the tree

For a state s, the recurrence has three cases:

V(s) = U(s)                              if s is terminal
V(s) = max V(Result(s, a))               if Player(s) = MAX
V(s) = min V(Result(s, a))               if Player(s) = MIN

The procedure tests for a terminal state, recursively scores each legal child, then returns the largest score at MAX or the smallest at MIN. Moves lead downward from the root, but evaluation travels upward from leaves. At the root, keep the action separately with argmax; its label and backed-up utility are different objects.

Before calculating, label every level. If the root is MAX, its children are MIN, its grandchildren are MAX, and the pattern continues. A depth cutoff is a separate base case and uses a heuristic evaluation instead.

Minimax worked example: back up an eight-leaf game tree

Root R is MAX. Children A and B are MIN, their children are MAX, and every terminal utility uses MAX's perspective.

Back up every node from the bottom:

1. V(A1) = max(3, 5) = 5.

2. V(A2) = max(6, 9) = 9.

3. V(A) = min(5, 9) = 5.

4. V(B1) = max(1, 2) = 2.

5. V(B2) = max(7, 4) = 7.

6. V(B) = min(2, 7) = 2.

7. V(R) = max(5, 2) = 5.

MAX therefore chooses R -> A. MIN can hold branch A to 5, while MIN can hold branch B to 2, so rational MAX chooses the guaranteed value 5. With leftmost tie-free choices, the principal variation is R -> A -> A1 -> terminal 5.

Leaf 9 is not the answer because MIN chooses between backed-up values 5 and 9 at A. The nodes and edges use familiar tree vocabulary from Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step, but minimax backup is not shortest-path relaxation.

Depth-limited minimax worked example: heuristic values are not terminal utilities

When search stops at a chosen depth, use a heuristic H(s) that estimates the cutoff position for MAX. It is not an exact game result. Above that frontier, the same MIN and MAX backups apply.

Let root X be MAX. Move P reaches a MIN node whose cutoff evaluations are [8, -1], so V(P) = min(8, -1) = -1. Move Q reaches a MIN node with [4, 3], so V(Q) = min(4, 3) = 3. Therefore V(X) = max(-1, 3) = 3, and MAX chooses Q. The individual frontier value 8 under P cannot survive MIN's reply.

The chosen value 3 is only the best estimate at this cutoff. A damaging move just beyond the horizon can change the decision at greater depth. Iterative deepening controls how search depth grows, but it does not guarantee that a weak heuristic becomes correct.

Minimax mistakes: opponent cooperation, wrong perspective and premature choices

Four common errors produce distinct wrong results on the eight-leaf tree:

If two root moves have the same backed-up value, both are minimax-optimal unless a tie-break rule is supplied. If a node has no legal moves, apply the question's terminal or pass convention rather than inventing a score.

Repair routine: label player levels, fix the payoff perspective, evaluate every required leaf, back up one level at a time, then choose only among root actions.

Alpha-beta pruning: the same minimax answer with fewer evaluated leaves

alpha is MAX's best guaranteed value on the current path. beta is MIN's best guaranteed value. When alpha >= beta, remaining children cannot affect the final choice and may be pruned. The minimax value must remain unchanged.

Visit the first tree from left to right. Start at R with alpha = -infinity and beta = +infinity.

1. Evaluate A1 fully: max(3, 5) = 5. Node A now has beta = 5.

2. At A2, the first leaf 6 makes that MAX node's alpha = 6. Since 6 >= 5, prune leaf 9. Node A returns 5.

3. Root R updates alpha = 5.

4. Under B, evaluate B1 = max(1, 2) = 2. Node B now has beta = 2.

5. Since 2 <= 5, prune all of B2, including leaves 7 and 4.

Root still returns 5 and chooses A. Plain minimax evaluates eight terminal leaves. This ordering evaluates five, in order 3, 5, 6, 1, 2, and prunes three: 9, 7, 4. Another legal ordering can prune fewer nodes.

Minimax complexity and exam patterns: parse the tree before calculating

Let b be the branching factor and m the depth in plies. In a full uniform tree, minimax visits b^m leaves and takes Theta(b^m) time. Generating successors one at a time keeps depth-first recursion proportional to m; storing the full tree costs Theta(b^m) space. Alpha-beta is Theta(b^m) with worst ordering and can approach Theta(b^(m/2)) with ideal ordering.

A transposition table can cache repeated positions. This resembles Dynamic Programming Explained with a Worked 0/1 Knapsack, but not every game tree repeats states, and caching does not replace minimax backups.

Checklist:

1. Mark MAX and MIN levels.

2. Confirm whose perspective the utilities use.

3. Compute every required terminal utility or heuristic.

4. Back up values and record the root action.

5. For alpha-beta, obey the stated order and count only evaluated leaves.

After the hand calculations are stable, use the GATE Test Series for mixed timed practice.

Minimax search algorithm in the short version and the next step

Keep one recall chain: utilities use one perspective, MAX takes the largest child value, MIN takes the smallest, values travel from leaves to root, and the root selects the move with the best guarantee. The full tree chooses A with value 5. The depth-limited tree chooses Q with heuristic value 3.

Use GATE Guidance by Sanchit Sir if you want artificial intelligence placed inside a structured GATE preparation sequence. Then redraw the eight-leaf tree and reproduce every alpha-beta cutoff without looking at the diagram.