A pass is not a move

A pass is the move that does nothing. It is not part of Nim, and putting one on the board is the smallest possible change to the rules — a single token, available to whichever player wants it, spendable once.

The interesting thing is that “the smallest possible change” is not one change. It is two, and the difference between them is five words.

The pass that may end the game #

Take the permissive rule first: the pass may be spent at any moment, by either player, including when there is nothing else on the board.

$$G(\text{heaps} + \text{pass}) \;=\; (h_1 \oplus h_2 \oplus \cdots) \oplus 1$$

That is a clean result and it is clean because the pass has turned out to be something familiar. A component with exactly one move, available to either player, spendable once and then gone, is a Nim heap of one counter. It has Grundy value one, it adds by nim-addition like everything else, and the theory absorbs it without noticing.

So the permissive pass is not a modification of Nim at all. It is Nim with an extra heap, drawn as a token instead of as a counter, and every theorem survives.

The pass that may not #

Now the restrictive rule, which is the one Guy actually asked about: the pass may be taken at any time except as the move that finishes the game. If the heaps are empty, a player facing the pass alone must instead be unable to move, and has lost.

The clause looks trivial. It is not.

It is also not artificial. A pass that may end the game is a pass that lets a player who has run out of moves take one more, which is to say it is not really a pass at all — it is a spare move, and spare moves are exactly what normal play is about. Forbidding it as the final move is what makes the token do what the word suggests: skip a turn, without changing who is going to run out first.

Under it the Grundy value is no longer a function of the nim-sum. Positions whose heaps nim-add to zero come out at 0, 1, 2 and 6; positions summing to three come out at 0, 2, 4, 5, 6, 8 and 11. The grouping that was a bijection under the permissive rule is a mess under the restrictive one.

Why the clause has that much force #

The permissive pass is a component because it is available unconditionally. Whatever else is on the board, the pass is there; it does not consult the rest of the position; so it is an independent part and adds like one.

The restrictive pass consults the rest of the position. Whether it is legal depends on whether the heaps are empty, which is a fact about the other components. That is exactly the definition of a component that is not independent, and once independence goes, the nim-sum goes with it.

The same shape appears in an entailing move — a move that compels the opponent’s reply to be in a named component — and the damage is the same in kind. What is different here is where the dependence sits. An entailing move is a move inside a component that reaches out; the restrictive pass is a whole component whose legality is decided elsewhere.

Equality, and the universe it was proved in #

The witnesses above are the part worth carrying away, and they are a statement about equality rather than about passing.

$3$ and $1 + 2$ are equal games. Not similar, not equivalent for practical purposes — equal, in the sense the whole theory uses: their difference is a second-player win, so either may be substituted for the other inside any sum whatsoever and nothing changes. That is what equal in every company means, and it is the property that makes a value worth computing.

Put a held pass on the board and the substitution fails. One position is worth $\ast 4$ and the other zero, so a player handed the first has a win and a player handed the second does not.

Nothing has gone wrong with the equality theorem. What has happened is that “every company” was quantified over a universe — the finite impartial games under the ordinary disjunctive sum — and the held pass is not in it. Adding the pass did not add a company; it changed what a position is, by making legality depend on the whole board.

Reading the table #

The rows of the restrictive table repay a closer look, because the values in them are not scattered at random.

The row for nim-sum zero holds 0, 1, 2 and 6. Zero is the empty board, where the pass is illegal and the mover has lost. One is a pair of heaps of one, where the pass is legal and behaves like a third heap of one. Six is further out, and is the kind of value that appears when the pass interacts with the parity of what remains.

What is absent is any pattern that would let a reader predict the value from the nim-sum and one more number. Seven distinct values occur with nim-sum three; five with nim-sum two; and the sets overlap heavily. The map from positions to values has genuinely stopped factoring through the nim-sum.

The sharper version of that is the question asked backwards. A reader who has been handed the value of a position with a held pass on it wants to know what the heaps were, and the honest answer is almost nothing — with one exception, which is the sort of thing a table has to be read for rather than argued about.

Which of the two rules is the real question #

The permissive version is a curiosity and the restrictive one is a research problem, and the reason is the asymmetry above.

For Nim itself the restrictive pass is settled on one heap and on two and open from three heaps up — three heaps and a pass computes the losing positions and finds no formula for them — so the sweep above is a small corner of an unsolved problem rather than of a solved one. For games in general it is open too, and it has been open since Guy raised it, which is a long time for a question that can be stated in one sentence about the oldest solved game there is. Adding a single pass to an arbitrary impartial game changes the values in a way nobody has described, and the reason is precisely that the pass’s legality depends on the rest of the board: any general theory would have to track “is anything else left”, which is a global fact and exactly what a Grundy value is designed not to carry. The same shortage is what makes the impartial theory stop at every other rule of this shape.

That is a good illustration of what a theory of sums is for. Sprague–Grundy compresses a position into a number, and the compression is lossless with respect to every question the disjunctive sum can ask. Whether the board is empty is not such a question, and a rule that asks it is a rule outside the theory’s reach.

The smallest witness, worked through #

$3$ against $1 + 2$ is the pair to do by hand, and it takes four lines.

Without the pass, both are $\ast 3$. A single heap of three has Grundy value three; heaps of one and two nim-add to three; and either may be substituted for the other anywhere.

With a held pass available, the heap of three comes out at $\ast 4$ and the pair comes out at zero. Spending the pass is the same move on both sides and is worth the same on both: it leaves the same heaps with the token gone, which is an ordinary Nim position of value $\ast 3$. So both option sets contain a three, and everything that separates the two positions is in the ordinary moves underneath.

The mex does the rest, and the two answers part company. What a reader should take from the arithmetic is that nothing exotic happened: the pass added one option to each position, and one option was enough, because the two positions’ option sets were never the same — only their values were. What makes the separation inevitable rather than lucky is which entry the two sets differ by. It is a nought, and a nought is the one entry a mex cannot look past.

What the solver computed, and how #

Positions are heap lists with a flag saying whether the pass is still available, and the Grundy value is the mex of the options’ values. The options are the ordinary Nim moves in each heap, plus — when the pass is unspent, and when the rule permits — the same heaps with the flag cleared.

The two rules are two memo tables and one line of difference: whether the pass move is offered when the heap list is empty. Everything else is shared, which is what makes the comparison a comparison.

The grouping by nim-sum is the whole finding and is computed rather than illustrated. For each rule, every position is filed under the nim-sum of its heaps and the set of values in each group is recorded; a group with one member says the parts determine the whole, and a group with several is a counterexample. The permissive rule’s groups are checked to be singletons and the check throws if they are not, since a permissive pass that failed to behave like a heap of one would mean the recursion was wrong rather than that something had been found.

The witnesses are chosen smallest-first, by total counters and then by number of heaps, so the pair a reader is handed is one they can check by hand rather than the first the enumeration happened to build. That is a presentation choice and it is worth naming: the first pair the enumeration produces is the empty board against two heaps of one, which is a witness and is a bad one, since a reader would suspect the empty case of being special.

Normal play has no room for a free pass #

The essay opens by saying that the smallest possible change is not one change but two. There is a reason it cannot be one, and it is a fact about the winning condition rather than about either rule.

Under normal play the loser is the player who runs out of moves. That is the entire content of the convention: everything this site computes is a statement about who is left with nothing to do. A token that lets a player take a turn without doing anything is therefore not a neutral object — it is one more turn, which is precisely the currency the game is played in.

So the permissive pass being worth $\ast$ is not a curiosity about Nim. It is forced. A component offering exactly one move to either player, once, is a spare move, and a spare move under normal play is a Nim heap of one whatever it is drawn as. The permissive rule is honest about what it has added and the theory absorbs it without noticing, because the thing added is already in the theory’s vocabulary.

The restrictive rule is an attempt to have the other thing: a token that lets a player skip a turn without giving them an extra one at the end. And the only way to arrange that is to make the token illegal exactly when it would matter — when the board is otherwise empty — which is a condition about the rest of the board.

So the two rules are the two horns of a dilemma, and there is no third option. Either the pass is a move, in which case it is a component worth $\ast$ and nothing has changed; or it is not a move, in which case its legality has to consult the whole position and it is not a component at all. A pass that was both free and local would be a move that does not affect who runs out of moves, and under normal play there is no such thing.

That is why the sentence “put a pass on the board” does not name a game. It names a choice, and the choice is between changing nothing and leaving the theory.

Which convention a pass belongs to #

The dilemma is specific to normal play, and seeing where it dissolves says what it was really about.

In a scoring game a pass is free and unremarkable. Go ends with two consecutive passes — passing is a legal move, it costs nothing, and it is the ordinary way a player says the board is finished. Nothing breaks, because the winner is decided by counting rather than by who moved last, so a turn spent doing nothing is a turn that changes nothing. The token this essay’s restrictive rule is trying to build already exists there, and it needed no clause.

That is the sharpest available statement of what the last-move convention costs. It buys the group structure, the canonical forms and the whole arithmetic; what it charges is that doing nothing becomes impossible to express. A scoring game can afford a pass because its winning condition does not consult the move count, and a normal-play game cannot because its winning condition is the move count.

And it explains why the open problem is the shape it is. A general theory of held passes would have to carry, alongside each component’s value, whether that component still has anything in it — which is a fact the value was designed to compress away, because under the disjunctive sum nothing can ever ask it. The restrictive pass asks it. So the missing object is not a cleverer nimber; it is a summary that answers a question the sum was built to make unanswerable, and that is a considerably better reason for fifty years of no progress than “nobody has found the right generalisation”.

What would have to be true for the theory to survive #

It is worth asking what a general theory of held passes would need, because the requirement is stark.

A Grundy value summarises a position so completely that two positions with the same value are interchangeable. For that summary to survive a held pass, the value would have to determine whether the position is empty — and it does: the empty position is the only one worth zero. So far so good.

The trouble is one level up. In a sum, the pass is illegal when the whole board is empty, which happens exactly when every component is. A component’s value settles whether that component is empty; it settles nothing about the others; and legality depends on all of them at once. So the summary would have to be extended to carry, alongside the value, whether the component is empty — which is one extra bit — and then the sum’s legality is the conjunction of those bits.

That much looks workable, and on two Nim heaps it is: the losses there have a one-line rule. It is not enough on three heaps, where the losses have no known description, and what a component would have to carry shows that a Grundy value with an empty bit does not decide the held pass even on single components. What is not workable is the next step: once the pass has been spent, the position is an ordinary game again, and before it has been spent it is a game with an extra option whose availability shifts as components empty. Tracking that through a general sum needs more than a bit, and nobody has found the right object.

Where the model stops #

Nim, and heap lists of at most three heaps with no heap above seven — 120 positions. The permissive result is an identity and would be surprising to see fail anywhere; the restrictive result is a demonstration of failure and needs only the witnesses it has.

Neither says anything about a pass in a game other than Nim, and that is where the open problem lives. It also says nothing about two passes, or a pass for each player, which is a different game again — with a pass per player the position stops being impartial, since the two players no longer have the same moves available, and the whole apparatus of Grundy values goes with it.

And the restrictive rule is one of several. “May not end the game” is not the only way to forbid a degenerate pass; “may not be taken twice in succession by the two players” is another, and would give a third table.

Where the ladder goes next #

This rung establishes that whether a rule is a component or a change to the game is decided by whether its legality consults the rest of the board, and exhibits both answers on one game. The rung above is the general case: what a held pass does to an arbitrary impartial game, which is open.

Two neighbours are worth the trip. A move that must be answered is the other way a rule reaches across components, and its damage is measurable in the same way. And equal in every company is the theorem the witnesses here qualify — not by contradicting it, but by making its quantifier visible.