Cram — where it appears
Named by 13 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
A check in front of a search
The rung below found a pairing one move away on 288 of the 767 even first-player shapes, and asked what a solver that tested for one before recursing would save on a real game. On an even Cram board it saves nearly the whole search — a 4 × 5 board takes 17,348 node expansions without the check and one with it — and the depth profile shows why that number flatters: the check settles every winning position at the opening and at the last two moves, and about one in ten in between.
A product against a sum
A company closed under both addition and options licenses a solver to rewrite any subposition, and the rung below found that exactly the nimber groups have both closures. Priced on Cram boards, that licence is the difference between walking a product of position sets and walking their sum — four to twenty-five times on two components, twenty-four to a hundred and sixty-one on three — and it is available to impartial games because their class representative is a heap rather than a form.
The check that was not a check
The rung below asked for a depth-conditioned solver and named the board to measure it on. Building it found two things first. The pairing check is unsound at interior positions — on a four by five Cram board it fires on 8,613 positions and 1,026 of them are losses — and the board it named has twenty-five squares, so the check can never fire there at all. Repaired, the check is right everywhere, and the policy that pays is the root alone.
Half a licence is nearly all of it
The rung below priced the substitution licence a restricted universe gives a solver and asked what half of one is worth — the licence to rewrite components but not subpositions. It is worth nearly the whole saving. Rewriting components collapses a million and a half states to three thousand six hundred; rewriting subpositions collapses those to eight hundred and eighty-four, and splitting the pieces takes it to fourteen.
A pairing, and the pairing
The rung below repaired the half-turn check and asked whether a reflection would fire where it does not. It does — forty positions of 58,830 on the largest board — and it is sound, and it is worth one node in a thousand to a solver. It can never fire on an empty rectangle at all, which is why the ladder's whole subject is the half turn.
One half multiplies, the other adds
The rung below priced the two halves of a substitution licence on sums of two Cram boards and predicted that the first half's saving would grow with the number of components while the second's would not. It is right, and both halves have closed forms: the component licence saves s^(k−1)/k and the subposition licence k·s over a shape count that never moves.
A symmetry that is not a pairing
The quarter turn was the last symmetry a Cram pairing argument had not tried, and the one a square board seemed to offer. It fires on the empty four by four and it settles nothing the half turn misses — and the reason is a clause four rungs of this anchor never had to write down, because every map tried so far was its own inverse.
The licence that weighs nothing
The third substitution licence is constant in the number of components, exactly as predicted, and it saves under two times where the first saves seventy-six million. Priced by its table instead of by its saving it is the only one of the three whose cost does not run away — which reverses the order three rungs of this anchor have put them in.
A pairing that is not a symmetry
Every pairing strategy this ladder has found is a rigid motion of the square, and the requirement mentions no geometry at all. Searching all 8.8 million fixed-point-free involutions instead of the eight maps more than doubles what a pairing explains — and the smallest new one turns out to be a reflection with its two fixed squares swapped.
Named alongside it
The objects these essays reach for when they reach for this one.
EnumerationImpartialSymmetryExhaustive searchStrategyGrundy valueInvariantMemoisationPairingPairing strategyCounterexampleDecomposition