The check that was not a check

A check in front of a search put a pairing test in front of a Cram solver — before recursing, look for a move that leaves the free squares symmetric under a half turn, and if there is one, declare a win. It measured what that saves and closed by asking for the policy the profile recommends:

The rung above is the depth-conditioned solver the profile recommends. The policy is stated here and not implemented: check at the root, skip the middle, check again once the free squares fall below some count. What that saves against always-check and never-check on a board large enough for the difference to matter — 5 × 5 Cram, say, at 25 squares — is a measurement with a definite answer and the machinery for it is now in place.

The machinery was not in place. Building the solver found out why.

The check is unsound #

Run the check at every node of a search and compare its verdicts against the recursion, and they disagree. On a 4 × 5 board the check fires on 8,613 of the 58,830 positions reachable by play, and 1,026 of those are losses — the check says the mover wins and the mover does not.

The proportions are similar on every even board swept: 19 per cent wrong on a 3 × 4, 14 on a 4 × 4, 16 on a 2 × 7, 12 on a 4 × 5. This is not a rare edge case. It is one firing in eight, on the game the whole anchor is about.

The missing clause is one line. The pairing strategy answers each opposing move with its half-turn image, which is a different domino on a different pair of squares — so it needs the image to exist and to be a legal move. A domino whose two cells are swapped by the half turn is its own image. The opponent plays it, and the reply the strategy prescribes is the move that has just been made.

Why nothing had caught it #

The check had never been asked a question it could get wrong.

The rung below ran it from empty boards. An empty rectangle has a domino invariant under its half turn only when the two cells at the centre of the rectangle are adjacent, and no board in that sweep has them — a 4 × 5 maps square 9 to square 10, which are the last cell of one row and the first of the next, and those are not neighbours. So on every position the check had ever been shown, it was exactly right.

Its own solver even carried the test that would have caught it: the hybrid solver asserts that its answer agrees with the plain search, and it does, on all five boards, because the check fires at the root and the root is one of the positions it is right about.

A check that fires once, correctly, at the top of a search is not a check that has been tested. The thing that found the fault was running it 58,830 times, which is what the depth-conditioned solver required and what nothing before had needed.

Repaired #

Adding the clause — no two cells swapped by the half turn may be adjacent — makes the check correct on every position of all five boards. It fires about a quarter less often, which is the honest price: 6,561 firings on the 4 × 5 against 8,613, and the 2,052 lost include the 1,026 that were wrong.

The site already had the clause. It decides the question for a whole rectangle and was written for the essay that introduced Cram’s pairing strategy; the general test on an arbitrary cell set never got it. That is the shape this fault usually has and the fleet’s own rule names it: a good local helper does not stay local, and a special case that was got right does not automatically reach the general one.

And the board was the wrong board #

The rung below named 5 × 5 as the board large enough for the policy question to matter. A 5 × 5 has 25 squares. A domino covers two, so the number of free squares stays odd for ever; a half turn with no fixed point pairs the free squares off; an odd number of things cannot be paired.

So the check can never fire on a 5 × 5, at any depth, under any policy — which the 3 × 5 in the sweep confirms directly, 3,054 positions and not one firing. The experiment as proposed would have measured the cost of a test that never succeeds, on a board where the answer is never check before any measurement is made.

Where the check is worth running #

With the repaired check, the policy question can finally be asked, and it has a clear answer.

Five policies were solved from the same positions with a fresh table each time, which is what a player’s solver would do, and every one returns the same answers.

• No check: 3,708 nodes.
• A check at every node: 128 nodes, 580 checks.
• A check in the first two plies: 158 nodes, 358 checks.
• A check once eight squares are left: 3,437 nodes and 10,380 checks.
• A check at both ends: identical to checking everywhere.

So the root check does nearly all the work — 158 nodes against 128 — for three fifths of the checks, and the endgame half of the rung below’s policy is the wasted half. Running the check only in the endgame barely reduces the search at all and runs eighteen times as many checks as the root policy, because there are enormously more nodes deep in a search than near its top and each of them pays for a test.

That inverts the reading the profile suggested. The profile said the check fires most often at the two ends of a game, and it does; what it did not say is that firing near the end of a search saves almost nothing, because the subtree below a nearly-empty board is tiny. A check is worth running where the subtree it prunes is large, which is at the top, and how often it fires there is almost beside the point.

Why the root is where a check belongs #

The policy result deserves an argument as well as a table, because it generalises past Cram and past pairings.

A search’s nodes are not evenly distributed. On a 4 × 4 board there is one position at depth nought, twenty-four at depth one, 215 at two, 912 at three, 1,911 at four. The tree widens for most of its height and then narrows again, and the great majority of its nodes are in the middle and lower parts.

A check run at a node costs one test per move and saves, if it fires, the whole subtree beneath. So its value is how often it fires times how big the subtree is, and those two quantities pull in opposite directions: the subtree is largest at the top and the firing rate is highest at the bottom. The product is dominated by the top, because subtree sizes vary by four orders of magnitude across a search and firing rates vary by one.

That is why the root policy wins and why it is not close. It is also why the profile in the rung below is a misleading guide on its own — a profile of firing rates answers where a check succeeds and not where it is worth trying, and the two questions have opposite answers here. When the catalogue starts paying is the other place on this site where a cheap test is priced against what it saves rather than against how often it works, and the two pages agree: a saving is a product, and the rate is the smaller factor.

What a false check costs #

It is worth separating the two things this page found, because only one of them is about pairing.

The unsoundness is a bug and it is now fixed. What it cost is measurable: the rung below’s depth profile counted firings that included the wrong ones, so its middle-game shares were too high — 26 of 26 at one domino placed on a 4 × 5 rather than 10 of 26, and 56 per cent at seven moves rather than 50. The page’s argument survives intact, since it was about the shape of the profile rather than about its exact heights, and its numbers have been corrected.

The lesson is the site’s standing one and this is a clean instance of it. An assertion that has never rejected anything proves nothing. The hybrid solver’s agreement check was a real assertion, correctly written, and it could not fail because the only position it ever examined was one the check was right about. What made the fault visible was widening the population — the same move that finds nearly everything on this site, and the one looking for the symmetry made when it stopped being handed a pairing and started searching for one — and the population that found it was 58,830 positions rather than five.

The two ways a strategy argument goes wrong #

The clause that was missing is worth generalising, because pairing arguments are common in this subject and both of their failure modes are on this page.

A pairing strategy says: whatever the opponent plays, the copier plays its image, so the copier always has a move and the opponent runs out first. For that to be a proof it needs two things — the image of a legal move must be legal, and it must be different from the move just made. The first is what the symmetry of the cells gives; the second is what the absence of a self-paired domino gives.

The strategy that is a symmetry is where this site sets the argument out in its clean form, on a board where neither condition can fail. Cram on an arbitrary set of free squares is where both can: a set that is not symmetric fails the first, and a set whose centre holds two adjacent squares fails the second.

The failure this page found is the second, and it is the easier one to lose because the first is the one the picture shows. A reader looking at a symmetric arrangement of free squares sees the symmetry; nothing in the picture says whether a domino sits across the centre. That is the whole of why a check written from the drawing was missing a clause about the moves.

Why the root is a different kind of place #

The policy that pays is test at the root and nowhere else, and it is worth saying why a root is special, because it is the reverse of the rule decomposition follows.

Decomposition’s test cannot be wrong. A flood fill either finds two components or it does not, and if it does they are independent by the rules. So the test is safe everywhere, it costs a linear pass, and running it at every node is free money.

A pairing check can be wrong, and this page is the measurement of how often. So its value at a node is not the subtree it saves but the subtree it saves times the probability the answer is right, and a wrong answer does not merely waste the node — it propagates a false verdict up through every parent that trusted it.

At the root those two considerations point the same way and the arithmetic is easy: one test, the largest possible subtree, and a verdict a caller can check. Below the root the subtree is small, the tests are many, and one wrong answer poisons everything above it.

So the asymmetry is about the ratio of payoff to exposure rather than about correctness. Even a sound check is worth running only where it saves enough to justify its own cost, and a check whose payoff shrinks as it descends while its exposure grows is a check with an optimum at the top.

That is the general form and it is worth carrying to any filter in front of a search. Ask what it saves and what it risks, and note that both change with depth — usually in opposite directions.

What this does not say #

Five boards. The soundness census covers 69,592 positions on boards up to twenty squares, and the repaired check is right on every one. That is a strong statement about small boards and it is not a proof — the argument for the clause is a strategy argument and it is written out above, which is stronger than the census, but the strategy argument is a sketch rather than an induction.

The policy comparison is one board. The five policies are compared on a 4 × 4, which is small enough for every policy to be run from many positions with a fresh table. A larger board would make the root check’s advantage larger, since the subtree it prunes grows and the endgame subtrees do not.

And the catalogue figure is unaffected. The rung two below counted 288 of 767 even first-player shapes with a symmetric position one move away, and that is what it says: a count of symmetry, restricted to shapes that are first-player wins anyway. What is not licensed is treating each of those as settled at no cost, since the copying strategy wins from only some of them.

The check is still only a sufficient condition. Repaired, it never claims a win that is not there; it also misses most wins, since a first-player win usually has no symmetric position one move away at all. That was true before and is true now, and it is the ordinary state of a strategy argument — a winning strategy that is a spanning tree is the other place on this site where a construction wins some positions and says nothing about the rest.

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 it is an impartial game and every position is a win or a loss outright.

A half-turn pairing of a set of free squares is the map about the centre of its bounding box. The pairing is a winning strategy for the player who left the position when every square is swapped with a different square and no domino is swapped with itself.

The check fires at a position when some move from it leaves a set of free squares the test accepts. A firing is wrong when the position is a loss, which the recursion decides exactly.

A position reachable by play is one some sequence of legal placements produces from the empty board, which is fewer than the occupancies: a set of covered squares that is not a union of dominoes never arises.

A policy says when the solver runs the check, as a function of the depth in the search and the free squares remaining. Nodes and checks are counted separately because a check is not free, and each policy is run with its own memoisation table.

Where the ladder goes next #

The pairing anchor has five rungs: the conditions a pairing has to satisfy, what an exhaustive search for one finds, what the same search finds one move later, what putting it in front of a solver is worth, and now that it could not be put there as it stood.

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. Whether a reflection check fires on positions the half-turn one misses, and how much a solver carrying both would save at the root, is the same measurement with a second predicate and it would say whether the ladder’s whole subject is the pairing or a pairing.

Two neighbours are worth the trip. The symmetry one move away is where the catalogue count comes from, and reading it beside this page separates a count of symmetric positions from a count of winnable ones. And a position reached eleven ways is one position is the other way a Cram search is made cheap, and the two are worth comparing: memoisation saves work on positions the search visits twice, and this check saves work at the one place a search has only one node.