The Minimax Algorithm in Tic Tac Toe: Game Theory, Decision Trees, and Perfect Play

Tic Tac Toe (also known as Noughts and Crosses) is frequently the first game examined in artificial intelligence and game theory curricula. While children quickly memorize heuristic rules like taking the center square or setting up diagonal forks, computer scientists solve the game using Minimax—a recursive backtracking algorithm that evaluates every possible future move to guarantee optimal decision-making.

In this deep dive, we explore the mathematics of zero-sum decision trees, how state spaces are traversed, and how you can test your tactical skills against an Unbeatable Tic Tac Toe AI online.

---

1. Game Theory Foundations: Zero-Sum Perfect Information

In game theory, Tic Tac Toe is categorized as a:

• Two-player game: Players alternate discrete sequential turns.
• Zero-sum game: One player's gain is exactly equal to the other player's loss (+1 utility for victory, -1 for defeat, 0 for stalemate).
• Perfect information game: Both competitors possess complete knowledge of the entire board state and historical moves; there are no hidden cards, fog of war, or dice rolls.

Because all information is public, the entire contest can be mapped as an acyclic directed game tree. The root node represents the empty 3x3 grid, each branch corresponds to a valid placement, and every leaf node represents a terminal condition (win, loss, or draw).

---

2. The Decision Tree State Space

While a naive combinatorial estimation suggests 9! = 362,880 possible move permutations, the actual reachable state space is constrained by game termination rules:

1. Total Reachable States: Exactly 255,168 terminal game paths exist.
2. Distinct Board Configurations: Only 5,478 unique configurations appear throughout play.
3. Symmetry Reduction: Because a square grid possesses 8-fold dihedral symmetry (rotations of 90, 180, and 270 degrees plus horizontal and vertical reflections), the board reduces to just 765 strategically unique states.

Because 765 states is trivial for modern computer hardware, an algorithm can search the entire tree in single-digit milliseconds inside a web browser without requiring external server computation or pre-computed lookup tables.

---

3. How the Minimax Algorithm Works

The algorithm operates on a simple principle:

• The Maximizer (the AI) attempts to achieve the highest possible score.
• The Minimizer (the human opponent) attempts to achieve the lowest possible score.

Recursive Evaluation Flow

       [Max Node] (AI turn: picks highest score)
        /        \
   [Min Node]   [Min Node] (Human turn: picks lowest score)
     /    \       /    \
   +10    -10    0    +10  (Terminal outcomes)

At every step of recursion:

1. Base Case Check: Does the current board state have a winner?
   • If AI wins: Return +10 - depth
   • If Human wins: Return depth - 10
   • If Tie: Return 0
2. Recursive Maximizing Step: If it is the AI turn, iterate through every available empty square, simulate placing the AI piece, recursively call minimax(board, depth + 1, false), and pick the maximum evaluation.
3. Recursive Minimizing Step: If it is the Human turn, simulate placing the opponent piece, recursively call minimax(board, depth + 1, true), and pick the minimum evaluation.

Factoring in Search Depth

Notice the score calculation: 10 - depth. By subtracting the search depth from the victory score, the algorithm naturally favors faster wins over delayed wins. Conversely, adding depth to human wins (depth - 10) ensures the AI fights stubbornly for the longest possible survival path even when facing an inevitable defeat.

---

4. Key Strategic Lessons from Perfect Play

When playing against the AI or a friend:

• The Center Advantage: The center square belongs to 4 winning lines (1 horizontal, 1 vertical, 2 diagonals). The 4 corner squares belong to 3 winning lines each, while the 4 edge squares belong to only 2 winning lines.
• The Corner Trap (The Fork): If Player 1 takes opposite corners on moves 1 and 3, and Player 2 mistakenly plays on an edge, Player 1 can capture a third corner, establishing two simultaneous unblockable winning threats.
• The Only Counter to Opposite Corners: If Player 1 plays opposite corners, Player 2 must play on an edge (not a corner) to force a block and maintain a stalemate.

---

Practice Against the Minimax Engine

Ready to test your strategic intuition? Launch our free Tic Tac Toe Game to play against Easy, Medium, or Unbeatable Master AI, or switch to local 2-Player Pass-and-Play mode on desktop or mobile.