Minimax Algorithm

Minimax Algorithm, Game Theory, Artificial Intelligence, Zero-sum games, Maximizer, Minimizer, Game Tree

Imagine playing a perfect game of Chess or Tic-Tac-Toe against a mind reader. The Minimax algorithm is a decision-making AI that assumes its opponent is just as smart as it is. It features two players: 'Max' (who wants the highest possible score) and 'Min' (who wants to crush Max by forcing the lowest possible score). By mapping out every possible future move and working backward, Minimax finds the absolute best move to make, assuming the opponent will play flawlessly to stop you.

The Recursive Minimax Formula

Max(s) = \max_{a \in A(s)} Min(Result(s,a))

What do these variables mean?

$s$ The current state (the current board position).
$a$ A specific action or move.
$A(s)$ All possible actions you can take from state $s$ .
$Result(s,a)$ The new board state after taking action $a$ .
The Max FormulaMax looks at all possible moves, figures out what Min would do in response, and chooses the move that leaves Max with the highest guaranteed score.
The Min Formula$Min(s)

How Does it Work?

Generate the Game Tree: Draw out every single possible move from the current state down to the end of the game (or a specific depth limit).

Evaluate Terminal States: Look at the very bottom nodes (the leaves). Assign them a 'Utility Value' (e.g., +10 for a win, -10 for a loss, 0 for a draw).

Propagate Upwards (Bottom-Up): Start at the bottom and move up one level. If it is Min's turn, look at the children below and pull up the smallest number. If it is Max's turn, pull up the largest number.

Repeat the Climb: Continue passing the numbers up alternating layers (Max gets the biggest, Min gets the smallest) until you reach the very top (the root node).

Select the Optimal Move: At the root node, Max looks at the options directly below it and chooses the branch with the highest number.

Important Rules & Conventions

Exam Trick 1: Always label your layers! Write 'MAX' and 'MIN' clearly next to each row of the tree before you start doing the math. Students constantly pull up a minimum value during a Max turn because they lost track of whose turn it was.
Exam Trick 2: Use shapes to help you remember. The industry standard is drawing Squares for Max nodes and Circles for Min nodes.
Exam Trick 3: You have to solve this Bottom-Up. You cannot figure out the top node until you have evaluated every single terminal node at the bottom.

Advantages

✓ Guarantees the optimal mathematical move. If the game is fully mapped out, Minimax will never lose.
✓ Conceptually elegant. The logic of alternating between maximizing and minimizing perfectly mimics real human strategic thinking.

Disadvantages

× Computational Explosion. For complex games like Chess or Go, the game tree gets so massive (millions of branches) that a computer would take years to check them all. This is called high branching factor.
× Requires modifications like Depth Limits and Alpha-Beta Pruning to be actually usable in modern, complex games.

Summary

Minimax is the grandfather of game-playing AI. It works by mapping out the future, calculating the final scores, and pulling those scores backward through time. By planning for the worst-case scenario (Min's turn), it guarantees the best possible outcome for itself (Max's turn).