The Nine Men's Morris Capture Rule Almost Everyone Gets Wrong

A piece standing in a mill cannot be taken. Unless every enemy piece is standing in a mill, in which case any of them can.

That second sentence is the one people skip, and skipping it does not produce a subtle bug. On a position where White owes a removal and all six Black pieces sit inside mills, the take-list goes from 6 to 0. Zero legal moves means the mover is blocked, and a blocked player loses. So the engine hands the win to the side that was being ground down.

👉 Playable, with a selectable-depth alpha-beta opponent: https://dev48.in/game/day83-nine-mens-morris.html

The board is not a grid, and storing it like one costs you the rest of the build

Twenty-four points on three nested squares. The corner of a square has 2 neighbours, the midpoint of the outer or inner square has 3, and the midpoint of the middle square has 4. Across the board that splits as 12 / 8 / 4 points, degrees summing to 64, which is twice the 32 edges.

A 7×7 array can hold that picture, but 25 of its 49 cells are holes and every rule then needs a special case for them.

So the board is a graph, and the only thing typed by hand is the sixteen lines of three:

const MILLS = [
  [0,1,2], [2,3,4], [4,5,6], [6,7,0],              // outer ring
  [8,9,10], [10,11,12], [12,13,14], [14,15,8],     // middle ring
  [16,17,18], [18,19,20], [20,21,22], [22,23,16],  // inner ring
  [1,9,17], [3,11,19], [5,13,21], [7,15,23]        // the four spokes
];

Adjacency is computed from them: each line contributes exactly two pairs, 16 × 2 = 32, and after de-duplication there are still 32. None of the pairs collide, which is itself a check on the list.

Every point lies on exactly 2 lines (24 × 2 = 48 = 16 × 3), so a mill test after a move reads two lines instead of sixteen.

A mill does not end your turn

This is where a first implementation breaks. Closing a mill obliges you to remove an enemy piece, and only then does the opponent move. Model a turn as "one move, then swap sides" and the removal has nowhere to live, so it usually ends up as a prompt outside the engine — at which point the search cannot see captures at all.

The fix is a flag, and a move generator that answers it first:

if (millAt(n.b, mv.to, p)) n.pending = true;   // same player moves again
else n.turn = opp(p);

// ...and the generator:
if (s.pending) return removable(s, opp(p)).map(at => ({ t: 'r', at }));

The capture exception is then three lines, a filter with a fallback:

function removable(s, victim) {
  const all = [], free = [];
  for (let i = 0; i < 24; i++) {
    if (s.b[i] !== victim) continue;
    all.push(i);
    if (!millAt(s.b, i, victim)) free.push(i);
  }
  return free.length ? free : all;   // all milled -> protection lapses
}

Measured on two positions that differ by one Black piece: with a loose piece on the board the list is 2 long and the milled pieces are protected. With every Black piece milled it is 6.

Flying is where the branching factor explodes

Phase is never stored. It is a question asked at the top of the generator: pieces in hand means placing, exactly three pieces means flying, otherwise slide.

position	phase	White's legal moves
opening	placing	24
mid-game, six pieces	moving	16
White down to three	flying	54

Three flying pieces times 18 empty points is 54. The search slows down exactly when the position gets sharp.

Without draw rules a deterministic engine never stops

Two sides that cannot get through each other shuffle forever. Driving a four-ply shuffle (White 0↔1, Black 16↔17) through the engine with history tracked, threefold repetition fires at ply 9. The same shuffle with history off runs to the fifty-move limit and is drawn at exactly ply 100.

Both are needed. Repetition catches the shuffle; the fifty-move counter catches a side that keeps finding new positions and no progress. The counter resets on anything irreversible, which here means a capture or a placement.

The search has to ask whose turn it is

Plain negamax negates each level, which bakes in the assumption that sides alternate. In this game a mill gives the same player another ply, so that assumption scores captures for the wrong side. Asking s.turn === me at every node costs nothing and makes pending removals just another node that happens to maximise again.

Alpha-beta on top of that, same position, measured both ways:

depth	plain minimax	with alpha-beta	saving
1	22	22	1.0x
2	244	37	6.6x
3	4,201	682	6.2x
4	39,264	1,236	31.8x

Same score and the same chosen move at every depth. Pruning changed the cost, never the answer.

On a position where White can slide 3→2, close 0-1-2 and take Black from three pieces to two, the depth-3 search finds that single move in 25 nodes and scores it 999,998 — a win has to outrank every static evaluation, so it is scored as WIN - ply.

Twenty-four opening moves are really four

The board's symmetries are four rotations, four reflections, and the swap of the inner and outer rings, which is a symmetry of the graph even though it is not a symmetry of the drawing. The page finds them by searching for every relabelling of the points that preserves adjacency, rather than assuming a list, and gets 16. They split the points into 4 orbits:

orbit	points
corners of the outer and inner rings	8
midpoints of the outer and inner rings	8
corners of the middle ring	4
midpoints of the middle ring	4

So the opening tree is four times smaller than it looks.

What was actually checked

The page runs 38 assertions in the browser against the same engine the game is played with, and the badge reads 38 of 38.

A separate verifier builds the board a second time from geometry instead of from the list of lines: two points touch when they share a row or column with nothing between them and the segment does not run through the empty centre. That derivation independently produces 32 edges and 16 lines, and both match the page exactly.

It then re-implements the rules over a board of characters and drives both engines side by side through 12 seeded games, 1,743 plies, comparing the full legal-move set and the resulting position at every single ply. 65 asserts, 0 failures. Endings: 8 by reduction to two pieces, 3 by the fifty-move rule, 1 by repetition.

The engine playing itself at depth 1 finishes in 45 plies.