← mnk-bench site · play the agents

mnk-bench results

Where does each game-playing AI fall apart as the board gets bigger? mnk-bench 0.1.0, Python 3.13.16, generated 2026-10-14T08:24:09

MENACE learns tic-tac-toe

MENACE learns tic-tac-toe from scratch by bead reinforcement. Who it practises against matters: against random play it never learns to survive perfect play, while games against a perfect player teach it to draw. Games to learn is the first checkpoint from which it loses at most 5% of games against perfect play.

trained vsgamesgames to learnmatchboxeswin vs randomnon-loss vs perfectoptimal-move rate
random5000-5510.8950.5750.898
minimax500035001160.5601.000.830
random+minimax500020004100.9101.000.944
self5000-5090.8400.6800.843
MENACE learning curves
MENACE matchboxes in use

Board symmetries

Storing positions up to rotation and reflection is what got Michie down to about 300 matchboxes. The counts below are exact enumerations of every position MENACE could face.

configplayersymmetryskip_forcedmatchboxes
(3,3,3)Xyesyes304
(3,3,3)Xyesno338
(3,3,3)Xnoyes2201
(3,3,3)Xnono2423
(3,3,3)Oyesyes280
(3,3,3)Oyesno289
(3,3,3)Onoyes2097
(3,3,3)Onono2097
(3,4,3)Xyesyes10657
(3,4,3)Xyesno10661
(3,4,3)Xnoyes42141
(3,4,3)Xnono42141
(3,4,3)Oyesyes9322
(3,4,3)Oyesno9427
(3,4,3)Onoyes37012
(3,4,3)Onono37422
learning with and without symmetry
matchboxes with and without symmetry

MENACE vs Q-learning vs TD

MENACE, Q-learning and TD(0) all use one table entry per position. Averaged over seeds, after the same number of training games:

agenttrained vsgames to learn (per seed)non-loss vs perfectwin vs randomoptimal-move ratetable entriestrain time (s)
menacerandom+minimax1500, 2500, 30000.9980.8530.930449.671.30
menaceself6000, 2500, -0.9320.8680.963553.330.317
qlearningrandom+minimax1500, 1000, 10001.000.9280.987500.001.29
qlearningself6000, 5500, 50000.9930.9270.984541.330.397
tdrandom+minimax6000, 4500, 50001.000.9200.997529.001.91
tdself5000, 3000, 60001.000.9251.00490.331.26
tabular learners, mixed opponents
tabular learners, self-play
table growth

Head to head on tic-tac-toe

Every agent against every other on tic-tac-toe, alternating who moves first.

agentgameswindrawlossscore
qlearning80014865200.593
alphabeta:depth=480014565500.591
mcts:iterations=100080014365160.586
alphazero80011768300.573
minimax80011168900.569
rule8009370700.558
td80096650540.526
menace800785661560.451
random8008697230.053
head-to-head matrix

Bigger boards: where tables choke

Tabular learners get the same 3000 training games on every board. As the board grows, the share of positions they have seen before (coverage) collapses, and so does their play; depth-limited alpha-beta has no table and keeps getting relatively stronger.

boardagenttable entriescoveragescore vs randomscore vs rule
(3,3,3)menace3830.9290.9080.500
(3,3,3)qlearning4841.000.9250.500
(3,3,3)td4011.000.9500.500
(3,3,3)alphabeta:depth=40-0.9670.500
(4,4,3)menace39080.7570.5330.500
(4,4,3)qlearning36050.7270.6420.500
(4,4,3)td11850.9880.9500.500
(4,4,3)alphabeta:depth=40-1.000.500
(4,4,4)menace88400.5810.4920.267
(4,4,4)qlearning94320.5170.5000.042
(4,4,4)td92060.7310.7420.075
(4,4,4)alphabeta:depth=40-0.9250.500
(5,5,4)menace123500.4410.5580
(5,5,4)qlearning128840.4010.4830
(5,5,4)td107910.5970.8170
(5,5,4)alphabeta:depth=40-1.000.658
(6,6,4)menace164610.2790.5670
(6,6,4)qlearning166020.3230.6000
(6,6,4)td129530.5000.8670
(6,6,4)alphabeta:depth=40-1.001.00
score vs rule
table size
coverage
tournament

Tournament on (6,6,4)

agentgameswindrawlossscore
alphabeta:depth=4240240001.00
alphabeta:depth=22401810590.754
rule2401790610.746
td24010701330.446
random2404711920.198
qlearning2404601940.192
menace2403912000.165

Monte Carlo Tree Search

MCTS needs no evaluation function, only playouts. More playouts per move help, but on boards where random games are uninformative (6x6, k=4) it stays weak.

playoutsboardmetricvalues/move
25(3,3,3)optimal_rate0.824-
25(4,4,4)score_vs_rule0.4870.00024
25(6,6,4)score_vs_rule00.00056
25(6,7,4)+gravityscore_vs_rule0.0750.00044
50(3,3,3)optimal_rate0.871-
50(4,4,4)score_vs_rule0.5000.00055
50(6,6,4)score_vs_rule00.001
50(6,7,4)+gravityscore_vs_rule0.1880.00066
100(3,3,3)optimal_rate0.879-
100(4,4,4)score_vs_rule0.5000.00092
100(6,6,4)score_vs_rule00.003
100(6,7,4)+gravityscore_vs_rule0.1250.002
200(3,3,3)optimal_rate0.903-
200(4,4,4)score_vs_rule0.5000.002
200(6,6,4)score_vs_rule00.006
200(6,7,4)+gravityscore_vs_rule0.6120.003
400(3,3,3)optimal_rate0.969-
400(4,4,4)score_vs_rule0.5000.005
400(6,6,4)score_vs_rule00.012
400(6,7,4)+gravityscore_vs_rule0.6500.006
800(3,3,3)optimal_rate0.985-
800(4,4,4)score_vs_rule0.5000.012
800(6,6,4)score_vs_rule0.1250.022
800(6,7,4)+gravityscore_vs_rule0.8750.014
1600(3,3,3)optimal_rate1.00-
1600(4,4,4)score_vs_rule0.5000.022
1600(6,6,4)score_vs_rule0.1750.046
1600(6,7,4)+gravityscore_vs_rule0.7000.031
3200(3,3,3)optimal_rate1.00-
3200(4,4,4)score_vs_rule0.5000.046
3200(6,6,4)score_vs_rule0.1880.087
3200(6,7,4)+gravityscore_vs_rule0.8500.064
MCTS strength vs playouts

Elo ratings

Ratings fitted to every game of a round robin (Bradley-Terry, random play anchored at 1000, 95% bootstrap intervals).

(3,3,3)

agentelo95% CI
alphabeta:depth=41,5251472 to 1592
mcts:iterations=10001,5231467 to 1586
qlearning1,5221460 to 1584
alphabeta:depth=21,5211466 to 1588
alphazero1,5161459 to 1578
minimax1,5151456 to 1582
rule1,5041452 to 1568
td1,4891433 to 1550
mcts:iterations=2001,4831427 to 1549
menace1,4181358 to 1482
random1,0001000 to 1000
Elo on (3,3,3)
matrix on (3,3,3)

(6,6,4)

agentelo95% CI
alphabeta:depth=43,1662929 to 3532
alphabeta:depth=22,5992462 to 2817
rule2,5032390 to 2726
mcts:iterations=10002,0731983 to 2219
mcts:iterations=2001,7961728 to 1841
random1,0001000 to 1000
Elo on (6,6,4)
matrix on (6,6,4)

(6,7,4)+gravity

agentelo95% CI
alphabeta:depth=22,3202253 to 2385
alphazero2,3162254 to 2398
mcts:iterations=10002,1942137 to 2260
alphabeta:depth=42,0762021 to 2126
rule1,9621911 to 2015
mcts:iterations=2001,9421894 to 1989
random1,0001000 to 1000
Elo on (6,7,4)+gravity
matrix on (6,7,4)+gravity

Feasibility map

Each agent estimates its time per move, memory and training time for a board and compares them with the budget: ok, degraded (runs in a cheaper configuration, e.g. shallower search, fewer playouts, or under-trained), or refused. Cells marked * were confirmed by running the agent in a guarded subprocess that kills it if it overruns (aborted).

standard budget: 1.0s/move, 1024 MB, 600s training

feasibility map standard
agentlargest ok boardlargest usable boardfirst refused
random(19,19,5)(19,19,5)-
rule(19,19,5)(19,19,5)-
minimax(4,4,4)(4,4,4)(5,5,4)
menace(4,4,4)(4,4,4)(5,5,4)
qlearning(3,3,3)(4,4,4)(5,5,4)
td(3,3,3)(4,4,4)(5,5,4)
alphabeta:depth=4(19,19,5)(19,19,5)-
mcts:iterations=1000(19,19,5)(19,19,5)-
alphazero(6,7,4)+gravity(6,7,4)+gravity(7,7,5)
llm---

tight budget: 0.05s/move, 128 MB, 30s training

feasibility map tight
agentlargest ok boardlargest usable boardfirst refused
random(19,19,5)(19,19,5)-
rule(19,19,5)(19,19,5)-
minimax(3,3,3)(3,3,3)(4,4,4)
menace(3,3,3)(3,3,3)(4,4,4)
qlearning(3,3,3)(3,3,3)(4,4,4)
td(3,3,3)(3,3,3)(4,4,4)
alphabeta:depth=4-(19,19,5)-
mcts:iterations=1000(7,7,5)(19,19,5)-
alphazero--(3,3,3)
llm---

Performance

Throughput of the hot paths and time per move on growing boards. The fast playout (bare cell array, inlined win check, lazy shuffle) is what MCTS uses.

boardreference playouts/sfast playouts/sspeedup
(3,3,3)61,885132,3392.14
(6,6,4)15,16549,2213.25
(6,7,4)+gravity22,27248,1492.16
(9,9,5)3,73621,8055.84
(15,15,5)853.237,9089.27
(19,19,5)361.455,41114.97
time per move
playouts

Gomoku (15,15,5)

The full gomoku board (15,15,5): only heuristic search and sampling remain feasible.

agentelos/move
alphabeta:depth=42,3510.051
alphabeta:depth=62,2910.548
rule2,1230.001
alphabeta:depth=22,1040.004
mcts:iterations=10001,5290.111
random1000.001.7e-05
agentgameswindrawlossscore
alphabeta:depth=45042080.840
alphabeta:depth=650390110.780
rule50300200.600
alphabeta:depth=250290210.580
mcts:iterations=100050100400.200
random5000500
gomoku Elo
gomoku matrix

AlphaZero-style agent

A small residual policy/value network guides MCTS (PUCT) and is trained only from self-play games. The table shows each training run's final evaluation.

boarditerationsself-play gamesparamstrain time (s)score vs randomscore vs rulenon-loss vs perfectoptimal-move rate
(3,3,3)2612503945877.000.9380.5001.001.00
(4,4,4)26100039458776.540.8880.5001.000.992
(6,7,4)+gravity26100039458589.481.001.00--
alphazero_training

LLM players

No ANTHROPIC_API_KEY was available when these results were generated, so this table comes from the offline mock client (random legal moves with simulated token counts). It checks the pipeline, not a model. Set ANTHROPIC_API_KEY and run `mnk-bench experiment llm` for real numbers.

agentconfigopponentgameswindrawlossscoresec_per_moveinput_tokens_per_moveoutput_tokens_per_movecost_per_move_usdretry_ratefallback_rate
llm:provider=mock(3,3,3)random104150.4503.6e-05219.7940.000.0008400
llm:provider=mock(3,3,3)rule10001002.8e-05220.1940.000.0008400
llm:provider=mock(6,7,4)+gravityrule400403.2e-05275.8840.000.0009500
llm:provider=mock(9,9,5)rule200206.7e-05315.4440.000.00100

Targeted labelling with submodular information (PRISM)

PRISM-style targeted learning for games (full write-up: docs/research/targeted-selection.md). A briefly self-trained network on (5,5,4)+gravity misses tactical motifs (immediate wins, forced blocks, poisoned moves). Given a few example positions of a motif, each method picks k positions from an unlabelled pool for the exact solver to label; the network is fine-tuned on them and evaluated on held-out motif positions. Numbers are averaged over the three motifs and 5 seeds.

methodhit rate k=100target acc k=100hit rate k=400target acc k=400hit rate k=50target acc k=50hit ratetarget acc
base-------0.672
query-only-------0.691
random0.1330.6730.1320.7070.1450.680--
entropy0.0880.6830.0910.6790.0990.675--
margin0.1020.6620.1050.6830.1070.681--
FL0.0780.6580.0970.6770.0810.667--
LogDet0.1380.6820.1330.7130.1250.676--
GCMI0.2280.6820.1960.7120.2410.696--
FLMI0.2190.6840.1490.7030.1930.675--
FLVMI0.3100.6820.2150.7080.3650.679--
COM0.2250.6860.1960.7090.2400.690--
LogDetMI0.2980.6920.2260.7500.3360.684--
FLCMI0.2260.6830.1510.7140.2350.676--
oracle1.000.8260.9210.8901.000.780--

Paired comparison with random selection

methodmetricbudgetswins/lossesmean diff95% CIp (sign)p (Bonferroni)
entropyacc_targetall36/35-0.0070.0121.001.00
marginacc_targetall28/42-0.0110.0120.1201.00
FLacc_targetall31/41-0.0140.0150.2891.00
LogDetacc_targetall32/41-0.0010.0130.3491.00
GCMIacc_targetall39/300.0100.0120.3361.00
FLMIacc_targetall38/310.0050.0120.4701.00
FLVMIacc_targetall34/340.0050.0111.001.00
COMacc_targetall34/320.0070.0100.9021.00
LogDetMIacc_targetall46/240.0180.0110.0120.127
FLCMIacc_targetall35/360.0010.0111.001.00
oracleacc_targetall72/10.1330.0161.6e-201.7e-19
entropyacc_criticalall54/190.0130.0055.1e-050.00056
marginacc_criticalall35/38-0.0030.0060.8151.00
FLacc_criticalall36/39-0.0020.0040.8181.00
LogDetacc_criticalall36/36-0.0030.0061.001.00
GCMIacc_criticalall25/50-0.0100.0060.0050.058
FLMIacc_criticalall41/320.0030.0050.3491.00
FLVMIacc_criticalall26/49-0.0100.0060.0110.116
COMacc_criticalall28/45-0.0090.0060.0600.664
LogDetMIacc_criticalall22/52-0.0130.0060.000640.007
FLCMIacc_criticalall34/41-0.0010.0050.4891.00
oracleacc_criticalall19/54-0.0200.0065.1e-050.00056