Minimax Algorithm Theory Guide
Try the Minimax Algorithm Solver →Minimax Algorithm, Game Theory, Artificial Intelligence, Zero-sum games, Maximizer, Minimizer, Game Tree
Minimax is a decision-making algorithm used in two-player, zero-sum games like Chess and Tic-Tac-Toe to determine the provably optimal move. Unlike a reckless gambler hoping the opponent blunders, Minimax assumes the opponent plays perfectly — every single time. It recursively maps every possible future game state into a tree, then propagates scores backward from the terminal outcomes: the player selects the branch with the highest guaranteed score, while the player selects the branch that minimizes it, until the best move at the root is mathematically certain.
The Recursive Minimax Formula
What do these variables mean?
- The current state (the current board position).
- A specific action or move.
- All possible actions you can take from state .
- The new board state after taking action .
- 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 does the exact opposite, choosing the path that forces Max into the lowest possible score.
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.
Solved Example: Solving a Simple 2-Level Game Tree
Assume a tree with a root MAX node. It has two branches leading to MIN nodes. Branch A leads to leaves [3, 5]. Branch B leads to leaves [2, 9].
Step 1: Go to the bottom-left. MIN looks at leaves [3, 5]. MIN chooses 3 (the smaller value).
Step 2: Go to the bottom-right. MIN looks at leaves [2, 9]. MIN chooses 2 (the smaller value).
Step 3: Move up to the Root. MAX now sees the values [3, 2] coming from the branches.
Step 4: MAX chooses 3 (the larger value).
Result: The optimal move for MAX is to choose Branch A, guaranteeing a score of at least 3.
Master the Math
Choose how you want to practice Minimax Algorithm next:
Implementation Pseudocode
function runMinimax(nodeId, isMaximizing):
currentNode = tree[nodeId]
// Base Case: Leaf Node (Bottom of the tree)
if currentNode.children is empty:
return currentNode.value
// Recursive Case: MAX's Turn
if isMaximizing:
extremum = -Infinity
for each childId in currentNode.children:
evalValue = runMinimax(childId, false) // Pass turn to MIN
extremum = Math.max(extremum, evalValue)
return extremum
// Recursive Case: MIN's Turn
else:
extremum = Infinity
for each childId in currentNode.children:
evalValue = runMinimax(childId, true) // Pass turn to MAX
extremum = Math.min(extremum, evalValue)
return extremumRules & Common Mistakes
Exam Trap: 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, destroying the rest of the tree.
Use shapes to help you remember. The industry standard is drawing Squares for Max nodes and Circles for Min nodes.
You have to solve this Bottom-Up. You cannot figure out the top node until you have evaluated every single terminal node at the very bottom of the branches.
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.
Algorithm Complexity
| Scenario | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Time Complexity | Where is the branching factor (legal moves per turn) and is the maximum depth of the tree. It has to evaluate every single possible future state. | ||
| Space Complexity (DFS) | If implemented recursively (like our code), it only needs to keep the current path of depth in the call stack memory at any given time. |
Minimax vs. Alpha-Beta Pruning
Alpha-Beta Pruning is not a separate algorithm — it is a mathematically safe optimization layer applied directly on top of Minimax. Both produce the exact same final answer at the root of the game tree; Alpha-Beta simply gets there faster by provably skipping branches that cannot change the outcome.
- •Standard Minimax visits every single node in the game tree (); Alpha-Beta Pruning can skip entire subtrees using two tracking variables ( and ), reducing the search to in the best case — effectively doubling the depth the AI can explore in the same compute time.
- •Minimax requires no extra state beyond the current node's value; Alpha-Beta requires passing and updating two boundary values ( = best guaranteed score for Max, = best guaranteed score for Min) down through every recursive call.
- •Minimax is always deterministic — it checks nodes in the same order every time; Alpha-Beta's pruning efficiency depends entirely on move ordering — if the best moves are evaluated first (left side of the tree), pruning is maximal; if the worst moves come first, zero pruning occurs.
Detailed Comparisons & Guides
Summary
Minimax is the algorithm that teaches AI to think like a chess player: always assume your opponent will make the best possible move, and choose the response that guarantees you the best outcome under that assumption. It works by mapping all possible futures, scoring the end states, and propagating those scores backward through alternating MAX and MIN layers. The algorithm is logically perfect but computationally brutal for complex games — which is exactly why Alpha-Beta Pruning was invented as its essential companion.
Common Exam Questions & FAQ
+ Does Minimax guarantee a win?
Minimax guarantees the best *possible outcome given optimal play from both sides* — not necessarily a win. If the game position is mathematically a loss (for example, being two pieces down in Chess with no tactical tricks available), Minimax will identify that and choose the move that delays the loss the longest, but it cannot manufacture a win out of a losing position.
+ Why is Tic-Tac-Toe trivially solvable with Minimax but Chess is not?
Branching factor and tree depth. Tic-Tac-Toe has at most 9 possible first moves and terminates within 9 total moves — the entire game tree has only a few thousand nodes, solvable in milliseconds. Chess has an average branching factor of ~35 legal moves per turn and games lasting ~80 moves, producing more possible positions than there are atoms in the observable universe. Even with Alpha-Beta Pruning, a full tree search is computationally impossible.
+ What is the 'Utility Value' of a terminal node and who decides it?
The utility value is the score assigned to a game-over state — the number that represents how good that outcome is for the MAX player. Common conventions are: +10 (or +1) for a MAX win, -10 (or -1) for a MIN win (MAX's loss), and 0 for a draw. For more complex games, a 'Heuristic Evaluation Function' is used to estimate the utility of non-terminal states at a depth limit, replacing the true terminal value with an educated guess.
🎓 Core University Curriculum
This algorithm and its manual calculation methods are foundational requirements in leading Computer Science and Software Engineering programs worldwide. You will find this topic heavily featured in the syllabi of these standard AI courses:
Explore Related Algorithms
Try the Alpha-Beta Pruning Calculator
Step through a game tree interactively and watch Alpha-Beta Pruning eliminate redundant branches, achieving the same optimal move as Minimax in a fraction of the node evaluations.
Alpha-Beta Pruning Theory
Understand how Alpha-Beta Pruning is a provably equivalent optimization of Minimax: by maintaining α (best maximizer score) and β (best minimizer score) bounds, it prunes entire subtrees without affecting the final decision.