Half the difference in odd runs

The domineering ladder has been carrying a reading for three rungs: count the dominoes each player could still place, subtract, and call the difference what the region is worth. Counting the moves each side has scored it, the moves a player can be talked out of replaced the number by an interval, and two errors that cancel added the interval across a whole board and found it holding the value three quarters of the time.

That page closed on the quarter it does not:

The rung above is the shape of the failures. A quarter of boards fall outside the band … so the reading fails on a class of regions rather than on random ones, and nobody has looked at which … what do the shapes with the largest errors have in common, and is it something a player could see?

The class turns out to be picked out by the reading itself — and before that, the reading turns out to be something much simpler than a packing search.

The count is a count of odd runs #

Call a run a maximal line of cells inside the region, taken across or down. The vertical adjacencies of a region are exactly its vertical runs and nothing else — a Left domino sits on two cells of one column with nothing between them — so the largest vertical packing is the sum of $\lfloor \ell/2 \rfloor$ over the vertical runs, and every odd run contributes exactly one wasted cell. Hence

$$\text{Left's optimistic packing} = \frac{\text{cells} - \text{odd vertical runs}}{2},$$

and the same with the words swapped for Right. Subtracting, the count a player reads is

$$\text{count} = \frac{(\text{odd horizontal runs}) - (\text{odd vertical runs})}{2}.$$

Checked against the census’s packings on all 1,042 shapes of the catalogue, with no exception. The maximum-packing search two rungs of this ladder have been running is not needed: the reading is a matter of looking at a region and counting its odd lines, which takes about as long as reading a phone number.

That already answers half of the rung below’s question. Is it something a player could see? — the count is, exactly, and it always was; nobody had written it down.

Never out by more than a move #

The errors are $0$, $\pm 1/4$, $\pm 1/2$ and $\pm 1$, and nothing else occurs. A hundred and forty-one of the 315 regions are read exactly and no region is misread by more than a single move — which is a stronger statement about the reading than any of the three rungs below made, and it is the reason the reading survives being added across a board at all.

The table is exactly symmetric, and the reason is worth naming so that nobody reads it as a finding: the catalogue holds every shape beside its transpose, and transposing a region negates both its value and its count. So each error of $+1/2$ has a mirror at $-1/2$ by construction. What is not by construction is that the same seven values occur and no eighth.

The class is the reading’s own magnitude #

Sorting the 315 regions by what the count says rather than by anything about their shape gives the class the rung below was looking for:

• when the count says one move, it is exact on 70 per cent of the regions, and on 78 of the 86 eight-square ones;
• when it says nothing at all, it is exact on 31 per cent;
• when it says two moves, it is exact on 7 per cent, and on none of the 42 eight-square regions where it says two.

So the reading is at its best in the middle of its range and worst at the top of it. That is not the shape an approximation usually has and it is a genuinely useful thing for a player to know, because it costs nothing to apply: a region the count reads as one move is a region to trust it about, and a region it reads as two is a region to evaluate.

The count-of-nothing case is a different failure and deserves separating. A count of nought is the reading declining to say anything, and 121 regions get it; a third of them really are worth nought, and the rest are worth up to a whole move in one direction or the other. That is not the reading being wrong so much as being silent, and a player who treats silence as a claim of equality is reading more into it than it says.

Why the strips are exact, and what that says #

Fifteen of the 315 regions are single lines — a row or a column of cells and nothing else — and the count is exact on every one of them. That is not a coincidence and the closed form says why in a line.

A single row of $n$ cells has one horizontal run, of length $n$, and $n$ vertical runs of length one each. So the odd vertical runs number $n$ and the odd horizontal runs number $n \bmod 2$, and the count is $((n \bmod 2) - n)/2$, which is $-\lfloor n/2 \rfloor$: exactly Right’s largest packing, negated, with nothing for Left. And that is the value, because Left has no move at all and the position is the integer $-\lfloor n/2 \rfloor$ outright — the strip where every number is a whole one is where that class is set out.

So the reading is exact on strips for the reason it is a reading at all: there is nothing for either player to interfere with. Every failure in the census is a failure of interference, and the two extremes of the population — a strip where nobody can interfere and a long even run where everybody can — sit at opposite ends of how much the count should be believed.

And when it is wrong, it exaggerates #

Of the ninety regions where the count is non-zero and inexact, 72 are further from nought than the value and 18 are nearer. Four times in five, the reading over-states.

That is what its own construction should have predicted and what none of the three rungs below measured. maxPacking is optimistic by definition — it assumes every slot a player could use survives — and a real game breaks slots, which is exactly why the moves a player can be talked out of replaced the number by an interval whose lower end assumes every avoidable waste happens. Two optimistic counts subtracted do not cancel their optimism, because they are optimistic about different players in different directions.

It also explains why the interval is worth carrying and the point is not. The interval’s lower end is built to be pessimistic for its owner, so the pair brackets the truth from both sides; the point sits at the optimistic end of that bracket and inherits the bias. A player who wants one number rather than two should take the count and shade it toward nought — which is a repair the ladder has not tried, and the third figure above says how much it would be worth.

Why the loud regions are the hard ones #

The shape in the last figure is a good instance of the whole class. It is a long horizontal run of seven with one square hanging below the end of it, which makes two odd runs across and six down — hence a count of $-2$ — and it is worth $-5/2$.

The long run is where the reading goes wrong, and the mechanism is one sentence. A run of even length is read as pure profit for the player who plays along it, because $\lfloor \ell/2 \rfloor = \ell/2$ and nothing is wasted; the count charges nothing for the fact that the opponent can spend a move in the middle of it and cut it into two odd pieces. On a short run there is nowhere useful to cut. On a run of seven or eight there are several, and a region large enough for the count to claim two moves of advantage is very nearly always a region with a long run in it.

Which gives the mechanism its own testable form, and it is a form the ladder can use: the count exaggerates in proportion to how much of the region is in long even runs, because that is the part of its arithmetic that assumes an opponent will not interfere. That claim is not tested here — what is tested is the correlate, which is that the count is wrong when it is large — and the two would come apart on a region with a long run and a compensating shape elsewhere.

What the closed form costs to have #

It is worth being clear about what has been gained, because “the count has a formula” can be read as more than it is.

Nothing about the reading’s accuracy changed. The 141 exact regions were exact before this page and are exact after it; the identity is a statement about how the count is computed, not about how good it is. What changed is the price. Two rungs of this ladder computed the count with a maximum-matching search over the region’s adjacency graph, which is polynomial and is still a search, and a player at a board cannot run one. Counting the lines of odd length in a region is something a person does by looking.

That matters more than it sounds, because the whole justification for the packing reading is that it is cheap. What is at stake in a region is exactly computable by the recursion, and the recursion is the correct answer; the reading exists only because the recursion is out of reach at a board. A cheap-in-theory reading that needs a matching algorithm is not cheap where it is wanted. A count of odd lines is.

And it makes the reading’s failures inspectable in the same currency. When the count is wrong on a region, the question why now has a shape — which run did the arithmetic charge nothing for — rather than being a discrepancy between two opaque numbers. The last two sections are both instances of that, and neither would have been available while the count was the output of a search.

Why odd runs, and what an even one contributes #

The formula counts odd runs and ignores even ones, and the reason is worth a paragraph because it makes the rule memorable rather than arbitrary.

A run of $\\ell$ free cells in one direction holds $\\lfloor \\ell/2 \\rfloor$ dominoes of that orientation packed end to end. For an even run that is exactly $\\ell/2$ and the run is used completely — no cell is wasted, and the two players’ counts over that run differ by exactly what the lengths differ by. An even run is fully spent by whichever player it belongs to, so it contributes to both packings in the same proportion and cancels out of the difference.

An odd run leaves one cell over. That leftover cell is what the other player can use, and it is where the asymmetry between the two packings comes from — so the difference between the two players’ largest packings is a count of leftovers, which is a count of odd runs.

Half the difference then follows from the leftover being worth half a domino to each side rather than a whole one, which is why the formula divides.

That reading also predicts the error profile this page measures. The formula is a count of leftovers and says nothing about whether a leftover can actually be used — a stranded cell in a corner is counted the same as one adjacent to open space — so the count is optimistic, which is what exaggerates four times in five when it is wrong records. And it explains the failure on large regions claiming two moves of advantage: two leftovers being simultaneously usable is a much stronger claim than one, and the geometry has more ways to refuse it.

What this does not say #

It is a class, not a criterion. The count says two picks out 42 eight-square regions and is wrong on all of them, and it also leaves 16 of the 80 count-nothing regions wrong with nothing to warn a player. The reading’s magnitude sorts the population usefully; it does not partition it into the right ones and the wrong ones.

The identity is about the optimistic packing only. minMaximalPacking, the pessimistic end of the interval, has no such closed form here and is still computed by search. It is a minimum maximal matching, which is a harder object than a maximum matching, and finding its run formula — if it has one — would make the whole interval readable off the drawing and is the obvious thing to want.

Regions of at most eight squares, as everywhere on this ladder. The count-says-two class is small and entirely eight-square, so the finding is being read at the very edge of the catalogue, and what the count says three or four about is six regions in total.

And a number-valued region only. The 315 are the regions worth numbers; the other 727 are hot, and for those the ladder compares the count to the stops rather than to a value. Whether the magnitude rule holds there is the same filter over data already in hand and was not run.

The convention, named #

Normal play throughout. Left plays vertically, Right horizontally, and a player who cannot place loses.

A region is a connected set of free squares, four-connected; the catalogue is every such region of at most eight squares up to the symmetries of the square, which is 1,042 of them.

A run is a maximal line of cells of the region, taken along a row or along a column. A single isolated cell is a run of length one in both directions and is counted in both.

The optimistic packing for a player is the largest number of that player’s dominoes that fit at once, and the count is Left’s less Right’s. The band is the pessimistic count for one player against the optimistic count for the other, in both directions, which is the interval the moves a player can be talked out of established.

The error is the count less the value, signed, so a positive error means the count claims more for Left than the region carries. Exaggerates means further from nought than the value, which is a statement about magnitude and not about sign, and it is undefined when the count is nought — those 121 regions are excluded from that figure rather than counted as neither.

Where the ladder goes next #

The domineering anchor reaches eight rungs to here, and this one has given the optimistic end of the packing interval a closed form. The rung above gives the other end, and it is not the formula the symmetry suggests.

Having found the largest packing in the odd runs, the natural expectation is the smallest maximal packing in the even ones. One domino every three cells finds parity to be the wrong arithmetic entirely: the smallest maximal packing is $\sum \lceil (\ell - 1)/3 \rceil$ over the runs, exact on all 1,042 shapes. That is a rule about spacing rather than about parity — a maximal packing must leave no two adjacent free cells, so it places a domino roughly every three cells whatever the run’s parity.

With both ends in closed form the whole interval is readable off a drawing: count the runs, apply two formulas, and a board of several regions is bracketed by two sums with no evaluation anywhere.

And the same rung closes the ladder honestly rather than by running out of ideas. Regions with the same runs have different values, so a reading built entirely out of run lengths can never reach the value however sharp either end becomes. The interval is a genuine bracket with a floor on its own width, and the floor is a theorem rather than a limitation of the two formulas.