A pairing, and the pairing

The check that was not a check repaired the half-turn pairing test — a set of free squares can be closed under the half turn and still hold a domino the half turn maps to itself — and closed on the symmetry the ladder had never tried:

The rung above is the other pairings. The half turn is one symmetry and it is the only one this ladder has ever used; a reflection pairs a symmetric position too, and it has its own self-paired dominoes — the ones lying across the axis … it would say whether the ladder’s whole subject is the pairing or a pairing.

It is a pairing in principle and the pairing in practice, and the reason is structural.

The second predicate #

A reflection about a vertical axis sends $(r, c)$ to $(r, C - c)$, where $C$ is the sum of the extreme columns. The pairing strategy is the same: answer each move with its mirror image, and the player who left the position wins.

The two clauses are the same two clauses:

• no fixed square, or that square has no partner and no reply. For the half turn that is the centre of an odd region; for a reflection it is every square on the axis.
• no self-paired domino, or the reply to it is the move that was just made. For the half turn that is a domino straddling the centre; for a reflection it is a domino lying across the axis — a horizontal one for the vertical reflection.

The second clause is the one the rung below found missing from the half turn, and it has to be written again for each symmetry. It is not the same condition in different coordinates: the half turn’s self-paired dominoes sit at the centre and a reflection’s sit along a whole line.

It fires, soundly, and rarely #

Run both checks over every position a game of Cram can reach on six boards. The last column is nought everywhere: every firing of either check is a genuine loss for the player to move, so the reflection check is sound as written and needs no repair of its own.

It fires much less often. On the 4 × 5 — 58,830 reachable positions — the half turn settles 645 and the reflection settles 129. On the 2 × 7 it is 133 against 57.

And most of what it settles the half turn settles too. The positions only the reflection reaches are 40 on the 4 × 5, 10 on the 2 × 7, 4 on the 4 × 4, 2 on the 2 × 6 and none at all on the two smallest.

So the answer to the first half of the rung below’s question is yes, and the yes is small: 56 positions across six boards, against the half turn’s 1,127.

And it is worth almost nothing #

The second half of the question is what a solver carrying both would save, and the answer is twenty nodes.

Solving the 4 × 5 takes 17,348 node expansions with no check at all, 17,258 with the half turn in front, and 17,242 with both. On the 3 × 6 it is 3,857, 3,841 and 3,837. On the boards where the half turn collapses the whole search to a single node — the 4 × 4 and the 2 × 6, both losses at the root — it was already doing so, and the reflection changes nothing.

Across the six boards the second check saves 20 nodes of 21,212, which is one part in a thousand. The reflection check on its own is worse than useless in the same currency: it costs a predicate at every node and saves 32 nodes across all six.

Why it can never fire at the root #

The reason the reflection is worthless to a solver is not that it fires rarely. It is where it fires, and there is an argument for it.

A reflection about a vertical axis needs an even number of columns, or a whole column is fixed and every square in it has no partner. But with an even number of columns the two central columns are adjacent, so a horizontal domino lies across the axis and is its own mirror image — and the second clause refuses it.

So every empty rectangle fails one clause or the other, and the reflection check fires on none of the 28 tested. Sixteen of them reflect and are refused by the domino clause; the rest have an odd side and are refused by the fixed-square clause.

That matters because a pairing check is worth most at the root. A check in front of a search measured exactly this: the saving is the firing rate times the subtree pruned, and the subtree at the root is the whole search. A check that fires only at interior positions is a check that saves interior subtrees, and those are small.

The odd boards, and what parity forbids #

The 3 × 5 is fifteen squares, so every position reachable by play has an odd number of free squares, and neither check fires on any of its 3,054 positions.

That is parity rather than luck, and it rules out more than these two symmetries. A pairing of a set with an odd number of elements has a fixed point whatever the map is, and a fixed point is a square the strategy cannot answer a move in. So no pairing check of any kind can settle a position with an odd number of free squares, and an odd board stays odd however many dominoes are placed.

Which puts a ceiling on the whole programme that has nothing to do with which symmetry is chosen. Half the boards are out of reach before the question of symmetry arises.

A negative result, and why it is worth a rung #

Most of what this site reports is a measurement that came out one way rather than another. This one came out the way nobody would have bet against — a second symmetry adds a little and costs a little — and it is worth saying why that was not obvious in advance.

The rung below’s repair had just shown that the half-turn check fires on 8,613 positions of a 4 × 5 when run at interior positions, against a handful when run from the empty board. That is a factor of a thousand between where the ladder had been looking and where the check actually fires, and it made an interior-firing check look valuable. A reflection fires only at interior positions. Before the measurement, the reasonable expectation was that it would add something like a fifth of the half turn’s coverage and be worth carrying.

What it actually adds is 56 positions across six boards and 20 nodes of 21,212. And the reason the expectation was wrong is the one a check in front of a search had already isolated: firing often and saving much are different things, because a saving is a firing rate times a subtree size and subtree sizes vary by four orders of magnitude while firing rates vary by one.

So this rung is that finding applied to itself. The ladder learned once that where a check fires matters more than how often; the reflection is a check that fires in exactly the wrong place, and it is the cleanest possible demonstration of the lesson.

There is one thing the measurement does buy that a solver does not care about. The reflection check is a second certificate: a position it settles has a written strategy — mirror every move — that a reader can verify by hand, and 56 positions now have one that had none. Looking for the symmetry is where the ladder’s interest in certificates rather than verdicts is set out, and by that standard a rarely-firing sound check is worth exactly as much as a common one.

What the ladder’s subject turns out to be #

The rung below asked whether the ladder’s subject is the pairing or a pairing, and both answers are true in different senses, which is worth separating.

As a class of strategies, there are many. A reflection is one, a half turn is another, and every symmetry of the plane that preserves the domino shapes could supply one. All of them are sound with the two clauses written correctly.

As a useful check, there is one. The half turn is the symmetry an empty rectangle has and the reflection is not, so the half turn is the one that can fire where firing is worth a whole search. That is not a fact about the two maps; it is a fact about the positions a game starts from.

The general form is worth naming because the site keeps meeting it. A tool’s value is decided by the distribution of positions it will be shown, and a rectangle is a very particular distribution — the obstacle was the catalogue is the same lesson on a different ladder, where an evaluator’s difficulty turned out to be about which shapes a board produces rather than about size. Here the whole advantage of one symmetry over another is that games start on rectangles.

Where the forty sit #

The forty positions on the 4 × 5 that only the reflection settles are worth a sentence, because they are the whole of the finding’s positive content.

They are all deep — a reflection needs the free squares to be symmetric about a line, and a rectangle’s free squares become line-symmetric only after dominoes have been placed in a matching pair on the two sides. And they are all in the class the half turn refuses for the reason the rung below found: the cells are closed under the half turn as well, and a domino is invariant under it, so the half-turn check is correctly silent while the reflection’s own domino clause is satisfied.

That is a slightly delicate situation and it is the reason the two checks are not nested. A position can pass the reflection’s clauses and fail the half turn’s, or the other way round, and the two failures have different causes — one about the centre and one about an axis.

The symmetry one move away counted the shapes with a symmetric position one move away and found 288 of 767; the same count for a reflection has not been made here, and it is the cheapest extension of this page. What this page measured is the check at a position, not the check one move ahead of it, and the rung below’s own ladder shows the second is usually the larger number.

Why the reflection was never going to matter #

Forty firings in 58,830 is a small number and the interesting thing about it is not its size. It is that the positions where the reflection fires are positions that arise during play and never at the start.

A pairing strategy needs the board to be carried to itself by the symmetry. An empty rectangle is carried to itself by both reflections and by the half turn — but the reflection has a fixed line, a row or column of cells mapped to themselves, and cells on it cannot be paired with anything. The half turn on an even-celled rectangle has no fixed cells at all, so its matching is defined everywhere.

That is why one of the two is the anchor’s subject and the other appears nowhere. On the shapes anybody starts from, the reflection cannot supply a strategy and the half turn always can, and the difference is a fixed line rather than anything about how the two symmetries look.

The forty are positions where earlier moves have removed the fixed line — filled it, or split it away — leaving a reflection-symmetric shape with nothing on its axis. Those are reachable, they are rare, and they are exactly the configurations that cannot occur at a root.

So the finding is that the reflection is a play-time symmetry and the half turn is a design-time one. A solver testing both loses nothing and gains one node in a thousand; a reader learning the anchor loses nothing by never hearing about the reflection, which is why they have not.

What this does not say #

Six boards, none larger than twenty squares. The 4 × 5 is the largest, and the reflection’s contribution grows with the board across the six — 0, 2, 4, 10, 40 — so nothing here says it stays negligible on a 6 × 6. What it does say is that the growth would have to be very fast to matter, since it is competing with a search that grows faster.

Two reflections, not every symmetry. The vertical and horizontal reflections are tested; the two diagonal reflections of a square board are not, and neither are the quarter turns. A quarter turn maps a horizontal domino to a vertical one, which Cram allows and Domineering does not, so it is a legitimate candidate and it is untested.

This is Cram and not Domineering. A reflection sends a horizontal domino to a horizontal domino, which is fine in an impartial game where both players place both orientations. In Domineering the two players place different pieces, and a reflection strategy would answer a Left move with a Left move, which is not a reply at all.

And a check that never claims a win is not a check that finds them. Both predicates are sufficient conditions. Repaired, neither ever claims a win that is not there; both miss most wins, because a winning position usually has no symmetric arrangement of any kind. That was true of the half turn before this page and it is true of both now.

The convention, named #

Normal play throughout: a player who cannot place loses. Cram is Domineering with the partisanship removed — both players place dominoes either way up on the same board — so every position is a win or a loss outright.

A pairing of a set of free squares is a map sending each square to a different square, with the map its own inverse. The pairing strategy for the player who has just moved is to answer each move with its image, and it wins when every square is paired with a different square and no domino is its own image.

The half turn of a cell set is the map about the centre of its bounding box; a reflection is the map swapping columns about the vertical midline, or rows about the horizontal one. Both are computed from the bounding box of the free squares rather than of the board, so a position whose free squares sit in a corner is tested about the corner’s own centre.

A check fires at a position when the test accepts its free squares. A firing is wrong when the player to move can win, which the recursion decides exactly.

Node expansions count positions the solver evaluates for the first time; a memoised solver visits each once, so the count is the size of the position graph it has to build.

Where the ladder goes next #

The pairing anchor has six rungs: the strategy that is a symmetry, looking for the symmetry, the symmetry one move away, a check in front of a search, the check that was not a check, and now the other pairings.

The rung above is the quarter turn. It is the one symmetry not tested here and the only one that could plausibly beat the half turn at the root, because a square board has it and a square board is where Cram is usually played. A quarter turn sends a horizontal domino to a vertical one, so its self-paired dominoes are a different object again — there are none, since no domino is its own image under a ninety-degree rotation — and the fixed-square clause is the whole of it. Whether it fires on an empty square board, and what a solver carrying it saves, is one predicate and the same sweep.

Two neighbours are worth the trip. The strategy that is a symmetry is where the copying argument arrives, and it is the page that makes any of this a strategy rather than a coincidence. And a check in front of a search is where a check’s worth was priced as firing rate times subtree, and it is the formula this page’s negative result is an instance of.