A difference the rows cannot predict

A wall the pawns cannot cross settles what Dawson’s diagram is and is not. Two rows of files separated by a file with no pawn on it are separate game trees — 1,616 moves examined and not one crossing the gap — and the diagram is still not the sum of its rows, because the rule that a capture must be made is a sentence about the mover and ranges over the whole board.

It ends by naming what it did not do. The failures were counted and never priced. On the diagrams where the rows do not add, the whole board is worth one thing and the rows add to another, and the difference between them is a quantity nobody had computed. If that difference were nought except in some describable circumstance, the compulsory diagram would be a sum with a correction and the correction could be written down. If it were a different number on every shape, it would not be.

It is neither. Over 50 diagrams and 63,408,981 positions it takes three values, no property of the rows predicts which, and the one thing that does predict it is a parity nobody would have guessed at.

Subtracting one board from another #

The difference is a subtraction, and a subtraction is a thing that has to be earned.

Short games under normal play form a group. Every position has a negative — the same position with the players’ roles exchanged — and a position added to its negative is worth nought, which is what comparing positions is built on and what makes G − H a legitimate object rather than a figure of speech. Dawson’s diagram is symmetric under turning the board upside down, so a diagram is its own negative, and the subtraction is available without any extra care.

So for each diagram there are three quantities. The whole board, found by searching every position the diagram reaches and taking the canonical form of what comes back. The sum of its rows, found by valuing each row on its own and adding. And the difference, being the first less the second, canonicalised. A diagram adds exactly when that difference is nought.

The range is wider than the count of failures needed, deliberately, and it is wide in two directions at once. Every arrangement of rows within seven files of pawns is there. So is every arrangement of two rows within nine, which costs 41.8 million of the 63.4 million positions — two thirds of the whole sweep — and is the reason the set of values is what it is. And so are the long-and-short shapes, a row of three or five beside five or six rows of one, which reach fifteen files of board and seven separate rows for a few hundred thousand positions apiece.

That last group is cheap for a reason worth knowing before anybody budgets a sweep like this. A diagram’s cost is set by its longest row and not by its width. A row of seven files alone is 2.7 million positions; seven rows of one file each, on a board thirteen files wide, is 2,187. So the sweep reaches boards twice as wide as its most expensive one, and the shapes it reaches there are exactly the shapes that test the only rule the numbers support.

Thirty-nine of the fifty diagrams add. Eleven do not. And the difference on those eleven is nought, ∗2 or ∗3 — three values out of the infinitely many a game could be, which is the first thing worth noticing and the least useful. A quantity confined to three values still has to be predicted before a reader can add anything.

Seven diagrams with the same rows, and two answers #

The obvious thing for the difference to depend on is what the rows are worth, since that is what a reader adding rows has in front of them.

It does not.

Seven of the diagrams have two rows each worth ∗. Five of them — one file and one, two and one, two and two, six and one, six and two — are the sum of their rows exactly. The other two — five files and one, five and two — are not, and the difference on each is ∗2. A reader told that a board carries two rows each worth ∗ has been told everything the parts can say and cannot distinguish the five from the two.

The second group is sharper still, because it splits three ways rather than two. Four diagrams have one row worth ∗ and one worth ∗2. Three of them — three files and one, three and two, five and three — have difference ∗2. The fourth, seven files and one, has difference ∗3.

A third group says the same thing at four rows rather than two. Five diagrams carry four rows each worth ∗ — one file four times, two and one and one and one, two and two and one and one, two and two and two and one, and five and one and one and one. The first four add exactly and the fifth does not.

That is the answer to the question a wall the pawns cannot cross leaves, and it is a flat no. The difference is not a function of the rows’ values, and the demonstration is not a subtle one: it is two diagrams whose parts are indistinguishable and whose corrections differ, with five more on the other side of the same line.

Which is worth setting against what a value is supposed to be for. Every impartial game is a Nim heap is a theorem about a component of a sum, and the point of computing a component’s value is that the value is all a reader needs — the component can then be forgotten. Here the row values are computed, they are correct, and forgetting the rows loses information the board still depends on. The value is not sufficient because the board is not a sum, and that is a different failure from a value being wrong.

Every failure has an even number of rows #

If the coupling were a matter of rows interfering pairwise, more rows would mean more interference.

The count does not climb, and what it does instead is alternate. Six of sixteen two-row diagrams fail. None of eleven three-row diagrams fails. Three of nine four-row diagrams fail. None of eight five-row diagrams fails. Two of four six-row diagrams fail. Neither seven-row diagram fails.

A coupling firing once per pair of rows would give three rows three chances to go wrong against two rows’ one, and three rows go wrong not at all. A coupling that accumulated would make the share climb, and the share is 38% at two rows, 33% at four and 50% at six with nothing at all between them.

The odd side is not a thin sample. Twenty-one diagrams carry three, five or seven rows; they run from one file three times up to a row of three beside six rows of one, across thirteen files of board; their rows carry every value a single row produces — nought, ∗ and ∗2 — and their longest rows run to five files. Every one of the twenty-one is exactly the sum of its rows.

So the failure is not about how many rows there are in any quantitative sense. It is about the parity of how many, which is a different kind of dependence and not one a coupling between neighbours would produce.

Adding a row takes the difference away, and another brings it back #

The clearest case is a single diagram watched while it grows.

Three files and one file is worth ∗ whole and ∗3 apart: a difference of ∗2. Add a third row of one file and the board is worth ∗2, the rows add to ∗2, and the difference is nought. Add a fourth and the board is worth ∗ against rows adding to ∗3, and the difference is ∗2 again.

The same thing happens one file over. Three and two has difference ∗2; three and two and one adds exactly; three and two and one and one has difference ∗2.

That rules out the last comfortable reading of the numbers. A correction that accumulated — that a reader could carry from a smaller board to a larger one, or bound by the number of parts — would not vanish when a part is added. The difference is not monotone in the parts, and a diagram that adds says nothing about the diagram one row larger. It is a property of the whole arrangement, computed from the whole arrangement, which is exactly what a value is supposed to spare a reader from computing.

The parity is the one rule the numbers support, and the reason to believe it rather than merely notice it is that the sweep was extended to test it. The shapes that do the testing are the long-and-short ones: a row of three beside four, five and six rows of one file each. Those carry five, six and seven rows, they cost between thirty thousand and three hundred thousand positions apiece, and the rule predicts each before it is computed. Five rows: adds. Six rows: fails, at ∗2. Seven rows: adds. All three come out as predicted, and the same triple with a row of two added behaves the same way.

A rule read off a handful of failures and then confirmed on shapes chosen to break it is a different object from a rule read off a handful of failures. It is still a rule about fifty diagrams, and it is still without an explanation.

The ninth file, and a value nothing below it produces #

A rule fitted to small boards is the characteristic failure of everything written about this game. A chess problem that turned out to be an octal game is about a sequence that is eventually periodic with five values below the start that disagree with their repeats and always will, and the word doing the work there is eventually. The same care is owed here.

Stopped at eight files, the sweep finds the difference taking two values, nought and ∗2, on thirty diagrams. Every failing diagram then has one row worth ∗2 or one row of five files, and a reader could write down a rule that fits all thirty.

The ninth file kills it. Seven files beside one is worth nought as a board and ∗3 as a sum of its rows — 8,006,301 positions to establish, and a disagreement not about a value but about the winner, since nought is a second-player win and ∗3 is a first-player one. It is the only diagram in the range whose difference is ∗3, and it is the largest two-row diagram the search reaches.

Two things follow from that, and the second matters more than the first.

The first is that the set of values the correction takes is larger than any smaller sweep shows, so nothing here is a statement about the values it takes — only about the values it takes within ten files.

The second is about the shape of the evidence. The three-file rows and the five-file rows are where the failures are on small boards, and that looked like a fact about those rows. The seven-file row is worth ∗2, exactly as the three-file row is, and it behaves differently from it. So the failures are not indexed by the rows at all, which the collision group said already and which this says again from the other end, with a new value rather than a new pair.

A wider gap changes nothing, and it is counted anyway #

One question the two-row search raises and leaves is whether the rows have to be adjacent — whether two empty files between them behave as one does.

They do, and the reason is the reason the first gap is a wall. A pawn reaches a file by stepping straight ahead within it or by taking diagonally onto it, and taking requires an enemy pawn standing there. An empty file never has one and nobody can put one there. A second empty file is unreachable for exactly the reason the first is, and a third would be too.

That argument is two sentences and it is the kind that is wrong once in ten times, so the boards were searched instead. Three diagrams were computed at one empty file and at two: the values agree and, more tellingly, the position counts agree exactly — 1,278 either way on three files and one, 100,404 on five and one, 127,005 on four and two. The same number of positions, not merely the same verdict, which is what a genuinely inert file produces and what a file doing any work at all would not.

So the gap is not a parameter. Everything on this page is about which rows sit on the board and nothing about where.

What the difference is made of #

The mechanism is not new here and is worth having in view while the numbers are being read.

Compulsory capture says that a player with a capture available must make one, and available ranges over the whole diagram. A capture in the left row therefore removes a step in the right, at no cost in distance and with nothing travelling between them. Independence is a claim makes the general point and this is the concrete instance: the parts are as separate as parts can be and the rule book joins them.

What the numbers above add is that the joining is not proportional to anything. The coupling fires at a measurable share of positions — a fifteenth of them on the smallest diagram and better than a third on three rows against three — and the share climbs steadily with the size of the board while the difference does not climb at all. Most positions where the coupling fires are positions already decided, so a rule that bites often can change the answer rarely, and a rule that bites in proportion can change the answer in no proportion whatever.

This is the opposite of the ordinary case. The board falls apart, and the arithmetic changes is what a decomposition usually looks like: the board separates, the sum is exact, and the work is establishing the separation. A wall an amazon can walk through and how wrong a nearly-independent split is are the usual failures, where something crosses and the split was never real. Here the split is real, the crossing never happens, and the sum is wrong anyway.

What the search cannot say #

Ten files is the limit and it is a hard one. The whole sweep is 51,320,928 positions and three quarters of them are the four two-row diagrams of nine files. Each extra file multiplies the positions by roughly ten, so eleven files — which is what a five-row diagram or a two-row diagram of eight and two would need — is out of reach here by two orders of magnitude. Every statement above is a statement about thirty-four shapes.

The parity rule is fitted, not derived. Eight failures against twenty-six successes is not many positives, and the number of rows is even is one of several rules that fit them. It is stated because it is the only one that survives all thirty-four, and it should be read as the thing a larger sweep would test rather than as a finding.

Three values is a floor. The range holds nought, ∗2 and ∗3. The two-row diagrams of ten files — eight files beside one, seven beside two, six beside three, five beside four — are where a fourth would appear next, and each is around a hundred million positions, an order of magnitude past anything here.

And the parity is a rule with no mechanism. Nothing on this page explains why an odd number of rows should be safe, and a rule that predicts correctly and explains nothing is a rule that can stop predicting at the first shape outside the range.

The convention the values are computed under #

Normal play throughout: the player with no move loses. That is the ending ·137’s Grundy values are computed under, the ending the two-row search uses, and the only ending in which the diagram has a value to subtract at all.

The convention Dawson actually used is the other one, and under it a row does not carry a number — what replaces it is a classification whose size grows with the board, so whole board less sum of rows is not an expression that can be written. The measurement here therefore belongs, as the one below it does, to the ending Dawson did not use. The reduction to ·137 that the capture that has to be made verifies holds under both; the arithmetic does not exist under one of them.

A pawn on its far rank has no move in this model and no pawn ever reaches one while captures are compulsory, so the no-promotion rule does no work in any number above. That was established for single rows and holds here for the same reason: the pawn that could capture onto the far rank is always taken first.

The surprise: a value that is right and not enough #

The usual reason a sum fails is that one of its parts was valued wrongly, or that the parts were never apart. Neither is what happens here.

Every row value on this page is exact. Each was computed by searching the row alone, each is the canonical form of the position, and each would be accepted without argument anywhere in this subject. The rows are genuinely separate: no move crosses between them, over every position of every diagram, counted rather than argued. And the sum of those exact values, of those genuinely separate parts, is the wrong answer on eleven of fifty boards, by an amount nothing about the parts predicts.

What that costs is precisely the thing a value is for. A value is a licence to forget the position: once a row is worth ∗2, the row can be put away and the symbol carried. Here the symbol is right and the licence does not come with it — a reader who forgets the rows and keeps the values has thrown away what the board still depends on, and no amount of care in computing the values repairs it, because the values were never the problem.

That is a hazard with no symptom at the level of the parts. It cannot be found by checking a value, by checking the independence of the regions, or by looking at the board, and all three of those checks pass here. What has to be checked instead is whether any sentence of the rules quantifies over the whole position, and Dawson’s diagram has exactly one that does. One sentence, written for a chess magazine in 1934 with no theory of sums in view, is the reason the heap game exists and the reason its arithmetic does not apply.

Still open: a tenth file, and why an odd number of rows is safe #

Two questions are left and they pull in opposite directions.

The first is the set of values. The correction is nought, ∗2 or ∗3 over everything here, and ∗3 appears exactly once, on the widest two-row diagram the search reaches. That is the shape of a range that has just begun to show something rather than one that has finished. The measurement is the ten-file row — eight files beside one, seven beside two, six beside three, five beside four — at roughly a hundred million positions each, which needs a search that does not keep every position it visits.

The second is the parity, and it wants an argument rather than another diagram. A rule that predicts eleven failures and twenty-one successes across fifty shapes is unlikely to be an accident, and nothing here says what it is about. The thing to look at is the exchange: a step in one row sets off a forced run of captures whose length is always odd, and the compulsion couples the rows precisely while such a run is in progress. Whether the number of rows enters through the parity of how many runs can be interleaved is a question about the mechanism, and it would be settled by watching the coupling fire rather than by valuing another board.