How our Tic-Tac-Toe AI never loses: minimax, alpha-beta, and a full-tree proof
Everyone says a minimax Tic-Tac-Toe bot is "unbeatable." We wanted a number, not a vibe — so we benchmarked the exact engine that ships on the Tic-Tac-Toe game. The code is open source, and every figure below reproduces with node benchmark.js.
· 6 min read · all numbers from a re-runnable benchmark
1. The proof isn't a sample — it's the whole game tree
On 3×3, Hard mode runs a full-depth (9-ply) minimax search, so its reply to any position is deterministic. That lets us enumerate every reachable game — every move a human could make, answered by the AI. Playing second, the way it does in the game, and playing first:
| Scenario | Lines | Wins | Draws | Losses |
|---|---|---|---|---|
| Human moves first (the real game) | 569 | 386 | 183 | 0 |
| AI moves first | 73 | 71 | 2 | 0 |
| All reachable 3×3 games | 642 | 457 | 185 | 0 |
Across all 642 reachable lines the AI never loses. On a 3×3 board the best any opponent can force is a draw — that's not a claim, it's the shape of the game.
2. Alpha-beta pruning earns its keep
Searching the whole tree naively is wasteful. Alpha-beta pruning discards branches that can't change the decision. Choosing the opening move at full depth, counting minimax node visits:
93.4% fewer node visits for an identical decision — 549,945 down to 36,528.
3. Does it break on bigger boards?
Larger boards cap the search depth (9 on 3×3 → 7 on 4×4 → 5 on 5×5 → 3 on 6×6+) and only need 4-in-a-row. We expected that to open a crack. It didn't: across 628 simulated games up to 6×6, against random and greedy opponents, still 0 losses. What changes isn't losing — it's that forcing a win gets harder, so results drift toward draws. Win/draw split vs a random opponent (the loss bar never appears):
Win Draw — 0% loss at every size. Against a competent (greedy) opponent the result settles into draws; against loose (random) play it mostly wins.
Why it holds up (and where it's actually fragile)
Two things keep it airtight: it always blocks an immediate threat before it searches, and 4-in-a-row stays defensible within the depth cap. So the depth-limited AI on big boards never handed over a game.
The only real fragility is theoretical — a human who can plant a fork beyond the AI's search horizon on a large board, forcing a win the capped search can't see coming. That's exactly why the full game offers boards from 3×3 up to 10×10: 3×3 is a guaranteed draw against perfect play, but the bigger boards are where a sharp human actually has a shot.
engine.js in the repo is the exact file the game ships — the benchmark measures the engine you actually play against, not a re-implementation. Opponents use a seeded PRNG, so the figures reproduce exactly.
node benchmark.js # all three parts
node benchmark.js proof # exhaustive 3×3 proof (0 losses)
node benchmark.js pruning # alpha-beta node counts (93.4%)
node benchmark.js scaling # by-board-size sweepFrequently asked questions
Is a minimax tic-tac-toe AI really unbeatable?
On a 3×3 board, yes — provably. The engine searches the full 9-ply game tree with minimax, so its reply to any position is optimal. Enumerating all 642 reachable games gives 0 losses; the best any opponent can force is a draw.
How much faster is alpha-beta pruning?
Choosing the opening move at full depth, plain minimax visits 549,945 positions; alpha-beta visits 36,528 for an identical decision — a 93.4% reduction.
Can the AI lose on bigger boards?
Not in testing. On 4×4 through 6×6 the search depth is capped, but across 628 simulated games against random and greedy opponents the AI still lost 0. What changes is that forcing a win gets harder, so results drift toward draws rather than losses.
Try to beat it
642 reachable games, 0 losses. See if you can do better against the same full-depth engine — or scale up to a bigger board where humans still have a chance.
Related: the methodology behind all our game-AI numbers is in How We Benchmark a Game AI, and why these are search algorithms and not LLMs in Game AI Isn't an LLM.