Adversarial Search: Minimax

Last lesson dropped you across a chessboard, where the old “cheapest path” frame fell apart: after every move you make, a second player makes the move that hurts you most. Minimax is the idea that makes reasoning against such an adversary precise. Two perfect players share one game tree; each plays the move best for them, knowing the other will do the same.

The crux is that you cannot plan only for yourself. Every plan you draft has to survive the opponent picking their best reply — so you read the tree backward from the leaves, score in hand, and let each player choose the child that matches their goal: the largest value for MAX, the smallest for MIN. This worst-case-aware reasoning is the backbone of every game-playing agent (chess and Go engines, poker bots) and of adversarial robustness in ML — anywhere you must act well against an opponent who answers your every move.

The minimax value

Formally, the minimax value V(n) of a node n:

V(n) = utility(n)                    if n is a leaf
V(n) = max over children c of V(c)   if n is a MAX node
V(n) = min over children c of V(c)   if n is a MIN node

That is the entire algorithm. Recurse to the leaves, then back the value up one level at a time. The root’s value is the score MAX can force against a perfectly playing MIN — the best result MAX can rationally hope for.

How GATE asks this

A typical NAT: a small game tree (often 2–3 levels, sometimes drawn as a MAX root with three strategies leading to MIN nodes of three leaves each). Compute the root’s minimax value, or state which strategy MAX should choose. Sometimes it is an MCQ asking “which strategy is optimal for MAX” — the same calculation, just read the index. This pattern appeared in GATE DA 2026.

Worked example — GATE DA 2026

MAX has three strategies, each leading to a MIN node with three leaf utilities:

• Strategy 1 leaves: 8, 6, -1
• Strategy 2 leaves: 1, 5, 7
• Strategy 3 leaves: -4, -3, -12

Which strategy should MAX play, and what is the game’s value?

Step 1 — back up MIN at each strategy node (MIN takes the smallest leaf):

• Strategy 1: min(8, 6, -1) = -1
• Strategy 2: min(1, 5, 7) = 1
• Strategy 3: min(-4, -3, -12) = -12

Step 2 — MAX picks the largest of those:

V(root) = max(-1, 1, -12) = 1

So MAX plays strategy 2 and secures a value of 1 — the real GATE DA 2026 answer. Pause on the intuition: strategy 1 holds the highest individual leaf (8), but MIN will never let MAX reach it — MIN steers to the -1. Strategy 2’s worst case is 1, and MIN cannot do better than that, so the rational choice is strategy 2 even though its peak is lower. The shiniest leaf was a trap, exactly as the prompt hinted.

In one breath

Minimax solves a two-player zero-sum game by backing utility values up the game tree from the leaves: a MAX node takes the maximum of its children, a MIN node the minimum, so the root’s value is the score MAX can guarantee against a perfectly playing MIN; the optimal move is the child carrying that root value, and the classic trap is that the single biggest leaf is usually unreachable because MIN will steer away from it.

Practice

A question to carry forward

Minimax is correct — and brutally expensive. To back up the root value it must, as written, examine every leaf of the game tree. For tic-tac-toe that is fine. For chess the tree has more leaves than there are atoms in the observable universe, and no machine will ever visit them all.

Yet stare at the worked example and a glimmer appears. Once MIN had found, under some strategy, a leaf bad enough, did MAX ever need to see that strategy’s remaining leaves? If one reply already drags a branch below something MAX can secure elsewhere, the rest of that branch cannot change MAX’s decision — so why look? Here is the thread onward: how do you prove, mid-search, that an entire subtree cannot possibly affect the root value, prune it away unexamined, and in the best case explore only the square root of the leaves minimax would — without changing the answer by even one?