Three heaps and a pass

A pass is not a move put one pass token on a Nim board and showed that five words decide what it is. A pass that may end the game is a heap of one and changes nothing. A pass that may not end the game — the held pass, unavailable once the heaps are empty — breaks the nim-sum: positions with equal Nim values come apart, and the Grundy value of a position stops being a function of its heaps’ nim-sum. That essay then said, in two places, that Nim with a held pass has been analysed and solved, and that only the general case is open.

That was wrong, and the correction is the subject here. Nim with a held pass is itself the open problem — it appears in the standard lists of unsolved problems in combinatorial games — and what is known about it is easy to state because it stops so early. One heap has a formula. Two heaps have a formula. Three heaps do not, and the losing positions on three heaps are known only by computing them.

The rule, and the one question it raises #

The game is Nim — any number of counters may be taken from any one heap, and the player who cannot move loses — with a single pass token on the table. On their turn either player may spend the token instead of moving in a heap, and then it is gone for good. The only restriction is that the pass may not be spent when the heaps are all empty: a player facing an empty board has lost whether or not the token is still there.

Everything interesting follows from asking, of a position with the token still on the table, whether the player to move wins. Call such a position lost when every move leads to a position the opponent wins — the P-positions of this game — and won otherwise. Two facts do most of the work. Spending the pass leaves ordinary Nim, which the player then to move wins exactly when the heaps’ nim-sum is not nought. So a non-empty position whose nim-sum is nought is always won: spend the pass and hand the opponent a Nim loss. And a position is lost exactly when its nim-sum is not nought and no move in a heap reaches another lost position.

That definition is short enough to compute from, and the pictures that follow are all it.

One heap #

A single heap is the case to settle first, because every larger position eventually becomes one.

The rule is $G(h) = h + 1$ for odd $h$ and $G(h) = h - 1$ for even $h > 0$, checked on every heap to forty and easy to see by induction. A heap of $h$ with the pass has as options every smaller heap with the pass still there, plus the pass itself, which leaves an ordinary heap of $h$ worth $h$. The smaller heaps supply the held-pass values of $0, \dots, h-1$, which by the rule are exactly $\{0, \dots, h-1\}$ when $h$ is odd and $\{0, \dots, h-2, h\}$ when $h$ is even — the heap $h-1$ has just been swapped up to $h$. Adding the value $h$ from the pass completes the run for odd $h$ and duplicates what is there for even $h$, leaving the gap at $h-1$. The mex is then $h+1$ or $h-1$ as stated.

This is a formula for one heap and nothing more. A heap is not a sum of anything, and the whole point of the held pass is that its values do not add, so the one-heap formula is a boundary condition for the next case and not a step towards a general one.

Two heaps #

The two-heap losses are the filled cells at the top, and the rule they follow is as simple as a rule can be: the mover loses exactly at the empty board and at the pairs $(2k-1, 2k)$. Every pair to sixteen agrees, and the computation behind the figure checks every pair to twenty against it.

The reason is visible in a single position.

Two numbers of the form $2k-1$ and $2k$ are different, so their nim-sum is never nought — it is 3 for five and six, 15 for seven and eight — and that is what makes spending the pass useless at such a pair: it leaves ordinary Nim with a non-zero nim-sum, which the opponent wins. And a single heap move from $(2k-1, 2k)$ changes one heap and leaves the other, and no other pair of the form $(2j-1, 2j)$ shares a heap with this one. So every option is won for the opponent, and the pair is lost.

The converse needs a move from every other pair to a lost one, and there is always one. If the two heaps are equal and non-empty, spend the pass: Nim with nim-sum nought is lost for the opponent. If they are unequal, move the larger heap to make a pair of the form $(2j-1, 2j)$ with the smaller one — which is possible whenever the larger heap exceeds the partner the smaller one needs. The cells of the grid are these two arguments drawn.

What the grid also shows, and is worth pausing on, is how thoroughly the pass rearranges Nim’s losses. Not one of Nim’s losing positions on two heaps survives except the empty board. Every equal pair, which Nim calls lost, becomes a win by spending the pass; every pair $(2k-1, 2k)$, which Nim calls won, becomes a loss. The two losing sets are disjoint apart from one cell.

Three heaps #

Three heaps are where the formulas stop.

Sixty-six losing positions with three non-empty heaps up to twenty. One row is regular: with a smallest heap of one, the losses are $1, b, b$ for every $b \ge 3$, together with $1, 1, 1$. Every other row is scattered. The row for a smallest heap of two reads $2, 2, 2$; $2, 3, 5$; $2, 4, 7$; $2, 6, 8$; $2, 9, 12$; $2, 10, 11$ — and by then the eye has stopped looking for a rule.

Nim itself has a one-line answer for three heaps, and it is natural to ask whether the answer here is some modification of it: the nim-sum shifted, or taken mod something, or corrected on a parity. The nim-sums of the losses say no.

Eighteen different nim-sums among sixty-six losses. The only structure is the absence of nought, which is the pass argument once more, and the bar at 1, which is the one regular row. Knowing a position’s nim-sum tells almost nothing about whether it is lost — which is the same finding the essay below this one made about Grundy values, now made about the losing set itself.

One partner per pair #

There is one piece of structure the three-heap losses share with Nim, and it is the thing that makes them computable at all.

In ordinary Nim, for any two heaps $x$ and $y$ there is exactly one third heap $z$ that makes the position lost — namely $x \oplus y$. With a held pass there is at most one: if two third heaps $z < z'$ both made $(x, y, \cdot)$ lost, then $(x, y, z')$ could move to $(x, y, z)$ by taking from the third heap, and a lost position cannot have a lost option. So the losing set is a partial function from pairs to partners, and some pairs have none — the pair $(1, 2)$, for instance, has no third heap that completes a loss.

That is exactly the shape of a question with an answer in Nim and none here. Nim’s partner function is $x \oplus y$. The held-pass partner function exists, is computable pair by pair, and has no known formula. The solver that draws these figures stores it directly — one entry per pair — and fills it in by increasing total, which reaches heaps of several hundred in a few seconds and is checked against the Grundy recursion of the first essay on every position with heaps up to nine.

Slices #

The way to find structure in a function of two variables is to fix one of them. Fix the smallest heap $a$ and look at how the partner of $(a, b)$ depends on the middle heap $b$.

Each slice has the same anatomy. For a stretch of small $b$ the partners are scattered; then the dots fall into a lattice of short diagonal runs, and the offset $c - b$ repeats with a fixed period for as far as the computation goes. With a smallest heap of two the offsets settle from $b = 9$ into the repeating block $+3, +1, -1, -3$: the pairs $9$ and $12$, $10$ and $11$, $13$ and $16$, $14$ and $15$, and so on in blocks of four. With a smallest heap of one, the slice is the regular row above, offset nought from $b = 3$. Every slice is a pattern with an irregular start, and the start is where the difficulty lives.

The table is the whole of the measurement, and it has a shape. Slices one to nine settle with periods of 1, 4, 4, 8, 8, 8, 4, 8 and 10, from middle heaps between 3 and 22. Slice ten has a period of 160 — sixteen times the one before it — starting from $b = 18$. Slice eleven has the same period, 160, but starts only at $b = 336$: an irregular opening more than fifteen times longer than any below it. From slice twelve on, no period of up to 256 is seen within the range computed, which reaches middle heaps of a thousand.

The run that found slice eleven’s period is itself the lesson. At heaps up to 640, slice eleven showed no period at all and looked like the first slice that does not settle. At heaps up to 1,100 it settles, three hundred heaps after the point where the smaller computation had to stop looking. So “no period seen” in the last rows of the table is a statement about the range and not about the slices, and the natural reading is that the starts grow quickly — faster than the periods — and that slices twelve onwards need ranges this computation does not reach.

That reading is only natural; it is not established. Either the periods and starts keep growing, and every slice settles eventually, or something changes past eleven and some slices never do. The periods found are observed, not proved: each is accepted only after three repetitions and twenty heaps beyond its start, and no theorem guarantees that a slice which has repeated three times will repeat a fourth.

Where the two-heap rule came from #

There is a way of stating the two-heap rule that connects it to the one-heap formula, and it is worth having because it is the clearest sign of what the pass does to Nim’s arithmetic.

In ordinary Nim two heaps are lost exactly when they are equal — when the value of one heap equals the value of the other. With a held pass the pairs $(2k-1, 2k)$ are exactly the pairs the one-heap formula exchanges: a heap of $2k-1$ is worth $2k$ with the pass, and a heap of $2k$ is worth $2k-1$. So the two-heap rule reads: two heaps are lost exactly when the held-pass value of one equals the ordinary size of the other. One heap is carrying the pass and the other is not, in effect, because only one pass exists and only one of the two heaps can be the one it is spent beside.

That reading does not extend to three heaps — it cannot, because the whole difficulty is that the three-heap losses are not a function of any single heap’s value — but it explains why two heaps are easy. With two heaps the pass has exactly two places to be spent, and the rule records which. With three there are three, the options interact, and the partner function stops having a description.

How the losses were computed #

The pictures rest on one computation, and it is simple enough to describe completely. Positions are triples of heap sizes with the pass unspent. They are visited in order of their total, smallest first, so that every option of a position has been settled before the position itself. A position is lost when its nim-sum is not nought — otherwise spending the pass wins — and no heap move reaches a lost position. Because each pair of heaps has at most one lost partner, the set of losses is kept as a table from pairs to partners, and “does any heap move reach a loss” is three table lookups rather than a search over all smaller heaps.

That is what makes heaps of a thousand affordable: about 220 million triples, each settled in constant time. The results are checked against the plain Grundy recursion of the first essay on every triple with heaps up to nine, and the two agree on all of them. What the method cannot do is go much further; the number of triples grows as the cube of the largest heap, and a slice with a start at ten thousand would need a computation a thousand times larger.

What this says the problem is #

Put the three cases together and the difficulty has a precise location. The held pass is the smallest possible change to Nim, and on two heaps it leaves a rule as clean as Nim’s own. On three heaps it leaves a partner function with one regular slice, eight more slices that settle quickly, one that settles slowly, and an infinite remainder about which nothing is known. The open problem is not a single hard case; it is infinitely many easy-looking ones whose starts and periods drift upward with no formula for the drift.

That shape is familiar from the sequence nobody has settled, where every finite octal game is conjectured to be eventually periodic and the evidence is a list of games that settled and a list that have not yet. Here each slice is its own sequence and the conjecture would be that every slice settles; the evidence is nine slices that settle quickly, two that settle late, and the rest that have not been computed far enough.

It is also why the correction matters. Saying that Nim with a held pass is solved makes the general question — a held pass on an arbitrary impartial game — sound like a hard generalisation of an easy base case. It is not. The base case is already hard, and a general theory would have to contain a solution to it.

The convention named #

Everything here is normal play: the player who cannot move loses, and the pass cannot rescue a player facing an empty board. That clause is what makes the pass held. With a pass that may end the game, the earlier essay showed the whole problem vanishes, because the pass is then a heap of one and the nim-sum absorbs it. With a misère ending the pass would be a different object again, since a player facing an empty board would then want to have no move.

There is one pass and it is shared. A pass for each player breaks the symmetry of the moves and makes the game partizan, and the Grundy-value arithmetic that the one-heap formula uses does not apply.

What the pictures cannot show #

The slices show where each pattern starts and how long it is. They cannot show why a slice settles, and nothing here explains the periods: why 4 for a smallest heap of two or three, why 8 for four, five, six and eight but 4 for seven, why 10 for nine. A period read off a computation is a description, and a description of nine cases is not a pattern in the nine.

They also cannot show what happens beyond the range. Heaps up to 640 were computed; the losses beyond that, and every slice from eleven upwards, are unknown here. A reader looking for a counterexample to “every slice settles” would need to look far past where these figures stop, and a reader looking for a proof would need an argument none of these pictures suggests.

Still open: what a component would have to carry #

Three heaps defeat a formula, but they are still heaps. The question the first essay on the pass raised was broader: what does a held pass do to an arbitrary impartial game, where the components are not Nim heaps but rows of Kayles, heaps of Dawson’s chess, anything the Sprague–Grundy theorem turns into a nimber?

That essay proposed an answer — carry each component’s Grundy value together with one extra bit saying whether it is empty — and said the proposal was workable. It can be tested directly. Take a pool of components from several rulesets, put a held pass on the board beside each and beside every company of one or two others, and count how many genuinely different behaviours there are. If the Grundy value and an empty bit are enough, the count will equal the number of distinct pairs. If it is larger, the held pass is reading something no short summary of a component contains — and the difficulty of three Nim heaps is the first sign of a difficulty that no choice of components can avoid.