Cram impartial Domineering

Take turns placing dominoes on the grid, horizontally or vertically — both players may use either direction. Whoever cannot place a domino on their turn loses. As the dominoes wall off parts of the board, the game splits into independent regions; each one is labelled with its nimber, and the whole position is worth their XOR. With hints on, every move you could make carries a dot: green brings the XOR to *0 and keeps a won game won, red does not.

rows cols first move hints

this position

nimber of the empty m × n board

How the perfect player works

Cram is impartial: both players have the same moves, so by the Sprague–Grundy theorem every position behaves exactly like a single Nim heap of some size, its nimber. A region's nimber is the smallest number that is not the value of any of its options (the mex), and a position made of several regions that no domino can bridge is worth the XOR of their nimbers. The player to move wins exactly when that XOR is not *0, and a winning move is one that brings it to *0.

The solver keys its table by the region's shape, cut down to its bounding box and reduced over the eight symmetries of the square, so an L of five cells in one corner is the same entry as a mirrored L anywhere on any board. Cells that have lost all their free neighbours are dropped on the spot: nobody can ever cover them. The table lives in a Web Worker for the whole visit, so once the empty board has been solved, the positions later in the game are mostly lookups.

The chart

Every value was recomputed under Node, three ways: a full mex over every option of every shape; a win/loss search that does not use nimbers at all and remembers whole sums of regions; and the method of Lemoine and Viennot's Nimbers are inevitable (2010), which never runs a full mex but asks "does the player to move lose this region plus a Nim heap of n?" and stops at the first winning reply. The values are checked against the tables in that paper.