A check in front of a search

A pairing strategy wins a game without evaluating it: match the opponent’s every move with a reply, and the reply is always available, so the opponent runs out first. The symmetry one move away asked which positions are one move short of such a strategy and found 288 of the 767 even first-player shapes in the catalogue to be.

It closed by naming the solver the finding makes 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 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.

The saving on a whole board is nearly total, and the reason it is total is not the reason anybody would hope.

What the check is #

At each position the solver looks at every domino it could place and asks one question of what would be left: does a half-turn about the centre pair every remaining square with a different one? If it does, the mover plays that domino and then answers every reply with its half-turn image, which is always free — so the position is a win and no search is needed.

The test is a single pass over the free squares: build the map $(r, c) \mapsto (R - r, C - c)$ about the centre of their bounding box, and check that every square’s image is present and is not itself. It costs nothing beside a recursion.

It is one-sided, and that is what makes it usable in front of a search. A position that passes the test is a win, proved; a position that fails it is unknown, and the search runs as it would have anyway. So the check can never give a wrong answer — it can only fail to give one — which is the property a filter needs before it can be trusted to short-circuit anything.

What it saves #

On a 4 × 5 board the plain solver expands 17,348 positions and the hybrid expands one — because the check fires at the opening position itself. The same happens on 3 × 4 and 2 × 7. On 4 × 4 it fires 24 times and the search stops at 25 nodes against 3,112.

That looks like a triumph and the depth profile says what it really is.

The check fires on the opening position itself. That is why the whole-board number is one node: the root is settled before any recursion starts, and the enormous saving is a saving on a search that never begins.

Through the middle game the picture is quite different: 38 per cent of winning positions at one domino placed, 12 at two, 12 at three, 4 at four, 12 at five, 6 at six. Then it climbs again — 50 per cent at seven, 100 at eight — as the board empties and the surviving squares are few enough to be symmetric by accident.

So the answer to how deep does it keep paying is: it does not. It pays at the two ends of a game and hardly at all between them, and the shape of the curve is a U rather than the decay a reader would predict — symmetry is not something a game slowly loses, it is something a game has at its tidiest moments and lacks in between.

Played positions against catalogued shapes #

The rung below’s figure is 38 per cent — 288 of 767 even first-player shapes with a pairing one move away. A played board never sees that number for long. It sees 100 per cent at the opening, about 10 in the middle, and 100 again at the end.

So the catalogue’s average is an average over a population no game passes through. That is not a criticism of the catalogue, which was answering a different question; it is the reason a rate measured on a catalogue cannot be quoted as a rate a solver will experience, and this site has now made the same correction twice — once for temperatures and once here.

The middle-game dip has a plain explanation. An opening position is symmetric because a rectangle is symmetric; an endgame position is symmetric because two or four squares have few ways not to be. In between, a board has been cut about by seven or eight dominoes placed in no particular pattern, and a half-turn is a strong condition to ask of it.

There is a second reading of the dip, and it is about what the check is for. A pairing argument is a way of proving a win without knowing anything about values, and it works when a position has structure a person can see. The middle game is where a Cram position has least structure — the board is neither a rectangle nor a handful of squares — so the check failing there is the same fact as a person finding the middle game hard.

That is worth saying because it is the honest limit of every argument of this kind. Strategy stealing and pairing both prove wins from symmetry, and both are most available exactly where a search is cheapest — at the start, where the board is regular, and at the end, where it is small.

Parity decides in advance #

The check never fires on a board with an odd number of squares. That is parity rather than luck: a fixed-point-free half-turn pairs the squares two by two, so it needs an even number of them, and every Cram move removes exactly two squares — so an odd board is odd after every move that will ever be made on it.

That makes the check’s usefulness a property of the board rather than of the position. A solver can decide before its first node whether the test is worth running at all: on an even board it is decisive at once, on an odd board it is dead weight, and the deciding is a multiplication.

The 3 × 5 row in the table is the whole of that: 481 nodes with the check and 481 without, and the check consulted at every one of them for nothing.

What a solver should actually do with it #

Three practical readings, and the third is the useful one.

Run the check at the root, always. On an even board it settles the game outright a large share of the time, at the price of one pass over the dominoes, and no measurement is needed to justify a cost that small against a search of seventeen thousand nodes.

Do not run it at every node. In the middle game it fires on one winning position in ten, which means nine tenths of the calls are wasted, and the calls are not free — each is a pass over the free squares for every available move. On the boards here the hybrid is faster anyway because it stops at the root; on a board where it did not, the middle-game calls would be a tax.

Run it again near the end. The share climbs back to 100 per cent in the last two moves, and a solver deep in a game is exactly where node counts matter. A depth-conditioned check — on at the root, off in the middle, on in the endgame — is what the profile actually recommends, and it is a policy nobody would have guessed from the catalogue figure.

A check that can only say one of two things #

The check has an asymmetry worth stating plainly, because it decides where a solver should put it and the rungs above turn on getting that wrong.

A pairing argument establishes that the player to move loses. It never establishes that they win, and it cannot: the argument is a strategy for the second player, so a position where it applies is a second-player win and a position where it does not apply is a position the argument has nothing to say about. So the check is one-sided — it either returns lost or returns no answer, and no answer is by far the commoner reply.

That shape is what makes it a filter in front of a search rather than a substitute for one. A two-sided test could replace the search on the positions it settles; a one-sided one can only skip a subtree when it fires, and every time it does not fire the search runs anyway and the test was pure cost.

And it is exactly the shape that makes soundness matter more than reach. A one-sided check that is right when it fires is worth whatever it saves and nothing worse. A one-sided check that is wrong when it fires does not merely waste time: it returns lost for a position that is won, and the wrong answer propagates up through every parent that trusted it. There is no partial credit, because the check’s whole contribution is the subtree it stopped anybody looking at.

So the two things a reader should want measured about a check like this are how often it fires and whether it is ever wrong, and only the first is what a performance figure reports. The second is the one that decides whether the check may be used anywhere below the root at all.

What the check costs when it fails #

The one number the whole-board table hides is the price of asking.

Each call examines every available move and, for each, walks the free squares once. On a twenty-square board early in the game that is about thirty moves and twenty squares each — six hundred operations to answer one question, against a node expansion which is a handful. So the check is worth perhaps a hundred nodes, and the profile says it returns a win on one call in ten through the middle game.

That arithmetic is why the depth-conditioned policy is the right one rather than a refinement. A check that fires one time in ten and costs a hundred nodes is worth running only where a node is dear, which is deep in a search, and where the fire rate is high, which is at the ends. The two conditions coincide at the endgame and disagree in the middle, and the middle is where a naive implementation spends all its time.

What this does not say #

Four limits.

Cram only. The pairing here is a half-turn, which works because Cram is impartial and a domino’s image under a half-turn is a domino. In a partizan placement game — Domineering — the image of a vertical domino is a vertical domino, so the same argument gives the second player nothing and a different pairing is needed.

One symmetry. Only the half-turn is tested. A reflection pairing exists for some boards and would fire on positions this check misses, at the cost of another pass. Nothing here prices that.

The comparison is against a plain solver, not a good one. A real Cram program reduces positions by the board’s symmetries and by splitting the board into independent regions, and both of those would cut the plain solver’s 17,348 nodes a long way before the pairing check was consulted. What the check adds on top of those is the number an implementer would want, and it is not measured here.

Small boards. The largest board solved both ways is 4 × 5, twenty squares, because the plain solver has to finish for the comparison to exist. What the check does on a board the plain solver cannot finish is the interesting engineering question and it is not measured here.

And the node counts are not times. A node expansion and a pairing test are different units, and the hybrid’s one node hides five pairing tests at the root. On these boards the comparison is not close enough for the units to matter; on a board where the check fired rarely it would be the whole question.

Who steals strategies #

Pairing arguments are the oldest trick in the subject and they predate the theory by decades. The Tweedledum-and-Tweedledee argument — copy the opponent’s move in the mirror component — is the standard example in Winning Ways, and it settles a whole family of games without any value being computed.

What is unusual about Cram is that the pairing is available on the whole board rather than between two copies of a component: an even Cram board is its own mirror, so the second player can answer every move by its half-turn image and win outright. That is the strategy that is a symmetry, and it makes even rectangles a second-player win by an argument a child can follow.

This ladder’s contribution is to ask when the argument is one move away, which turns a theorem about special boards into a test any position can be given — and this page prices the test. The answer, that it is decisive at the root and scarce in the middle, is the kind of thing only a measurement says: from the argument alone, one would expect symmetry to be common in tidy positions and would have no way to guess how tidy a played position is.

The convention, named #

Normal play, Cram: both players place dominoes in either orientation, and the player who cannot place loses. The game is impartial, so a position is a win or a loss for the mover and nothing else.

A pairing here is a fixed-point-free half-turn about the centre of the free squares’ bounding box: every free square maps to a different free square, and the two form a domino only if they are adjacent — which the strategy does not require, since the reply is to the image square’s domino rather than to a fixed partner.

A position is settled by the check when some move leaves a position the half-turn pairs, which makes the mover a winner without further search. The check is one-sided: it proves wins and never proves losses.

Nodes are positions expanded, memoised on the occupancy mask, and the two solvers share the same memo discipline so the comparison is of search shape rather than of caching.

One more reading of the profile is worth keeping, because it generalises past Cram. A cheap proof of a win is available exactly where the position is regular, and a position is regular at the start of a game and at the end. So a filter of this kind is worth building for the moments a search is cheapest and worth switching off in the middle, which is the opposite of how a filter is usually deployed.

Where the ladder goes next #

The pairing anchor has four rungs to here, and the two above it both begin by finding something wrong with what this page proposes rather than with what it measures.

The check that was not a check sets out to build the depth-conditioned solver this page asks for and finds two things in the way. The pairing check is 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 that trusted it below the root would answer wrongly rather than slowly. And the board this page names as the one to measure on has twenty-five squares, so the check — which needs an even count — can never fire there at all.

Repaired, the check is right everywhere, and the policy that turns out to pay is the plainest one available: test at the root and nowhere else. That is the opposite of the rule decomposition follows, where testing at every node is free money, and the difference is that a flood fill cannot be wrong.

A pairing and the pairing then asks whether the other symmetry would fire where the half turn does not. It does — forty positions of 58,830 on the largest board — and it is sound, and it is worth about one node in a thousand to a solver. It also can never fire on an empty rectangle, which is the reason this whole anchor is about the half turn and mentions the reflection nowhere: the symmetry that pairs a board with itself is the one a rectangle has, and the other is a fact about positions rather than about shapes.