Where does each game-playing AI fall apart as the board gets bigger?
Exact search gives up at (5,5,4), matchbox-style tables at (4,4,4), self-play training just past Connect Four, and depth-limited alpha-beta is still playing at 19×19.
-
Tic-tac-toe (3,3,3)
All 9 run
Minimax plays it perfectly.
-
4×4 (4,4,4)
7 run, 2 cut back
Q-learning and TD only fit with reduced settings.
-
5×5 (5,5,4)
5 run, 4 refuse
Minimax and all three learning tables refuse.
-
Connect Four (6,7,4)+gravity
5 run, 4 refuse
The AlphaZero-style network is level with alpha-beta.
-
Gomoku (15,15,5)
4 run, 5 refuse
Self-play training would take about 42 h, so it refuses. Search and rules still play.
In 1961 Donald Michie taught about 300 matchboxes to play tic-tac-toe. Gomoku is the same game on a 15×15 board, where a matchbox per position would need more boxes than there are atoms in the universe. mnk-bench measures exactly where that approach, and every other kind of game AI, breaks down, and why.
What is an m,n,k game?
Two players take turns placing stones on an m×n board, and the first to get k in a row wins. Tic-tac-toe is (3,3,3) and gomoku is (15,15,5). With gravity, stones drop to the bottom of their column, so Connect Four is (6,7,4)+gravity. One engine covers all of them, so the same agents can be measured on every board.
Where each method breaks
Every agent estimates its own time, memory and training cost before playing, then runs, degrades to cheaper settings, or refuses. Guarded probes on real hardware confirmed the estimates; no probe had to be aborted. Click a cell for its numbers.
| method | breaks at | why |
|---|---|---|
| Minimax (exact) | (5,5,4) | About 4×10⁷ nodes to solve the opening (an estimated 14 min per move and 11 GB). A forced run is killed by its guards, which confirms the refusal. |
| MENACE, Q-learning, TD | (4,4,4) in practice | One table entry per position. After 3,000 games they have seen only 28 to 50% of the positions they meet on (6,6,4), and from (5,5,4) on they score 0 against the rule-based player. |
| AlphaZero-style | beyond (6,7,4) | Play stays cheap (~60 ms per move). The limit is self-play training: an estimated 23 min for (7,7,5) and 42 h for gomoku on one core. |
| MCTS (random playouts) | never refuses, but weakens | Random playouts carry little signal on open boards: it scores 0.19 against rule-based on (6,6,4), even with 3,200 playouts per move. |
| Alpha-beta (depth-limited) | nowhere up to 19×19 | Cost grows with the candidate set, not the state space: 0.15 s per move at depth 4 on 19×19. |
Bigger boards spread the ratings out
On tic-tac-toe every competent agent draws the others, so the ratings bunch up between 1,418 (MENACE) and 1,525. On (6,6,4) depth-4 alpha-beta went 240–0 and the trained tables lost to everything except random.
On Connect Four a 39k-parameter network trained only by self-play, for 10 minutes on one CPU core, is level with alpha-beta and beats the rule-based player 40–0. The same network trained on (3,3,3) and (4,4,4) never loses to perfect play.
Built end to end
One person built every layer, from the rules of the game up to the page you're reading. Each step links to its evidence.
-
Engine
One m,n,k engine for any board up to 19×19, with gravity and exact-k rules. Written in Python, ported to JavaScript for this site.
Try any board -
10 agents
From random play and MENACE to minimax, MCTS, an AlphaZero-style network and LLM players. They share one interface, and each estimates its own time, memory and cost.
Run them in the Arena -
13 experiments
Every run is seeded and saved as JSON, CSV and plots, so any figure can be redrawn without replaying a game.
Open the results report Read the research write-up -
132 tests
119 Python tests and 13 browser-engine tests. CI runs them on Python 3.10 to 3.13 on every push, with a short AlphaZero training run and a quick pass of every experiment.
See the CI runs -
Package and site
A Python package with an
Read the source Watch MENACE learnmnk-benchcommand line, and this static site, where every agent runs in your browser in Web Workers.
More of my research and projects are on my portfolio.