Looking for the symmetry

The strategy that is a symmetry took seven proposed symmetries, tested them on thirteen Cram rectangles, and found that the half-turn wins exactly the boards with both sides even. It closed by naming the version of the question nobody had asked:

Given a game and a position, is there any involution that pairs it? That is a question about the automorphisms of a position graph, it is finite for a small board, and a program that answered it would find pairing strategies nobody had noticed.

Run over every connected shape of at most eight squares — 1,042 boards rather than thirteen — it finds nine that nobody had noticed and 852 boards with nothing to look at.

What is being searched #

A pairing strategy is a promise: whatever the opponent plays, the second player has an answer, and after the answer the position is back where it was in some respect that matters.

Made precise for Cram it is an involution of the squares with three properties. It must have no fixed square, because a square that is its own image is a square the opponent can take with nothing to answer. It must carry dominoes to dominoes, because the answer has to be a legal move. And it must carry no domino to itself, because a domino that is its own image is a move the answer would have to repeat.

Given such a map, the second player answers each move with its image and can always do so, because the position after the opponent’s move is off the fixed set and the image restores it. The strategy needs nothing about values and it produces a win.

The search space is small and the reason is worth stating. An involution of the squares that is not a symmetry of the shape carries some domino off the board, so the only candidates are the maps of the square that take the shape to itself: the two reflections, the half-turn, the two diagonal reflections and the two quarter-turns, of which the quarter-turns are involutions only in degenerate cases. Eight maps, the identity discarded, tested per shape.

Twelve of a thousand #

Of the 1,042 shapes, Cram is a second-player win on seventy-four.

A pairing wins twelve of them.

Every one of the twelve is a second-player win — the soundness is asserted, so a pairing that won a shape the solver calls a first-player win would stop the build — and the other sixty-two second-player wins have no pairing at all.

Sixteen per cent is a low number for a strategy presented as the way Cram is understood, and the reason is not that the strategy is weak. It is that most shapes have nothing to apply it to: 852 of the 1,042 have no involution of any kind.

One of the seven maps does all of the work. Every one of the twelve is paired by the half-turn, and no reflection and no quarter-turn pairs anything at all — a fact the search asserts rather than reports, so a shape paired by something else would stop the build. The reason is the second condition: a reflection has an axis, a domino lying across that axis maps to itself, and a shape with a reflection but no domino across the axis is a shape in two disconnected halves. Connectedness rules the reflections out.

Why the rectangles were the wrong sample #

Thirteen rectangles are a fair test of a proposed symmetry and a terrible sample of a board.

A rectangle has four symmetries at least and eight if it is square. A polyomino chosen at random has one — the identity — and nothing else, and the fraction with any symmetry falls as the shape grows: at four squares seven of nine have an involution, at six twenty-eight of sixty-eight, at eight ninety-eight of 730.

The eight-square row makes the point sharpest. Seven hundred and thirty shapes, ninety-eight with an involution, nine with a pairing. So even among the shapes that have a symmetry, having one is almost never enough: eighty-nine of the ninety-eight fail one of the other two conditions.

So the strategy was demonstrated on the most symmetric objects the game admits, and generalising from them is the same error as generalising about polygons from regular ones. The rectangles are not typical; they are the extreme.

That has a consequence for how the argument should be presented, and this site has been presenting it the usual way. Cram is won by pairing is a sentence about a small and highly symmetric family. What is true of Cram in general is that pairing wins when the board happens to have a symmetry to spare, which on a board arising in play it usually does not — a partly filled board is not symmetric. That is the same objection the region catalogue raises against rectangles from the other side of the Domineering essays: the shapes a game produces are not the shapes a game starts on.

Parity, which decides whether the argument can begin #

The size breakdown has one striking feature and it has a one-line proof.

A pairing needs a fixed-point-free involution. An involution of a finite set partitions it into fixed points and two-element orbits, so a set of odd size must have a fixed point. A shape with an odd number of squares therefore cannot be paired, whatever its symmetries are, and every second-player win on such a shape is won some other way.

Thirty-two of the seventy-four second-player wins are on odd shapes — the fourteen at five squares, the seventeen at seven, and the single square, which is a second-player win because the first player cannot move at all. So two fifths of the target is out of reach before the search starts, for a reason that has nothing to do with Cram.

That also explains the commonest failure the search reports. Of the symmetries rejected, 158 were rejected because a square is its own image, ninety-four because a domino is, and none because a domino had no image at all — a symmetry of a polyomino carries adjacent squares to adjacent squares by construction, so the third condition is never the binding one.

What the other sixty-two are won by #

Sixty-two second-player wins with no pairing is the interesting residue, and the first thing to establish about it is that “no pairing” is three different failures wearing one name.

Fifty-two of the sixty-two never reached the conditions at all. That is worth separating from the ten that did, because the two are different complaints: the first is that the argument has no material to work on, and only the second is a case of the argument being tried and found wanting. A method that fails because it was never applicable is not a method with a failure rate.

Some of the sixty-two are won by a strategy of a related kind. The centre-then-pair argument handles an odd board by taking the middle first and pairing afterwards, which is why an odd Cram rectangle is a first-player win — and on an odd shape with a centre square that argument applies to the opponent rather than to the pairer, so it explains first-player wins rather than second-player ones.

The rest are won by nothing describable. Where the impartial theory stops is the general form of that complaint and Cram is a mild case of it: the values exist, the search finds them, and no shorter account of them is known. Their Grundy value is nought because the recursion says so, and the search that says so is the whole explanation available. That is the ordinary situation for a combinatorial game and it is worth naming here because the pairing argument is so satisfying that its absence reads as a gap rather than as the default.

A strategy argument is a bonus, not a method. Cram’s is real, and it covers twelve of a thousand boards.

The one shape of four squares #

The smallest board a pairing wins is worth looking at, because it is the whole argument at a size that fits in a sentence.

It is the 2 × 2 box. The half-turn sends each corner to the corner diagonally opposite; no square is fixed; each of the four dominoes maps to the one parallel to it across the centre, and none maps to itself. Whatever the first player plays, the second player plays the other one, and the board is full.

That is the complete proof for a four-square board and it generalises to the even-by-even rectangles without a further idea. What it does not generalise to is anything else at four squares: the other eight shapes of four squares include an L, an S, a T and a straight strip, and Cram is a first-player win on every one of them.

So at four squares the pairing explains the one second-player win there is, which is the best it does at any size. At five it explains none of fourteen; at six two of twenty-two; at seven none of seventeen; at eight nine of nineteen.

What a search for a strategy is worth #

The search was proposed as a way of finding pairings nobody had noticed, and it found nine — the nine of the twelve that are not rectangles, two of them of six squares and seven of eight. All nine carry a half-turn, because a half-turn is the only map in the table that ever pairs anything.

Nine new pairings is a modest yield and it is the right yield, because the search is exhaustive over its space. What it establishes is not that there are few pairings but that there are no more: within the eight maps of the square, every pairing that exists on a shape of at most eight squares is in the gallery above.

That is worth more than the nine. A search that comes back nearly empty over an exhaustive space has settled a question, and the question is whether the pairing idea has been under-exploited. It has not.

The natural objection is that the space is too small — that an involution of the position graph rather than of the squares might pair a board with no geometric symmetry. It might, and it would not be a pairing strategy in the sense anybody uses: the answer it prescribes would not be a move determined by the opponent’s move, only a move determined by the whole position, which is a strategy in the ordinary sense and is what the search already is.

Two numbers on this page are worth remembering, and they point in opposite directions.

Every pairing found is sound. Twelve for twelve, asserted rather than reported. A strategy argument that promises a win delivers one, and there is no shape where the symmetry looks right and the solver disagrees. That is what a strategy argument is for and it does its job perfectly.

And a pairing exists on one board in eighty-seven. Not one second-player win in eighty-seven — one board. A player sitting down in front of a shape they have not seen before has essentially no chance that the argument applies.

Those two together are the honest description of a pairing strategy: completely reliable and almost never available. The literature presents the first half, because a proof is what a paper contains, and the second half is a fact about a population that nobody had counted.

It is the same shape as what the periodicity results do for octal games — a certificate that settles a game outright, on the games that have one — and the same caution applies. A method with no failures and a small domain is not the same object as a method that works.

Why a pairing argument is so rarely available #

The search turns up few symmetries and it is worth saying why that is the expected outcome rather than a disappointment, because the reason is a counting argument and not a fact about any board.

A pairing strategy needs an involution on the position’s moves: a way of matching each move with a partner such that answering a move with its partner always restores the position to something equivalent. That is a very strong demand. The matching must be defined on every move, it must be its own inverse, and the answer must remain legal after any sequence of exchanges — so the involution has to survive being applied repeatedly to a position it is itself changing.

Board symmetries supply involutions and almost nothing else does. A half turn or a reflection gives a matching for free, defined everywhere, self-inverse by construction, and preserved by the exchanges because the board’s symmetry is preserved. Constructing an involution by hand on an asymmetric position means specifying a matching move by move and checking it survives — which is the same amount of work as solving the position.

So a pairing argument is available when the position is symmetric, and the search is really a search for symmetric positions rather than for strategies. That is why the counts come out small: symmetric positions are rare among positions, and they get rarer as boards grow, for the same reason folding by symmetry saves less than its group order.

And it is why parity does so much of the work. A symmetric position with an odd number of cells has a fixed point under its own symmetry, so the matching cannot be defined everywhere and the argument fails before it begins — which is a condition a reader can check by counting rather than by searching.

What the sweep does not say #

Three limits.

Eight squares is where the enumeration stops. There are 1,042 connected shapes at that size and 2,725 at nine, and Cram on each is a search over subsets of the squares. The counts here — seventy-four, twelve, 852 — are counts and not rates; the proportion of second-player wins a pairing explains at ten squares is a different number and is probably smaller, since symmetry gets rarer.

Only Cram is swept. The generic test is written against a move rule and a symmetry, and it has been pointed at Domineering, Toads and Frogs and Clobber as well. Sweeping those over shapes rather than rectangles is the same computation with a different move function and it has not been run — Domineering in particular, where the half-turn is useless for a reason the rung below explains and a reflection is not.

The search is over geometric symmetries and says so. An involution of the squares that is not a symmetry of the shape carries a domino off the board and cannot be a pairing, which is the argument for restricting the space; it is an argument and not a proof, and the proof would need a sentence about connectedness that this page does not give.

And nothing here is about misère play. A pairing strategy under the misère convention answers the same moves and loses, because the player who always has an answer is the player who eventually has to make the last move. The twelve shapes above are second-player wins under normal play and say nothing about the other ending.

The convention, named #

Normal play, and Cram: both players place dominoes in either orientation, and the player unable to move loses. A shape is a connected set of squares, normalised so that two shapes related by a reflection are one shape — the same catalogue the Domineering regions are drawn from, so that “every shape” means the same thing on both pages.

The Grundy value of each shape is computed by the recursion over subsets of its squares. A candidate symmetry is one of the eight maps of the square that carries the shape to itself; it is a pairing when it has no fixed square, carries every domino to a domino, and carries no domino to itself.

Where the ladder goes next #

The pairing anchor has two rungs to here: the strategy that is a symmetry, and now the search for one on a real board.

The symmetry one move away is the natural weakening — positions that are not symmetric but become so after a single move — and it is where a pairing argument stops being a curiosity about symmetric shapes and starts covering openings.

A check in front of a search then prices it as machinery rather than as mathematics: a one-sided test that either returns lost or returns nothing, cheap to run, and worth whatever subtree it stops anybody looking at.

The two rungs after that are corrections to the machinery and both matter more than the saving. The check that was not a check finds the pairing check unsound at interior positions — on a four by five Cram board it fires on 8,613 of them and 1,026 of those are losses — so a solver trusting it below the root answers wrongly rather than slowly. Repaired, the policy that pays is the plainest available: test at the root and nowhere else.

A pairing and the pairing then asks whether the other symmetry fires where the half turn does not. It does, on forty positions of 58,830, it is sound, and it is worth about one node in a thousand — and it can never fire on an empty rectangle, which is why this anchor’s whole subject is the half turn and the reflection appears nowhere in it.