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. Alpha-beta prunes branches the moment it can prove they cannot change the outcome, so it explores far fewer nodes to reach the same optimal move. That saving is why Hard mode still replies instantly even though it is searching the complete 3×3 game tree.
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.
Does the difficulty level change the algorithm?
Yes. Easy picks a legal move at random, Medium uses a greedy heuristic that plays well but makes deliberate mistakes, and only Hard runs the full minimax search benchmarked on this page. That is why Easy and Medium are beatable while Hard, on a 3×3 board, is not.
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.