Cram

Domineering is played on a grid of squares with dominoes. Left places hers vertically, Right places his horizontally, and a player who cannot place a domino loses. Two players looking at the same board and seeing different games is what partizan means, and it is why the position needs a value with two sides to it.

Change one word. Either player may place a domino either way up. Same board, same dominoes, same losing condition — and now both players have exactly the same moves from every position. That game is called Cram, and it is impartial.

One word, and the apparatus it removes #

Sharing the orientations costs the game its whole apparatus. Every impartial game is a Nim heap: with the same options for both players, a position is equivalent in every sum it can appear in to a single heap of counters, and its whole content is one non-negative integer.

So Cram needs no Left values and Right values, no canonical form to simplify, no temperature and no thermograph. A Cram position is a nimber. Partizan Domineering, on the same squares, needs all of it.

Cram on those same nine squares is worth 0, and 0 means the player to move loses — a P-position. One word of the rule, and the opposite outcome on an identical board.

The gap widens as fast as the boards do. Four Domineering boards nobody would call large — $1\times2$, $2\times3$, $3\times3$ and $3\times4$ — are worth $-1$, the switch $\{2 \mid -\tfrac12\}$, the switch $\{1 \mid -1\}$ and $-\tfrac32$: a negative integer, two switches and a fraction, four different kinds of object from four boards of at most twelve squares. Cram answers the same four with ∗1, ∗1, 0 and ∗1. One family of answers is a zoo and the other is a single non-negative integer per board, and the difference is one word of the rule.

Set the two games side by side and the difference in what a value has to carry is plain.

The row that matters most does not fit in a cell. On the empty 4 × 4 board Cram’s answer is the single character 0; Domineering’s canonical form on the same sixteen squares is

{0, { {2 | 0}, {2 | {2 | 0}} | {2 | 0}, { {2 | 0} | 0}} | 0, { {0 | {0 | −2}}, {0 | −2} | {0 | −2}, { {0 | −2} | −2}}}

which is 114 characters of nested braces, every one of them load-bearing: the form is already reduced, with nothing left to remove. The position it describes is the empty 4 × 4 grid the hero figure draws.

A strategy that names no move #

Cram’s answer on 4 × 4 is 0, and there is a way to know that without computing anything at all.

Suppose the board is even by even. The second player adopts one rule: whatever the opponent plays, reply with the same domino rotated a half-turn about the centre. If the reply is always legal, the second player always has a move, and a player who always has a move never loses under normal play.

The reply is always legal for a reason specific to even sides. The centre of an even × even board falls at a corner where four squares meet rather than inside one, so the half-turn fixes no square at all. A domino can therefore never be its own image, and the two squares the reply wants are exactly the two the opponent has just failed to touch.

That is a strategy that names no move: no opening move, because there is none to name, and the whole plan stated as a function of what the opponent does. What it gives up in exchange is the value. It establishes that 4 × 4 is a second-player win and says nothing about which nimber the board is.

The pairing was audited rather than asserted, on every even × even board the search reaches, by walking each position the strategy arrives at and trying every reply the opponent has:

One odd side, and the domino that is its own reflection #

Try the same rule with one odd side and it fails — but repairably, and the repair shows how much of the argument the parity was carrying.

On a 3 × 4 board the centre of the half-turn falls on the middle line, inside a square. The horizontal domino lying across that centre maps to itself, so if the opponent plays it, the reply the strategy demands is the same two squares, which are no longer empty.

Exactly one domino is self-reflecting, and one is a number a strategy can afford. Let the first player take it as an opening move. What is left has no self-reflecting domino at all, and the first player is now in the second player’s seat for everything that follows.

The repair was checked on every board with one odd side the search reaches, and holds on all of them:

Every one is a first-player win, and the last column is the thing to notice: ∗1, ∗2 and ∗4, not one value repeated. The symmetry argument proves the outcome and touches the value not at all. Knowing that 3 × 6 is a first-player win is not knowing that it is worth ∗4, and only the mex search produces the second.

Two odd sides, where nothing can be removed #

Now make both sides odd, and the failure changes character.

The centre of a 3 × 3 board is the middle square, and the half-turn fixes it. There is no self-reflecting domino to take first, because no domino covers that square symmetrically: a domino covers two squares and the fixed point is one, so the covering is always lopsided and the image always overlaps the original.

The two failures look alike on the page and are not alike. On an odd × even board the obstruction is one object of the same kind as a move, so a move disposes of it. On an odd × odd board the obstruction is a square, and nothing removes a square without also covering one of its neighbours.

The audit records the difference plainly. On 3 × 4, 3 × 6 and 5 × 4 the first failure is a horizontal domino that is its own reflection. On 3 × 3 and 5 × 5 it is a domino whose reflected image wants a square the move has just filled — 6 positions in on the small board, 623 on the larger.

The larger board is worth drawing because the small one is small enough to be dismissed. Six positions is a walk a reader could do by hand, and a failure that early invites the thought that the strategy was never seriously tried. The 5 × 5 board makes the same failure after six hundred and twenty-three positions, which is a long way into a game.

That is the practical reason a symmetry argument has to be audited rather than admired. The pairing on this board is legal for hundreds of moves, in every game anybody would play out by hand, and it is still not a strategy — a strategy has to work in every position it can reach, and the one position it fails in is the one that decides the game. A walk that stops at the first failure is the only honest way to report it, and the number it stops at says nothing about how close the argument came.

A strategy failing is not the position failing #

This is where an argument by symmetry gets over-read, and the two odd × odd boards this site can compute say so as sharply as it can be said.

3 × 3 is a second-player win. 5 × 5 is a second-player win. Both are worth 0, and both are P-positions. The pairing strategy proves neither, and its failure to prove them is not evidence against them.

The mex takes the same twelve moves the pairing argument was reasoning about and reaches the answer by a route with no geometry in it. On 5 × 5 it runs over 40 placements whose values are 1 and 3, giving mex 0 again. So the square boards up to 5 × 5 are all second-player wins — 1 × 1, 2 × 2, 3 × 3, 4 × 4, 5 × 5 — and pairing accounts for exactly two of the five.

The three it accounts for none of are the three it fails on, and they agree with the two it settles. That is worth stating carefully, because it is the coincidence that makes the over-reading tempting: every square board this site can compute is a second-player win, whether or not the half-turn argument reaches it, so a reader who took the strategy as the explanation would be right about the outcome five times out of five and right about the reason twice. The distinction is invisible in the answers and total in the arguments.

The distinction that survives is this. A strategy is a proof technique, and one that fails has established nothing in either direction; the outcome is a fact about the position, settled by exhaustive search or not settled at all. Reading “the symmetry argument breaks on odd × odd boards” as “odd × odd boards are first-player wins” would have been wrong about 3 × 3, 5 × 5, 1 × 1 and 1 × 5.

What the solver computed, and how #

Every Grundy value on this page came out of one recursion. A position is a set of filled squares; its options are the positions reached by adding a domino wherever the empty squares allow; its value is the mex, the smallest non-negative integer that is not the value of any option. That is the whole of it, and it is the same rule that gives every impartial game its heap.

The board is held as a bitmask, one bit per cell, and positions are memoised on the mask, so a board reached by two different move orders is evaluated once. That matters more than it sounds: the number of orders is factorial in the dominoes placed, and the number of distinct positions is not.

Four readings are worth stating, all of them off the computed numbers rather than off a pattern that looked plausible.

Every even × even board computed is worth 0 — 2 × 2, 2 × 4, 2 × 6, 2 × 8, 2 × 10, 2 × 12, 4 × 2, 4 × 4 and 4 × 6. The pairing argument predicts all nine and nothing contradicts it.

2 × n is worth 0 exactly when n is even, checked for every n from 1 to 13; the odd ones are all ∗1, including 2 × 11 and 2 × 13 at 22 and 26 cells.

3 × 6 is worth ∗4, the largest value in the table, at the end of a row that had run ∗1, ∗1, 0, ∗1, ∗1. Nothing in the neighbouring entries suggests it.

And the 1 × n row is where any pattern in n breaks. 1 × 1 = 0, 1 × 3 = ∗1, 1 × 5 = 0, 1 × 7 = ∗1, 1 × 9 = 0 looks like a clean alternation; 1 × 11 = ∗3 and 1 × 13 = ∗2 destroy it, and 1 × 15 = 0 restores it as though nothing had happened. The n up to 40 for which the strip is worth 0 are 0, 1, 5, 9, 15, 21, 25, 29, 35 and 39.

The strip turns out to be Dawson’s Kayles #

That last row is where the surprise lives, because a second machine produces exactly the same numbers and never sees a board.

A 1 × n strip of Cram is a row of cells, and a domino covers two adjacent cells. Placing one removes two counters and leaves the remainder whole, split in two, or empty. That is an octal game written out: the digit 7 in the second place for those three outcomes, and a zero in the first, meaning an isolated single cell can never be played on. The code is ·07.

That code is already on this site. ·07 is Dawson’s Kayles, one bit away from the chess problem of 1934 that turned out to be the octal game ·137. So a row of Cram, a heap game with no board in it, and a puzzle about pawns capturing on three ranks are descriptions of two closely neighbouring objects.

The identification was checked rather than assumed: the board search on 1 × n for n = 0 to 30, and the octal machinery on ·07 over the same range, agree on all 31 values with no disagreement anywhere.

And that buys something the board search cannot. The octal computation is linear in the heap size, so it runs to 2,000 where the board search stops at 31 cells, and it finds the sequence settling into period 34 from heap 53. Four values and a sequence is settled for ever explains why a found period, once it has run long enough, is a proof rather than an observation — and here it is a proof about Cram strips of every length, reached by a computation that never represented a board.

Where the search stops #

The representation stops at 31 cells. The board is a bitmask over the cells, so 6 × 6 is 36 cells and is not reachable at all — not slow, unrepresentable. The evaluator throws rather than silently overflowing the mask, which is the difference between a limit and a bug.

The largest boards actually computed are 2 × 13 at 26 cells in 3.3 seconds, 5 × 5 at 25 cells in 5.2, and 4 × 6 and 2 × 12 at 24 cells. The table figure is capped at twenty cells so the build stays fast, and the cells past that are drawn blank rather than hidden.

No general formula is claimed. The table is a catalogue. Every even × even entry has a proof behind it, every other entry has a search behind it, and the searches do not add up to a pattern.

Nothing is claimed about odd × odd Cram beyond the boards listed. The pairing argument is silent there by construction, three boards of that shape have been computed, and three is not a family.

And the period of ·07 is claimed only over the range computed — period 34 from heap 53, holding through all 2,001 values, which is what was checked. Bigger boards belong to solvers written for Cram alone, and the 3 × n and 4 × n families in particular have been taken a good deal further than this by people who wrote them.

What the picture cannot show #

The pairing figures draw the strategy as a set of lines through the centre. That drawing is honest about the pairing and silent about the strategy.

What it cannot show is that the reply is legal at every point of every game. A line joining two squares says those squares correspond; it does not say that whenever one is filled the other is empty, which is the whole content of the claim and a statement about every position reachable while the rule is followed. The figure answers with a count instead — 60 positions walked on 4 × 4, 624 on 4 × 6, a legal reply at every move of every one — and a count is a promise rather than a picture.

Nor can it show a failure properly. The 3 × 3 figure marks one domino in the failure colour, and a reader could reasonably infer that repairing that domino would fix the strategy. It would not: the obstruction is the fixed centre square, and the marked domino is only where the walk met it first. The difference between a first counterexample and a cause is not something a colour can carry.

The third invisible thing is the values. A drawn board shows a position; the number under it is the output of a recursion over thousands of positions that are not on the page, and no amount of looking at sixteen empty squares reveals that they are worth 0.

The convention, named #

Everything here is normal play: the player unable to place a domino loses. Every outcome, every Grundy value and both symmetry arguments depend on it.

Misère Cram — last player to move loses — is a different game with the same rules, and none of this transfers. The mex rule is a normal-play theorem; under misère play a position has no value that composes, and what survives is a quotient rather than a number. Nor does the pairing, and the reason is exact: mirroring guarantees the second player always has a move, which is a winning property under normal play and a losing one under misère.

The second convention is that Cram is impartial by construction, with no partizan reading hiding underneath. The temptation is to think of it as Domineering with each player given extra options; it is not, because in Cram there are no Left dominoes and Right dominoes at all, only dominoes. That is why the impartial theory applies here and stops at Domineering: the games differ in whether the two option sets coincide, and nothing else about the board matters to that question.

Göran Andersson’s game reached print as Crosscram, in Martin Gardner’s Scientific American column of 1974, and Conway renamed it Domineering. The impartial version and the symmetry argument for even boards are in Winning Ways, where the pairing appears as the standard specimen of an argument that settles an outcome without producing a value.

Where the ladder goes next #

This is the base rung of the cram anchor, and the boards above it are real ones.

Misère Cram. The same boards under the opposite convention, where the pairing inverts from a win to a loss and the values stop composing. The question is whether the small boards are tame — genus values matching Nim’s — or whether Cram goes wild this early.

The 3 × n and 4 × n families. The rows of the table that go furthest, taken as sequences rather than entries, and asked what every impartial family gets asked: is the value sequence eventually periodic, and what is the prefix? The 1 × n row settles at period 34 because it is an octal game; nothing says the wider rows are.

Cram as a sum of regions. A part-played board is usually several disconnected pieces, and the value of the whole is the nim-sum of the pieces — which is why a board that falls apart is easier, and why a real Cram solver wants a catalogue of small region shapes rather than of rectangles. The regions that arise are not rectangles, and none of them is computed here.

Which impartial board games have a symmetry strategy. The pairing used two facts only: that the board has a centre, and that a move is a small symmetric shape. Stating in general when a half-turn pairing works, and what the fixed point has to be for it to fail repairably or unrepairably, is a rung about strategies rather than about Cram.

And the values that are not zero. Everything above is about the second-player wins, because they are the ones with an argument attached. Why 3 × 6 is worth ∗4 rather than ∗1, and what the Grundy sequences of the rows do past the boards a bitmask can hold, need a solver rather than a figure library.