Search & Planning11 min read

Minimax Algorithm

Think ahead — what's the best move if your opponent plays perfectly?
scope:Core Conceptdifficulty:Intermediate

The Chess Grandmaster's Secret

Watch a chess grandmaster play. Before every move, they're not just thinking about their best option — they're thinking about what their opponent will do next. And what they'll do after that. And what the opponent does after that.

It's a mental conversation: "If I move my knight here, she'll take my bishop. Then I'll push my pawn, and she'll have to retreat her queen..."

This is the minimax algorithm in a nutshell. You assume your opponent is just as smart as you and will always make the best possible move. Then you pick the move that gives you the best outcome even in the worst case.

Max and Min Take Turns

Think of it as two players with opposite goals:

  • Max (you) wants to maximize the score.
  • Min (your opponent) wants to minimize your score.

They alternate turns. Max picks the highest-scoring move. Min picks the lowest. The algorithm builds a tree of all possible game states, evaluates the leaves, and works backward to find the best opening move.

Walking Through an Example

Imagine a simple game where you and a friend pick numbers. The game tree has these final scores at the bottom: [3, 5, 2, 9, 1, 7, 4, 6].

Working backward:

  1. Min's turn (bottom): Min picks the smaller of each pair: min(3,5)=3, min(2,9)=2, min(1,7)=1, min(4,6)=4
  2. Max's turn (middle): Max picks the larger: max(3,2)=3, max(1,4)=4
  3. Min's turn (top): Min picks the smaller: min(3,4)=3

So with perfect play from both sides, Max can guarantee a score of 3. Not the best leaf (9), but the best guaranteed outcome against a perfect opponent.

Alpha-Beta Pruning: Don't Search What Doesn't Matter

Full minimax is expensive — it explores every possible game state. But often you can skip entire branches. If you already know a branch can't produce a better result than what you've found, why explore it?

This optimization is called alpha-beta pruning. It can cut the search space nearly in half, making the algorithm dramatically faster without changing the result.

Minimax with Alpha-Beta Pruning

def minimax(node, depth, is_maximizing, alpha, beta):
    """Minimax with alpha-beta pruning."""
    # Base case: leaf node
    if isinstance(node, int):
        return node
    
    if is_maximizing:
        max_eval = float('-inf')
        for child in node:
            eval_score = minimax(child, depth + 1, False, alpha, beta)
            max_eval = max(max_eval, eval_score)
            alpha = max(alpha, eval_score)
            if beta <= alpha:
                break  # Prune!
        return max_eval
    else:
        min_eval = float('inf')
        for child in node:
            eval_score = minimax(child, depth + 1, True, alpha, beta)
            min_eval = min(min_eval, eval_score)
            beta = min(beta, eval_score)
            if beta <= alpha:
                break  # Prune!
        return min_eval


# Game tree: nested lists = branches, ints = leaf scores
game_tree = [[3, 5], [2, 9]], [[1, 7], [4, 6]]


# Find the optimal value for Max
result = minimax(game_tree, 0, True, float('-inf'), float('inf'))
print(f"Optimal value for Max: {result}")
Output
Optimal value for Max: 3
Note: Deep Blue's secret weapon: When IBM's Deep Blue defeated chess champion Garry Kasparov in 1997, it used minimax with alpha-beta pruning — evaluating about 200 million positions per second. It could look 12+ moves ahead. Today's chess engines like Stockfish combine minimax with neural networks to play even stronger.

Beyond Simple Games

Minimax isn't just for chess. It applies to any two-player, zero-sum, perfect-information game:

  • Tic-tac-toe — minimax can solve it completely (it's always a draw with perfect play)
  • Checkers — fully solved using minimax variants in 2007
  • Go — too complex for pure minimax (more states than atoms in the universe), which is why AlphaGo used neural networks instead

The key limitation: minimax assumes your opponent plays perfectly. In real life, opponents make mistakes. More advanced algorithms like Monte Carlo Tree Search account for this by simulating random play instead of assuming perfection.

Quick check

In minimax, what does the 'Min' player try to do?
Challenge

Continue reading