Proving It's Actually Unbeatable: How I Benchmark a Game AI Before Publishing a Number

This was originally published on the LK Forge blog, where the charts are interactive and you can play the AI it talks about.

"Unbeatable" is a testable claim, not a marketing word. Before that word goes anywhere near the tic-tac-toe page, the shipped AI has to survive a headless self-play harness — the same functions the browser runs, played thousands of times with no human at the keyboard. Here is what that harness measured, including the part that didn't look good at first.

The counterintuitive result

A tic-tac-toe AI with an 87% win rate still lost games that the full-depth engine never would. "It's minimax, so it's unbeatable" is true at exactly one depth setting — and the only way to find which is to run every depth and count the losses.

The numbers

Against 1,000 games of a random-move opponent, the AI went 825 wins, 175 draws, 0 losses. Against 200 games of the AI playing a perfect copy of itself, every game ended in a draw — the correct result for perfect tic-tac-toe play, and the harder claim to satisfy. Across both runs, 1,200 games total, the loss count is 0. That is the number the word "unbeatable" is actually standing on.

The harness

The benchmark is headless self-play: the exact move-selection functions from the shipped page, imported into a script with no DOM and no human, playing thousands of games back to back. A benchmark written against a re-implementation of the algorithm proves the algorithm is sound in theory; it says nothing about the code a browser actually executes. Pulling the real functions out of the production page means the numbers describe the shipped build, not a clean-room stand-in that happens to share a name with it.

It also has to be re-runnable. A number from one afternoon of manual play-testing is an anecdote; a script that plays 1,000 games and produces the same counts every time is a measurement. Mean move time came out at about 0.3 ms across 500 sampled positions.

Depth is the proof

The shipped engine searches to depth 9 — the full game tree for a 3×3 board — which is what guarantees the zero-loss result. To find out whether that depth is necessary, the harness re-ran the same 200-game vs-random test with the search capped at each depth from 1 to 9:

The honest finding is in the depth-2 row: at a search depth of 2, the AI lost 2 of 200 games. An 87% win rate looks fine on its own, until you notice the two losses hiding next to it. Depth 9 is the only depth with a 0-loss guarantee behind it; every shallower depth is a different, weaker program that happens to share the same UI.

That is the entire argument for benchmarking instead of reasoning from the algorithm's name. "It's minimax, so it's unbeatable" is true only at one specific depth setting, and the only way to know which is to run all of them and look for the losses.

The 2048 case

Tic-tac-toe has a small enough state space that "unbeatable" is checkable in an absolute sense. Most games don't — 2048 has no realistic path to "solved," so the only honest claim is a measured reach-rate: 250 headless self-play games with the shipped expectimax-plus-corner-snake solver.

A strength profile, not a single number — and one that would be indistinguishable from a coin flip if I'd run it 10 times instead of 250.

Reproduce it yourself

The harness is public and seeded, so runs are deterministic. Each file copies the shipped game code verbatim and drives it headlessly:

The benchmark harness (public gist)

node tictactoe-benchmark.mjs   # 549,945 -> 36,528 nodes, 0 losses, depth-2 loses 2
node 2048-benchmark.mjs        # reach-rate profile

The deterministic numbers (node counts, 0 losses at full depth, "only depth 2 loses") reproduce to the exact digit. The stochastic ones (win/draw split, 2048 reach %) reproduce as the same profile with seed-dependent variance. I also included the one number that didn't cleanly reproduce — a Color Lines pathfinding stat that turned out to be board-sampling-dependent — and documented why, rather than curve-fitting to hit it.

The rule this enforces

Benchmark before you publish a number. Any performance or strength claim has to come from a measurement that can be re-run, not a description of what the algorithm should do in theory. The depth-2 result is exactly the kind of thing that rule is for — a plausible-sounding claim ("it's minimax, it can't lose") that turns out to be depth-dependent, and would have shipped wrong without a script that actually played the games.