Over-engineered tic-tac-toe
A tic-tac-toe you can't beat — six opponents from a coin-flip to a tree-search AI, in one file.
Tic-tac-toe is solved — so we over-engineer it. One self-contained HTML file plays the classic 3×3 game against six opponents that trace the arc from naive to formidable: Random, Minimax, Alpha-Beta, MaxN, Paranoid, and Monte Carlo Tree Search — across both 2-player and 3-player modes. The rules stay a pure, framework-free core; every engine hides behind one interface; and "unbeatable" is a claim the tests are required to prove.
§1 Context
The point isn't to win at tic-tac-toe — a child can force a draw. The point is to make the game a teaching surface for the algorithmic progression in Over-Engineering Tic-Tac-Toe: from a coin-flip, to exhaustive search, to search that prunes, to the multiplayer generalisations, to a learner that knows only the rules. Each engine is meant to be tried, felt, and compared side by side.
§2 User scenarios
As a player, I pick an opponent and play a full 2-player game on a 3×3 board.
Acceptance: I place a mark on any empty cell on my turn; the CPU replies; the game ends the instant someone makes a line or the board fills, and the result is shown.
As a player, I switch to 3-player mode and choose an engine for each CPU seat.
Acceptance: a third seat (△) appears; the opponent menu now offers the multiplayer engines; turns rotate three ways; the game still detects wins and draws correctly.
As a curious player, I want to see how each opponent "thinks."
Acceptance: after each CPU move a chip reports its work — positions explored, or simulations run — and a legend one-lines every engine.
§3 Requirements
Only legal moves are accepted
A move MUST land only on an empty cell, only on the player-to-move's turn. Occupied cells and out-of-turn input are ignored.
Wins and draws end the game immediately
The system MUST detect a completed line across all eight rows, columns, and diagonals and halt play on that move; a full board with no line MUST resolve as a draw.
Six engines behind one interface
The product MUST offer Random, Minimax, Alpha-Beta, MaxN, Paranoid, and MCTS, each selectable and each reached through a single chooseMove(engine, board, player, players) contract. Adding an engine MUST NOT touch the game loop.
Two- and three-player modes
The game MUST support 2 and 3 players on a 3×3, 4×4, or 5×5 board, and the opponent menu MUST offer only the engines that are meaningful for the current mode.
Show each engine's work
After a CPU move the game SHOULD report the engine and the effort it spent — positions explored (search) or simulations run (MCTS).
Configurable board size and win length
The game MUST support a board of 3×3, 4×4, or 5×5 and a win length of 3 to N marks in a row, chosen independently; the win-length and opponent menus MUST stay valid for the chosen size.
A move resolves under 500 ms
Every engine MUST return a move in under 500 ms on a laptop — on every board size — bounding search (full on 3×3, depth-limited beyond) and the per-size MCTS iteration budget.
One self-contained file, zero dependencies
The whole product MUST be one HTML file with no build step and no runtime dependencies — it opens from file://.
- ×Boards beyond 5×5, or non-square / gravity rules → defer-to TBD
- ×Networked / remote multiplayer → defer-to TBD
- ×Persisted stats / accounts → defer-to TBD
§4 Data model
- Board
- Nine cells, each null | 0 | 1 | 2 (empty, or the player who owns it).
- Seat
- { kind: human | cpu, engine } — seat 0 is you; CPU seats carry a chosen engine.
- Game
- { board, current, players, over } — whose turn, how many seats, and whether play has ended.
§5 Success criteria
A perfect engine never loses. A random player wins zero of at least 20 games against Minimax and against Alpha-Beta.
Every game terminates cleanly. In 2- and 3-player modes, play always ends in a win or a draw with no illegal or over-filled board states.
Pruning demonstrably pays. For the same opening, Alpha-Beta explores strictly fewer positions than plain Minimax.
Larger boards stay decisive. A three-player game on a 5×5 board won by three in a row does not always draw — measured: 0 draws in 8 games.
§6 Open questions
None open at write time. The one real design fork — whether 3-player needs a bigger board for MaxN to matter — was resolved in the plan (D-001): keep the 3×3 board, accept that strong 3-player play tends to draw, and surface that as a finding rather than a defect.
§7 Change log
One file. Renders anywhere. Degrades to readable static HTML.