Tic-Tac-Toe AI with Minimax and Alpha-Beta Pruning

My earlier Programs page listed a Lisp tic-tac-toe opponent using minimax with alpha-beta pruning. The archived summary also mentioned XLISP-Plus 3.04 on Windows. That small project is a useful way to explain a fundamental game-search idea: choose a move while assuming the opponent will also choose well.

The implementation in this article is new JavaScript teaching code, not recovered source from the old Lisp program. You can play against the browser demo or download its search engine. The aim is to make the decision process inspectable and testable, rather than attach a machine-learning label to a program that does not train on data.

Represent a complete game state

The board is an array of nine cells containing an empty string, X or O. A fixed list describes the eight winning lines. A separate function decides whether the board contains a win, a draw or an unfinished game. Separating that rule from the search lets you test the game itself before testing the opponent.

A state also implies whose turn comes next. X starts, so equal counts mean X is next; one extra X means O is next. The helper rejects malformed cell values and inconsistent turn or winner counts. Its normal input is a position produced by legal play. It copies the input so the caller’s visible board does not change while hypothetical moves are explored.

Score endings from one consistent perspective

This example always measures the score from X’s perspective. An X win is positive, an O win is negative and a draw is zero. X therefore chooses a maximum and O chooses a minimum. Mixing a score from one player’s perspective with a comparison from the other is a common source of an opponent that seems to help you win.

The terminal score also includes search depth. A faster X win receives a larger positive number; a faster O win receives a more negative number. That makes both players prefer an earlier win when one is forced. Draws remain equal. The depth is relative to this call’s starting position, so it should not be cached blindly as if the score were an immutable property of every board.

Minimax considers the opponent’s best reply

For every legal move, the search places a hypothetical mark, explores the opponent’s possible replies and then undoes the mark. It continues until a terminal position is reached. The value returned through the tree represents what each player can force when both play optimally.

For standard tic-tac-toe, the remaining tree is small enough to search completely. A larger game often needs a depth limit and an approximate evaluation of unfinished positions. That changes the guarantee: a search using an imperfect estimate is not equivalent to looking all the way to the game’s ending.

Alpha-beta skips branches that cannot change the decision

Alpha and beta record bounds established by choices already available along the current search path. When a branch cannot improve the result for the player considering it, the remaining siblings can be skipped. This is pruning, not a different set of game rules.

Move order affects how much work gets skipped. The code tries the center, corners and then edges. Another ordering can produce a different node count or choose another equally good move, while preserving the same game-theoretic value. The small implementation starts each root move with a fresh full window for clarity; a more advanced version can share bounds between root alternatives.

Inspect the complete engine

The helper returns a move index, score and visited-node count, or no move for a finished game. It uses no external library. The complete download is also the engine used by the standalone demo.

const 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]
];
const ORDER = [4, 0, 2, 6, 8, 1, 3, 5, 7];

function outcome(board) {
  for (const [a, b, c] of LINES) {
    if (board[a] && board[a] === board[b] && board[a] === board[c]) {
      return board[a];
    }
  }
  return board.includes('') ? null : 'draw';
}

function chooseMove(input) {
  if (!Array.isArray(input) || input.length !== 9 ||
      Array.from(input).some(cell => !['', 'X', 'O'].includes(cell))) {
    throw new Error('Use an array of nine empty, X or O cells');
  }
  const board = input.slice();
  const x = board.filter(cell => cell === 'X').length;
  const o = board.filter(cell => cell === 'O').length;
  const xWins = LINES.some(line => line.every(i => board[i] === 'X'));
  const oWins = LINES.some(line => line.every(i => board[i] === 'O'));
  if (!(x === o || x === o + 1) || (xWins && oWins) ||
      (xWins && x !== o + 1) || (oWins && x !== o)) {
    throw new Error('Board has inconsistent turns or winners');
  }
  if (outcome(board)) return null;
  const turn = x === o ? 'X' : 'O';
  let nodes = 0;
  function search(player, depth, alpha, beta) {
    nodes++;
    const result = outcome(board);
    if (result === 'X') return 10 - depth;
    if (result === 'O') return depth - 10;
    if (result === 'draw') return 0;
    let best = player === 'X' ? -Infinity : Infinity;
    for (const index of ORDER) {
      if (board[index] !== '') continue;
      board[index] = player;
      const value = search(player === 'X' ? 'O' : 'X', depth + 1, alpha, beta);
      board[index] = '';
      if (player === 'X') {
        best = Math.max(best, value);
        alpha = Math.max(alpha, best);
      } else {
        best = Math.min(best, value);
        beta = Math.min(beta, best);
      }
      if (alpha >= beta) break;
    }
    return best;
  }
  let bestScore = turn === 'X' ? -Infinity : Infinity;
  let bestIndex = null;
  for (const index of ORDER) {
    if (board[index] !== '') continue;
    board[index] = turn;
    const value = search(turn === 'X' ? 'O' : 'X', 1, -Infinity, Infinity);
    board[index] = '';
    if (bestIndex === null || (turn === 'X' ? value > bestScore : value < bestScore)) {
      bestScore = value;
      bestIndex = index;
    }
  }
  return {index: bestIndex, score: bestScore, nodes};
}

if (typeof module !== 'undefined' && module.exports) {
  module.exports = {chooseMove, outcome};
}

Keep the interface separate from the search

The browser demo lets the reader play X and asks the engine for O’s response after each valid human move. Its buttons retain native keyboard interaction, and a status message reports whose turn it is or how the game ended. Clicking an occupied cell does nothing; the engine is not asked to explain an illegal move.

The demo does not simulate a thinking delay. The search is small enough to finish quickly for this board, and adding animation would not improve the algorithm. For a game with expensive search, keep the interface responsive and consider a worker. Do not make a frozen page look intentional by placing a spinner above it.

Test decisions against an independent reference

A good test is stronger than a few matches against a human. Enumerate the positions reachable from an empty board, stopping expansion after a win or draw. Compare the chosen move’s eventual value with a simple reference minimax that does not use alpha-beta pruning. This checks that skipping branches did not change the decision.

Also verify that the input board remains unchanged, terminal boards return no move, and malformed boards fail clearly. From a valid position where a draw can still be forced, optimal play should not choose a losing continuation. Separately explore every human reply against the chosen computer moves to check that the demo opponent cannot be defeated from the initial board.

What the old project still explains

Minimax shows that useful game AI can come from explicit rules and search rather than training examples. The archived project and the new demo use different languages but share that underlying idea. Keep the historical claim narrow until original files are recovered: the archive identifies the technique, not every implementation choice in the new engine.

Read the archived Programs page and Berkeley’s minimax explanation for context. Continue with the A* puzzle project to compare adversarial search with finding a path to a fixed goal.