The moves a player can be talked out of

Counting the moves each side has tested the reading a Domineering player actually carries. Count the largest number of vertical dominoes a region holds, count the largest number of horizontal ones, subtract: a whole number, computable from the drawing, with no game theory in it.

It is the value on 141 of the 315 regions of up to eight squares worth numbers. That page closed by naming what it was missing:

Seventy regions are worth one whole number and pack another, the discrepancy is exactly one on all seventy, and the U suggests why: a pair of the player’s own dominoes that a single opposing domino can break. Counting those pairs and subtracting is a well-defined quantity computable from the drawing.

The quantity exists and the correction is real. What it is not is a subtraction, and seeing why turns the count into a better instrument than the repair would have made it.

One number doing two jobs #

The largest packing of vertical dominoes is what Left could place if nothing went wrong: every slot survives, no domino is laid across two of them, and the last vertical square is used by a vertical domino.

That is an optimistic count, and the difference of two optimistic counts is a strange object. In optV − optH the first term is optimistic for Left and the second is optimistic for Right — so the difference is optimistic for Left in its first half and pessimistic for Left in its second. It is not a bound in either direction, and the 174 misses split above and below with no pattern in the sign.

The repair is to stop asking one number to be both. Each player gets two counts:

• the optimistic count, the largest packing, which is what that player achieves unopposed;
• the pessimistic count, the smallest maximal packing — the fewest dominoes that can be placed before no more will fit, which is what that player is left with when every avoidable waste happens.

Pair them across and the reading becomes an interval: Left’s pessimistic count minus Right’s optimistic count at the bottom, Left’s optimistic minus Right’s pessimistic at the top.

What a wasted move is #

The pessimistic count is exactly the quantity the rung below reached for. A vertical domino laid across two squares that each belonged to a different would-be vertical slot destroys two placements and makes one, so Left is one move worse off than the packing said — and the same domino also takes two squares out of Right’s reach.

That is the U: a shape where one orientation can be laid so as to spoil its own future, and the difference between the largest packing and the smallest maximal one is how many times that can happen.

On 505 of the 1,042 regions there is nothing to waste, the two counts coincide for both players, and the interval is a single point. That is the fact that makes the correction worth having rather than merely wider: it does not blur the shapes it was already right about.

The census asserts it. A region where neither player can waste a move and whose bracket is not a point would mean the two quantities had come apart for some reason other than waste, and the census refuses to report rather than passing it on.

The seventy, revisited #

The rung below’s sharpest observation was about a subset: seventy regions worth a whole number whose count is a different whole number, with the discrepancy exactly one on all seventy. An error that is always the same size is an error with a mechanism behind it.

The mechanism is the one above, and the interval is what it looks like once it is counted rather than described. A region where one player can waste exactly one move has a bracket one wide, and a bracket one wide contains the point count and one integer beside it — which is precisely the answer needed when the value is one away.

It does not catch all seventy, because a bracket one wide extends in only one direction from the point and the value is sometimes on the other side. What it catches is the cases where the waste is available to the player the error favours, which is most of them and not all.

That is worth stating as a limitation of the picture rather than of the arithmetic. The interval is built from what each player can do to themselves; the value is decided by what each player can do to the other, and those coincide only when a wasted move is the only way to be hurt.

How the two counts are found #

Neither count needs a game. Both are matchings in a graph whose vertices are the region’s squares and whose edges join squares adjacent in the relevant direction.

The maximum matching is brute force over the edges, which is affordable because eight squares admit at most eleven edges of a given orientation. The minimum maximal matching is the same search with the test inverted: descend until no edge is free, and keep the smallest set reached, pruning on the best found so far. The whole catalogue of 1,042 shapes takes under a second for both directions of both quantities.

Straight strips are the degenerate case and are the check. A strip admits one orientation, so one player’s two counts are both nought and the other’s coincide — a strip of $n$ holds exactly $\lfloor n/2 \rfloor$ dominoes however they are laid. Fifteen regions in the catalogue are strips, their brackets are points, and the point is the value, which is the rung below’s own finding restated as arithmetic.

What it buys #

On the 315 regions worth numbers, the point is right 141 times and the interval contains the value 209 times. That is 45 per cent against 66, bought at a mean width of 0.56 of a move.

The gain is not spread evenly and it should not be.

Below six squares the correction does nothing at all: 2 of 4 at four squares, 3 of 9 at five, unchanged. Those regions are too small to waste anything in, so their brackets are points and their misses are misses for a different reason. At six squares the count goes from 10 right to 14 contained, at seven from 25 to 37, and at eight from 96 to 148.

The reading improves exactly where it was getting worse. The rung below’s complaint about the point count was that its score falls as the regions grow — from exact on everything below four squares to under half at eight — and the correction is a term that grows in the same direction.

What it does not buy #

A hundred and six of the 315 remain outside the interval, and they split 53 above and 53 below.

That symmetry is a check rather than a finding: the catalogue is closed under reflection, reflecting a region negates its value and swaps the two players, so any count of misses on one side has to equal the count on the other. A census reporting 60 and 46 would be reporting a bug.

Sixty-two of the 106 are regions worth a fraction. An interval with integer endpoints can contain a half — $[0, 1]$ does — so a fraction is no longer automatically a miss, and 42 of the fractional values now land inside. What defeats the rest is width: a region whose bracket is a point cannot contain a half, and most of the small regions bracket to points.

The remaining 44 are worth whole numbers the interval still misses, and those are the honest failures. There is no reason a maximum matching should know what a game is worth, and the surprise of this whole ladder is that it so nearly does.

Where the failures concentrate is instructive. They are the regions whose two players’ moves interfere without either being able to waste one — a shape where a horizontal domino removes a vertical slot but no vertical domino can spoil a second vertical slot. Interference of that kind costs the value and costs the bracket nothing, so the interval stays a point and the point is wrong. Where the fight stops is the general account of what interference does to a position, and it is the thing every reading on this ladder is trying not to look at.

Why an interval is the right shape for the answer #

This site has an essay about exactly this kind of instrument. A rule that is never right and cannot be far wrong is about approximations that come with a guarantee attached, and the argument there is that a bound with a known width is a better object than a point estimate with an unknown error.

The packing count as a point is the second kind. It is right 45 per cent of the time, it does not say when, and a player using it has no way to tell a region it gets right from one it does not.

The packing count as an interval is the first kind. It is wrong 34 per cent of the time and it says how wide it is on every region — and on 505 of them it says the width is nought, which is the case in which a bound is an answer.

And both endpoints are still counts of dominoes on a drawing. That is the constraint the whole ladder is under: the point of the reading is that a player can carry it, so a correction requiring the value would be no correction at all. A minimum maximal matching is a harder count than a maximum matching and it is still a count, findable by eye on a region of eight squares.

What this says about the regions worth fighting over #

Which shapes are worth fighting over sorted the same catalogue by whether a region is worth a number at all, and 727 of the 1,042 are not. Those cannot be tested against a value, so the rung below asked instead whether the count lands between the two stops — the widest claim a whole number could make about a value that is not one — and found it doing so on 619.

The interval does better on those too, at 661, and the improvement is smaller in proportion because the stop interval is already generous. A hot region is where the packing count has least to say, and that is not a defect of the count: a region worth a switch is one where the two players’ moves interfere, and interference is the thing a packing ignores by construction.

Two counts that cannot be one number #

The step this page takes — one number to two — is worth stating in the abstract, because the reason it was forced is the reason most single-number readings in this subject are wrong.

A packing count answers how many dominoes can this player place? and there are two honest answers, because two different questions are hiding in it. How many can a player place if the opponent cooperates is a largest packing. How many can they be reduced to if the opponent obstructs is a smallest maximal packing. Both are properties of the shape, both are computable, and they are different numbers.

The value of a region is decided by play, and play has an opponent in it. So a reading that reports one number is reporting one of the two questions and staying silent about the other — and which of the two it should report depends on whose move it is, which is exactly what a value does not fix.

A single number is therefore not a slightly imprecise reading; it is an answer to a question the position does not pose. The interval is not a hedge around a true value either: it is the pair of answers to the two questions that are actually well-posed, and the value lies between them because play lies between cooperation and obstruction.

That is why the interval collapses to a point on half the regions. Those are the shapes where the opponent’s obstruction cannot cost anything — the two answers coincide, the question stops being two questions, and one number is right for the reason the single-number reading assumed everywhere.

What the census does not say #

Four limits.

Eight squares. The catalogue stops there because the value of every shape is computed exactly and a nine-square region has too many of them. Whether the interval’s advantage keeps growing is the same census one square wider, and the trend across six, seven and eight says it should.

The pessimistic count is not a strategy. The smallest maximal packing is what a player would be left with if every waste happened, and nothing says an opponent can force all of them. So the lower end of the interval is a genuine lower bound on a bad outcome rather than a value anybody can be held to, and the interval is consequently a little wider than the truth.

The interval is not proved to contain the value. It contains it on 209 of 315 and fails on 106, so it is not a bound at all in the theorem sense — it is a reading with a measured hit rate, like the point it replaces. What has improved is the hit rate and the fact that the reading now reports its own precision.

And the correction was found by looking for it. The rung below named the U, this page formalised what the U does, and the formalisation was tested on the same 1,042 regions that suggested it. A second catalogue — Cram’s regions, or Domineering on a board with holes — is what would say whether the quantity is about Domineering or about matchings.

The convention, named #

Normal play, Left placing vertical dominoes and Right horizontal, and a region is a set of orthogonally connected empty squares.

The optimistic count for a direction is a maximum matching in the graph whose vertices are the region’s squares and whose edges join squares adjacent in that direction. The pessimistic count is a minimum maximal matching in the same graph: a set of disjoint dominoes that no further domino of that direction can be added to, chosen as small as possible.

The bracket is $[\,\text{pessimistic}_V - \text{optimistic}_H,\ \text{optimistic}_V - \text{pessimistic}_H\,]$, signed so that positive favours Left, and the point count of the rung below always lies inside it — which the census asserts, since an interval that failed to contain the number it was built around would be an interval around something else.

Where the ladder goes next #

The domineering anchor has six rungs to here, and this one has just replaced a single number with an interval. The three above ask what an interval is worth on a board, and then make both of its ends readable.

Two errors that cancel settles the doubt this page ends on. The pessimistic half does add across a board, for a one-line reason — an interval’s width adds and its error does not — and the consequence is the reverse of what a reader would expect. Over boards of one to four regions the exact count decays from right on 45 per cent to right on 11, while the interval’s containment rises from 67 per cent to 74.

That is the argument for brackets in this subject stated at its sharpest. A point estimate multiplies its chances of being right across components; an interval adds its widths. On a board with more than two pieces the first is already hopeless and the second has lost almost nothing.

Half the difference in odd runs then gives the optimistic end a closed form — half the difference between a region’s odd horizontal and odd vertical runs — and one domino every three cells gives the pessimistic end $\sum \lceil (\ell-1)/3 \rceil$ over the runs, exact on all 1,042 shapes and a rule about spacing rather than the parity formula anybody expected.

With both ends in closed form the interval is a glance rather than a computation. And the same rung ends the ladder honestly: regions with the same runs have different values, so a reading built out of runs has a floor on its own width and can never become the value.