Minimax — Game Tree Search

The Simplest Explanation

You and an opponent take turns. You want the score high; they want it low. Minimax answers one question:

"If both of us play perfectly, what outcome can I guarantee?"

The answer comes from working backwards from the end of the game:

• Your turn (MAX node): assume you pick your best option → take the max of children
• Opponent's turn (MIN node): assume they pick your worst option → take the min of children

That's the whole algorithm. Back up values from leaves to root, alternating max and min.

Game Trees in One Minute

A two-player, zero-sum, perfect-information game is modeled as a tree:

• Root = current position; it's MAX's turn
• Each level alternates between MAX nodes (your move) and MIN nodes (opponent's move)
• Leaves carry a value from a static evaluation function: positive favors you, negative favors the opponent

Interactive Demo: The Backup Rule

Click through the trace and watch values bubble up from leaves to root:

Reading the Result

$\text{value}(A) = \max\big(\underbrace{\min(3,5)}_{=3},\ \underbrace{\min(6,2)}_{=2}\big) = \max(3, 2) = 3$

• Minimax value = 3
• Optimal first move: A → B

Why is B's backed-up value only 3 when its best leaf is 5? Because after you move to B, a perfect opponent chooses D (value 3) — their best is your worst. Minimax assumes no mercy.

Worked Exam-Style Example (by hand)

Given this tree, compute the minimax value:

Exam tips for hand traces:

1. Label every node MAX or MIN first — most errors come from mixing levels
2. Leaves are already "computed" — never apply min/max to them
3. Write backed-up values next to internal nodes as you go; the examiner gives partial credit for correct backups
4. The answer format usually wants just the root value and/or the optimal move

Properties

Time is exponential, which is why alpha-beta pruning (next page) exists — same answer, far fewer nodes.