Tic-Tac-Toe

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.

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">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_your_move_click}}</div>
<div class="btns">
  <button id="reset" type="button">{{btn_new_game}}</button>
  <button id="first" type="button" class="ghost">{{btn_o_first}}</button>
</div>
<div class="score" id="score">{{score_you}}: 0 &nbsp; {{score_draws}}: 0 &nbsp; {{score_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; }

// Code not found

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.

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 $3^{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.

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.

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.