Two errors that cancel

The moves a player can be talked out of took the oldest reading of a Domineering region — count how many dominoes each player could still place and subtract — and found that the correction it needs is not a subtraction but an interval: an optimistic count and a pessimistic one for each player, giving a band the value lies in on 209 of 315 number-valued shapes.

That page closed on the board:

Everything here is one connected piece evaluated alone, and a board in play is a sum of several — so the question is whether the intervals add. The optimistic counts do add, trivially, and the pessimistic ones probably do not, because a waste in one region is a move the player did not make in another.

They do add, and the reason takes one line. What the census here is really about is what happens next.

Why the pessimistic count adds #

The doubt is about waste. A pessimistic count is the smallest number of dominoes a player can be left having placed if the opponent is unhelpful — the smallest maximal packing — and the worry is that a player forced to waste a move in one region has thereby not made a move in another, so the wastes interact.

They do not, and the reason is what maximal means. A packing of a whole board is maximal exactly when no further domino fits anywhere, which is exactly when its restriction to each region is maximal there. So the maximal packings of a board are precisely the combinations of maximal packings of its regions, and the smallest of them is the sum of the smallest.

That is a proof rather than a measurement, and it is checked against the census on every board here. The consequence is that the interval carries across a board with no correction at all: the board’s band is the sum of the regions’ bands, term by term.

What the reading is then worth #

Additivity is not usefulness. A reading that adds can still be worthless once added, because the thing it is trying to say may get harder to say.

For the point count it does. On single regions the count is exactly the value 45 per cent of the time; on two regions 27, on three 21 and on four 11. That is what one expects: a board is right only when every one of its regions is right, so a rate of about a half falls off geometrically.

For the interval it does not. Containment runs 67, 66, 71, 74 per cent as the regions go from one to four — flat, and if anything improving.

The mechanism is the difference between adding numbers and adding errors. The band’s width is a sum: 0.59 on one region, 1.22 on two, 1.84 on three, 2.46 on four. The error is a sum of terms that are as often positive as negative, so its spread grows like $\sqrt{k}$: 0.52, 0.76, 0.85, 1.07 — against $0.52\sqrt{k}$, which is 0.52, 0.74, 0.90, 1.04.

A linear bound covering a square-root error gets safer the more terms it has. That is the whole finding, and it is the reverse of what a reader would guess about piling approximations on top of one another.

Why the width adds and the error does not #

The result in the table — the count decaying and the interval holding — has a one-line reason, and it is worth having because it is the general reason bracketing survives addition and estimating does not.

An interval reading assigns each region a pair $[\ell, u]$ with the value guaranteed to lie between. Add two regions and the guaranteed interval is $[\ell_1 + \ell_2, u_1 + u_2]$: the width adds, and containment is preserved with certainty, because a value inside each part’s interval is inside the sum’s by ordinary arithmetic. Nothing about the two regions has to be assumed and no error compounds, because there is no error — the claim was never that the value is any particular number.

A point reading has no such argument available. It assigns each region a single number and the sum’s number is the total, so the sum is exact only when every part is exact. If a region is exact with probability $p$ and the regions are roughly independent, a board of $k$ of them is exact with probability about $p^k$ — which is the decay from 45 per cent to 11 across one to four regions, almost exactly.

So the two readings have different failure arithmetic and it is the arithmetic rather than the readings that decides. A point estimate multiplies its chances of being right; an interval adds its widths. On a board with a handful of components the first is already hopeless and the second has lost only a little precision, and the crossover is at two or three regions rather than at ten.

That is the general shape of the trade and it is worth carrying to any approximation on this site. An answer that can be wrong should be replaced by an answer that can only be wide, wherever the thing being approximated is going to be added to something else — and in this subject it always is, because a board is a sum.

The reading that declines to answer #

The practical question is not containment but decision: does the band tell a player who is ahead?

The band excludes nought on 42 per cent of single regions and 41 per cent of four-region boards, and when it does, it names the right winner 248 times out of 254 at one region and 236 of 245 at four. The point count names a winner on every board and is right on 70 to 76 per cent of them.

So the two readings are two different offers. The count answers always and is wrong a quarter of the time; the band answers two boards in five and is wrong one time in twenty-five. Which is better depends entirely on what a player does with silence, and that is the honest state of every approximation on this site.

What is new here is that the choice does not change with the size of the board. Both readings hold their shape as regions are added — one holding its unreliability, the other holding its usefulness — so a player who has decided which to trust on a single region need not revisit the decision on a board.

Why the square root is the whole story #

It is worth spelling out the arithmetic, because a reader who has met error bars will recognise it and a reader who has not will think it a coincidence.

Adding $k$ regions adds $k$ band widths, so the band is $k$ times as wide. Adding $k$ errors that are independent and centred on nought gives a total whose typical size is $\sqrt{k}$ times one error’s — the errors partly cancel, and the more of them there are the more thoroughly they do it. So the ratio of what the band covers to what it has to cover grows like $k/\sqrt{k} = \sqrt{k}$, and the containment rate climbs.

That is not a fact about Domineering. It is a fact about summing a reading whose errors are not systematic, and it applies to every additive approximation on this site: the packing count, the stop reading on a sum, any per-component estimate a player carries across a board. The condition it needs is the one worth remembering — the errors must not share a sign — and the way to check it is the mean error, which is within a hundredth of nought at every board size here.

Where the band is still wrong #

Containment is 67 to 74 per cent, which means a quarter to a third of boards have a value outside the band. That has to be said plainly: the interval is not a bound and never was. The rung below found the same on single regions and named it — the band holds the value on 209 of 315 shapes — and adding regions does not repair it.

The failures are worth one sentence about their direction. The mean error is within a hundredth of nought at every board size, so the band is not systematically low or high; it is simply too narrow on the shapes where the packing reading misses badly, and those shapes go on missing badly when they are put on a board with others.

That is the difference between this reading and a real bound. A rule that is never right and cannot be far wrong is what a proved bound looks like: it may be loose, and it is never violated. The packing band is the other kind of object — usually right, occasionally wrong, and useful for exactly that reason as long as nobody calls it a theorem.

What this changes for a whole board #

Two consequences for a player facing a real position, and they run in opposite directions.

The bookkeeping is cheap. A band per region, added up, is a band for the board, and no interaction term is needed. So a player who has learnt the small shapes can carry the reading across a board of any size at the cost of an addition.

And the answer gets vaguer as the board gets bigger. The band on four regions is two and a half moves wide, which is wide enough to contain nearly every position a player might care about. So the reading is more reliable and less informative at once: it will not mislead, and it will increasingly decline to say anything.

That combination is what a good approximation looks like when it is honest about a large object, and it is the reason the board falls apart matters as much as it does. The saving from decomposition is in the evaluation, and this page says the cheap reading survives the decomposition as well — it simply does not survive it with enough precision to replace the evaluation.

What a player carries across a board #

Three practical consequences, and the third is the one that changes a habit.

Add the bands, not the counts. Both add, and only one of them keeps its meaning: a board’s count is the sum of its regions’ counts and is right one time in nine, while the board’s band is the sum of the regions’ bands and holds the value three times in four.

Read the band’s width as a warning. A band two and a half moves wide on a four-region board is saying that the reading has nothing useful to offer about that board, and a player who treats the midpoint as an estimate is re-introducing exactly the point count the band was built to replace.

And prefer fewer, larger regions when the reading has to be trusted. The band’s width grows with the number of regions rather than with the number of squares, so a board of one eight-square region is read far more sharply than a board of four two-square ones — even though the second is by every other measure the simpler position. That is a genuinely odd consequence and it follows directly from the additivity: each region contributes its own uncertainty whatever its size.

What this does not say #

Four limits.

Number-valued regions only. The packing reading is a count of moves and compares against a value that is a number; a region worth $\{2 \mid 0\}$ has no number to compare with. That restriction is inherited from the rung below and it removes two thirds of the catalogue.

Boards are assembled, not played. The regions here are drawn from the catalogue at random and put side by side, which is not the distribution a real game produces — a played board’s regions are small and cold, and a census over played boards would have a different mix and probably a narrower band.

Six hundred boards per size. These are samples rather than an enumeration, since the four-region boards number a hundred million. The shares are stable to a percentage point across seeds and nothing here turns on a difference that small.

And the square-root claim is an observation about this sample. Errors from separate regions are treated as independent because the regions are drawn independently; two regions of the same shape err identically, and a board made of four copies of one region has an error four times its region’s, not twice. A real board is somewhere between the two, and nothing here says where.

The convention, named #

Normal play, Domineering, Left placing vertically and Right horizontally.

The optimistic count for a player is the largest number of dominoes that player could place if the region were theirs alone; the pessimistic count is the smallest maximal packing — the fewest they could be left having placed with no further move available. The band runs from the pessimistic Left count less the optimistic Right count to the optimistic Left count less the pessimistic Right count.

A board here is a disjoint union of regions, and its value is the sum of theirs, which is the disjunctive sum theorem and the one piece of exact theory this page uses.

The error is the value less the point count, signed, so a positive error means the count under-rates Left.

Who reads a board this way #

Counting the moves each side can still make is what every player of every placement game does before they know any theory, and it is the reading Berlekamp’s endgame work is built to replace — with values, which are exact, and with temperatures, which say where to play. The interval is a halfway house: cheaper than a value, honest about being wrong, and — this page’s contribution — safe to add.

There is a small literature on bounding a partizan value by a count, and its shape is always the same: a quantity readable off the board, an inequality in one direction, and a class of positions where the inequality is tight. What is unusual in the Domineering case is that the natural count is not a bound at all, in either direction, which is why the rung below had to reach for an interval and why this page has to keep saying that the interval is not a theorem.

It is worth naming what would break the whole reading, since the census cannot rule it out. If a board’s regions were correlated — if the shapes that appear together tended to err the same way — the errors would add rather than cancel and the band would decay like the count does. Nothing here measures that, and a played board is the population where it might be true.

Where the ladder goes next #

The domineering anchor reaches seven rungs to here, and the two above finish the job this one leaves half done: the interval adds, and now it can be read off a drawing without any packing being computed at all.

Half the difference in odd runs gives the optimistic end a closed form. The largest packing count is half the difference between the region’s odd horizontal runs and its odd vertical runs, which is a quantity a player can total by eye. And it comes with its own error profile: exact seven times in ten when it claims one move of advantage, exact on none of the largest regions where it claims two, and exaggerating four times in five when it is wrong at all — so the reading is not merely approximate but approximate in a known direction.

One domino every three cells gives the other end, and it is the rung that overturns the obvious guess. Having found the optimistic end in the odd runs, the natural expectation is the pessimistic end in the even ones. Parity is the wrong arithmetic entirely: the smallest maximal packing is $\sum \lceil (\ell - 1)/3 \rceil$ over the runs, exact on all 1,042 shapes — a rule about spacing rather than about parity, and one that says a maximal packing places a domino roughly every three cells whatever the run’s parity.

Together those two make the whole interval readable off the drawing, which is what this page’s additivity result was worth having. A board of four regions can be bracketed by counting runs and doing two sums, with no evaluation anywhere.

They also close the ladder honestly. Regions with the same runs have different values, so a reading built entirely out of run lengths cannot reach the value no matter how sharp either end becomes. The interval is a genuine bracket and it has a floor on its own width, and the ladder ends by proving that rather than by running out of ideas.