Introduction

Almost everyone learns tic-tac-toe before they learn to read: three rows, three columns, and a race to line up three of your marks. You probably also discovered, after a few rounds, that between two careful players nobody ever wins. Every game grinds to a draw.

That gut feeling is exactly right — and computer science can prove it. Tic-tac-toe is a solved game: someone has computed the outcome of every possible position with perfect play on both sides. The answer is short and complete. With no mistakes, the result is always a draw.

What makes this remarkable is not the game itself but the fact that we can finish the analysis at all. For most interesting games the full tree is astronomically large. Tic-tac-toe is the rare case small enough to solve by hand — and that makes it the textbook example of what "solved" really means.

Play the Unbeatable Engine

Here is a tic-tac-toe board. You play X, the computer plays O. The computer uses minimax: before every move it looks ahead through every line the game could take and picks one that can never lose.

<p class="hint">You are <b>X</b>, the computer is <b>O</b>. The engine uses <b>minimax</b>: it looks at every line the game could take and plays one that can never lose. Try to beat it — the best you can manage is a draw.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Your move. Click any square.</div>
<div class="btns">
  <button id="reset" type="button">New game</button>
  <button id="first" type="button" class="ghost">Let O move first</button>
</div>
<div class="score" id="score">You: 0 &nbsp; Draws: 0 &nbsp; Engine: 0</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(3, 64px); gap: 4px; margin: .4rem 0; }
.cell { width: 64px; height: 64px; display: flex; align-items: center; justify-content: center;
        font: 700 34px ui-monospace, monospace; border-radius: 8px; user-select: none;
        background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; cursor: pointer; transition: all .1s; }
.cell.taken { cursor: default; }
.cell.empty:hover { background: #d9e3ec; }
.cell.x { color: #1d3557; }
.cell.o { color: #e63946; }
.cell.win { background: #c8e6c9; border-color: #0a7d33; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.score { font-size: .85rem; color: #555; margin-top: .6rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Tic-tac-toe is a SOLVED game: minimax explores the whole game tree, so the engine (O) can always at least draw. With perfect play from the empty board the value is a draw — you can never beat this engine.
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]];
let board, gameOver, score = { you: 0, draw: 0, eng: 0 };

// Returns 'X', 'O', 'draw', or null (game not finished).
function outcome(b){
  for(const [a,c,d] of LINES){ if(b[a] && b[a]===b[c] && b[a]===b[d]) return b[a]; }
  return b.includes('') ? null : 'draw';
}
function winningLine(b){
  for(const L of LINES){ const [a,c,d]=L; if(b[a] && b[a]===b[c] && b[a]===b[d]) return L; }
  return null;
}
// Minimax: O maximizes, X minimizes. Score +10/-10 adjusted by depth so the engine prefers faster wins and slower losses. Returns {score, move}.
function minimax(b, turn, depth){
  const w = outcome(b);
  if(w === 'O') return { score: 10 - depth };
  if(w === 'X') return { score: depth - 10 };
  if(w === 'draw') return { score: 0 };
  let best = (turn === 'O') ? { score: -Infinity } : { score: Infinity };
  for(let i=0;i<9;i++){ if(b[i]) continue;
    b[i] = turn;
    const r = minimax(b, turn === 'O' ? 'X' : 'O', depth + 1);
    b[i] = '';
    if(turn === 'O'){ if(r.score > best.score) best = { score: r.score, move: i }; }
    else { if(r.score < best.score) best = { score: r.score, move: i }; }
  }
  return best;
}
function engineMove(){
  const { move } = minimax(board.slice(), 'O', 0);
  if(move != null){ board[move] = 'O'; }
}

const boardEl = () => document.getElementById('board');
function setStatus(t, cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function showScore(){ document.getElementById('score').innerHTML =
  fmt('You: %you% &nbsp; Draws: %draw% &nbsp; Engine: %eng%', { you: score.you, draw: score.draw, eng: score.eng }); }

function render(){
  const b = boardEl(); b.innerHTML='';
  const win = winningLine(board);
  for(let i=0;i<9;i++){
    const d=document.createElement('div');
    const v=board[i];
    d.className='cell '+(v?'taken '+v.toLowerCase():'empty')+(win && win.includes(i)?' win':'');
    d.textContent=v;
    if(!v && !gameOver) d.addEventListener('click',()=>play(i));
    b.appendChild(d);
  }
}
function finish(){
  const w = outcome(board); gameOver = true;
  if(w === 'X'){ score.you++; setStatus('You win! (the engine let that slip — it should be impossible)','ok'); }
  else if(w === 'O'){ score.eng++; setStatus('The engine wins. Try forcing a draw next time.','bad'); }
  else { score.draw++; setStatus('Draw — perfect play on both sides. That is the solved value.','ok'); }
  showScore(); render();
}
function play(i){
  if(gameOver || board[i]) return;
  board[i] = 'X';
  if(outcome(board)){ finish(); return; }
  engineMove();
  if(outcome(board)){ finish(); return; }
  setStatus('Your move.', '');
  render();
}
function newGame(engineFirst){
  board = ['','','','','','','','','']; gameOver = false;
  if(engineFirst){ engineMove(); setStatus('Engine opened. Your move.',''); }
  else setStatus('Your move. Click any square.','');
  render();
}
document.getElementById('reset').addEventListener('click',()=>newGame(false));
document.getElementById('first').addEventListener('click',()=>newGame(true));
newGame(false);
Result
Console

Try as hard as you like — set a double threat, play the corners, rush the center. You will find the same thing the math guarantees: the engine never loses. The best outcome you can force is a draw. That is what a solved game feels like from the inside: the answer was decided before you made your first move.

The Real Complexity

How hard is tic-tac-toe, really? For the standard 3×3 board, the honest answer is: not hard at all — and that is precisely the point.

  • The tree is tiny. A loose upper bound on board arrangements is 393^{9} = 19,683, and the number of actually reachable games is only a few hundred thousand before symmetry. That fits comfortably in memory, or even on paper.
  • Minimax solves it exactly. Walk the game tree to the end, label each leaf win/lose/draw, and back the values up. The value of the empty board is a draw: neither player can force a win against perfect defense.
  • It is a solved game. Every position's perfect-play outcome is known. The optimal strategy is so small it can be written as a short list of rules — center, opposite corner, block, fork — which is why beginners eventually "solve" it on their own.
  • Generalize and it gets hard. Tic-tac-toe is the 3,3,3 case of the m,n,k-game family (an m×n board, k in a row). Scale the board up and the tree explodes; deciding the winner of generalized k-in-a-row games is PSPACE-hard, and broader generalized games climb to EXPTIME.

So tic-tac-toe sits at the friendly end of a spectrum that runs all the way to genuinely intractable games. It is solvable for one reason only: the tree is small enough to look at all of it.

Where It Matters

Tic-tac-toe is small, but the machinery used to solve it is everywhere a decision has an opponent:

  • Game-playing AI: minimax, plus the alpha-beta pruning that speeds it up, is the historical backbone of engines for checkers, chess and beyond — tic-tac-toe is where you first see the idea in full.
  • Solved games: checkers was solved in 2007 (Schaeffer et al.) by the same back-up-the-tree logic, just on a colossally bigger tree. Tic-tac-toe is the gentle warm-up for that whole research program.
  • Adversarial decision making: "assume the opponent plays their best reply" is the heart of minimax and reappears in economics, security and robust planning.
  • Teaching search: because its tree is small enough to draw, tic-tac-toe is the standard first example for game trees, recursion and dynamic programming.

Understand why tic-tac-toe is a draw and you have met minimax — the same engine that, scaled up against an exploding tree, runs into the wall described in Why Chess Is Hard for Machines.

Conclusion

Tic-tac-toe earns its place as the textbook solved game: its tree is small enough that we can look at every line, prove that perfect play always ends in a draw, and write the winning-or-drawing strategy on a napkin. That is the rare luxury of completeness.

The lesson is not that the game is easy — it is that "easy" means the whole search fits. Push the board a little bigger and the same minimax idea slams into the same exponential wall that makes chess so hard. Tic-tac-toe is the one corner of that landscape where we genuinely get to see the end.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/tic-tac-toe/Content licensed under CC BY-NC 4.0.