How an unbeatable Tic-Tac-Toe AI thinks: Minimax and alpha-beta, with real numbers

01Why you can’t beat it

Tic-Tac-Toe looks too small to need an algorithm. It isn’t small for a computer that wants to be sure. Counting every way a game can unfold, move by move until someone wins or the board is full, there are 255,168 possible games.

With perfect play from both sides, every game ends in a draw. So “unbeatable” doesn’t mean the AI always wins. It means you can never find a line where it loses. Minimax is the method that guarantees it: before each move, the AI looks at every way the rest of the game can go and picks the move whose worst case is best for it.

In my version, you play O and move first; the AI plays X. Everything below uses that setup.

02Every game, played to the end

Minimax treats the game as a tree. The current board is the root, each empty square is a branch, and the leaves are finished games. To choose a move, the AI:

1. Lists every empty square on the board.
2. Plays each one in its head, then lets you answer with every possible reply — and repeats, until every line has ended.
3. Scores each finished game and passes the scores back up the tree: on its own turns the AI keeps the maximum, on your turns it assumes you pick the minimum.
4. Plays the square whose score survived to the top.

Step 3 is the whole idea. The AI never hopes you will make a mistake. It assumes you will always play your best move, so the score it gets is a score you can’t take away from it.

03Scoring the end of a game

The leaves need a number. My game uses the simplest scale there is:

A common refinement subtracts the depth from the score (10 - depth for a win, depth - 10 for a loss). The AI then prefers a quick win over a slow one, and, when a loss can’t be avoided, takes the longest road to it. Against a human it makes the AI feel sharper; it doesn’t change whether it can lose.

04The code

The whole idea fits in one recursive function. winner(board) returns 'X', 'O' or null, and emptyCells(board) lists the free squares:

function minimax(board, player, alpha = -Infinity, beta = Infinity) {
  const w = winner(board);
  if (w === "X") return 10;   // the AI won
  if (w === "O") return -10;  // you won
  const cells = emptyCells(board);
  if (cells.length === 0) return 0; // draw

  let best = player === "X" ? -Infinity : Infinity;
  for (const cell of cells) {
    board[cell] = player;
    const score = minimax(board, player === "X" ? "O" : "X", alpha, beta);
    board[cell] = null;

    if (player === "X") { best = Math.max(best, score); alpha = Math.max(alpha, best); }
    else                { best = Math.min(best, score); beta  = Math.min(beta, best); }
    if (beta <= alpha) break; // prune: the other side will never allow this line
  }
  return best;
}

Without alpha, beta and the break, this is plain Minimax: correct, but it explores every branch. Those few additions are alpha-beta pruning. To pick a move, the AI tries each free square with this function, keeps alpha from one square to the next, and plays the first square with the highest score.

05Cutting the tree: alpha-beta

Alpha-beta carries two numbers down the tree. alpha is the best score the AI is already sure of; beta is the best score you are already sure of. The moment a branch can’t beat what one side already has, the rest of that branch is skipped: that side would simply never let the game go there.

Pruning doesn’t make the AI smarter. It makes it stop thinking about moves nobody would play.

A concrete case: the AI has already found a move that guarantees a draw (alpha = 0). It starts looking at a second move, and the first reply it examines lets you win (-10). Since you will pick the minimum, that second move is worth at most -10, which is already worse than the draw in hand. The AI stops looking at your other replies to that move.

06What the numbers say

I counted the positions each version visits for the AI’s first decision, after each of your 9 possible opening moves:

That is roughly 13 to 26 times less work for the same decision. From an empty board the gap is wider still: 549,946 positions for plain Minimax against 18,297 with alpha-beta.

The order in which squares are tried matters. Alpha-beta prunes most when the best move is examined first, which is why the range is so wide: some openings happen to put good replies early in the list. Trying the centre and the corners before the edges is a cheap way to prune more.

On a 3×3 board none of this is needed for speed: plain Minimax answers instantly in a browser. It matters as soon as the game grows. On a 4×4 board or in Connect Four, the full tree is far too big to search, and alpha-beta plus a depth limit is what makes a strong AI possible.