Combinatorial Game Theory
who wins, and by how much
Generator

Cram on 4 by 4

Cram on 4 by 4
Cram on 4 by 4. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements.

Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements.

5 essays call cram-board. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

11 distinct positions, harvested by drawing the figure again at the options each essay asked for.

PositionWorth OutcomeDrawn in
1×1 0 P Cram · Looking for the symmetry
1×5 0 P Cram · Looking for the symmetry · The strategy that is a symmetry
2×2 0 P Cram · Looking for the symmetry
2×3 ∗1 N Cram · The strategy that is a symmetry
2×4 0 P Cram · Looking for the symmetry · The strategy that is a symmetry
2×5 ∗1 N The strategy that is a symmetry
3×3 0 P Cram · The strategy that is a symmetry
3×4 ∗1 N Cram
3×4 with 1 domino placed 0 P Cram
4×4 0 P Cram · The strategy that is a symmetry · The symmetry one move away
5×5 0 P Cram

Where it is called

Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.

Cram on 4 by 4: the pairing strategy. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements. Impartial games

Cram

Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.

 7 symmetries, and the one that is a strategy. 4 games and 7 candidate symmetries, each tested by playing the strategy out against every opponent line rather than by argument. A pairing strategy needs a map that fixes the start, is an involution, and carries one player's moves to the other's — and the last condition is where most of these fail. Impartial games

The strategy that is a symmetry

A pairing strategy is a symmetry of the board that turns one player's moves into the other's, and it wins without computing anything. Tested by playing it out rather than argued, it wins one of seven candidate symmetries across four games — exactly the Cram boards with both sides even, which is exactly where no domino is its own image.

 A thousand shapes, and twelve pairings. Cram on every connected shape of at most eight squares, with the search for a symmetry that answers each of the opponent’s moves. Every pairing found is a second-player win, most shapes have no involution at all, and the strategy accounts for a sixth of the second-player wins there are. Impartial games

Looking for the symmetry

Answering every move with its mirror image wins Cram on a board with both sides even, which is the argument everybody meets. Asked of every connected shape of at most eight squares instead of of thirteen rectangles, it wins twelve — and accounts for a sixth of the second-player wins there are, because 852 of the 1,042 shapes have no symmetry to answer with in the first place.

 Parity decides it before the shape does. For each size, how many first-player wins can reach a position a half-turn pairs in a single move. Every odd size is nought and cannot be anything else, because a pairing needs an even number of squares and a move removes two. Impartial games

The symmetry one move away

A pairing argument proves the second player wins and names no move to do it with. Asked of every shape of up to eight squares it settles twelve boards. Asked one move later — can the first player reach a position a half-turn pairs? — it settles 288, and which boards those are is decided by parity before anything about their outline is looked at.

 Misère Cram, board by board. The normal-play value and misère genus of every Cram rectangle with at least two rows and at most twenty squares. 12 are fickle, 4 × 4 is firm, and 3 × 6 and 4 × 5 are wild. Impartial games

Cram with the last move losing

Under misère play every Cram rectangle to twenty squares is tame at the start except 3 × 6 and 4 × 5, and twelve of the fifteen boards two rows deep behave like one counter or none. The pairing that settles even boards under normal play hands the misère game to the first player, who wins by any vertical domino. And the tame boards are not tame inside: wild positions appear on boards as small as 3 × 4, always at ten empty squares, the length at which the strip goes wild.

The whole library · The position index · The figures that play back