Cram with the last move losing

Cram is Domineering with the orientations shared: either player may place a domino either way up, so the game is impartial and every position is a Nim heap. The essay on it settles the even-by-even boards with a pairing — answer every domino with its half-turn — and ends by naming the question it did not ask: what happens when the player who makes the last move loses? Under that convention, misère play, the Nim heap a position is worth no longer tells who wins a sum, and the question for any impartial game is whether it stays close enough to Nim that a short symbol still does. A game that does is called tame; one that does not is wild. Tame and wild found Kayles wild at heap five and Dawson’s chess at heap nine.

The answer for Cram has three parts, and they pull against each other. The boards are almost all tame. The strategy that made the even boards easy becomes the wrong strategy. And the tameness of a board is a property of the empty board only — the positions a game passes through on the way are a different population, and some of them are wild.

A symbol for each board #

The tool is the genus, as tame and wild defines it. Take the position’s misère Grundy value — the mex rule run with a position that has no moves scoring one instead of nought — and then the same value with one heap of ∗2 added beside the position, then two heaps, and so on. The run always settles into repeating its last two numbers, and the symbol is the normal-play value with that run written as a superscript. Nim positions produce only three shapes of symbol. The firm ones are $n^{n,\,n \oplus 2}$ — a heap of $n$ carries exactly that — and the two fickle ones are $0^{120}$ and $1^{031}$, which only rows of single counters reach: $0^{120}$ is the empty position or an even number of ones, and $1^{031}$ is an odd number of ones. A position whose symbol is one of these is tame; anything else is wild.

Every rectangle two rows deep or more, to twenty squares, gets a symbol in the hero figure. Twelve of the fifteen are fickle. The 2 × n boards alternate between $0^{120}$ and $1^{031}$ all the way to 2 × 10 — the even lengths are an empty Nim position under this reading, the odd lengths a single counter — and 3 × 3, 3 × 4 and 3 × 5 are fickle too. The 4 × 4 board is firm, $0^{02}$, the genus of two equal heaps. Only 3 × 6, genus $4^{146}$, and 4 × 5, genus $2^{03157}$, are wild, and they are also the only two boards whose normal-play value is past ∗1.

So by the measure the subject applies to heaps, Cram is tame on nearly every board a person would play. A fickle board is worth one counter or none, and a sum of fickle boards is played like a row of counters: under misère play the player facing an odd number of counters loses. That is a simpler description than the normal-play values give, where 3 × 6 is worth ∗4 and every board has to be solved to be summed.

The boards that change hands #

The first consequence of the symbols is who wins. A fickle board is a single counter or nothing, and under misère play those two positions swap outcomes: an empty board is a win for the player to move, who has no move to make, and a single counter is a loss. So every fickle board changes winner when the convention changes. The 2 × 2k boards, which the pairing wins for the second player under normal play, are first-player wins under misère play; the 2 × (2k + 1) boards go the other way.

A firm board keeps its winner, because a firm symbol starts with its own normal value — $2^{20}$ is misère value two, a win for the mover, exactly as ∗2 is. The strip of four and the 4 × 4 board are the examples here, and 4 × 4 is a second-player win either way.

The wild boards have no Nim position to be read off, and the table shows what that means in practice: of the five wild boards swept, including the strips, two change winner and three do not. There is no rule to consult. The 4 × 5 board is a first-player win under normal play and a second-player win under misère play; 3 × 6 is a first-player win under both. Nor can either be swapped for anything simpler. Every Nim position of up to three heaps of up to seven counters — 119 candidates besides the empty one — was tested against 3 × 6 and against 4 × 5 in the 56 misère sums with up to three further heaps of up to five, and for both boards every candidate disagrees somewhere. That is what wild means operationally: the board is not a disguised Nim position of any small size, and a sum containing it has to be searched rather than read off.

The pairing hands the game away #

Cram proves that the second player wins every even-by-even board by answering each domino with its reflection through the centre. The argument is that the reply is always free, so the second player always has a move — and under normal play, always having a move is winning. Under misère play it is exactly the wrong thing to guarantee: the reflecting player makes the last move, and the last move loses.

On 2 × 2 and 2 × 4 the reflected reply is a misère loss against every opening. From 2 × 4 onward, on boards two rows deep, the first player wins misère play and the winning openings are exactly the vertical dominoes — any column will do, and no horizontal domino wins. The reason is visible once the board is read as a counter. A 2 × 2k board is fickle with symbol $0^{120}$, a position worth nothing, and the mover wants to hand the opponent the other fickle symbol, a single counter. A vertical domino cuts the board into two shorter boards two rows deep, one of odd length and one of even, or one of odd length alone at the edge; their symbols are one counter and nothing, and one counter is what the opponent then faces. A horizontal domino leaves a shape that is not a rectangle and, checked, is never worth a single counter.

The 4 × 4 board is the one exception to the pattern and it is instructive. It stays a second-player win under misère play, and reflection still wins against twenty of its twenty-four openings. Against the other four the second player has to find a different reply, and the four have something in common: each is the domino in the middle of an edge, lying along that edge. Its reflection is the matching domino in the middle of the opposite edge, and after that pair what is left is the two middle rows and the four corner squares — a symmetric position that the player to move wins under misère play. Eleven of the nineteen replies to an edge-centre opening win for the second player, among them the domino laid directly beside the first one; the reflected reply is not one of the eleven. So the pairing is not simply reversed by the change of convention; it survives as a heuristic that is right most of the time and wrong exactly when the end of the game is in sight, which is how Nim’s own strategy behaves under misère play — play the normal strategy until a move would leave only single counters, then do the opposite.

Tame at the start, wild inside #

Every figure so far is about empty boards. A game played on a board passes through positions, and the genus of each of those can be computed the same way.

The census is where the picture changes. On 3 × 4, whose empty board is fickle, two of the 550 reachable positions are wild. On 4 × 4, which is firm, 206 of 5,700 are wild. The long boards two rows deep carry more as they grow — 12 positions on 2 × 7, 1,074 on 2 × 10 — and the two wild boards are four and five and a half per cent wild throughout. Of the boards swept, only 3 × 5 is tame all the way down.

And on every one of those boards the smallest wild position has ten empty squares. Not nine, and never fewer.

The 3 × 4 position is the board with two adjacent squares of the middle row covered, leaving a ten-square region shaped like a U lying on its side, open to the left, with a base two squares thick. Its genus is $4^{146}$ — normal value ∗4, but a misère run that starts at one rather than at four, which no Nim position does. It is one move from the empty board, which is fickle.

Why ten: the strip is Dawson’s Kayles #

The strip of squares one row deep explains the number. A domino on a strip covers two adjacent squares, anywhere, possibly splitting the strip in two, and the game that results is the octal game ·07, known as Dawson’s Kayles. A chess problem that turned out to be an octal game is where it first appears: a strip of $n$ squares is Dawson’s chess on a heap of $n - 1$.

Dawson’s chess goes wild at heap nine, which tame and wild computes, so the strip goes wild at ten. The Cram computation here recovers that independently, from dominoes on a row rather than from the octal code: tame through nine squares, wild at ten, tame at eleven and thirteen, wild at twelve, fourteen and sixteen.

A board is not a strip, and the wild 3 × 4 region is not a strip of ten either: it has a different genus and a different shape. What the strip supplies is the threshold. Nothing with fewer than ten empty squares is wild on any board swept, and the first wild things arrive at exactly the size where the one-row version of the game first goes wild. Whether a region of ten squares is wild depends on its shape — of the seventeen positions one domino makes on 3 × 4, all with ten squares empty, two are wild — but nothing with nine empty squares is. That is a measured statement about the boards to twenty squares, and it is the most concrete answer to the question Cram raised: Cram goes wild at ten squares, on the strip and on the board alike.

What tame buys, tested in wild company #

The reason anyone cares whether a position is tame is substitution. What a tame heap may be replaced by states it: a tame position may be swapped for the Nim position with the same genus in any misère sum, and the outcome of the sum does not change. The census raises a doubt about that for Cram. A board whose empty position is fickle but which passes through wild positions is tame in its symbol and not in its interior — and a sum is played through the interior.

So the substitution was tested where it is most likely to fail. The 3 × 4 board, fickle with two wild positions inside it, was put beside nothing, beside the strip of ten, and beside the wild ten-square region of 3 × 4 itself, each time together with small Nim positions — fifteen sums — and its misère outcome was compared with the outcome of the same sum with a single Nim counter in its place. The 2 × 7 board, fickle with twelve wild positions, was tested the same way against one counter, and the strip of four against ∗2. Every one of the forty-five comparisons agrees. The replacements the genus names hold even when the company includes wild regions and the board itself will pass through wild positions.

The noughts are only worth something if the same tests can say no, so two wrong replacements were run beside them. Replacing 3 × 4 by nothing, which would be right if its misère outcome were all that mattered, disagrees on ten of the fifteen sums. Replacing the strip of four by ∗3 disagrees on two. The tests have the power to refuse; they refuse the wrong guesses and accept the genus.

That is not a proof that the genus of the empty board licenses the swap for every Cram board in every company, and nothing here claims one. It is a measurement that the worry the census raises does not bite on the boards and companies tested, and it sharpens what tame ought to mean for a board: the symbol of the starting position, not the symbols of everything below it.

How the symbols were computed #

Each board is a set of covered squares. The state of a computation is that set together with how many heaps of two and of one sit beside it, and one memoised recursion computes every value at once: the mex over all placements and all heap moves, with a position that has no moves scoring nought for normal play and one for misère play. That single number — what an empty position scores — is the whole difference between the two conventions, which is the point misère play makes about Nim.

For each board the superscript run is computed to seven heaps of ∗2, far past where every run here settles into its period of two. The census walks every set of covered squares reachable from the empty board by legal placements and computes each one’s symbol from the same memo. The substitution tests are a separate search over sums of a board, a region and Nim heaps, with every move in every component tried. The 4 × 5 board, the largest, has 58,830 reachable positions and takes about four seconds.

The convention named, and what the tables cannot show #

Misère here means the player who makes the last placement loses, applied to the whole sum; a single board in a sum with Nim heaps ends only when the heaps are empty too. The genus convention is Winning Ways’, the same one tame and wild uses for heaps, so a Cram board and a heap of Dawson’s chess can be read off one list.

The tables stop at twenty squares. Whether 3 × 6 and 4 × 5 are the start of wild boards becoming common, or two exceptions among tame ones, needs 5 × 5 and 4 × 6, which are twenty-five and twenty-four squares and past this computation. The census counts sets of covered squares, not shapes, so a wild region that occurs in many positions is counted many times. And the substitution tests are forty-five sums, not every sum: a Cram board beside another wild board, rather than beside a wild region of ten squares, is untested.

Still open: whether the wild boards have a quotient #

The wild boards have no Nim position to be swapped for, and the tool the subject uses in that case is the misère quotient: restrict attention to sums of positions drawn from one game and find the small monoid that tells them apart. For Cram that game is the collection of regions that arise on real boards, and the quotient would say how many genuinely different misère behaviours those regions have. The measurement is a quotient of the regions up to ten or twelve squares — the size at which wildness begins — tested against sums of up to three of them. If it is small, misère Cram has a finite description on the boards people play; if it grows with every square, the wildness that begins at ten squares is the start of a game with no short answer, as a function with no formula found for the wild side of the octal games.