The rows that cancel

A difference the rows cannot predict priced the failure it inherited. Dawson’s diagram, with captures compulsory, is a board of rows separated by empty files that no move ever crosses, and it is still not the sum of its rows, because the rule that a capture must be made ranges over the whole board. Over fifty arrangements of rows the difference between the whole board and the sum of its rows took three values — nought, ∗2 and ∗3 — and no property of the rows predicted which. One rule survived everything the sweep could throw at it. Every one of the eleven failures carried an even number of rows, and every one of the twenty-one diagrams with three, five or seven rows was exactly the sum of them.

That essay was careful to call the rule fitted rather than derived, and it ended by asking for the mechanism: why an odd number of rows should be safe. The mechanism turns out to exist and to be something other than parity. And the first thing it predicts is a diagram the sweep did not reach, with three rows, that fails.

Four files, three files, one file #

The diagram is a row of four files, a row of three and a row of one, with an empty file between each pair: eight files of pawns on a board ten files wide. It is one file past the edge of the sweep, which valued every arrangement of seven files of pawns and only a chosen handful of wider ones.

The search visits 4,153,158 positions and returns ∗ for the whole board. The rows alone are worth nought, ∗2 and ∗, which add to ∗3. Three rows, and the difference is ∗2. The parity rule said this could not happen, and it does not survive the first diagram chosen to test it from the right direction.

The direction matters, because the rule had been tested before and had passed. The previous sweep extended itself specifically to check the parity, with long-and-short shapes reaching seven rows, and those checks all came out as predicted. What they had in common was the material they were built from: a long row padded out with rows of one file. The diagram that breaks the rule is built differently. It contains a row of four, and a row of four on its own is worth nought — the only row up to seven files that is. Every other row is worth ∗ or ∗2.

And the value it comes out at is not arbitrary. Three files beside one file, the smallest failure in the original table, is worth ∗ as a board and ∗3 by its rows. Four beside three beside one is worth ∗ as a board and ∗3 by its rows. The row of four changed nothing. It is worth nought alone, and adding it to a board that does not add left the board exactly as wrong as it was.

Two more three-row diagrams were valued past the sweep’s edge to see whether that was a coincidence of one shape. Five beside two beside one, 3,409,812 positions, is worth ∗ and is the sum of its rows. Three beside two beside one was already in the table and adds. So three rows can go either way, and whether they add is not a property of the number three.

Two deletions that a sum allows #

A sum of games has two cancellation laws that a reader uses without noticing. A part worth nought can be deleted, because a second player answers every move in it inside it and never loses a tempo there; and two parts that are negatives of each other can be deleted together, because every game has a negative and a game beside its negative is nought. A row of Dawson’s diagram is symmetric under a half-turn of the board, which exchanges the colours and reverses the files, so each row at its start is its own negative, and two identical rows are a game and its negative.

Neither law has any business holding on the compulsory board, because the compulsory board is not a sum. The proof of each law is a strategy that answers a move in a part with a move in the same part or its partner, and compulsion forbids exactly that: a player whose opponent has just set off an exchange in one row must capture in that row, whatever the strategy would have answered elsewhere. What can be struck out is the general version of the question — when G + X = H + X licenses G = H — and its answer depends on the arithmetic of a sum, which is the thing missing here.

They hold anyway, on everything checked. Delete the row of four from four, three and one, and the board is worth what three and one is worth. Delete it from four, two and two, and then the two rows of two: what is left is nothing, and the whole board, over 4,057,125 positions, is worth nought. Delete the pair of twos from three, two, two and one, and what is left is three and one — and the whole board is worth ∗, as three and one is, with the same ∗2 difference. Three, three and two reduces to a row of two, and is worth ∗, as a row of two is. The deleted pairs in those last three are rows with exchanges in them, where a step sets off a forced run of captures, which is precisely where a strategy that answers locally ought to break.

Every diagram is worth its kernel #

Call what is left after both deletions the diagram’s kernel. It is a list of distinct rows, none of them worth nought — possibly a single row, possibly nothing at all.

Of the 55 diagrams valued — the fifty of the original sweep and the five past its edge — 44 reduce to something smaller, and for every one of the 44 the kernel has also been valued, either because it is a single row or nothing, or because it is in the table. Each is worth exactly what its kernel is worth. Not one exception, over boards from three files to fifteen and from two rows to seven.

The groups are where the parity used to live. Nine diagrams reduce to a row of one: one file three times, four and one, two and two and one, three and three and one, one file five times, four and one and one and one, and three more. Seven of those have an odd number of rows and two have an even number, and all nine add, because a diagram worth what a single row is worth is worth the row’s own value, which is what the sum of its rows comes to after the pairs and the noughts have cancelled. Five diagrams reduce to three and one: three and one itself, three with three ones, three with five ones, three with two twos and a one, and four with three and one. Four have an even number of rows and one has an odd number, and all five fail, by the same ∗2.

So a diagram’s difference is its kernel’s difference. Single-row and empty kernels contribute nothing; a kernel of several rows contributes whatever that diagram, valued directly, turns out to contribute. The rows that cancel cancel on both sides of the subtraction, and whatever the compulsion does to a board, it does it only through the rows that are left.

Why the sweep showed a parity #

The deletions explain the rule and the exception together, without any appeal to how many rows there are.

Deleting a pair takes away two rows, so it leaves the number of rows odd or even as it found it. Deleting a row worth nought changes the parity, but the row of four is the only such row up to seven files. So a diagram without a row of four has a kernel of the same parity it started with — and in the sweep that meant an odd diagram reduced to one row, or to three rows, and an even diagram reduced to nothing or to two rows.

Look at what that does to the table. Every odd diagram in the sweep without a row of four has a kernel of one row, which cannot fail, or a kernel of three rows — three, two and one — which happens to add. Every even diagram without a row of four has a kernel of nothing, which cannot fail, or of two rows, which can. That is the whole of the parity. The rule was the kernels’ parity seen through the rows’, and the rows’ parity matched the kernels’ because the sweep was built almost entirely from rows that cancel in pairs — rows of one and two padding out a long row, chosen because they were cheap to search.

The rows of four were the only place the two parities could come apart, and in the sweep they came apart only on diagrams that add. Four and one, four and two, four and three each reduce to a single row. Four, two and one reduces to two and one, which adds. The first diagram where a row of four turns an odd diagram into a failing kernel is four, three and one — which needs eight files of pawns, one more than the sweep’s every-arrangement limit. The counterexample was sitting exactly one file past the edge of the range, in the one kind of diagram the range could not have shown.

None of this was visible as a rule about rows because the deletions are not a rule about rows. They are a rule about values, and a table organised by the number of rows cannot see them.

A row and its mirror #

The deletion of identical rows is the stronger claim of the two, and it can be pressed further than the start position.

A row of two files reaches 41 states from its start under compulsory capture; a row of three reaches 426. Take any one of those states, add it to a diagram together with its half-turn — which is its negative, in the same way a row at its start is its own negative — and search the whole board. Beside a row of one, beside a row of three, and beside three and one, which does not add, every one of the 41 states of a row of two disappears: the board is worth what the diagram is worth. Beside a row of two, all 426 states of a row of three disappear too.

The states that matter most are the ones in which a capture is already pending, because there the compulsion is live in the pair from the first move. Sixteen of the 41 states of a two-file row have one, and 122 of the 426 of a three-file row. Every one of them vanishes as completely as the quiet states. Three and one, with a pair added beside it, is still worth ∗ and still differs from the sum of its rows by ∗2: the pair leaves the board exactly as wrong as it found it.

This is a measurement and not a proof, and the reason a proof is not obvious is worth saying. The usual proof that a game beside its negative is nought is the mirror strategy of every game has a negative: answer each move in one copy with the mirrored move in the other. Here the mirror move is often illegal. When the opponent steps in one copy and sets off an exchange, the answer has to be a capture in that copy, and the exchange then runs to its end with the opponent choosing at alternate moves; mirroring it afterwards in the other copy hands the choices to the other player. Misère play has no negatives shows a rule change that breaks the mirror outright. Compulsion is a rule change that breaks the mirror’s proof and, on everything searched, leaves its conclusion standing.

The lock fires everywhere and decides rarely #

The earlier essay proposed watching the coupling at work rather than valuing another board, and that measurement is cheap enough to make on the small diagrams.

Two things come out of it. The first is structural and makes everything above easier to believe: no position ever has two rows in the middle of an exchange for the same side. A capture becomes available only when the other player has just stepped next to an enemy pawn, and that step is in one row; the run of captures it sets off stays in that row because no file is crossed. So the lock is always a single row holding the rest of the board still, never two rows interfering with each other. That is exactly the shape independence is a claim would call a rule joining parts that are otherwise apart, and it is a much simpler shape than the failures suggested.

The second is that the lock changes values constantly and the start position barely notices. On two and one, four of 123 positions are worth something other than the sum of their rows. On three and three it is 1,932 positions, on three, two and one it is 2,154 — and both of those diagrams are exactly the sum of their rows at the start. On three and one it is 31 positions and the start fails. The count of local changes does not predict the failure, and neither does the count of positions where the lock forbids a step.

What the deletions say about this is that most of those local changes are inside pairs or inside rows worth nought, where they cancel against each other by the time the search reaches the start. A change of value deep in the tree is not a change of value at the root unless something carries it up, and the kernels are what carry it.

What is left to explain #

The deletions reduce the question; they do not answer it.

Eleven diagrams in the whole range are their own kernels. Six fail: three and one, three and two, five and one, five and two, five and three, seven and one. Five add: two and one, six and one, six and two, and the two three-row kernels, three, two and one and five, two and one. Every failure is a pair containing a row of three, five or seven. That is a pattern on six cases and it is not stated here as a rule — the pairs that would test it, seven and two, six and three, five and five, three with a row of eight, are each past ten million positions.

What the deletions do say is how much work is left. Before them, a reader asking whether a diagram adds had to search the diagram. After them, the reader deletes the rows of four and the pairs, and searches only what is left — and if what is left is one row or nothing, there is nothing to search. Five and one and one and one is worth what five and one is worth; three and a long tail of ones is worth what three alone or three and one is worth, according to whether the tail is even or odd. The diagrams that need searching are the irreducible ones, and there are far fewer of them than diagrams.

The rules the values are computed under #

Normal play throughout: the player with no move loses. The board is Dawson’s three ranks — White’s pawns on the first, Black’s on the third, the middle rank empty at the start — with a pawn stepping straight ahead onto an empty square and capturing diagonally forward, and a capture available anywhere on the board forbids every step everywhere. No pawn reaches a far rank while captures are compulsory, so promotion does no work. Rows are separated by exactly one empty file; a difference the rows cannot predict established that a second empty file changes neither the value nor the count of positions. Every value is the canonical form returned by exhaustive search, and each row is valued alone with captures compulsory inside it, which is what makes ·137 its Grundy sequence, as the capture that has to be made verified. The half-turn of a row is the board rotated through a half-turn about the row’s centre, which exchanges White and Black and reverses the files; it is the row’s negative because the rules treat the two colours symmetrically.

Under Dawson’s own convention, the one he actually used, there are no negatives and nothing to subtract, so neither deletion can even be stated there. Everything here belongs to normal play, as the previous two measurements of this board did.

What the search cannot show #

The deletions are measured, not proved. Forty-four diagrams and two families of mirrored states agree with them, and no argument here shows that compulsory capture must respect them. The obvious argument fails, for the reason given above, and an argument that works has to explain why an exchange that hands the choices to the other player still lands where the mirror would have put it.

The range is still small. The largest diagrams valued are around five million positions for three rows and eight million for two; three and one, beside every state of a row of three and its half-turn, was too large to search. A pair of long rows — five and five, seven and seven — has never been put beside anything.

A kernel of several rows has to be searched. The deletions say nothing about which irreducible diagrams fail, and the six that do are not enough to state a rule about them.

The surprise: the rule was right about the wrong thing #

The parity rule fitted every one of fifty diagrams, survived shapes built to break it, and is false. What makes the failure instructive is that nothing about the rule was carelessly read. Odd diagrams in the sweep really did all add, and they really did add for a reason — the reason just was not the number of rows. Rows of one and two cancel in pairs on the compulsory board as they would in a sum, and a sweep padded with them turns a statement about kernels into a statement about parity, because every deletion it performs takes away two rows at a time.

That is a hazard specific to sweeps that are cheap where they are wide. The previous essay noted that a diagram’s cost is set by its longest row, so many short rows are almost free — which is exactly why the long-and-short shapes were chosen to test the rule, and exactly why they could not have refuted it. Every diagram they added was a kernel already in the table with pairs of ones attached. The test of the rule was built from the material the rule could not see.

And the result reverses the direction of the previous measurement. A difference the rows cannot predict found the compulsory board less like a sum than its separated rows suggest: values that are right and not enough. Here it is more like a sum than its rule book suggests. The compulsion breaks the strategy that proves cancellation and the cancellation holds anyway, on both of the laws a reader would most want and on states where the compulsion is already live. What it does not respect is addition of distinct rows that do not cancel — and that is a much narrower failure than the one that was counted.

Still open: why the mirror survives the compulsion #

Two questions are left and the first is the better one.

The deletions want a proof, and the place to look is the exchange. When one copy of a pair is in the middle of an exchange, the other is frozen, and the exchange’s end state is chosen by both players alternately. For the mirror to survive, it must not matter which player chose which capture — the end states reachable from a run of captures must be equivalent under the half-turn in a way that lets the second copy’s exchange land on the negative of the first’s, whoever chooses. That is a claim about single rows, checkable row by row: for each step that sets off an exchange, compare the set of end states with the set of half-turned end states of the mirrored exchange. If they match up to value, the deletions have a proof; if they do not, the searches above have found a coincidence that a longer row will break.

The second is the irreducible diagrams. Six of eleven fail, every failure has a row of three, five or seven, and both three-row kernels add. The next measurements are the pairs that would test whether an odd row is necessary for a failure — six and three, seven and two — and the three-row kernels with a failing pair inside them, five, three and one above all, which at around forty million positions needs a search that keeps only one row’s states at a time, as the lock itself does.