mnk-bench

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.

  1. Tic-tac-toe (3,3,3)

    All 9 run

    Minimax plays it perfectly.

  2. 4×4 (4,4,4)

    7 run, 2 cut back

    Q-learning and TD only fit with reduced settings.

  3. 5×5 (5,5,4)

    5 run, 4 refuse

    Minimax and all three learning tables refuse.

  4. Connect Four (6,7,4)+gravity

    5 run, 4 refuse

    The AlphaZero-style network is level with alpha-beta.

  5. Gomoku (15,15,5)

    4 run, 5 refuse

    Self-play training would take about 42 h, so it refuses. Search and rules still play.

The nine agents that run without an API key, at the standard budget of 1 s per move, 1 GB of memory and 10 minutes of training. Filled stones run (amber ones with reduced settings); hollow ones refuse.

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.

Loading…
okdegraded (reduced settings)refused aborted (stopped by its guards)unavailable (no API key) corner dot: estimate only, not probed
methodbreaks atwhy
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 practiceOne 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-stylebeyond (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 weakensRandom 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×19Cost 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.

Try Connect Four against alpha-beta →

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.

  1. 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
  2. 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
  3. 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
  4. 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
  5. Package and site

    A Python package with an mnk-bench command line, and this static site, where every agent runs in your browser in Web Workers.

    Read the source Watch MENACE learn

More of my research and projects are on my portfolio.