One domino every three cells

Half the difference in odd runs gave the optimistic packing count exactly — $(\text{cells} - \text{odd runs})/2$ in each direction, so a player reads the count as half the difference between the odd horizontal and the odd vertical runs — and left the interval’s other end a search. It closed on that, with a prediction:

The rung above is the other end of the interval. The optimistic count has a closed form in odd runs; the pessimistic one is still a search … A minimum maximal packing is what remains when an opponent spends moves breaking slots, so the quantity it should be a formula in is not the odd runs but the even ones.

There is a closed form and it is not about even runs. It is about thirds.

The formula, and why thirds #

A minimum maximal packing is the smallest set of same-direction dominoes leaving no two free cells adjacent in that direction — the worst a player can be reduced to while the opponent spends moves spoiling slots. Vertical adjacency lives inside a vertical run and nowhere else, so the problem falls apart into one problem per run, exactly as the optimistic count does.

On a single run of $\ell$ cells the answer is $\lceil (\ell - 1)/3 \rceil$, and the reason is one sentence. A domino covers two cells and spoils the cell on each side of it, because a free cell next to a covered one has no free partner in that direction. So each domino accounts for three cells’ worth of run, and the run’s two ends give one cell back.

Summed over the runs, that is exact on all 1,042 shapes in the catalogue, in both directions, with no exception.

The rung below’s guess is scored on the same shapes as a control and reaches 115 of the 1,042. That is not a near miss; it is the wrong arithmetic. The optimistic count is about halves, because a domino covers two cells and the leftovers are the odd runs. The pessimistic count is about thirds, because a domino also wastes two. Parity had no reason to appear, and appeared in the guess because parity is what the rung below had just finished using.

The whole interval, off the drawing #

With both ends in closed form, the interval

$$[\,\text{pes}_V - \text{opt}_H,\ \ \text{opt}_V - \text{pes}_H\,]$$

is four counts a reader takes off the picture: in each direction, how many runs have odd length, and what $\lceil (\ell-1)/3 \rceil$ sums to over the runs. No packing search anywhere, and no game evaluation.

That completes a programme this anchor started four rungs ago. Counting the moves each side has proposed the difference of largest packings as a reading of a region and got it exact on 141 of 315; two errors that cancel turned the point into an interval; half the difference in odd runs made one end a look instead of a search. The interval is now a look at both ends, and a player with a pencil has as much as a program with a packing solver. A board that is a sum of its regions is what makes that worth having on a real board rather than on one region, since a whole game reduces to a sum of these readings.

The width is a sum over run lengths #

Subtracting the two formulas run by run, a run of $\ell$ cells contributes $\lfloor \ell/2 \rfloor - \lceil (\ell-1)/3 \rceil$ to the interval’s width. That quantity is nought at $\ell = 1, 2, 3$ and $5$, and positive at $4, 6, 7, 8$ and everything above.

Five is the one worth staring at. A run of four holds two dominoes at best and can be reduced to one — put a domino across the middle two cells and the two end cells are stranded. A run of five holds two either way: the best is two, and the smallest maximal packing is also two, because one domino cannot spoil five cells. So the sequence is not longer runs waste more; it is a genuinely arithmetic condition, and four is worse than five.

Which gives a criterion with no computation in it at all: a region’s interval is a single number exactly when every run in it, in both directions, has length one, two, three or five. That is right on all 1,042 shapes, and 505 of them satisfy it — so on nearly half the catalogue the packing reading gives a number rather than a range, and a reader can tell which by looking at the lengths of the lines.

What the reading cannot reach #

Both ends of the interval are sums over run lengths, so the interval is a function of the region’s multiset of run lengths and of nothing else. Two regions with the same lengths in each direction have the same interval, however different they look.

That is a fact with a consequence, and the consequence is a ceiling.

A hundred and forty-three groups of shapes in the catalogue share a multiset, and every group shares an interval — which it must. Sixty of those groups hold two or more number-valued shapes, and 21 of the 60 hold two different values. Four regions with runs of $1, 1, 1, 2, 3$ down and $1, 1, 1, 5$ across all have the interval $[0, 0]$, and three of them are worth $-\tfrac14$ while the fourth is worth $0$.

So the packing reading is not merely imprecise. It is saturated: it extracts everything the run lengths contain, the run lengths do not determine the value, and no refinement of a run count can close the gap. Sharpening it further is not hard work, it is impossible work.

That is a better place for a ladder to end than a residue. A bound instead of an answer is the site’s standing form for a rule of thumb — a bound it satisfies rather than a share it achieves — and this reading now has both a bound and a proof that the bound is the best of its kind.

Two counts, two arithmetics #

It is worth setting the two formulas side by side, because between them they say something about the game that neither says alone.

$$\text{opt}(\ell) = \left\lfloor \frac{\ell}{2} \right\rfloor, \qquad \text{pes}(\ell) = \left\lceil \frac{\ell - 1}{3} \right\rceil.$$

The first counts what a domino covers. The second counts what a domino costs — the two cells it sits on plus the one it strands beside it, less the fact that a run’s far end has no neighbour to strand. Both are properties of a single line of cells and neither knows anything about the game beyond the length of that line.

So a Domineering region, for the purposes of this reading, is not a shape at all. It is two lists of numbers, and everything about where the cells actually are has been thrown away before the arithmetic starts. That is what makes both formulas cheap, and it is exactly what the ceiling later in this page is about: a reading built from two lists of numbers can be no better than those lists.

The pair also explains why the interval is usually narrow, which two errors that cancel measured and could not account for. The two functions agree at $\ell = 1, 2, 3, 5$ and differ by one at $4, 6, 7, 8, 9$ — so on regions of at most eight squares, where most runs are short, most runs contribute nothing to the width. The narrowness is not a happy accident of Domineering; it is the arithmetic of small numbers, and it would loosen on larger boards where runs of ten and twelve appear.

What a player should do with it #

The practical upshot is worth separating from the theory, because it is unusually direct for this site.

A player looking at a Domineering region counts four things. The odd runs down and the odd runs across give the optimistic count, and half their difference is the reading. The thirds sums give the pessimistic end, and the interval is the two combined. If every run has length one, two, three or five, the interval is a point and the reading is as good as it can be; if some run has length four, six or more, the reading is a range and its width is one per such run.

That is the whole of it, and it fits in a paragraph. What it does not give is the value, and where the interval is wide the player should expect the value to be somewhere in it rather than at either end — two errors that cancel is the measurement of how often the value is inside, which is about three quarters of the time when the interval is summed over a whole board.

The one piece of advice that is new here is about which runs to break. A run of four is the cheapest thing on a board for an opponent to attack, because it is where the gap between best and worst is opened; a run of five is not, and neither is a run of three. A player who wants their own count to be reliable should avoid leaving runs of four, and a player who wants to spoil an opponent’s should make them.

The shape of the result, against the anchor’s usual #

Nine rungs into this anchor it is worth naming what kind of finding this is, because it is not the kind the anchor usually produces.

Most of what these ladders reach is a rule with a residue: a reading that works on four fifths of a population, an error term with a mean and a spread, a class of exceptions that has to be described. Which shapes are worth fighting over is a criterion with a boundary; the moves a player can be talked out of is a reduction with a count of what it fails to remove.

This one is two exact identities and a proof of a limit, which is the shape a subject reaches when the object being measured is arithmetic rather than geometric — the same observation the short side only says how many makes about Maundy Cake, where a game whose positions are factorisations gives a complete rule. A Domineering region is geometric, but the packing of one is not: it is a question about lines of cells, and a line of cells is a number.

So the honest reading of this rung is that the exactness belongs to the packing and not to Domineering. The moment the reading is asked for the value rather than for the packings, the geometry comes back — and it comes back as the 21 groups this page cannot separate.

Why the ceiling is what closes the ladder #

The finding that regions with identical runs have different values is the last thing this ladder says, and it is worth reading as a result rather than as an admission.

A negative result of that shape is a ceiling on a whole family of readings. Any rule computed from run lengths assigns the same answer to two regions with the same runs, so a pair with the same runs and different values refutes every such rule at once — the two closed forms here, and every refinement of them anybody might write.

That is more useful than a further improvement would have been. An open question invites more work of the same kind; a ceiling says the work has finished and names what would have to change to continue. What would have to change is the input, and the natural next input is something about how the runs are arranged rather than how long they are, which is a different family and a different ladder.

It also puts a floor under the interval’s width, which is what a reader with a board actually needs. The bracket cannot be tightened to a point by any run-based reading, so its width where it is widest is not a defect to be engineered away but the resolution of the instrument.

Which is the honest way for a sequence of approximations to end. Not with the last one still improvable and nobody continuing, but with a statement of what no reading of this kind can do — measured on the same 1,042 shapes as everything else on the ladder, and refutable by one pair.

What this does not say #

Both formulas are about one direction at a time. The interval combines a vertical count with a horizontal one, and the two are computed on the same cells independently. Nothing here says the two players’ packings can be achieved simultaneously — they cannot, in general — and the interval is a bound built from two separate optimisations, which is why it is a bound at all.

The catalogue stops at eight squares. Runs of length one to eight appear in it and nothing longer, so the width formula is checked at lengths where it takes the values nought, one and nothing else. At ten it should be two, and no region in the catalogue has a run of ten.

The minimum maximal packing is a lower bound on what a player suffers, not a prediction. It assumes the opponent plays every move to break slots and achieves the worst arrangement; a real opponent is playing their own game and rarely does. That was true of the interval before this page and is unchanged by it.

And the ceiling is about run counts, not about drawings. What the 21 split groups show is that the run-length multiset does not determine the value. A finer reading of the drawing — where the runs sit relative to each other, which cells they share — is not ruled out by anything here, and which shapes are worth fighting over is where a different property of a region turns out to decide something the counts cannot.

The convention, named #

Normal play throughout: Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses.

A run is a maximal horizontal or vertical line of cells inside the region, so a region has a multiset of horizontal runs and a multiset of vertical ones. A packing in one direction is a set of non-overlapping dominoes of that direction.

The optimistic packing is the largest such set — what a player gets if the opponent never interferes — and equals $\lfloor \ell/2 \rfloor$ summed over that direction’s runs. The pessimistic packing is the smallest maximal one: the smallest set after which no two free cells are adjacent in that direction, which is what a player is reduced to when the opponent spends every move spoiling slots.

The interval is the pessimistic vertical less the optimistic horizontal, up to the optimistic vertical less the pessimistic horizontal. It is a bound on the region’s value, and the value is a number on 315 of the catalogue’s shapes and something else on the rest.

The run-length multiset of a region is the pair of multisets — vertical and horizontal — with no record of where the runs sit. Two regions share one when they have the same lengths in the same directions.

Where the ladder goes next #

The domineering anchor has nine rungs: the game, the values of every small board, which shapes are worth fighting over, the board as a sum of its regions, the moves a player can be talked out of, counting the moves each side has, two errors that cancel, half the difference in odd runs, and now the other end of the interval.

The rung above is what the run lengths leave out. The ceiling here is exact — the interval is a function of the multiset and the value is not — so the next object is the smallest addition to the multiset that separates the split groups. The candidates are visible in the four-region example: where the runs meet, which is a count of cells lying in a long run both ways, and how the runs are distributed rather than merely which lengths occur. Twenty-one groups with a value each are a small, completely specified set to test a candidate against, and a property that separates all twenty-one would be the first reading of a Domineering region on this site that is not a count of packings.

Two neighbours are worth the trip. Two errors that cancel is where the interval was introduced and where its accuracy on a whole board is measured, which is the number a player actually cares about. And the board falls apart is why a reading of one region is a reading of a board at all, and it is the decomposition every rung on this anchor rests on.