Three distances too many

Where the runs meet built a reading of a Domineering region that counts nothing. Every previous rung on this anchor counts dominoes — how many fit at worst, how many at best, the waste between the two. That one records instead where two runs cross and how far the crossing sits from four ends, which is a description of geometry rather than of supply, and it separates nineteen of the twenty-one groups the run-length multiset leaves ambiguous.

It also left a question, and the question is the useful thing about a reading that gets most of the way: a descriptor with seven hundred and twenty-one cells is one step from a lookup table unless the table has structure. The descriptor names a variable — the offset of a crossing along its run — and nothing had ever moved that variable and watched.

That is the difference between a classification and a function. A classification sorts the shapes it was built from; a function says what happens when one thing is changed. Every reading this anchor has produced so far, from the pessimistic packing onwards, has been offered as a classification and tested by how well it sorts a census. None has been asked the other question, because none of them named a variable that could be turned.

So move it. Hold the run lengths fixed, hold the crossing row fixed, slide the crossing from one end of the long run to the other, and read the value at each offset. The rung below offered three possibilities: the offset enters the value smoothly, or in steps, or not at all.

It is none of the three.

One sweep #

Take a run of seven cells crossed by a run of three, meeting on the top row of the vertical arm. Slide the crossing along the seven.

The descriptor changes at every offset, as it must: the crossing is 0 and 6 from the two ends, then 1 and 5, then 2 and 4, then 3 and 3, and back out again. Four distinct readings on a seven-cell run.

The value takes two. It is −2 at offsets 0, 2, 4 and 6, and −3/2 at offsets 1, 3 and 5, and that is the whole of it. Sliding the crossing one square changes the region’s worth; sliding it two squares changes nothing. The region does not care how far the crossing is from either end. It cares whether the number of squares to its left is even or odd.

That is not smooth and it is not steps. It is one bit.

It is worth being clear that this is not a small change being rounded away. The two values differ by a half, which on a shape worth about −2 is a quarter of the whole — the difference between a region a player should take and one they should leave is routinely smaller than that. The offset is doing something real to the region. It is doing exactly two things, and which of the two depends on one bit.

And one where even that does not arrive #

Now the same experiment on a run of six.

The descriptor behaves exactly as before — 0 and 5, then 1 and 4, then 2 and 3, three distinct readings — and the value does not move at all. Every offset gives −3/2. The crossing can sit against either end or anywhere between and the region is worth the same.

Two sweeps, two different answers, and the difference between them is nothing about the crossing. It is the parity of the run the crossing is sliding along.

Both of those sweeps are the same shape in every respect the earlier rungs of this anchor can see. The run-length multiset is fixed along a sweep by construction — sliding a crossing does not change how long any run is — so the multiset reading says one thing for all seven offsets and all six. The packing counts are fixed too, for the same reason. The junction descriptor is the only reading on this anchor that can tell the offsets apart at all, which is why it is the one being asked.

The law #

Sweep every cross: runs of three to eleven crossed by runs of two to seven, at every crossing row, two hundred and forty-three sweeps in all.

A hundred and eight of them have an even long run and the value is constant across the whole sweep, without exception. A hundred and thirty-five have an odd long run and the value takes exactly two readings, one at even offsets and one at odd, without exception. Nothing in the sweep does anything else.

So the answer to the rung below’s question is that the offset enters the value through one bit, and only on half the runs. The descriptor is recording four distances. Three of them never reach the value at all, and the fourth reaches it modulo two.

Stated that way it sounds like a negative result and it is not. “Not at all” was one of the three answers on offer and would have been a genuine finding — it would have said the descriptor’s distances are decoration and the reading should be thrown away. “Smoothly” would have been the best case, a value that moves with the offset and can be interpolated. What actually happens is a third thing, and it is the one that says the descriptor is measuring the right place and the wrong quantity: something at the junction matters, and it is a parity rather than a distance.

The parity class is worth one guard. “The value reads the offset’s parity” and “the value reads nothing” are the same statement if the two parity classes happen to agree, so the sweep checks that every odd-run family really does take two values rather than one. All hundred and thirty-five do; a family that flattened would be a constant family miscounted, and it would refuse to draw.

The two classes are also both large, which is the other thing a law like this can quietly lack. A hundred and eight against a hundred and thirty-five is close enough to even that neither is a handful of special cases, and the split follows the run parity rather than the shape size — there are constant families among the smallest crosses and among the largest, and parity families likewise. A law that held on the small shapes and failed on the big ones would be a law about small shapes.

Why the run’s own parity should be the thing is not something this page can answer, and there is a shape of explanation available that should be resisted. Domineering’s two players place dominoes along the two axes, so parity arguments are everywhere in it and it is easy to wave at one. But the parity that matters here is of the run being slid along, not of the arm doing the crossing, and the sweep says so directly: the crossing row makes no difference to which class a family falls in. Grouped by whether the arm above the crossing is odd or even, and the arm below, the four groups split constant-to-parity in almost exactly the same ratio. It is the long run’s length and nothing else.

What the descriptor is doing #

There are two ways for a reading to fail to be the value, and the descriptor manages both at once on the same shapes.

It is too coarse: the rung below found nineteen groups it leaves unseparated, three shapes sharing every descriptor and not sharing a value. And it is too fine: on two hundred and sixteen of these two hundred and forty-three sweeps it distinguishes offsets the value treats as identical, five hundred and forty surplus readings in all, with the worst a ten-by-two cross where the descriptor takes five readings and the value takes one.

Neither is a complaint. A reading that separated exactly what the value separates would be the value, computed some other way, and the point of a reading is that it is cheaper than the thing it reads. What the two failures together say is what the descriptor is: a geometric summary that overlaps the value rather than approximating it. It sees distinctions the value ignores and misses distinctions the value makes, and the useful question is not how close it gets but which of its parts are load-bearing.

This sweep answers that for one part. Of the four distances at a junction, the value uses the parity of one pair and nothing else — so a descriptor recording 2/4 and one recording 3/3 are, as far as the value is concerned along a sweep, the same reading, and a descriptor recording 1/5 is a different one. That is a strictly smaller object than the descriptor and it is not the descriptor’s own quotient by anything obvious.

A third class that was not there #

The first version of this sweep ran further — to crosses of thirteen cells — and reported something better than the law above. Twenty-one families where the value did neither of the two things, taking three, four, even five distinct readings as the crossing slid. A third class, and the interesting one, since two classes decided by a parity is nearly a formula and a third class is a phenomenon.

There was no third class.

A Domineering position on this site was a bitmask held in a number, one bit per square of the bounding box, and the shift that builds it is a thirty-two bit operation. A box of more than thirty-one squares therefore gave two different squares the same bit. Every one of the twenty-one families had a bounding box over the limit — six by six, seven by five, nine by four — and every family under it was clean.

What caught it was a symmetry, not a size. Reflecting a Domineering region left to right cannot change what it is worth: the move rule is the same in the mirror, so the mirrored position has the mirrored game tree and the same value. A six-by-six cross was coming back worth −1/2 with its own mirror worth −1∗. The values were plausible, the pattern they made was plausible, and the only thing wrong with them was that a fact about the game said they could not both be right.

The failure was silent and it was old, and it was not only waiting. The site’s shape catalogue reaches eleven cells, and an eleven-cell staircase has a six-by-six box — 1,741 of the 46,924 shapes at that size are over the limit, and two of this site’s own pages walk the catalogue that far. Their figures were drawn from corrupted values for those shapes and no gate could see it. Nine and ten cells are clean, at twenty-five and thirty squares, which is why nothing smaller had ever shown a symptom.

The fix is to stop indexing by the box. A shape’s cells are few even when its box is large, so a position is now one bit per free cell with the adjacency worked out from the cell list, and an eleven-cell shape needs eleven bits whatever shape it is in. The old route still exists for rectangles and now refuses a board it cannot represent, so the bug cannot come back through it. And every cross on this page is evaluated beside its mirror as a standing check.

The sweep above is wider than it would otherwise be because of that fix: the twenty-one families that were the artefact are now correctly evaluated, and every one of them falls into the two classes with everything else.

It is worth naming what made it dangerous rather than merely wrong. Nothing about the twenty-one families looked broken. The values were legal Domineering values, of the right rough size, arranged in patterns that would have made a paragraph — and the paragraph would have said that the offset enters richly on large shapes and simply on small ones, which is exactly the kind of claim a reader has no way to check. Every claim on this site is given a test it could fail, and this is the first time on this anchor that the test which fired was one about the evaluator rather than one about the game.

The two essays drawn from the corrupted catalogue were checked afterwards and their numbers are unchanged — the affected shapes were never among the hottest at their size, so nothing they claim moves. That is luck rather than correctness, and it is the reason to say so here rather than quietly.

It is also the reason to state what bounds a sweep. This one is bounded by how long a Domineering evaluation takes and by nothing else now, where before it was bounded by an arithmetic constraint nobody had noticed, and a reader should be able to tell those apart.

What is left of the descriptor #

Three rungs of this anchor have now looked for a reading that gives the value without computing it, and the honest position after this one is a little worse than it was.

The run-length multiset leaves twenty-one groups ambiguous. The junction descriptor separates nineteen of them and leaves two, which was the rung below’s result and is a good one. This page adds that within the descriptor, along the one axis it makes movable, the value uses a single bit of what is recorded — so the descriptor is not close to the value in the way a good approximation is close to a function. It is a different object that agrees with the value often.

That is worth knowing before anybody tries to extend it. The obvious next move from rung ten is to enrich the descriptor until the last two groups fall, and this page says what that would buy: a finer reading of a variable the value already declines to read finely. The last two groups are three shapes and their transposes, and if they are separated by adding distances to a descriptor whose distances the value ignores, the separation will be an accident.

The same warning applies to the descriptor’s own success. Nineteen groups out of twenty-one is a good score and it was earned on a census of a thousand and forty-two shapes; a reading with seven hundred and twenty-one cells has a great deal of room to score well by being nearly injective. What this page adds is a measurement of how much of that fineness is doing work — along the one axis where the question can be asked, none of it beyond a bit. That does not retract the nineteen. It says the nineteen were bought with something other than the four distances, and nobody knows yet with what.

Something else is going on in those two groups, and it is not geometry at this resolution.

There is one more thing this sweep settles and it is worth stating plainly, because it removes a possibility rather than adding one. The value along a sweep is not merely nearly constant on even runs, with the movement hiding below some resolution: it is exactly constant, on every one of the hundred and eight, in canonical form. Domineering values here are numbers and stars and sums of them, compared exactly rather than numerically, so “the same” means the same game and not the same to within a rounding. A reading that failed to move the value by a sixteenth would still be a reading that moved it.

Where the ladder goes next #

The domineering anchor has eleven 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, where the runs meet, and now what the descriptor’s own variable does to the value.

The rung above is the parity itself. The law here is stated over crosses, which have one junction, and the natural test is whether it survives a shape with two: slide one crossing of a shape that has two crossings, holding the other fixed, and see whether the value still reads one bit. If it does, the parity is a property of a junction and the descriptor should be recording it in place of the distances. If it does not — if two junctions interact, so that the bit one of them contributes depends on where the other sits — then the value is not a function of the junctions taken separately, and the reason the descriptor has seven hundred and twenty-one cells is that it is trying to be one.

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 that works. And the values of every small board is the census all of this is measured against — worth reading beside a page whose central number turned out to depend on how many squares fit in a machine word.

Further off, a board that is a sum of its regions is why any of this matters beyond the single shape: a region’s value is only worth reading off its shape because regions add, and a reading that gave the value of an isolated cross and nothing else would be a curiosity. And two errors that cancel is the other page on this anchor about a result that was right for a reason nobody had checked, which is the same species of luck as a bounding box that never happened to exceed thirty-one cells.