The symmetry one move away

A pairing strategy is the shortest complete argument in the subject. Find a map of the board to itself that sends every domino to a different domino and fixes no square; then whatever the first player plays, the second player plays its image, and the second player never runs out of moves first. No search, no evaluation, and no move named until the opponent has moved.

Looking for the symmetry searched every shape of up to eight squares for such a map. The result was discouraging: of the 74 second-player wins in the catalogue, twelve have a pairing, and 852 of the 1,042 shapes have no involution of any kind. It closed by naming a better question:

Which boards have a symmetry after one move has been played? A shape with no symmetry can become symmetric when a domino is removed from it, and a first player who could reach such a position would have the pairing argument on their side.

That is a question about the first player, and it has a much larger answer.

The question, made precise #

The census takes every shape in the catalogue that Cram makes a first-player win — 968 of the 1,042, since first-player wins are the overwhelming majority at these sizes — and asks of each: is there a domino whose removal leaves a position that a half-turn pairs?

If there is, the first player has a complete strategy. Play that domino; the rest of the game is the second player’s pairing argument run for the first player, and it names no further move.

The answer over the whole catalogue is 288 of 968.

That number is not the interesting one. What is interesting is that it is not distributed the way a reader would expect.

Parity, before anything about the shape #

The odd sizes are all nought, and not approximately nought — exactly nought, across 201 shapes of five and seven squares.

The reason takes one line. A pairing needs an involution with no fixed square, because a square that maps to itself would be a square the paired reply could not use. An involution with no fixed point pairs the squares up, so the number of squares must be even. A move removes two squares, which does not change the parity. An odd shape is odd after any number of moves and can never reach a paired position.

The census asserts that rather than reporting it. An odd shape appearing in the reachable column would mean the move generator or the pairing test is wrong, and the figure refuses to draw rather than reporting it.

So the first thing this search discovers is that half the question was never open. The interesting population is the even shapes, and among those the shares are 8 of 8, 44 of 46, and 236 of 711.

The share falls, and falls fast #

Among even shapes: 100 per cent at four squares, 96 at six, 33 at eight.

That fall is worth taking seriously because it is the direction the whole idea has to survive. A four-square shape has at most four dominoes to try and very little structure to break; an eight-square shape has up to ten, and each removal leaves a six-square position that must be exactly symmetric about its own centre.

The condition being asked for is severe. It is not the remaining squares are symmetric in some loose sense — it is that the half-turn about the midpoint of the bounding box sends every remaining square to another remaining square, and none to itself. Most six-square subsets of an eight-square shape fail that on the first square tested.

Four hundred and seventy-nine even shapes have no such move, and they are the same size and parity as the ones that do. That is the honest limit of the idea: it is a search, not a rule, and nothing about a shape’s outline predicts the answer.

What the paired position is allowed to be #

One decision in the census is worth defending because it looks like a licence and is not.

Removing a domino from a shape can disconnect it. The census allows that: it asks whether a half-turn pairs the remaining squares, whether or not they are in one piece.

That is legitimate, and the reason is what a pairing argument actually needs. The strategy is reply with the image of the opponent’s move, and its correctness needs exactly two things: the image of every legal domino is a legal domino, and no domino is its own image. Neither mentions connectivity. If the remaining squares fall into two regions that are half-turn images of each other, the reply is in the other region and is perfectly legal.

So the argument survives decomposition without being about it, which is unusual here. The board falls apart is normally the moment an evaluation gets cheap and a strategy gets complicated, and which part to move in is the question a decomposition usually forces; a pairing does not care, because it never evaluates anything.

The one thing it does need is that the centre is computed from the remaining squares rather than from the original shape. A half-turn about the original centre would not pair the leftover of an off-centre move, and computing it from the leftover is what makes the search find anything at all.

Twenty times as many boards, for one named move #

Setting the two searches side by side is the point of the exercise.

The rung below’s search asks is this board paired? and gets twelve yeses out of 74 candidates. This one asks can this board be made paired? and gets 288 out of 968. The population is larger and so is the share.

What was bought is one move. A pairing argument that names no move at all is a beautiful object and a rare one; a pairing argument preceded by one named move is a much commoner object and is still a complete strategy that names nothing after the first ply.

That is a good trade and it has a name in the literature: a strategy-stealing-adjacent move plus a symmetry, of which the centre-then-pair strategy for odd Cram boards is the standard instance. This census is that idea taken off the rectangles and asked of every shape.

And 288 is still a minority. Two thirds of the even first-player wins at eight squares have no such move, so the technique settles a third of the boards it is pointed at and leaves the rest to a solver. That is a good deal better than one in six and it is not a method.

Where the routes are, when there are any #

A shape with a reachable pairing usually has more than one route to it, and the distribution says something about how fragile the technique is.

The census records, for each shape that can reach a paired position, how many of its dominoes do it. The 288 shapes have 360 such moves between them, 1.25 apiece, and 242 of the 288 have exactly one.

That is the practically important fact: the move is usually unique, so a first player who knows the technique exists still has to find the domino, and there is no second chance if the wrong one is played.

That is a sharper constraint than it sounds. A first-player win reached by a different opening is still a first-player win — the game does not become lost — but the pairing argument is gone, and what remains is an ordinary search. So the technique is a way of playing without thinking that requires one piece of thinking, placed first.

Compare that with the rung below’s situation, where a shape either is paired or is not and the second player has nothing to find. A pairing on the board is a strategy; a pairing one move away is a puzzle with a strategy behind it, and the difference is the whole of what the extra move costs.

There is one consolation for a solver rather than for a player. Checking every domino is cheap — at most ten removals and a half-turn test each — so a program pays nothing to find the unique route, and the uniqueness that troubles a person is invisible to it.

Why the half-turn and nothing else #

Every shape here is tested against the half-turn only, and the rung below is where that is justified: of the eight symmetries of the square, the half-turn is the only one that ever pairs anything.

A reflection fails because a domino lying across the axis is its own image. A quarter-turn is not an involution unless it fixes the centre, and one that fixes the centre has a fixed square. That leaves the half-turn, and the rung below’s search asserts it — a shape paired by any other map would stop the build.

So the search here is not a restriction for cheapness; it is the whole of what is available. A shape whose remaining squares are symmetric under a reflection and not under a half-turn is not a shape this argument can use, however symmetric it looks.

That is worth saying because symmetric is the word a reader supplies and it is the wrong word. The condition is half-turn symmetric with no centre square, which excludes the letter-T, the letter-U and every shape with an axis of reflection and an odd cross-section — and includes plenty of shapes nobody would call symmetric at a glance.

What it says about Cram at these sizes #

Standing back from the technique, the census says something about the game it is played on, and it is not what the twelve pairings of the rung below suggested.

Cram at eight squares is overwhelmingly a first-player game. Nine hundred and sixty-eight shapes of 1,042 are first-player wins, which is 93 per cent, and the share climbs with size: 711 of 730 at eight squares. A second-player win is the exception and a provable second-player win rarer still.

That reframes the pairing argument’s role. It is not a tool for settling the hard cases; it is a tool for explaining the easy ones, and the direction of the explanation is the surprise. A pairing on the board proves the second player wins, and second-player wins are almost extinct at these sizes — which is exactly why the rung below found so few. Turned round to serve the first player it applies to a population two orders of magnitude larger, and finds something in a third of it.

So the technique was pointed at the wrong player. That is the transferable observation and it generalises past Cram: an argument that proves the second player wins is worth what second-player wins are worth in the game it is applied to, and in a game where the mover usually wins that is not much. Making the same argument serve the mover costs one move and buys the whole population.

Strategy stealing is the other argument on this site with that shape — it proves the first player wins by turning a hypothetical second-player strategy round — and it is worth reading beside this page for the contrast: stealing names no move at all and proves nothing about which move, while this names exactly one and then names none.

Why one move and not two #

The weakening stops at one move, and the stopping point is not a choice about how much work to do. It is where the argument stops working.

A pairing strategy needs the second player to have an answer to every move, for ever. From a symmetric position that is supplied by the symmetry itself. From a position one move away, the first player makes the move that reaches symmetry and is then the second player in a symmetric position — so the argument is the original one with a single move prepended, and the prepended move is chosen rather than answered.

Two moves away has no such reading. The mover would have to reach symmetry in two of their own moves with the opponent moving in between, and the opponent chooses that move. So the target is not one position but every position the opponent can produce, and reaching symmetry against any reply is a claim about a set rather than about a move.

That is not a harder version of the same check; it is a search. Checking one move away is testing each move and asking whether the result is symmetric — cheap, local, and decidable by looking. Checking two is asking whether some move leaves a position from which every reply leaves something one move from symmetry, which is two levels of quantifier and is most of what a solver was going to do anyway.

So the one-move weakening is the last cheap one, and the reason it is the last is the alternation rather than the arithmetic — which is the same boundary alternation is the difficulty draws around the whole subject, showing up here in a check that costs nothing until it costs everything.

What the census does not say #

Four limits.

Cram only. The pairing argument works because Cram’s two players have the same moves and a domino is a small symmetric shape. In Domineering the two players place perpendicular dominoes and a half-turn sends a vertical domino to a vertical domino, so the map is available — but the game is partizan and reply with the image is not a strategy, because the image of the opponent’s move is a move the opponent could make and not one this player can.

Up to eight squares. The catalogue stops where a build can enumerate every shape, so the fall from 96 per cent to 33 has two points on it. The trend is clear and its continuation is an extrapolation.

One move. Nothing here asks about two. A first-player win with no pairing one move away might have one three moves away, reached by a pair of forced exchanges, and searching for that is a different and much larger computation — it is a search over lines of play rather than over single dominoes.

And a reachable pairing is a strategy for the first player, not a proof that the first player wins. The census only asks the question of shapes Cram already makes first-player wins, so the pairing confirms a known answer with a strategy rather than establishing an unknown one. Used the other way round it would be a proof, and there are no such shapes here: every shape with a reachable pairing is already a first-player win, which is a consistency check the census gets for free.

The convention, named #

Normal play. Cram is played on a region of squares; either player may place a domino on any two adjacent empty squares, and a player unable to move loses. Both players have the same moves, so the game is impartial and every position has a Grundy value.

A pairing is an involution of the squares with no fixed point, sending every domino to a different domino. The half-turn is the map (r, c) ↦ (R − r, C − c), where R and C are the sums of the extreme rows and columns of the squares being paired — so the centre is the centre of what remains, recomputed after the move rather than inherited.

The outcome of each shape is computed by the Grundy recursion over subsets, and a shape is a first-player win when its Grundy value is not nought.

Where the ladder goes next #

The pairing anchor has three rungs: the conditions a pairing has to satisfy, what an exhaustive search for one finds, and now what the same search finds when the first player is allowed a move first.

The rung above is the hybrid the rung below asked for and this page has made worth building. A solver that checks for a reachable pairing before recursing settles a third of the even first-player wins at zero cost — the check is one pass over the dominoes and a half-turn test — and recurses on the rest. The number worth measuring is what that saves on a real search rather than on a catalogue: how deep into a game the check keeps paying, and whether the positions arising in play are more or less symmetric than the positions in a catalogue of shapes.

Two neighbours are worth the trip. Cram is where the pairing is used rather than tested, and where the centre-then-pair repair for odd boards is the one-move version of this page’s idea applied to rectangles. And a winning strategy that is a spanning tree is the other argument here that settles a game without a search, where the strategy is produced rather than merely shown to exist.