The move that gives counters back

Nim with one addition. Each player begins with a private reserve of counters — chips, in the version the name comes from — and on a turn may either take any number of counters from one heap, as usual, or put any number of counters from the reserve onto one heap.

Counters taken leave the game. Counters added come out of the adder’s own pile and do not come back.

The obvious first reaction is that this ruins everything. Nim ends because the heaps only shrink, and here they do not only shrink. A player who is losing can put counters back, and keep putting them back, and the game that was over in a dozen moves now has no evident reason to stop.

A reserve only ever shrinks. Putting counters onto a heap costs them out of the player’s own pile permanently, so each player can make only finitely many additions — at most as many as the counters they started with.

Between two additions, the game is ordinary Nim: heaps only get smaller, so only finitely many moves can pass. String the two facts together and the whole game is bounded. The number of additions is bounded, and between consecutive additions the number of takes is bounded, so no play can go on for ever.

That is not a small remark. It is exactly what the whole apparatus needs and all that it needs. The recursion that defines every value on this site works by induction on the options, and induction needs the descent to bottom out. It does not need the heaps to shrink; it needs play to end. Poker Nim is the cleanest example of a game where those two are different.

The reserves make no difference at all #

Now the result, which is stronger than one might expect and is the reason the game is in the textbooks.

The player to move wins a Poker Nim position exactly when the nim-sum of the heaps is not zero — whatever the reserves are. Not “usually”, not “if the reserves are equal”. A player holding a hundred counters against an opponent holding none is still lost if the heaps cancel.

Take the heaps 1, 2 and 3, whose binary columns all cancel: the nim-sum is nought and the player to move loses. The claim about Poker Nim is that hanging a reserve on each side of that position leaves the verdict exactly where it was, however the two reserves are sized.

A theorem that only ever said lost would be no theorem, so the same position is worth seeing with one counter moved and the verdict turned over.

Why: the counter-move that undoes it #

The proof is a strategy, and it is one sentence.

Suppose the nim-sum is not zero and it is Left’s turn. Left plays the ordinary Nim winning move — the one that makes the heaps cancel — and hands over a position with nim-sum zero. Right now has two kinds of reply.

If Right takes counters, the nim-sum becomes non-zero, and Left restores it by the ordinary rule, exactly as in Nim.

If Right adds $k$ counters to some heap, Left takes those same $k$ counters straight back off that heap. The position is precisely what it was — nim-sum zero, Right to move — and Right’s reserve is $k$ counters lighter. Right has spent part of a finite resource and gained nothing whatever.

Since the reserve is finite, Right can only do that finitely often, and every time it happens the position resets. Eventually Right must make a real move, and then the ordinary argument takes over.

Why the restoration always works is worth one line: the nim-sum is addition without carrying, done column by column, so removing exactly what was added is the inverse of adding it and no column can be disturbed by a carry from another. But the restoration is stronger than that. It does not merely return the nim-sum; it returns the position.

What the move actually is #

This is the point at which the essay stops being about Nim and becomes about the general theory, because the move Right made has a name.

A reversible move is one the opponent can answer so as to leave the mover no better off than before they started. The canonical form exists precisely to delete such moves: an option that can be reversed through is replaced by the options of the position it reverses to, on the grounds that nobody sensible takes it.

Adding counters is reversible in the purest possible way. The answer is not merely as good as the original position — it is the original position, restored exactly, at a cost to the mover. In the language of the reduction, the whole family of adding-moves collapses on inspection, and what is left is Nim.

So the answer to “why does a reserve not help” is not special pleading about Nim. It is the standard reduction, applied to an unusually vivid case, and it is why this game is a good place to meet reversibility before meeting it in a position where the trees are too big to draw.

The Grundy value, unchanged #

Impartial games are settled by the Sprague–Grundy theorem: every position is equivalent to a single Nim heap, and the heap’s size is the mex of the values of the options.

For a Poker Nim position, the options are the ordinary Nim options plus the added-counter positions. The mex is over a larger set — but every one of the extra values already appears among the ordinary ones, because adding $k$ counters to a heap of size $h$ produces a position that some ordinary take could also produce from a larger heap. The extra options widen the set of reachable values without adding anything new to it, and the mex is unmoved.

The mex rule is where that bites. A position’s Grundy value is the smallest non-negative integer that is not the value of any option, so an option whose value duplicates one already in the set is invisible: the smallest absent number does not move because a number already present has arrived twice. Adding a reversible move to a position is exactly a way of producing duplicates, and a great many of them at once.

That is the same fact stated in the impartial dialect rather than the partizan one. A reversible option in the partizan world is deleted by the reduction; an option whose Grundy value is already in the set is invisible to the mex. Both are the theory saying that a move which gains nothing does not have to be modelled.

What the ending condition is really made of #

The step worth isolating is the one at the start, because it is the one every theorem on this site leans on and almost never states.

Nim ends because a numerical quantity — the total number of counters — strictly decreases at every move. That is the easiest kind of termination argument there is, and it is the one most games here use. Poker Nim does not have it: the total goes up whenever somebody adds.

What Poker Nim has instead is a quantity that decreases lexicographically. Order a position by the pair (counters left in both reserves, counters left on the heaps), and compare pairs on the first coordinate first. An addition drops the first coordinate. A take leaves the first alone and drops the second. Either way the pair goes down, and pairs of non-negative integers ordered that way cannot descend for ever.

That distinction — decreasing versus well-founded — is where several of this site’s harder essays live. A game whose positions form a well-founded order has values; a game whose positions can repeat does not, and needs different machinery. The size of the position is not what matters, and neither is whether the moves look like they shrink anything. Only the well-foundedness matters, and Poker Nim is the example that separates the two ideas cleanly enough to see them.

It is also why the Sprague–Grundy theorem covers so much ground. Its statement never mentions heaps or counters: it covers every impartial game under the normal-play convention in which play must end. Poker Nim satisfies that and so is covered, unchanged, without anybody extending the theorem.

The lemma the argument is an instance of #

The strategy is one sentence about Poker Nim and it is really a general statement, which is worth writing out because the hypotheses are then visible and each of them can be shown to be doing work.

Take any game, and add to it a family of new moves such that, after any one of them, the opponent has a reply restoring the position exactly — and such that making one strictly decreases a resource of the mover’s that cannot decrease for ever. The outcome of every position is unchanged.

The proof is the one above with the nouns removed. A player who was winning keeps playing their winning strategy; when the opponent uses a new move, they undo it; the opponent’s resource falls; and since it cannot fall for ever, the opponent must eventually play a move of the original game, where the strategy applies.

Three hypotheses, and it is worth checking that none is decoration.

The undo must exist. In Poker Nim it always does: $k$ counters were just added to a heap, so that heap has at least $k$ on it and taking $k$ off is legal. Change the rule so that a player may only take from the smallest heap and the undo can be illegal — the restoration is not available, and the argument has nothing to offer.

The resource must be well-founded. With an unlimited reserve the additions never run out, the opponent stalls for ever, and the game acquires draws it did not have. The finiteness is not a tidiness condition; it is the whole of why the strategy terminates.

And the restoration must cost the mover. A new move that could be undone at no cost to anybody would simply be two wasted turns, which changes the parity — and parity is what normal play is about. What makes an addition harmless is that it is the mover who pays.

Stated that way the lemma covers a family of variants at once, and it says what to check before believing any of them: not that the extra moves look silly, but that the undo is legal, that the payment is real, and that the payments cannot go on for ever.

The reserve is shared, and the sum should not survive it #

There is a complication the essay has so far kept out of sight, and it is sharper than the theorem it threatens.

Everything on this site about sums assumes the components are independent. Put two Poker Nim positions side by side and they are not: the players have one reserve between the two of them, not one apiece per component. Spending counters on the left heap is spending counters that are then unavailable on the right. That is a resource reaching across the sum, and a resource reaching across a sum is exactly the condition under which the disjunctive theory stops applying.

So the position is not a disjunctive sum of its heaps in the technical sense, and the nim-sum has no right to decide it.

It decides it anyway, and the reason is that the undo strategy never consults the decomposition. When the opponent adds $k$ counters to a heap, the answer is to take $k$ counters off that heap — a purely local reply, correct whatever else is on the board and whatever the reserves are. The shared resource is spent and the position is restored, so the interaction between components is real and is worth nothing to the player who creates it.

That is a much better reason to like this game than “the reserve does not help”. The reserve genuinely does couple the components, and the answer survives because the coupling is on a quantity nobody can profit from. Compare the game where a move compels the opponent’s reply into a named heap: there the coupling is on the reply, which is the thing the Sprague–Grundy argument spends, and the theorem falls apart at two heaps of two.

Two games, two violations of independence, two opposite outcomes. What separates them is not how strange the extra rule looks but whether it touches the resource the proof is using.

Play it, and try to hold on #

The claim can be tested rather than read.

The figure plays ordinary Nim rather than Poker Nim, and the reason is worth stating plainly instead of hiding: the point of this essay is that the two games have the same answers, so the position a reader can lose is the same position either way. A Poker Nim interface would add a control for putting counters back, and every use of it would be answered by taking them off — which is a demonstration of nothing that the argument has not already made, at the cost of a much larger reply table.

What the solver computed, and how #

The claim about the reserves is checked, not argued, and it is checked over a range rather than on an example.

pokerNimWins(heaps, mine, theirs) is a plain search. It enumerates every take from every heap and every addition of every size from the mover’s own reserve, recurses on each, and reports whether any of them leaves the opponent lost. It knows nothing about nim-sums. Memoisation is on the sorted heaps together with both reserves, because the reserves are part of the state even though the theorem says they are not part of the answer — assuming otherwise in the code would be assuming the result.

The audit then runs it over every position with three heaps of at most four counters and reserves of at most two on each side: 1,125 positions, and the search agrees with the nim-sum on every one of them. A single disagreement stops the build with the offending position printed.

Agreement everywhere is also what a broken audit looks like, so the sweep is not the whole of it.

A test that only ever confirms is a test that cannot fail, which is why the second half of that figure exists at all.

Where the model stops #

Additions go onto an existing heap. Some statements of Poker Nim let a player create a new heap. The argument is the same — the opponent removes the new heap entirely — but the search space is larger, and this site computes the version it draws rather than the version it would like to have computed.

The reserve is finite and that is essential. With an unbounded reserve the game is loopy: a player can stall indefinitely, the induction has nothing to stand on, and a draw becomes possible. Everything on this page depends on a finite pile, and the finiteness is doing real work rather than being a convenience.

The audit range is small. Three heaps of four and reserves of two is 1,125 positions, which is exhaustive at that size and says nothing about a heap of a thousand. The general proof is the strategy argument above; the audit is evidence that the code implements what the argument describes.

Reversibility is stated here in its easiest case. The undo in Poker Nim restores the position exactly, which is a special and unusually clean situation. The general definition asks only that the answer leave the mover no better off than the original position — an inequality, not an identity — and reversing through an option can leave a position that is genuinely different and merely no worse. Everything in the reduction to canonical form is stated with the inequality, and a reader who takes the exact-restoration picture as the definition will find the general case surprising.

Who found it, and when #

Poker Nim is in Winning Ways (1982), where Berlekamp, Conway and Guy use it to introduce reversible moves and the bounded-play condition. The name is theirs and so is the framing: the game exists to make a point about the theory rather than to be played, which is unusual here — Nim, Domineering and Toads and Frogs were all invented as games first.

The underlying observation is older and more general. Bouton’s 1901 solution of Nim already turns on the fact that the second player’s replies restore a property rather than pursue an advantage, and the Poker Nim strategy is that idea applied to a move the original game does not have.

There is a longer history behind the termination condition. Mathematicians had been careful about well-founded orders since Zermelo’s 1913 paper on chess — the first proof that a finite two-player game of perfect information has a determined outcome — and the requirement that appears there is exactly the one Poker Nim satisfies and a looping game does not. What the twentieth-century game theory added was not the condition but the machinery that becomes available once it holds: a value, a canonical form, and an addition that behaves.

Where the ladder goes next #

This is the second rung on the Nim ladder, after the nim-sum itself. It takes the same game, adds a rule that appears to break it, and finds the theory absorbing the change without effort.

The next rung is the one where the absorption fails. Adding a move that gives counters back is harmless; adding a move that lets a player pass is not, and neither is allowing a position to recur. Where the recursion loses its footing is the boundary this essay stops just short of — and the whole difference is whether the resource being spent is finite.