I Built a Tic-Tac-Toe AI That Literally Cannot Lose

terministic game engine requires three architectural components: state representation, recursive traversal with alternating optimization objectives, and terminal scoring with temporal weighting. The implementation below uses TypeScript to demonstrate a production-grade structure that separates state mutation, evaluation, and move selection.

Architecture Decisions

1. In-place mutation with explicit backtracking: Cloning the board on every recursive call creates garbage collection pressure. Mutating a single array and reverting changes after evaluation reduces memory allocation by ~90%.
2. Depth-aware terminal scoring: Raw outcome values (+10, -10, 0) are adjusted by the current recursion depth. This forces the engine to prefer shorter winning paths and longer losing paths.
3. Alternating optimization: The engine maximizes on its turn and minimizes on the opponent's turn. This mathematical duality guarantees that the selected move is optimal against a perfect adversary.
4. No alpha-beta pruning at this scale: Pruning adds branch-checking overhead. For state spaces under 10,000 nodes, exhaustive traversal is faster and simpler. Pruning becomes necessary only when depth exceeds 12-15 plies.

Implementation

type Player = 'agent' | 'opponent';
type Cell = Player | null;
type Board = Cell[];

interface EvaluationResult {
  score: number;
  bestMove: number | null;
}

class DeterministicEngine {
  private readonly WIN_SCORE = 10;
  private readonly DRAW_SCORE = 0;
  private readonly WINNING_LINES = [
    [0, 1, 2], [3, 4, 5], [6, 7, 8],
    [0, 3, 6], [1, 4, 7], [2, 5, 8],
    [0, 4, 8], [2, 4, 6]
  ];

  public computeNextMove(board: Board, currentTurn: Player): number {
    const result = this.traverseStateTree(board, currentTurn, 0);
    if (result.bestMove === null) {
      throw new Error('No valid moves available in terminal state');
    }
    return result.bestMove;
  }

  private traverseStateTree(
    board: Board,
    turn: Player,
    depth: number
  ): EvaluationResult {
    const terminalCheck = this.evaluateTerminal(board);
    if (terminalCheck !== null) {
      return { score: terminalCheck, bestMove: null };
    }

    const availableIndices = board
      .map((cell, index) => (cell === null ? index : -1))
      .filter(index => index !== -1);

    let optimalScore = turn === 'agent' ? -Infinity : Infinity;
    let selectedMove: number | null = null;

    for (const index of availableIndices) {
      board[index] = turn;
      const nextTurn = turn === 'agent' ? 'opponent' : 'agent';
      const childResult = this.traverseStateTree(board, nextTurn, depth + 1);
      board[index] = null;

      if (turn === 'agent') {
        if (childResult.score > optimalScore) {
          optimalScore = childResult.score;
          selectedMove = index;
        }
      } else {
        if (childResult.score < optimalScore) {
          optimalScore = childResult.score;
          selectedMove = index;
        }
      }
    }

    return { score: optimalScore, bestMove: selectedMove };
  }

  private evaluateTerminal(board: Board): number | null {
    const agentWin = this.checkVictory(board, 'agent');
    if (agentWin) return this.WIN_SCORE - this.countOccupied(board);

    const opponentWin = this.checkVictory(board, 'opponent');
    if (opponentWin) return -this.WIN_SCORE + this.countOccupied(board);

    const isFull = board.every(cell => cell !== null);
    if (isFull) return this.DRAW_SCORE;

    return null;
  }

  private checkVictory(board: Board, player: Player): boolean {
    return this.WINNING_LINES.some(line =>
      line.every(index => board[index] === player)
    );
  }

  private countOccupied(board: Board): number {
    return board.filter(cell => cell !== null).length;
  }
}

Why This Structure Works

The traverseStateTree method implements the core minimax logic without external dependencies. By passing depth through recursive calls, the terminal evaluation function can adjust scores dynamically. The evaluateTerminal method returns null for non-terminal states, allowing the recursion to continue. When a terminal state is reached, the score is modified by the number of occupied cells. This creates a negative correlation between win speed and score magnitude for the agent, and a positive correlation for the opponent. The engine naturally selects branches that minimize its own path to victory while maximizing the opponent's path to defeat.

Move selection happens at the root level. The computeNextMove method calls the traversal once, extracts the bestMove from the root's evaluation, and returns it. This separation ensures that the recursive function remains pure and focused on score propagation, while the public API handles state interaction.

Pitfall Guide

1. State Mutation Without Backtracking

Explanation: Developers often mutate the board array during recursion but forget to revert the change after evaluating the branch. This corrupts subsequent recursive calls, causing the engine to evaluate invalid states. Fix: Always restore the cell to null immediately after the recursive call returns. The pattern board[index] = turn; ... board[index] = null; must be strictly enforced. Consider wrapping mutations in a try-finally block for safety.

2. Ignoring Depth in Terminal Scores

Explanation: Returning static values (+10, -10, 0) makes the algorithm indifferent to how quickly a win occurs. The engine may choose a 5-move win over a 1-move win if both evaluate to +10. Fix: Subtract the current depth from winning scores and add it to losing scores. This creates a gradient that forces temporal optimization without changing the fundamental minimax logic.

3. Array Cloning on Every Recursive Call

Explanation: Creating a new board array for each branch ([...board]) generates massive garbage collection overhead. In deeper state spaces, this causes frame drops and memory pressure. Fix: Use a single mutable array and backtrack explicitly. If immutability is required for debugging, clone only at the root level or use structural sharing techniques like persistent data structures.

4. Hardcoding Evaluation Thresholds

Explanation: Magic numbers like 10 or -10 scattered throughout the code make tuning difficult. Changing the scoring system requires hunting through multiple functions. Fix: Centralize scoring constants in a configuration object or class properties. This allows runtime tuning and makes the evaluation logic auditable.

5. Applying Alpha-Beta Pruning Prematurely

Explanation: Alpha-beta pruning is often introduced early to "optimize" the engine. For small state spaces, the branch-checking overhead actually slows execution. Pruning also complicates debugging because branches are silently skipped. Fix: Implement exhaustive search first. Only introduce pruning when the state space exceeds 50,000 nodes or when evaluation depth surpasses 12 plies. Validate correctness against the unpruned version before deployment.

6. Symmetry Blindness

Explanation: The engine evaluates mirrored or rotated board states as unique positions. This wastes computation on mathematically identical scenarios. Fix: Implement a canonicalization step that normalizes board states before evaluation. For tic-tac-toe, this reduces the effective state space by ~75%. Use hash-based memoization to cache evaluated positions.

7. Blocking vs Winning Priority Confusion

Explanation: New implementations sometimes prioritize blocking the opponent over securing a win, leading to missed opportunities. This usually stems from incorrect evaluation order or flawed heuristic weighting. Fix: Rely on the mathematical guarantee of minimax. If the engine correctly evaluates all terminal states, winning moves will naturally score higher than blocking moves. Remove manual priority overrides; they break the algorithm's optimality proof.

Production Bundle

Action Checklist

• Define terminal state evaluation with explicit win/loss/draw conditions
• Implement recursive traversal with alternating max/min optimization
• Add depth-aware scoring to prefer faster wins and slower losses
• Use in-place mutation with strict backtracking to minimize memory allocation
• Centralize scoring constants for runtime tuning and auditability
• Validate move selection against known solved positions before deployment
• Profile recursion depth and node count to determine pruning necessity
• Implement board canonicalization if state space exceeds 10,000 nodes

Decision Matrix

Scenario	Recommended Approach	Why	Cost Impact
State space < 10k nodes	Exhaustive Minimax	Simpler implementation, faster execution than pruning overhead	Low
State space 10k–100k nodes	Minimax + Transposition Table	Caches evaluated positions, reduces redundant computation	Medium
State space > 100k nodes	Alpha-Beta Pruning + Depth Limit	Prevents exponential blowup, enables real-time responses	High
Hidden information or randomness	Monte Carlo Tree Search (MCTS)	Handles probability distributions and incomplete state visibility	Very High
Real-time strategy / continuous state	Heuristic Evaluation + Iterative Deepening	Balances accuracy with strict time constraints	High

Configuration Template

interface EngineConfig {
  scoring: {
    winBase: number;
    lossBase: number;
    drawBase: number;
    depthMultiplier: number;
  };
  traversal: {
    maxDepth: number;
    enablePruning: boolean;
    pruneThreshold: number;
  };
  optimization: {
    useTranspositionTable: boolean;
    tableSize: number;
    enableMoveOrdering: boolean;
  };
}

const defaultConfig: EngineConfig = {
  scoring: {
    winBase: 10,
    lossBase: -10,
    drawBase: 0,
    depthMultiplier: 1
  },
  traversal: {
    maxDepth: 9,
    enablePruning: false,
    pruneThreshold: 0
  },
  optimization: {
    useTranspositionTable: false,
    tableSize: 0,
    enableMoveOrdering: false
  }
};

export { EngineConfig, defaultConfig };

Quick Start Guide

1. Initialize the engine: Import the DeterministicEngine class and instantiate it with default configuration. No external dependencies are required.
2. Prepare the board state: Create a 9-element array representing the grid. Use null for empty cells, 'agent' for AI moves, and 'opponent' for player moves.
3. Request the next move: Call computeNextMove(board, 'agent'). The method returns the index of the optimal cell. Update the board array and render the new state.
4. Handle terminal states: After each move, check if the board contains a winning line or is full. If either condition is true, end the game loop and display the result.
5. Tune for production: If evaluation latency exceeds 16ms, enable the transposition table in the configuration template. Increase tableSize to 4096 and set useTranspositionTable to true. Re-benchmark to confirm performance gains.