Where the runs meet

One domino every three cells gave the pessimistic packing of a Domineering region in closed form — a sum of $\lceil (\ell - 1)/3 \rceil$ over the region’s runs — and with it the interval a region’s value must lie in, as a function of nothing but the multiset of run lengths. It also found the ceiling on that reading: twenty-one groups of shapes share a multiset and do not share a value. It closed on what would raise the ceiling:

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. 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.

A count of crossings separates none of the twenty-one. Their positions separate nineteen.

What the multiset knows #

The multiset records how many runs a region has and how long each is, in each direction. It is enough to give the interval exactly, because both ends of the interval are sums over runs — the pessimistic packing counts the dominoes a bad player is guaranteed to fit, and the optimistic one what a good player can fit, and both are run by run.

What it cannot record is anything about how the runs are arranged, because a multiset has no places in it. Two regions with a five-long horizontal bar and three one-long verticals hanging off it have the same multiset however the verticals are distributed along the bar.

That is where the values come apart. Take a stem meeting a five-bar one square in from the corner and the same stem two squares in: same runs, same everything countable, and values of $-1/2$ and $-1$. A domino placed at the junction blocks different amounts of bar on each side, and how much it blocks on each side is exactly what the offset records.

It is worth being precise about the population, because the number twenty-one is a count of groups rather than of regions. The census holds 1,042 connected regions of at most eight cells with their values computed by the ordinary recursion. Sixty run-length multisets are shared by two or more regions whose values are numbers; on 39 of those sixty every member has the same value, and on 21 they do not. Between them the 21 groups hold 139 regions. So the packing reading is already right about most of what it is asked — the failure is a fifth of the shared multisets, and it is the fifth that a reader wanting to use the interval would run into, because a group whose members agree is a group whose interval is a point.

Eleven statistics, and none of them enough #

Before proposing a reading it is worth exhausting the obvious ones, and the obvious ones here are the local statistics a region has.

Each is computed for every member of each split group; a statistic separates a group when members agreeing on it agree on their value. The scores are poor and one of them is worth reporting precisely.

The crossing count separates none of the twenty-one. That is the rung below’s own proposal, and it fails completely: a group’s members typically have the same number of cells sitting in both a horizontal and a vertical run, which is unsurprising once stated, because the crossings are where the runs meet and the multiset already fixes how many runs there are.

The perimeter separates none. The bounding box separates none, in either dimension. The count of $2\times2$ squares separates none. The degree sequence separates four to six groups depending on which degree is read. The best single statistic is the checkerboard imbalance at eight of twenty-one, and that is not a reading of anything in particular — it is a parity argument that happens to correlate.

And the failure is not one that a combination repairs. Fifteen sets of regions agree on the run multiset and on all eleven statistics simultaneously — same crossings, same perimeter, same degree sequence, same imbalance, same bounding box, same squares — and hold different values. Any reading built out of these ingredients, in any combination, is already refuted by those fifteen.

The reading that works #

The information the multiset destroys is a position, so the reading has to record a position.

For every cell sitting in both a horizontal and a vertical run, record four numbers: how many cells of its vertical run lie above it and how many below, and how many of its horizontal run lie to its left and how many to its right. Write each pair unordered, so that $\{0, 4\}$ is the same descriptor whichever end it is measured from. The multiset of those descriptors, added to the run-length multiset, is the reading.

The unordering is not cosmetic. A Domineering value is preserved by the half turn and by reflection in either axis — all three map Left’s moves to Left’s moves — and is negated by transposition, which swaps the players. So a descriptor invariant under the first three and not under the fourth is the right shape for the job, and writing the pairs unordered gives exactly that.

It separates nineteen of the twenty-one split groups, and it makes 58 of the 60 groups of number-valued regions single-valued. Nothing about it is a count of dominoes: it does not ask how many fit, or how many are wasted, or how many packings there are. It asks where two runs cross and how far the crossing sits from four ends.

That is the test the rung below set for a new kind of reading of a Domineering region, and it is met.

One consequence is worth drawing out, because it explains why the reading is not more familiar. A run-length multiset is what a person writing a Domineering region down naturally produces — a five-bar with three stems — and it is what every count-based reading on this anchor consumes. The junction descriptor is not something anyone would write down unprompted; it is a list of four-number tuples with no obvious meaning until it is explained. So the reading is less legible than the object it refines, which is unusual on this ladder and is the price of the extra information.

It is also why the crossing count was the natural proposal and the wrong one. A count is legible and a position is not, and the rung below reached for the legible version of the right idea. The idea was correct — the crossings are where the missing information lives — and the count is the part of a crossing that carries none of it.

Coarse enough to count as a reading #

A refinement can always be made to work by being fine enough. Refine by the shape itself and every group separates, and nothing has been learnt.

So the coarseness has to be reported alongside the score. The 1,042 regions of at most eight cells fall into 721 descriptor classes; 221 of those classes hold more than one region and the largest holds six. The reading loses information about three regions in ten and keeps the value on all but two groups.

That is what makes it a reading rather than a re-description. It is genuinely throwing something away — which shapes exactly, in which orientation, with which cells where — and what it keeps is enough.

What is left over #

Two descriptor classes remain multi-valued, and they are one group and its mirror image, so the residue is really one case seen twice.

Three regions share their runs and their junctions and are worth $1$, $1/2$ and $1$. What distinguishes them is not any offset the reading records — the three have crossings in the same relative positions along their runs — and it is presumably something about which runs the crossings belong to, which the descriptor deliberately forgets when it takes a multiset.

Naming the residue is more useful than hiding it. Nineteen of twenty-one is a good reading and it is not a formula for a Domineering value, and the three regions above are the proof that it is not.

What the pictures can and cannot carry #

The figures on this page draw regions as grids of filled cells, and that is the right drawing: a Domineering region is a set of cells, and the whole argument is about arrangement, so the picture and the object are the same thing.

What the pictures cannot show is the descriptor. A junction descriptor is a multiset of four-number tuples, printed here as a string, and there is no way to draw it that is not simply the region again with some cells marked. That is a real limitation and it is worth stating rather than working around: the reading’s content is that two regions a reader would call obviously different-looking have the same descriptor, and that is exactly what a picture of the descriptor would have to convey and cannot.

The compromise the figures make is to print the descriptor beside the region and let the reader check the correspondence by eye on a small table. It works for three regions and would not work for seven hundred.

Why this kind of reading is different #

Every previous rung on this anchor reads a region by counting dominoes. Counting the moves each side has counts placements; two errors that cancel counts them twice and subtracts; one domino every three cells counts the ones a bad player is guaranteed. Those readings share a shape: a region is a supply of moves, the value is about how much supply each player has, and everything is arithmetic on counts.

The junction descriptor is not that. It says a region is a skeleton with joints, and that what matters is where the joints are. That is a geometric statement rather than a combinatorial one, and it is a different theory of what a Domineering region is.

It is also, in retrospect, the reading the game’s own rules suggest. A vertical domino at a crossing consumes one cell of a horizontal run and splits it into two shorter runs, and the lengths of the two pieces are exactly the offsets the descriptor records. So the descriptor is not a statistic fitted to the data; it is a record of what each move at that cell would do. That the fitted reading turns out to be the mechanical one is the reason to believe it generalises.

What this does not settle #

It is a separation, not a formula. The reading tells two regions apart; it does not say what either is worth. Turning it into a value would mean a function from descriptors to values, and 721 classes with a value each is a table rather than a formula. Whether such a function exists in closed form is untouched here.

Eight cells is small. The census stops at eight because the value of a nine-cell region is expensive and there are many more of them. Nothing about the descriptor gets harder at nine, and nothing here says it keeps working. The two residual regions are seven and eight cells, so the residue is not concentrated at the small end where a reading has least to do.

The eleven statistics are the ones that occurred to somebody. They are the local, cheap, obvious ones, and the fifteen agreeing sets make any combination of them dead. A statistic nobody tried might separate more; what has been established is that the ones a reader would reach for first do not.

Fifteen agreeing sets is not a proof that no statistic works. It rules out the eleven measured and every function of them, which is a large class and not all of them. A statistic reading something genuinely different — the number of maximum packings, say, or the number of distinct positions reachable in two moves — is untouched by the fifteen and untested here.

The regions are single components. A region here is connected, and a Domineering board is a sum of them — the board falls apart is the fact that makes reading one region worth anything at all. Nothing on this page is a statement about a whole board.

And the reading was found by search rather than derived. Eleven statistics were tried and failed, and the descriptor was written down afterwards. The argument at the end of the previous section — that the offsets are what a move at a crossing does — is a reason to expect it to work, and it was constructed after the measurement rather than before. A reading fitted to twenty-one groups and then justified is a weaker object than one derived and then tested, and the distinction is the same one a bound instead of an answer draws about rules of thumb generally.

Normal play, and number-valued regions only. The split groups are groups of regions whose values are numbers, because comparing values means comparing numbers. Regions worth switches are in the census and are not in the comparison, and whether the descriptor separates those is a question with a different answer waiting.

The one number a player could use #

None of this is a strategy, and it is worth saying what the closest thing to one is.

A player looking at a region with a long run and a stem on it now has a reason to care where the stem is, and a direction: the offsets of the crossing are the lengths the run will break into if a domino goes there. A stem near an end leaves one long piece and one negligible one; a stem in the middle leaves two medium ones. Two errors that cancel established that a region’s interval is usually narrow enough for the interval alone to decide a comparison, so on most regions this refinement is not needed at all — it is needed exactly on the shared multisets, which is where two candidate placements produce regions the interval cannot tell apart.

That is a small and specific use, and it is the honest size of what a separating reading buys before it becomes a formula.

Where the ladder goes next #

The domineering anchor has ten 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, one domino every three cells, and now where they meet.

The rung above is the descriptor as a function. Nineteen groups in twenty-one is a separating reading, and a separating reading with 721 classes is one step from a lookup table — so the question is whether the table has structure: whether the value moves in a describable way as one offset changes with everything else fixed. The descriptor makes that question askable for the first time, because it names the variable to move. Sweeping one junction along its run and recording the value at each offset is a small computation on shapes already in the census, and it would say whether the offset enters the value smoothly, in steps, or not at all.

Two neighbours are worth the trip. Which shapes are worth fighting over is where a region’s shape was first read for something other than its supply of moves, and it is the nearest thing on this anchor to a geometric reading. And the values of every small board is the census all of this is measured against, and it is worth reading beside a page whose whole finding is what a census cannot be summarised by.