Counting the moves each side has

A player looking at a Domineering region does not compute its value. They count — three dominoes fit in there for Left and two for Right, so Left is a move up — and the arithmetic of that is a maximum matching in each direction, subtracted.

Which shapes are worth fighting over sorted the regions by what kind of value they carry and closed by naming the rung above:

A shape only one orientation fits in is worth the number of moves the one player has, and that number is not the number of squares — a 1 × 5 strip holds two horizontal dominoes and has five squares. What the count actually is, as a function of the shape, is a small combinatorial question with a definite answer.

The answer to that question turns out to be one line, and the line is worth having before the interesting version of the question can be asked.

The one-line answer, and why it is not enough #

A region only one orientation fits in is a straight strip. Any shape with a bend in it has two squares side by side and two squares one above the other, so both players can move; a shape with neither has all its squares in one row or one column. There are fifteen such regions of up to eight squares — a single square, and a horizontal and a vertical strip of each length from two to eight — and a strip of n squares holds ⌊n/2⌋ dominoes.

So the rung below’s question has the answer half the length rounded down, and the census asserts it: a strip whose value stopped being its packing count would stop the build.

That is a fact about fifteen shapes out of 1,042, and the reason it is a small fact is the reason it was worth asking. The interesting version drops the restriction to one orientation and takes the count for both players.

The count is the vertical packing minus the horizontal packing. Left plays vertically, so her packing is the largest set of disjoint vertical dominoes the region holds; Right’s is the same horizontally. Subtract, and there is a whole number, computable by looking, with no game theory in it at all.

Forty-five per cent, and a reason that was always going to be there #

On the regions worth numbers the count is exact on 141 of 315, which is under half.

One hundred and four of the 174 misses are regions worth a fraction. The count is a difference of two integers and can never be a half, so those were lost before the census started. A region worth ½ is a region where Left is a move ahead if she moves and level if he does — an unfinished fight rather than a settled advantage — and no count of dominoes has a way to express it.

That leaves seventy regions worth a whole number that pack a different whole number, and those are the ones where the reading is not merely coarse but wrong.

The mechanism is visible in the first of them. A U of five squares — a row of three with a square hanging below each end — holds two vertical dominoes and one horizontal, so the count says Left is a move ahead. It is worth nought. The reason is that Left’s two vertical dominoes are in the two arms of the U, and after Left takes one arm Right plays the horizontal domino across the top and takes the other away.

The count is what both players could place if the other never moved. Both players do move, and the moves interfere. Maximum matching is a question about a static shape and Domineering is a game.

Where it does better than it deserves #

On the 727 regions worth something other than a number, exactness is not available, so the census asks the weakest question a whole number could usefully answer: does the count land between the two stops?

The stops bracket every reasonable reading of a position — the Left stop is what the position settles at if Left moves first and both play out to a number, the Right stop the same with Right moving first, and the two never cross. A count outside that interval is claiming a lead larger than the position can produce under any order of play.

It lands inside on 619 of 727 — 85 per cent.

That is a much better score than the 45 per cent above and it is a much weaker claim. A hot region has a wide interval and a count has a good chance of falling in it by accident; the two figures together say that the count is roughly right about direction and unreliable about amount, which is the ordinary condition of a heuristic.

The 108 failures are worth naming because they are almost entirely one shape of failure: on 68 of the 108 the two stops are equal, so the interval is a single point and the count has to hit it exactly or miss. Forty of those stop at nought both ways and the count is not nought; twenty-eight stop at a half either side, where an integer cannot land at all. Of the remaining forty, twelve have stops ½ and −½ — an interval an integer straddles without entering — and the rest are narrow intervals between quarters and halves.

So the band test is not really a band test on those sixty-eight. A position whose two stops coincide is one where the order of play makes no difference to where it settles — an infinitesimal sitting on a number — and against those the count has no more room than it had against the numbers.

It gets worse with the board, which is the direction that matters #

Every region of three squares or fewer has its value equal to its count. By eight squares the exactness score is 96 of 210.

That trend is the practically important number on this page and it points the wrong way for a player. A reading that is exact on small positions and increasingly wrong on larger ones is a reading whose errors arrive precisely where a player stops being able to check them by looking. A three-square region can be evaluated in one’s head; an eight-square region is where a count would actually be used, and it is where the count is wrong more often than not.

The mechanism is straightforward and it is the same one the U demonstrates. A larger region has more room for the two players’ dominoes to interfere, and interference is exactly what the count omits. There is no reason to expect the trend to reverse.

What a good approximation would need #

The count fails for two separable reasons and it is worth being precise about them, because they suggest two different repairs.

It cannot express fractions. A repair for that is not a repair of the count; it is a different quantity. The natural candidate is the count taken after one move each, averaged — which is a search of depth two and no longer something a player does by looking.

It ignores interference. A repair for that would subtract something for each pair of the player’s own dominoes that a single opposing domino can break. The U has exactly one such pair and is worth exactly one less than the count — and every one of the seventy is off by exactly one, in one direction or the other, which is a good deal more encouraging than a scatter of magnitudes would have been. Whether each of the seventy has exactly one breakable pair is a computation this page has not run and which the seventy are the data for.

Both repairs cost the property that made the count worth measuring. It is computable by looking, and every one of the site’s other readings of a Domineering position needs the recursion. The board falls apart is the economy that makes evaluation affordable and it is still evaluation; a count is not.

So the honest summary is that a domino count is worth having as a tie-breaker and is not worth having as a value. That is a lower claim than the folklore makes for it and it is the claim the census supports.

Two counts that are not this one #

Worth separating, because the word count attaches to three different quantities in Domineering and they disagree.

Squares is the crudest and it is the one this rung’s question was framed against. A 1 × 5 strip has five squares and is worth 2, so squares overstate by more than a factor of two, and nothing on this page uses them.

Moves available now is what a player sees first: how many placements are legal in the region at this moment. That is not a packing — it counts overlapping dominoes separately — so a 1 × 3 strip offers two moves and holds one domino. It is the quantity the reduction’s survivors turn out to be sensitive to, and it is not a candidate for the value because it grows with the region rather than with the advantage.

Maximum packing is this page’s, and it is the only one of the three with a chance of being the value, because it is the number of moves a player would get if the region were hers alone.

Getting those three confused is the ordinary way a player overestimates a region, and the difference between the first and the third on an eight-square shape is routinely a factor of four.

The seventy are all off by one #

That is worth pulling out of the previous section, because it is the strongest regularity on the page and it was not planned for.

Seventy regions are worth a whole number and pack a different whole number. In every single one of them the two differ by exactly one. There is no region here that packs +3 and is worth 0, none that packs −2 and is worth +1; the count is either right or one out.

A scatter would have said the count is unrelated to the value on those seventy. One-out-everywhere says something much more specific: the count is a correct measure of the position plus a correction, and the correction is small and integral. Whether it is always one, or one at eight squares and two at twelve, is exactly the question a larger catalogue would answer, and it is the question that decides whether the repair proposed above is a repair or a coincidence.

There is one more reading of it worth recording, because it makes the failure feel less like a defect. A region whose count is one too high is a region where one of the player’s dominoes is virtual — it can be placed, and it cannot be placed after the opponent has had a say. That is the difference between the moves a position offers and the moves a position will yield, and it is the same distinction the whole subject is built on: a position is not a list of moves, it is a list of moves each of which has a reply.

Two failures with different standing #

The count fails in two ways and this page reports both, and it is worth saying which of them is a fact about the reading and which is a fact about the game — because only one of them could ever have been repaired.

The first was inevitable. A single number cannot represent a quantity that depends on who moves. A packing count assumes cooperation from the opponent when it counts one player’s placements and obstruction when it counts the other’s, and no arithmetic on one number can hold both assumptions. That failure is in the shape of the reading, and the repair is to stop using one number — which is what the rung above does.

The second is a fact about the game. Even with both readings in hand, a region’s value is not determined by any count of placements, because two regions can admit the same packings and be worth different values. That is not a defect in the count; it is a statement that the value depends on the order moves become available, and a count has thrown the order away.

Keeping them apart decides what to do next. A failure of the first kind is an argument for a better reading, and the rest of this ladder is that argument. A failure of the second kind is a bound on how good any reading of this family can be, and it is the thing that eventually closes the ladder rather than the thing that motivates the next rung.

The general instruction is to ask, of any approximation that fails, whether the information it needs was thrown away by its own shape or was never in its inputs. The first is fixable and the second is a ceiling, and confusing them produces either wasted work or premature surrender.

What the census does not say #

Four limits.

Regions, not boards. Every count here is of a single connected region evaluated on its own. A board in play is a sum of regions and its value is the sum of theirs, so the counts add — but so do the errors, and a board of four regions each off by one can be off by four. Nothing here bounds the accumulated error, and the sum is where a player would use the reading.

Up to eight squares. The catalogue stops at eight, which is where a build can enumerate every shape. The trend across sizes is clear and its continuation is an extrapolation.

Maximum matching is exact and the census’s own arithmetic is brute force. The packings are computed by trying every set of disjoint dominoes, which is affordable at eight squares and would not be at twenty. That is a fact about this census rather than about the problem — matching in a bipartite graph is cheap — and it bounds the sweep and not the reading.

And the band test is a weak test that this page reports as a weak test. Landing between the stops is compatible with being wrong about everything that matters: a region worth {2 | 0} has stops 2 and 0, and a count of 0, 1 or 2 all pass. The 85 per cent should be read as not obviously absurd rather than as right.

The convention, named #

Normal play. Left plays vertical dominoes and Right horizontal ones, so a tall region is good for Left, and every count and every sign on this page follows that.

A region is a connected set of squares, taken up to translation but not up to rotation or reflection — a horizontal strip and a vertical strip of the same length are two entries in the catalogue and two different values. The value is computed by the recursion on the smallest rectangle holding the region, with everything outside it treated as occupied.

The packing of a region for a player is the largest number of disjoint dominoes of that player’s orientation it holds, computed exactly. The count is Left’s packing minus Right’s. The stops are computed by playing the region out under the two orders of play.

Where the ladder goes next #

The domineering anchor has five rungs to here, and this one has put a whole number from the drawing beside the value. The four above find out why one number cannot do it, fix that, and then make the fix readable.

The moves a player can be talked out of diagnoses the failure this page reports as two kinds. A packing count is optimistic for its owner and pessimistic for the opponent, and one number cannot be both — so it becomes an interval, from what a player can be reduced to against what the opponent can achieve. It contains the value on 209 more regions, collapses to a point on 505 of 1,042, and is never more than two moves wide.

Two errors that cancel then settles whether the interval survives a board, which is the only test that matters. It does, and better than the point estimate does: over boards of one to four regions the exact count decays from right on 45 per cent to 11, while the interval’s containment rises from 67 to 74 — because widths add and errors do not.

The last two rungs remove the packing computation entirely. Half the difference in odd runs gives the optimistic end as half the difference between the region’s odd horizontal and odd vertical runs, and one domino every three cells gives the pessimistic end as $\sum \lceil (\ell-1)/3 \rceil$ over the runs, exact on all 1,042 shapes.

And the last of them closes the ladder rather than continuing it: 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.