The strategy that is a symmetry

The cheapest winning strategy in the subject has no arithmetic in it. Whatever they do, do the mirror image of it. Nothing is computed, nothing is looked up, and the argument that it wins is one sentence: the answer is always available, so the player following it never runs out of moves first.

Cram uses one and closed by asking for the general statement:

The pairing used two facts only: that the board has a centre, and that a move is a small symmetric shape. Stating in general when a half-turn pairing works, and what the fixed point has to be for it to fail repairably or unrepairably, is a rung about strategies rather than about Cram.

One of seven. The other six fail, in two quite different ways, and separating the two ways is most of what a general statement has to do — because a symmetry that answers the wrong player’s moves and a symmetry that answers the right player’s moves and then runs out are not the same kind of failure, and only one of them can be repaired.

The three conditions #

Let $\sigma$ be a map from positions to positions. It is a pairing for the second player when three things hold.

It fixes the starting position. $\sigma(P_0) = P_0$. Without that there is nothing to restore.

It is an involution. $\sigma(\sigma(P)) = P$, so the image of the image is the original and the strategy does not drift.

It carries the opponent’s moves to the replier’s. After the opponent has moved to $Q$, the replier must have a move from $Q$ to a position $\sigma$ fixes.

The third is the whole content, and it is the one that has to be tested rather than inspected. The strategy is stated here as restore the symmetry rather than as play the image of their move — the two are the same strategy, and the first formulation works for a game whose board fills up and for one whose pieces move around, without needing a separate algebra of moves for each.

Where it wins, exactly #

Running the same test over every Cram rectangle gives a clean answer, and it is not the one the parity of the cell count suggests.

The pairing wins exactly the boards with both sides even. Not the boards with an even number of squares — $2 \times 3$ has six squares and the pairing fails on it. Both sides even, and nothing else — with one degenerate exception the table names rather than hides. The $1 \times 1$ board has no move on it at all, so the strategy never has to answer anything and completes vacuously; it is a second-player win because the first player cannot move. The characterisation is about boards a game can be played on, and among the twelve of those it is exact.

The reason is a single fixed object. The half-turn sends the cell at index $i$ to the cell at $N - 1 - i$, and it maps a domino to itself exactly when those two cells are adjacent. On $2 \times 3$ they are: the vertical domino in the middle column is its own image, so the opponent plays it and the answer would have to be the same move again. On $2 \times 4$ no pair $\{i, N-1-i\}$ is adjacent, and there is nothing to catch.

An odd number of squares is the same failure one step cruder: a square is its own image, so a domino covering it is covered by no image at all.

Neither failure depends on the board being small, and neither does the success. The same strategy on a board with twice the squares does the same thing for the same reason, and it is worth watching it do so before the essay starts describing what it costs.

Sufficient, and not necessary #

The second half of the census is the half a reader is most likely to get wrong.

Every board the pairing wins is a second-player win — that is asserted in the code, and it is the soundness of the argument. The converse is false. Two of the thirteen boards here are second-player wins the pairing cannot reach: $1 \times 5$ and $3 \times 3$, both of which have a square fixed by the half-turn and are nevertheless losses for whoever moves first.

That matters because a pairing argument is often presented as though it settled a game. It settles the boards it applies to and says nothing about the rest, and the rest contains second-player wins that need a real search.

The other one is smaller still, and it is the cleanest demonstration available that the strategy is a sufficient condition rather than a description of the second-player wins. A strip of five squares has nothing on it but a middle, and the search says the mover loses.

Cram records that $3 \times n$ is not settled in general, and this is why: the strategy that solves the even boards has no purchase on the odd ones, and everything past that is computation.

The condition the third one hides #

The three conditions above put the whole burden on the third — the replier must have a move restoring the symmetry — and that clause is doing two separate jobs. Separating them is what distinguishes the two failure modes.

The image must exist. The opponent’s move must have an image that is a legal move of the replier’s, which needs the involution to send one player’s moves to the other’s and to fix none of them. This is what the Cram census measures: a domino equal to its own half-turn image has no distinct answer, and both sides even is exactly the condition under which none exists.

And the image must still be available. Having played their move, the opponent has changed the board. The replier’s image move has to remain legal after that change — and nothing in the first clause guarantees it.

On Cram it is guaranteed, and the reason is disjointness. A domino and its half-turn image, when they differ, occupy four distinct cells: the map sends cell $i$ to $N-1-i$, so a domino’s image shares a cell with it only when the two cells are adjacent, which is precisely the fixed-move case already excluded. So playing one never covers a square the other needed, and the answer that existed before the move exists after it.

On Toads and Frogs it is not. Reverse the strip and exchange toad for frog and the involution is perfect — it fixes the start, it is an involution, and it sends every toad move to a frog move with no fixed moves anywhere. And a toad’s step and its mirror frog’s step can want the same empty square, because the two halves are one strip. The image exists when the opponent moves and has stopped existing by the time the replier answers.

Two failures, and only one is about the symmetry #

That gives the essay’s two modes their exact statements.

Wrong player. Domineering’s half-turn sends a vertical domino to a vertical domino, so the images are Left’s moves and Left is not the one replying. The symmetry is fine and it is a symmetry of the wrong thing — a defect in the choice of involution, and one that a different choice might repair.

Right player, no room. Toads and Frogs’ mirror sends the right moves to the right player and the moves interfere. There is no better involution to reach for: the interference comes from the two halves sharing a board, and every involution of that strip pairs squares the pieces have to move through.

So the first failure is a failure of the map and the second is a failure of the board, and only the first is the kind a reader should expect to fix by looking harder.

And it says what a pairing strategy really requires. Not that the position decomposes — Cram’s boards do not split into two independent halves, and a domino may straddle the centre. What it requires is that a move and its image never compete for the same square, which is a much weaker condition than independence and is exactly what disjointness supplies.

That is why the technique reaches the games it does. It works wherever moves are small, local and place-something-permanent; it fails wherever moves move things, because a piece and its mirror image are travelling through the same squares.

The other way to fail #

The four non-Cram rows of the first table fail differently, and the difference is worth stating because it is the difference between this symmetry is wrong and there is no symmetry.

Domineering has an obvious half-turn and it is useless. Rotating the board through half a turn sends a vertical domino to a vertical domino, so the image of Left’s move is another of Left’s moves. Left answering Left is not a strategy for Right; the symmetry exists, is an involution, fixes the board, and carries the moves to the wrong player’s list.

Clobber has the same trouble twice. Reversing a row without exchanging the stones sends a Left move to a Left move. Reversing and exchanging the stones does swap the players — and the strategy still fails, for a completely different reason.

Toads and Frogs fails for that second reason too. Reverse the strip and exchange toad for frog and the symmetry is exactly right: the image of a toad’s move is a frog’s move, the start is fixed, and it is an involution. Run it out on the four-square strip with two toads and two frogs and the play-out gets three moves in and stops — a toad steps into the middle, the frog’s mirror step wants the square the toad has just taken, and there is no reply to give.

The reason is the one thing a pairing needs that the three conditions do not state: the two halves have to be independent. On a Cram board the two halves are separate squares and a move in one does not touch the other. On a Toads and Frogs strip they share the middle, and the opponent can play a move whose image is no longer legal because the original has changed the middle.

The relation to the other mirror argument #

There is a mirror strategy on this site that always works, and setting it beside this one isolates exactly what independence is buying.

Every game has a negative proves that $G + (-G)$ is a second-player win, by the mirroring strategy: whatever the opponent does in one copy, do the reflection in the other. That argument never fails, and the reason is in the plus sign. $G$ and $-G$ are separate components, so a move in one leaves the other untouched by construction, and the image move is available because nothing could have taken it.

That argument is a pairing with the independence handed to it rather than established, and the difference is the plus sign and nothing else. A position and its negative are drawn side by side because they are side by side; a Cram board’s two halves are a fiction the half-turn maintains, and the fiction survives exactly as long as no move touches both halves at once.

So a pairing strategy on one board is the mirroring argument applied to a position that is pretending to be a sum. When the pretence holds — when the board really does split into two halves the symmetry exchanges — the argument goes through unchanged. When it does not, as on a Toads and Frogs strip or a Clobber row, no amount of symmetry helps.

That is the general statement the rung below asked for, and it has three clauses rather than two: a symmetry that fixes the position, exchanges the players’ move sets, and has no fixed points a move can touch — where “fixed point” has to mean anything a single move can be its own image of, not merely a fixed cell.

What the strategy is worth as an object #

A pairing is not merely a way of winning; it is a way of winning that a person can hold in their head, and the subject has very few of those.

Almost every result on this site names a winner by computing something. The nim-sum needs the heaps written in binary. A thermograph needs a recursion over the option tree. Comparing two positions means playing a third, which is a search. A pairing needs a glance at the board and no arithmetic at all, for ever, against any opponent.

That puts it in the same small family as strategy stealing — and the contrast between the two is instructive, because they are opposites. Strategy stealing proves that the first player wins and supplies no move; a pairing proves that the second player wins and supplies every move. One is a pure existence argument with nothing to play, the other is a complete strategy with nothing to prove.

The asymmetry between the two is worth being exact about, because it decides what each is for. A strategy-stealing argument is a proof and produces no program: it establishes that the first player is not losing, and every winning move it names has to be found afterwards by a search that owes the argument nothing. A pairing is a program and produces a proof only as a side effect: the reason it wins is that the program never runs out of moves, so the proof and the strategy are one object. Cheap arguments in this subject come in exactly those two kinds.

So the seven rows of the first table are not seven attempts at a proof. They are seven attempts at a program, and the one that succeeds is a program of two words.

What the fixed points cost, precisely #

The three failure modes can now be sorted by how much they cost.

A fixed cell costs a move. On an odd Cram board the half-turn fixes the centre square, and the first player can play a domino covering it — after which the position is not symmetric and the pairing is gone. It is the mildest failure and it is the one that produces a first-player win when it produces anything.

A self-paired move costs the strategy outright. On $2 \times 3$ the middle vertical domino is its own image, and there is no repair: taking it first leaves a symmetric position with no fixed object, but the opponent can take it instead and the second player has no answer. This is the failure that decides most of the Cram table.

A symmetry that answers the wrong player costs the idea. Nothing is repairable, because there was never a strategy to repair; the map is a symmetry of the board and not of the game.

Two conditions a reader would add, and should not #

Two plausible extra requirements turn out to be false, and both are worth ruling out because a general statement that carried them would be wrong.

The symmetry does not have to be geometric. Nothing above uses the fact that a half-turn is a rotation. All that is used is that it is an involution on positions carrying one player’s moves to the other’s, and a map with no picture attached would do. The half-turn is convenient because a reader can see it, and being seeable is not part of the argument.

The game does not have to be impartial. Three of the seven rows are partizan, and the two that fail on Toads and Frogs and on Clobber fail for the independence reason rather than because the game has two kinds of move. A partizan pairing is exactly the one that has to swap the players as well as the positions — which is what the negation does, and it is the natural case rather than the exotic one.

What is required, and does not appear in the three conditions as usually stated, is the independence clause. It is easy to leave out because on the game the argument is normally taught with it holds by construction: a board of squares splits into two halves that do not interact, and nobody has to say so.

What the census does not settle #

The boards are rectangles up to four by five and the symmetry tested is the half-turn. A reflection in a horizontal or vertical axis is a different involution and would give a different table; nothing here says that the half-turn is the best symmetry available for a given board, only what it does.

The four non-Cram games are tested on one position each. That is enough to refute — a symmetry that fails on one board is not a general strategy — and it is not enough to say anything about the family. A larger Toads and Frogs strip might have a symmetric position where the halves are independent, and nothing here has looked.

And the strategy tested is the pure one: restore the symmetry, every move, with no exceptions. A hybrid — pair until the symmetry breaks, then search — is what a real solver does, and how much of a board’s tree that saves is a measurement this page does not make.

The convention, named #

Normal play throughout: the player unable to move loses, which is what makes “the answer is always available” a winning argument. Under misère play the same strategy is a losing one, because the player who always has an answer is the player who makes the last move — and every pairing argument on this page inverts.

That inversion is unusually clean and is worth carrying. Most of what misère play destroys it destroys by making a theory inapplicable; here it leaves the strategy perfectly valid and simply reverses who wants it.

Where the ladder goes next #

pairing opens here with the conditions stated, the fixed points classified, and one instrument pointed at seven candidate symmetries.

The rung above is the search for symmetries rather than the testing of given ones. 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 rather than checking ones somebody proposed.

Beyond that is the hybrid: a solver that pairs while it can and searches when it cannot. The Cram table above says the pairing settles three of the twelve playable boards outright; what it saves on the other nine, used as far as it goes, is the number a solver author would want.

Two neighbours are worth the trip. Cram is where the strategy is used on the game it was named for, and where the boards it does not reach are recorded as open. And the theorem that names a winner and no move is the opposite kind of argument — a proof that somebody wins with no strategy attached at all — and a pairing is the cheapest possible answer to it.