How wrong a nearly-independent split is

A board that has genuinely fallen into two regions is two games and the arithmetic is exact. A board somebody has decided to think of as two halves is one game, and treating it as a sum is a claim about it.

Independence is a claim counted how often the claim fails — and how often it fails without changing the winner, which is the case an author never notices — and closed by naming the rung above:

The rung above is the quantitative one the last section named — how wrong a nearly-independent split is, and whether the error can be bounded.

It can. The bound is twice the height of the cut, the height alone is not enough, and the error has a sign before it has a size.

The error is a game #

The first thing to fix is what how wrong means, because the error is not a number.

The whole board is worth some value; the sum of the halves is worth another; their difference, reduced to canonical form, is the error. On three of the twenty-two failing cuts it happens to be a number — −1, −1/2 — and on the other nineteen it is something like { {2 | 0} | {−1/2 | −5/2}}.

So how wrong has no answer in the sense the question invites — the same difficulty the lattice’s error term runs into, where fifty-two discrepancies turn out to have seven sizes between them — and the right question is what the error is bounded by. That is a game comparison — is the error at least minus this? — and it is the form every bound on this page takes.

Nine distinct errors account for all twenty-two cuts. The same error arrives on several boards, which is a hint the error is a fact about the shape of the cut rather than about the board it is made in.

Twenty-two of thirty #

The pool is every vertical cut of every Domineering rectangle a build can hold: boards of one, two and three rows and two to five columns, with the whole-board table exhaustively enumerated, which is what an exact error needs.

Thirty cuts, and the halves add on eight of them. Those eight are not a random eight. Every one is a cut of a board with one row, or a cut that takes nothing away — a cut at the very edge, where one half is empty and the sum is the other half unchanged.

On a one-row board the cut destroys one horizontal domino and the error is exactly −1, which is a number, and the two halves add whenever that one domino was not there to be destroyed. So the whole of the agreeing set is a degenerate case, and the honest reading of eight of thirty agree is that the claim fails wherever it is being made non-trivially.

That is a sharper statement than the rung below’s, and it comes from the same numbers read one way further. Counting failures gives 22 of 30 and invites the thought that a quarter of splits are fine; identifying the agreeing eight says none of them is a split anybody would make.

The sign, which is a theorem #

Every error is at most nought and none is confused with nought. That is asserted by the census and it is not an observation about twenty-two boards; it is forced by which player the cut robs.

A vertical cut down a column destroys horizontal dominoes and no vertical ones. Left plays vertically, so every move Left had on the whole board is still available in one half or the other; every horizontal domino straddling the cut is a Right move that has vanished.

Deleting an option can only hurt the player who had it, so the halves are at least as good for Left as the whole board. The whole minus the parts is therefore at most nought, always.

That is the sort of result the census exists to check rather than to discover, and checking it is worth the trouble: it is easy to state, easy to believe, and would have been quietly false if the cut had removed anything of Left’s.

It also says the split is not merely inaccurate but biased, and in a known direction — which is more than outcomes do not add can say about its own failure, where the direction depends on the pair. An author who splits a Domineering board and reports the sum has reported a number too favourable to Left, every time, and there is no board on which the error runs the other way.

What bounds it #

Four candidates, each testable as a game comparison against every failing cut.

One domino is the smallest bound worth trying and it is right on a board of one row, where the cut destroys exactly one horizontal domino and the error is exactly −1. On sixteen of the twenty-two it holds and on six it does not.

The height of the cut is what a reader would reach for. A cut through an r-row board destroys one straddling domino per row, so r dominoes go, and a bound of r looks like the honest accounting. It fails on the same six.

Twice the height of the cut holds on all twenty-two, and the census refuses to build without it — and it also refuses to build if the height alone starts holding, because the essay’s sentence is that the obvious accounting is not enough and a census that stopped saying so would be about something else.

The whole board’s temperature fails on eighteen, which is worth recording because it is the bound a reader carrying thermographs would try. Temperature measures what a move is worth and the error measures what several missing moves are worth; they are not in the same units, and the census makes that concrete rather than arguing it.

Why twice, and this page does not know #

The factor of two is measured and is not explained, and it would be dishonest to dress it up.

The accounting says r dominoes disappear. If losing a move were worth at most one point, the bound would be r. It is not: on a 3 × 2 board cut down the middle the error reaches a Right stop of −4, against a height of 3.

A plausible story is that a lost move costs its own value and the tempo of having to move elsewhere, so each missing domino is worth up to two — but that is a story, and turning it into an argument means bounding what one deleted option is worth in a Domineering position, which is a claim about all positions and not about twenty-two.

What the census does establish is that a constant will not do. A bound of −4 fails on one cut and a bound scaling with the height holds; so whatever the right statement is, it grows with the cut. That is the useful half of the finding for anybody splitting a larger board: the error grows with the length of the cut, and treating an eight-row board’s split as no worse than a two-row board’s is wrong by a factor of four.

Fourteen quiet failures #

The rung below’s sharpest number was that fourteen of the failures leave the winner unchanged, and this page can say what those fourteen are made of.

They are the cuts whose error, while non-zero, is small enough or confused enough not to move the whole board across the boundary between outcome classes. A board worth {2 | 0} and a sum worth {2 | 1/2} are different values with the same outcome, and a split reporting one for the other has produced a wrong answer that passes every check an author would run. Knowing who wins is not knowing what it is worth, and here the gap between the two questions is exactly the gap an error hides in.

That is the practical hazard the two rungs together describe. The claim fails on twenty-two of thirty cuts; it fails visibly on eight. An author checking their split by asking who wins catches a quarter of their own errors.

Why “nearly independent” is not a quantity the theory has #

The phrase in this page’s title is doing something the rest of the subject refuses to do, and it is worth being explicit about the refusal, because it is what makes the measurement here unusual rather than routine.

Independence in this subject is a yes-or-no property. Two regions are independent when no move in one changes anything about the other, and the theorem that values add is stated under exactly that hypothesis. There is no theorem about regions that are almost independent, no correction term in the standard apparatus, and no notion of how independent two parts are — because the equivalence the whole theory is built on quantifies over all sums, and a sum either is one or is not.

So a page measuring how wrong a nearly-independent split is has to invent its currency, and the choice made here is the error as a game rather than as a number. That is the right choice for a reason worth stating: a numerical error would have to be the difference of two values, and the difference of two values is a game, so reducing it to a number throws away exactly the information about who the error favours and under what circumstances.

The consequence is that the bound on this page is a bound on a game and not on a score. It says the error is smaller than a stated infinitesimal or fits inside a stated interval, which is a statement about every sum the split appears in — the same standard the exact theory holds itself to — rather than a statement about one board’s total.

That is the honest form for an approximation in this subject, and it is more demanding than the approximations in most. A rule that is usually within a point is a rule about scores. A rule whose error is bounded as a game is a rule that can be substituted into anything, which is what the theory’s own results promise and what an approximation has to match to be usable beside them.

What makes a split legitimate #

Worth restating, because the whole page is about the illegitimate case and the legitimate one is a single line.

A split is exact when the two parts genuinely cannot interact, which for Domineering means no domino can span them. A wall of occupied squares does that; an imagined line does not. The board falls apart is the case where it happens by itself, and the arithmetic there is exact rather than approximate — and how thick a wall has to be is the same question asked of NoGo, where a wall of stones separates the sides only if its own groups do not span it.

The rung below’s pairing makes the point better than any argument: the same board with a column blocked rather than ignored has halves that add exactly, and the two drawings differ by whether the squares are there.

So this page is not about an approximation anybody should be making. It is about what it costs when somebody does, and the answer is that it costs a game, in a known direction, bounded by twice the cut.

Why a nine-error alphabet #

Nine distinct errors across twenty-two cuts is a small number, and it is the clue this page cannot follow.

The 2 × 3 board cut at column 1 and the 2 × 3 board cut at column 2 leave the same error, which is unsurprising by symmetry. But the 3 × 3 cut at column 1, the 3 × 5 cut at column 2 and the 2 × 5 cut at column 2 also leave it, and those are three different boards of three different sizes.

So the error is a function of something much coarser than the board. The obvious candidate is the shape of the cut — its height, and how much room sits on each side of it — and the census does not have enough cuts of each height to separate that from anything else.

If it is right, the practical consequence is large: an author splitting a board would look up the error in a table indexed by the cut rather than computing it, and correcting a split would cost a lookup. That is a genuinely useful object and it is nine rows long at this size.

What stops this page claiming it is the same thing that stops it claiming the tight bound — three heights, and cuts of height four are on boards of twenty squares. The nine errors are an invitation rather than a finding, and they are recorded here so that whoever runs the larger sweep has somewhere to start.

What the census does not say #

Four limits, and the first bounds everything.

Thirty cuts of boards up to fifteen squares. Every board here is small enough for the whole-board table to be enumerated, which is what the exact error requires. The bound twice the height is checked on cuts of height one, two and three, and the factor of two is three data points.

Vertical cuts only. A cut down a column removes only Right’s moves, which is what gives the error its sign. A horizontal cut would remove only Left’s and the sign would reverse; a diagonal or ragged cut removes both and this page has none.

Empty boards only. Every board cut here starts with no dominoes on it. A part-played board has its own shape and its cuts destroy a different number of straddling moves, so the height is no longer the right count.

And bounded is a bound and not a formula. Twice the height holds on all twenty-two and is attained on none of them exactly — the worst is −4 against a bound of −6. The smallest true bound is somewhere between the height and twice it, and this page has not looked for it.

The convention, named #

Normal play. Left places vertical dominoes and Right horizontal ones. A cut at column k of an r × c board means evaluating the left k columns as one board and the remaining c − k as another, and adding, which is what treating the board as two halves amounts to.

The error is whole − parts, computed by negating the sum of the halves, adding, and reducing to canonical form. A bound is tested as a game comparison against the number: is the error at least minus this? — so a bound holding is a statement about the value and not about the stops.

The height of a cut is the number of rows of the board, which is the number of horizontal dominoes the cut destroys — one per row, being the domino that would have straddled the line.

Where the ladder goes next #

The disjunctive-sum anchor has five rungs: the sum as the object, which part to move in, the other ways to add, whether the parts are parts, and now what it costs when they are not.

The rung above is the smallest true bound. Twice the height holds and is attained nowhere; the height fails on six. Something between them is exact, and finding it means either a sharper accounting of what a deleted option costs or a wider sweep with cuts of height four and five — which needs boards of twenty squares and a whole-board table too large to enumerate. That is the one place on this page where the limit is the machine rather than the mathematics.

Two neighbours are worth the trip. A bound instead of an answer is the general account of a rule that is never right and cannot be far wrong, which is exactly the shape this page’s split has once the bound is in hand. And how often a board falls apart is the measurement of when the exact version is available, and reading the two together gives the whole trade: split when the board has split itself, and know what it costs when it has not.