Tic-Tac-Toe

Easy Algorithms: Minimax, Game Tree Search

Tic-Tac-Toe

Easy Algorithms: Minimax, Game Tree Search

Overview

Tic-Tac-Toe is the perfect introduction to game-playing AI. With only 255,168 possible game states, we can compute the perfect strategy using the minimax algorithm.

Rules

Two players take turns marking spaces on a 3x3 grid. The first player to get three marks in a row (horizontally, vertically, or diagonally) wins. If all nine spaces are filled with no winner, the game is a draw.

The Minimax Algorithm

The minimax algorithm evaluates game positions by:

1. Recursively exploring all possible future moves
2. Assigning scores to terminal positions (1 for win, -1 for loss, 0 for draw)
3. Working backward to the current position, with each player choosing the move that maximizes their score

minimax(position, depth, isMaximizing):
  if position is terminal:
    return score
  
  if isMaximizing:
    maxScore = -∞
    for each move in position:
      score = minimax(nextPosition, depth+1, false)
      maxScore = max(maxScore, score)
    return maxScore
  else:
    minScore = +∞
    for each move in position:
      score = minimax(nextPosition, depth+1, true)
      minScore = min(minScore, score)
    return minScore

Key Properties

• Perfect Play: The minimax algorithm computes the optimal move for any position
• Game Outcome: With perfect play from both sides, the game always ends in a draw
• Computation: The AI must evaluate approximately 5,478 positions on average

Interactive Demo

Play against the unbeatable AI:

Tic-Tac-Toe Game

Click to place your mark (X). The AI will play as O.

The Negamax Algorithm

Negamax is an elegant variant of minimax that simplifies code by:

• Always maximizing from the current player’s perspective (not just one player)
• Negating child scores instead of alternating between min/max branches
• Results in 50% less code while maintaining identical behavior

Traditional Minimax:          Negamax:
- if isMaximizing:            - Always: maxScore = max(score)
    maxScore = max(...)       - Negate child: -negamax(child)
- else:
    minScore = min(...)

Implementation Notes

The provided implementation uses the clean negamax algorithm:

function negamax(board, depth) {
  const score = evaluateBoard(board);
  
  // Terminal states
  if (score !== 0) {
    return score - depth * (score > 0 ? 1 : -1); // Prefer faster wins
  }
  if (isBoardFull(board)) {
    return 0; // Draw
  }
  
  // Always maximize from current player's view
  let maxScore = -Infinity;
  for (let i = 0; i < 9; i++) {
    if (board[i] === 0) {
      board[i] = -1; // Current player moves
      let score = -negamax(board, depth + 1); // Negate child score!
      board[i] = 0;
      maxScore = Math.max(maxScore, score);
    }
  }
  return maxScore;
}

function findBestMove(board) {
  let bestScore = -Infinity;
  let bestMove = 0;
  
  for (let i = 0; i < 9; i++) {
    if (board[i] === 0) {
      board[i] = -1;
      let score = -negamax(board, 0); // Negate at root level
      board[i] = 0;
      
      if (score > bestScore) {
        bestScore = score;
        bestMove = i;
      }
    }
  }
  return bestMove;
}

Why Negamax is Better

Aspect	Minimax	Negamax
Code Complexity	2 branches (max/min)	1 branch (max only)
Lines of Code	~40	~20
Readability	Separate logic	Unified logic
Performance	Identical	Identical
Scores	Sign alternates	Relative to player

Key Insight: Score Negation

When evaluating a position from your opponent’s perspective, their gain is your loss. So:

• My best move scores +10
• From opponent’s view, it scores -10
• When I get their score back, I negate it: -(-10) = +10 ✓

Board Representation:

• 1D array of 9 numbers: indices 0-8
• Values: 0 = empty, 1 = your X, -1 = AI’s O

Scoring System:

• +10: Current player wins
• -10: Current player loses
• 0: Draw
• Depth adjustment: Prefers faster wins, delays losses

Where to find it: /assets/js/games.js (lines 5-40)

Code on GitHub

Check out the complete implementation on GitHub with detailed comments and performance notes.

Next Steps

Ready for more complexity? Check out Checkers to learn about alpha-beta pruning, an optimization that reduces computation by 100-1000x.