Minimax: Game Playing
See how AI plays perfect two-player games by thinking ahead, assuming both sides play their best moves every turn.
In 1997, IBM's Deep Blue defeated world chess champion Garry Kasparov. In 2016, DeepMind's AlphaGo beat the Go world champion. Both systems — despite operating on very different scales — share the same foundational idea: look ahead, consider what your opponent will do, and pick the move that's best even if the opponent plays perfectly.
That idea has a name: Minimax. It's one of the most elegant algorithms in all of computer science, and you can understand it completely from scratch. We'll build one today — no external libraries, just Python and logic.
Two Generals, One Map
Imagine two generals studying a map before battle. General MAX wants to reach the highest ground. General MIN wants to push MAX to the lowest ground. Each general moves in turn and always picks their best option. Minimax is exactly this: you are MAX, your opponent is MIN, and the "map" is a tree of every possible future position in the game.
#Game Trees and Leaf Scores
Every game can be drawn as a tree. The root is the current board. Each branch is a legal move. Each node is a resulting position. Leaf nodes are terminal positions — someone won, lost, or the game ended in a draw.
We assign a score to each leaf: +1 if MAX wins, -1 if MIN wins, 0 for a draw. The algorithm's job is to propagate these scores back up to the root so we know which move is truly best.
The propagation rule is simple: - At a MAX node (your turn) — take the highest child value. - At a MIN node (opponent's turn) — take the lowest child value.
Apply this recursively all the way up and you get the guaranteed best outcome from the current position.
def minimax(node, is_maximizing):
# Base case: leaf node is just a number
if isinstance(node, int):
return node
if is_maximizing:
best = -999
for child in node:
val = minimax(child, False) # opponent moves next
best = max(best, val)
return best
else:
best = 999
for child in node:
val = minimax(child, True) # our turn next
best = min(best, val)
return best
# Tree: root is MAX, children are MIN nodes, leaves are ints
tree = [[3, 5], [2, 9], [0, 7]]
# MIN will pick 3 from [3,5], 2 from [2,9], 0 from [0,7]
# MAX then picks 3 from {3, 2, 0}
print("Root value:", minimax(tree, True))#Picking the Best Move and a Real Game
Knowing the root's value is useful, but we also need the index of the move that leads to it. We run minimax on each child (switching to MIN's turn) and pick the one with the highest result. Below we also plug minimax into a real tic-tac-toe position — the board is a 9-element list, 'X' is MAX, 'O' is MIN:
WINS = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(b):
for a,i,c in WINS:
if b[a] and b[a]==b[i]==b[c]: return b[a]
return None
def minimax_ttt(b, is_max):
w = winner(b)
if w == 'X': return 1
if w == 'O': return -1
if None not in b: return 0
moves = [i for i,v in enumerate(b) if v is None]
if is_max:
best = -2
for m in moves:
b[m]='X'; best=max(best, minimax_ttt(b,False)); b[m]=None
return best
else:
best = 2
for m in moves:
b[m]='O'; best=min(best, minimax_ttt(b,True)); b[m]=None
return best
# X is one move away from winning via the diagonal 0->4->8
board = ['X','O',None, None,'X',None, 'O',None,None]
best_val, best_idx = -2, None
for i,v in enumerate(board):
if v is None:
board[i]='X'
val = minimax_ttt(board, False)
board[i]=None
if val > best_val: best_val,best_idx = val,i
print(f"X plays square {best_idx} — value: {best_val}")"Optimal" Means Assuming the Opponent Is Perfect Too
Minimax guarantees the best outcome if the opponent plays optimally. If a human opponent blunders, minimax still responds perfectly to whatever they actually do — but the score it reported assumed a perfect foe. This is a strength, not a weakness: you get a floor guarantee, not just an average-case result.
#Why Big Games Need Extra Tricks
Minimax is complete and correct, but it visits every node in the tree. With a branching factor b and depth d, that's roughly b^d nodes — exponential growth.
| Game | Avg. branching | Practical depth | Approx. nodes | |---|---|---|---| | Tic-tac-toe | ~4 | 9 (full) | ~255,000 | | Chess | ~30 | 6 | ~700 million | | Go | ~250 | — | intractable |
Real engines add alpha-beta pruning (skip branches that can't beat what we've already found) and evaluation functions (score non-terminal positions so we can stop early). AlphaGo replaced the evaluation function with a neural network — but the tree search idea remains.
It is MIN's turn. The three child nodes have values 7, 2, and 9. What value does MIN return?
In Practice: Use scikit-learn for ML, but Know Your Foundations
Libraries like python-chess or custom game engines wrap minimax for you. But understanding the algorithm from scratch means you can debug strange behavior, tune search depth, write a custom evaluator, or extend to alpha-beta pruning — skills that matter the moment the off-the-shelf tool doesn't fit.
Key takeaways
- Minimax models two-player zero-sum games as trees: MAX tries to score high, MIN tries to score low, and each assumes the other plays perfectly.
- Values are assigned at leaf nodes (win/loss/draw) and propagated upward by alternating max and min at each level.
- The algorithm guarantees the best possible outcome against a perfect opponent — a floor, not a ceiling.
- Minimax is exponentially expensive; real engines add alpha-beta pruning and evaluation functions to stay practical.
- From tic-tac-toe to AlphaZero, minimax and its descendants power almost every game-playing AI ever built.
Start with the scores of each final position (the leaves).
Using the same abstract game tree from the lesson, what does this print? The root is a MAX node, its children are MIN nodes, and leaves are integers.
def minimax(node, is_maximizing):
if isinstance(node, int):
return node
if is_maximizing:
best = -999
for child in node:
best = max(best, minimax(child, False))
return best
else:
best = 999
for child in node:
best = min(best, minimax(child, True))
return best
tree = [[8, 1], [6, 4], [2, 3]]
print("Root value:", minimax(tree, True))Complete the propagation rule. At a MAX node we take the highest child value; at a MIN node we take the lowest. Fill in the function each branch should use.
def minimax(node, is_maximizing): if isinstance(node, int): return node if is_maximizing: best = -999 for child in node: best = (best, minimax(child, False)) return best else: best = 999 for child in node: best = (best, minimax(child, True)) return best
This code should return the correct leaf scores for tic-tac-toe, where 'X' is MAX and 'O' is MIN. This code has a bug — what's wrong?
def score(b):
w = winner(b)
if w == 'X': return -1 # X is MAX
if w == 'O': return 1 # O is MIN
if None not in b: return 0
return None # not terminalPut these lines in the correct order to find the best move INDEX for MAX from the root of an abstract game tree (children are MIN nodes).
if val > best_val:
best_val, best_idx = -999, None
val = minimax(child, False)
print("Best move index:", best_idx)best_val, best_idx = val, i
for i, child in enumerate(tree):
Implement a minimax function that works on an abstract game tree of nested lists and integers. Then use it to find the best move (index) for the MAX player from a root node whose children are [[3, 5], [2, 9], [0, 7]]. At the root it is MAX's turn; at depth 1 it is MIN's turn; leaves are integers. Print both the minimax value of the root and the index of the best child.
Try it live — edit the code and hit Run to execute real Python: