The margin a count needs

Domination deletes an option no player would choose, and which option the reduction keeps asked what a surviving option looks like on a board rather than in a day of the construction. Two readings were scored: takes the most room and leaves the opponent fewest replies. The second names only survivors on nine lists in ten and the first on under half.

That page closed by naming what a proper statement would take:

The argument that Right’s mobility governs the order is a paragraph about the difference game; making it a statement means bounding the comparison by a count of the opponent’s moves, and the 161 failures are the data that would say what the bound has to be weakened to.

The weakening is a margin, and it is three.

The census #

Every position of eight Domineering boards, from 2×2 up to 3×5 and 2×6. Every position with two or more Left placements available, which is 14,244 option lists. Every pair of options in each list, which is 57,879 pairs.

For each pair: how many replies each option leaves Right, and how the two compare in the order — one better, one worse, equal, or confused.

The pairs are unordered and the four relations are kept apart, and both of those are load-bearing. At a margin of nought, more than half the pairs are the same value; counting an equality as agreement would make every column look like a success and the whole table meaningless.

The margin #

Sorted by the size of the mobility difference:

• A margin of one. The option leaving the opponent fewer replies is better on 19,316 pairs and worse on 1,052.
• A margin of two. Better on 9,734, worse on 72.
• A margin of three. Better on 1,584, worse on none.
• A margin of four. Better on 140, worse on none.

So the count does not bound the comparison and it does bound the direction of it. At a margin of three the option leaving fewer replies is better or confused with the other, and it is confused on 8 of the 1,596 pairs at that margin.

The census asserts both halves. A pair above the threshold in which the count went the wrong way would destroy the finding; a census with no failures at any margin would mean the count settles the comparison outright and there is no threshold to find.

The shape of the table #

Two features of the census deserve reading before the threshold, because they are what make the threshold legible.

The pairs are wildly unequally distributed. Eighteen thousand at a margin of nought, twenty-seven thousand at one, ten thousand at two, sixteen hundred at three and a hundred and forty at four. A large mobility gap between two options of the same position is rare, because the options are placements on one board and a domino changes the opponent’s count by a little.

And the equal column collapses as the margin grows. Half the pairs at margin nought are the same value; at margin two it is one in twenty; at margin three it is four pairs out of 1,596. That is the count doing exactly what it should: options that leave the opponent very different numbers of replies are very rarely worth the same.

Those two together are why the threshold sits where it does rather than being an artefact. The rows above it are small because large margins are rare, not because the census stopped looking, and the equality column shows the count separating values rather than merely correlating with them.

What a bound on the direction is worth #

It is worth distinguishing this from the kind of bound this site usually produces, because it is a different shape and a rarer one.

A rule that is never right and cannot be far wrong is the standard shape: a reading gives a number, the number is wrong, and the error is bounded. That bound is about size.

This one is about sign. It does not say how much better the option leaving fewer replies is; it says that it is not worse. And for the purpose the reduction is actually put to, sign is the whole question — domination deletes an option because another is at least as good, so a rule guaranteeing the direction is a rule that can be acted on.

A player with a margin of three can delete without comparing. That is a real saving: the comparison is a search over a difference game and the count is two flood fills.

Where two is not enough #

Seventy-two pairs sit at a margin of two with the count pointing the wrong way, and they are what stops the threshold being lower.

They share a shape once looked at. The option leaving the opponent more replies leaves them in a configuration Right cannot turn into anything — a scatter of separated squares, or a region already committed to a value — while the option leaving fewer leaves a smaller number of much better ones.

A count cannot see that, because a count is a count. The rung below’s finding that the reading scores nine in ten is the same fact from the other end: the reading is right nearly always because mobility usually does track the order, and it is wrong when the quality of the replies diverges from their number.

That divergence needs room to happen in, which is why it stops at a margin of three. Two replies of very different quality can outweigh four of similar quality; five cannot outweigh eight, because five moves that are all useless is not a position a domino leaves behind. The threshold is where the possible variation in quality stops being able to cover the variation in number — and stated that way it is a fact about how much a Domineering position can differ from itself, rather than about the order at all.

The seventy-two are also not spread at all. Every one of them is on the 3×5 board — the largest in the census — and the other seven boards produce none. That is the shortage of room seen from the other side: a 2×4 or a 3×3 does not have space for two options to leave the opponent counts two apart and leave them in shapes of very different quality.

It also means the threshold rests on one board. Seven of the eight would put it at two, and the eighth puts it at three, which is exactly the pattern a threshold has when it is real and the small cases have not caught up — and exactly the pattern a coincidence has when a single board is unusual. The nine-board corroboration in the next section is what separates those two readings, and it comes down on the first: adding a 4×4 board adds failures at margins one and two and none at three.

Why three and not four #

The threshold is the smallest margin with no failure, and there is a question about how much the data can support.

At a margin of three there are 1,596 pairs; at four there are 140. Those are small populations beside the 27,220 at margin one, and a threshold read off a small population is a threshold that could move.

Two things make it more solid than the raw count suggests. The failures thin out fast and smoothly — 1,052, then 72, then none — so the trend is doing the work rather than the last row alone. And the same census run over nine boards rather than eight, with a 4×4 added, gives 209,431 pairs, 6,408 of them at a margin of three or more, and still no failure.

That last check is not the census this page reports, because a 4×4 board is five times the work of the other eight together. It is a corroboration and it is worth recording as one.

It also settles the worry raised above. If the threshold of three were an artefact of the 3×5 board being unusual, a second large board would be the place it would show — and the 4×4 produces plenty of failures at margins one and two and not one at three. Two large boards agreeing is not a proof and it is the difference between a threshold and a coincidence.

What it says about the reduction #

The practical consequence is a shortcut with a precondition, which is the useful kind.

Computing a canonical form means comparing every pair of options, and comparison is the expensive half — the whole of the value-cost ladder is about how much dearer it is than deciding a winner, and the values of every small board is where that cost is paid on the boards this census uses. A rule that settles some pairs by counting is a rule that removes those comparisons.

How many? At a margin of three or more, 1,736 pairs of the 57,879 — three per cent. That is a small saving and it is an exact one, which is the trade this site keeps finding: a heuristic that is right nine times in ten covers everything and can be trusted nowhere, and a rule that covers three per cent can be trusted absolutely.

The other reading, for comparison #

The rung below scored two readings and this page has given a margin to the better one. It is worth asking what happens to the other.

Takes the most room — the option leaving Left the most placements — scores under half on the rung below’s test, which is what a description with no content scores on short lists. Giving it a margin does not rescue it: room and the order are related only through the value, and the value is what the count is trying not to compute.

The asymmetry between the two readings is the finding of the rung below and it survives the margin. One count is about the opponent and one about the player, and the one about the opponent is the one that governs — which is exactly what the difference game says it should be. $G \ge H$ is decided by whether Right can win $G - H$ moving first, so Right’s mobility in $G$ is the quantity in the question and Left’s is not.

That argument is the paragraph the rung below called a paragraph, and this page has not turned it into a proof either. What it has done is bound how far the paragraph can be trusted: three replies.

What the census does not say #

Four limits.

One game, and small boards. Eight rectangles up to 3×5. Whether the threshold is three on a larger board, or on a game whose moves are not dominoes, is the same census run somewhere else.

Left’s options only. Right’s are the reflection and give the same numbers by symmetry, which is why they are not run — and that symmetry is a property of Domineering rather than of games.

The threshold is the smallest margin with no failure in this data. It is not proved and it is not a theorem; what makes it more than an observation is the shape of the decline, and a census over a still larger board could in principle produce a failure at three.

The threshold rests on one board in eight. Every failure at a margin of two is on the 3×5, so seven of the eight boards would have supported a threshold of two. That is stated in the body and is worth repeating as a limit: what makes three the answer is one board and one corroboration, and the canonical form it is about does not care how large the board is.

And confusion is allowed. Never worse permits confused, and eight pairs above the threshold are confused. A player deleting on the strength of the count is therefore deleting an option that might be incomparable with the one kept, which is a legitimate deletion only if the kept option is genuinely at least as good — so the rule as stated licenses less than it appears to.

A rule that is right nine times in ten, made into one that is never wrong #

The move from a rule to a margin is the useful pattern here and it is worth stating generally, because it converts an unusable accuracy into a usable guarantee.

A rule right nine times in ten cannot be used on a single case. There is no way to tell which case is in hand, so every application is a gamble and nothing can be built on top of it — a chain of two such applications is right four times in five, and a search using it is wrong wherever it matters most.

A margin turns the same measurement into a bound. Instead of asking is the rule right?, ask how large must the gap be before the rule has never been wrong? — and then apply the rule only when the gap is at least that large. What comes out is a rule that answers less often and, on the answers it gives, has no counterexample in the census.

That is the same trade an interval makes and it is worth making for the same reason. An answer that can be wrong cannot be composed; an answer that declines can. A margin is silence chosen by the data rather than by the author, which is what makes the resulting accuracy honest rather than tuned.

And the margin itself is the interesting number. Three says how much slack the rule needs to be safe, which is a measure of how coarse the count is as a proxy for the value — and a rule needing a margin of one would be nearly exact while a rule needing ten would be nearly useless. Reporting the accuracy alone throws that number away.

Confusion, which is the awkward column #

The one place the rule as stated licenses less than it appears to is worth its own section, because it is the difference between a usable shortcut and a plausible one.

Domination deletes on at least as good, not on not worse. An option that is confused with another is incomparable to it, and neither may be deleted — that is what confusion means and it is why the order is partial.

The rule this page establishes says the option leaving fewer replies is never worse. Eight pairs above the threshold are confused, so on those eight the rule is true and licenses nothing.

That is a rate of one in two hundred, and it is the honest form of the shortcut: at a margin of three, either the option leaving fewer replies dominates the other or the two are incomparable, and the count cannot tell which. A program using the rule would still have to compare on those eight — or, more practically, would use the rule to order its comparisons rather than to skip them, which costs nothing and is never wrong.

The convention, named #

Normal play, Left placing vertical dominoes and Right horizontal.

A reply count is the number of legal Right placements on the position left after a Left move — a count over the board, computed without evaluating anything.

The margin of a pair is the absolute difference between their two reply counts. The relations are the four the order supplies: better, worse, equal and confused, computed by comparison rather than read off a value.

A pair is unordered: each pair of options appears once, and the attribution of better is made to whichever of the two leaves the opponent fewer replies. At a margin of nought there is no such option and the pair is recorded as comparable or confused without attribution.

Where the ladder goes next #

The dominance anchor has four rungs: what deleting removes, what decides how much, what a survivor looks like on a board, and now how large a mobility gap has to be before it decides the comparison.

The rung above is the quality of the replies. The seventy-two failures at a margin of two all have the same shape — the option leaving more replies leaves them useless — and turning useless into a count is the piece of work: replies weighted by whether they in turn leave the opponent anything, which is one more ply of the same measurement. If a weighted count has a threshold of one, it would replace this page’s rule with a much better one, and if it has no threshold at all that is worth knowing too.

Two neighbours are worth the trip. How rare it is to be bigger is where the four relations are counted over values, and it is the reason confusion has to be kept in a column of its own here. And a rule that is never right and cannot be far wrong is the shape of bound this site usually finds, which this page’s is not — and the contrast between a bound on a size and a bound on a sign is the thing worth carrying off.