A wall the pawns cannot cross and the rule can

The capture that has to be made takes Dawson’s 1934 pawn diagram and plays it as chess rather than quoting it as the octal game ·137. On a single row of files the two agree: from one file to twelve, under both endings, the same player wins — and the agreement rests on one clause of the diagram the octal code never mentions, that a capture, when one is available, must be made.

It ends by naming what a single row cannot settle. A diagram with two rows of files on it, separated by a file with no pawn, is the position an octal game is really about: ·137, the game Dawson’s puzzle turns out to be, on heaps a and b is a heap game with two heaps, and a heap game’s whole content is that heaps can be evaluated apart and added. Whether a chess diagram can be is a different question and it has a different answer under each of the two capture rules.

Without the compulsion the rows add, on every shape checked. With it they do not. And it is the second rule that ·137 describes.

What a row is worth, rather than who wins it #

The first thing a two-row diagram needs is a value for one row, and a winner is not one.

A row of five files with captures compulsory is worth ∗. The heap of five in ·137 has Grundy value 3, so ·137 calls the same object ∗3. Both are non-zero, so both name the same winner, and the earlier check — twelve boards, both endings — could not have seen the difference.

The difference is real and it is exactly the kind that matters. Two positions with the same winner can behave differently in a sum, which is the whole reason outcomes do not add and the whole reason every impartial game is a Nim heap is a theorem rather than a definition. ∗ added to ∗ is nought and ∗3 added to ∗ is ∗2, and those are opposite verdicts about a two-row board. So the reduction that survived at the level of the winner has a crack in it at the level of the value, and the crack opens at the first board with two rows on it.

The reason is visible in the move correspondence the earlier essay established. One move of ·137 is an odd number of pawn moves — a step, then a forced exchange that runs to its end. An odd number of moves passes the turn exactly as one move does, which is why the winner is preserved. It does not preserve anything else: the positions halfway through an exchange are positions of the pawn game with values of their own, and a value is computed from all of them.

The wall, and what it stops #

A diagram with two rows on it has a file with no pawn between them, and the first question is whether the pawns can get across.

A pawn moves straight ahead into an empty square or takes diagonally onto the next file, and taking diagonally needs an enemy pawn standing there. An empty file never has one, and neither player can ever put one there, because to reach the empty file a pawn would have to take onto it and there is nothing on it to take.

That argument is short and it is the kind that is wrong once in ten times, so it was counted instead. Over every position reachable in the two-row diagram, 1,616 moves were examined and not one crosses the empty file. The rows are separate game trees: the moves available in one are exactly the moves available in that row played alone.

Which is the hypothesis a sum needs, and it is not sufficient. Independence is a claim makes the point in the abstract; this diagram makes it concretely, and the thing that breaks it is not a pawn.

A rule that reaches across an empty file #

Compulsory capture is not a statement about a pawn or about a file. It is a statement about the mover: a player with a capture available must make one. The word have ranges over the whole diagram.

So a capture available in the left row removes the step that was available in the right row. Nothing has crossed the empty file — the two rows still cannot touch — and yet the move list in one row now depends on what is standing in the other. On the diagram of two files and one, that happens at 4 of the 16 board-and-mover pairs the diagram reaches; on the diagram of three and one, at 13 of 42; on three and two, at 25 of 89; on three and three, at 78 of 209; on five and one, at 65 of 220. The share climbs rather than thins — a fifteenth of the pairs at one file against one, a quarter at two against two, better than a third at three against three.

This is a different failure of independence from the ones a decomposition usually meets. A wall an amazon can walk through and how wrong a nearly-independent split is are both about regions that look separate and are not, because a piece or a threat crosses between them. Here nothing crosses. The regions are separate in every sense a board can express, and the rule book joins them.

That is worth stating as a general hazard, because a reader checking whether a position decomposes will check the board. Compulsory capture appears in draughts, in some chess problems and in a great many folk rules, and wherever it appears a board that falls into visibly separate regions is not a sum of them.

Whole, and apart #

Sixteen diagrams, each evaluated twice: once by searching the whole board, once by adding the values of its rows.

With captures optional the two answers agree on every one of the sixteen. The diagram is a disjunctive sum of its rows, in the full sense — a row can be evaluated alone, the values add, and the value of the sum is the value of the board. That is the answer to the question the earlier essay left, and it is a clean yes.

With captures compulsory they disagree on three of the sixteen. The diagram of three files and one is worth ∗ whole and ∗3 apart. Three and two is the same pair. Five and one is worth ∗2 whole and nought apart — which is not a discrepancy in a value but a disagreement about who wins, the whole board being a first-player win and the sum of its rows a second-player one.

Thirteen of sixteen agreeing is the shape to be careful with. A coupling that fires at a quarter of the positions does not change the answer at a quarter of the diagrams, because most positions are decided long before the coupling can matter. A rule that breaks additivity sometimes breaks it rarely, and a decomposition checked on three boards would have passed.

The reduction, and what it still gets right #

Against all that, ·137 is not wrong about the diagrams. It is right about every one of them.

On all sixteen diagrams the whole-board search and ·137’s exclusive-or name the same winner. The reduction is a correspondence between the pawn diagram as a whole and the heap position as a whole, and the compulsion is precisely what makes it one: an exchange is atomic because nobody may stop halfway, and an atomic exchange is one heap move.

Guy and Smith’s 1956 survey is where ·137’s values were first computed, and what that arithmetic cost prices the certificate by hand; nothing in it, and nothing since, asks what happens when two of Dawson’s rows sit on one board. So the reduction and the decomposition want opposite things from the same clause. The reduction needs the compulsion, because without it an exchange is not forced to finish and the correspondence with heaps collapses — that is what the capture that has to be made measures, and the winner changes on two, three, six and seven files as soon as the compulsion is dropped. The decomposition needs the compulsion gone, because the compulsion is what joins the rows.

Neither game has both properties. The game the heaps describe is not a sum of its rows; the game that is a sum of its rows is not the game the heaps describe. A reader who wanted both — a heap value per row, and permission to add the rows — would have to find a third rule, and there is no obvious candidate: the compulsion is the only clause of the diagram doing the work, and it is doing both jobs with the same words.

That is worth setting against the way a reduction is usually presented. Every impartial game is a Nim heap is a theorem about a component of a sum, and the reason it is stated that way is that a component’s value is only worth having if it can be added to something. Here the correspondence to a heap is exact, is verified on twelve boards, and does not license the addition — which is the one thing a heap value is for.

The exchange is where both facts live at once. Five pawn moves count as one heap move because nobody may stop in the middle, and nobody may stop in the middle is a condition on the mover rather than on the files — which is exactly the sentence that removes a step in some other row while the exchange is running.

The value that is a nimber anyway #

One thing the search settles that nothing had a right to expect: every value computed here, under either rule, is a nimber. Rows and diagrams alike come out as nought, ∗, ∗2 or ∗3 and never as a number, a switch or an infinitesimal.

That is not a small claim about a game whose two players move in opposite directions. Dawson’s diagram is partizan in form — White moves the White pawns up the board and Black moves the Black pawns down — and a partizan game has no reason to be worth a nimber. It is one here because the diagram is symmetric under reflection: turn the board upside down and White’s position is Black’s. A game equal to its own negative has value equal to its own negative, and among short games the ones that behave like that behave like Nim heaps.

So the compulsion does not cost the diagram its impartial character. It costs it additivity, which is a different thing and is the thing a heap game is for. A reader could hold every value on this page and still not be able to play a two-row board by adding, under the rule Dawson’s problem was posed with.

What the game that adds is worth #

The game with the additivity is worth having a table of, since nothing before now has had one, and its values are not the octal game’s.

A row of one file is ∗ under either rule: one White pawn faces one Black pawn, whoever moves first steps into the middle square, and the other takes it and has made the last move. A row of two is ∗ with captures compulsory and nought without them, which is the smallest place the two games part. A row of three is ∗2 with the compulsion and nought without it — the same collapse, from a value with a fight in it to a value with none. A row of four is nought either way, and a row of five is ∗ either way.

Two rows of nought are worth nought, so the optional diagram of two files and two, or of three and three, is a second-player win with nothing for either side to do about it — and the whole-board search agrees, which is one of the sixteen checks. The rows that collapse to nought are the ones where declining a capture is available to the player who would otherwise have to make it, and declining is what costs the first player the three-file board once the rule allows it.

So the game that adds is a thinner game than the one that does not. Its rows are worth nought more often, its diagrams are decided more often by a count of nonzero rows, and it is the game nobody has written about, because the game somebody wrote about in 1956 is the one with the compulsion in it and heaps to match.

What the search cannot say #

Six files is the limit, and it is a small one. The searches grow quickly: valuing every row and every diagram here means computing a value for 2,799,824 boards, and the optional searches over a board are several times the compulsory ones because a player who may decline a capture reaches positions the compulsory game never does. Every count on this page comes from diagrams of at most six files and rows of at most five, so the optional game adds is a claim about sixteen shapes rather than a theorem.

And the three failures are the ones a small range can show. A range that stopped at five files would have found two of them; a range stopping at four would have found none, and the decomposition would have looked sound.

Nothing here settles the diagram with rows separated by two or more empty files, which is the same question with more room in the middle. The coupling is a property of the mover rather than of the distance, so the expectation is that nothing changes, and an expectation is not a count.

Nor does anything here promote a pawn. The model gives a pawn on its far rank no move at all, and under compulsory capture no pawn ever reaches one, which is what makes the compulsory results independent of that choice. The optional game does put pawns on the far rank, so every optional result belongs to a model in which a pawn that breaks through is inert.

The convention the values are computed under #

Normal play throughout: the player with no move loses, which is the ending the octal game’s Grundy values are computed under and the ending the values on this page are computed under. Dawson posed his problem under the other one, and the convention Dawson actually used measures what that costs — under his rule a row does not carry a number at all, and what replaces it is a classification whose size grows with the board.

The two-row question is therefore asked here in the convention that has values to ask it with. Under Dawson’s own ending there is no value to add, so does the diagram add is not a question that can be put in the same form, and the honest statement is that the measurement on this page belongs to the ending he did not use.

The surprise: a sum needs the rules to be local, not the board #

The usual way a decomposition fails is that the parts were not really apart — a piece that can move between them, a threat counted in one region and spent in another, a group whose life depends on a point somewhere else. Every one of those is a fact about the position, and every one of them is found by looking harder at the board.

The board falls apart, and the arithmetic changes is the ordinary case: once a board genuinely separates, a sum is what it becomes. Here the board is as separate as a board can be. There is a file no pawn can occupy, no move crosses it in 1,616 tries, and the two rows have disjoint move sets at every position. And the diagram still is not a sum, because one sentence of the rules quantifies over the whole diagram.

That is a hazard with no board-level symptom at all. It cannot be found by drawing the position, it cannot be found by checking which squares a piece can reach, and it cannot be found by any amount of looking at the parts — the parts are fine. What has to be checked instead is the shape of the rule: whether the legality of a move in one region can depend on what is standing in another. Compulsory capture does. So does a rule that limits a player to one move of some kind per turn, and so does any rule phrased as a player who can do this must.

Dawson wrote his problem for a chess magazine in 1934 with no theory of sums in view, and the clause that makes his diagram reducible to a heap game is the same clause that stops the heap game’s arithmetic applying to two of his diagrams side by side. That is a tidy thing for one sentence to do, and it took a two-row board to see it, because a one-row board has nothing for the rule to reach across.

Still open: whether the coupling has a price #

The coupling is counted here and not priced. On the diagrams where the rows fail to add, the two answers differ by a known amount — ∗ against ∗3, ∗2 against nought — and nothing here says whether that difference is a function of anything.

The measurement that would begin to settle it is a correction term: for each diagram, the difference between the whole board’s value and the sum of its rows, tabulated against the shape. If that difference is nought except when some row is worth ∗ or ∗3, or except when the rows differ in parity, then the compulsory diagram is a sum with a correction and the correction is describable. If it is a different number on every shape, then the compulsory diagram is not a sum in any useful sense, and the only way to value a board with two rows on it is to search the board.