Taking from the ends

Nim is the game the whole impartial theory is built on: heaps of counters, a move takes any number from any one heap, and the position collapses to a single number computed by exclusive or. It is impartial, which means the two players have exactly the same moves.

Take that board and change one thing. Left may only take from the leftmost heap; Right may only take from the rightmost. A heap that empties disappears, so the next one along becomes the end. Everything else — normal play, no chance, perfect information — is unchanged.

The game is now partizan: the players have different moves, so the value theory rather than the Grundy theory applies. What the theory returns is close to useless, and what the game does anyway is highly organised. This essay is about that gap.

What the values do #

Every position with heaps of up to four counters and up to six heaps was solved: 5,460 rows.

A value theory earns its place when the value is smaller than the position — when a complicated board collapses to a short name that can be added to other short names. Here the value is larger than the position. $1\,3\,2$ is six characters; its value is

$$\{\,\{0 \mid \ast 3, \{0 \mid \ast 3\}\} \mid 0,\, \ast 3,\, \ast 2,\, \ast\,\},$$

which is not a summary of anything. This is the clearest case on the site of a game where computing the canonical form is possible, correct and of no use whatever.

What partizan costs, in one board #

The change from Nim is one sentence and its consequences are worth listing before any of them is measured.

The theory changes. Nim is impartial, so Sprague–Grundy applies: every position is a Nim heap, the value is a number, and a sum is read by exclusive or. End-Nim is partizan, so none of that is available and the value theory takes over — values are games rather than numbers, and there are four outcome classes rather than two.

The board does not change. The same heaps, the same counters, the same normal-play ending. A photograph of a Nim position and a photograph of an End-Nim position are the same photograph.

And the difficulty moves. Nim’s difficulty is nil — the winner and the winning move come from one exclusive or. End-Nim’s outcomes have a rule, discovered by Albert and Nowakowski in 2001, seventy years after Bouton solved Nim, for a game that is one clause away from it.

That gap is the reason this game is on the site. It is the smallest available demonstration that who may move where is a more consequential rule than anything about how much may be taken.

Except on one heap #

One special case behaves perfectly, and it is worth stating because it is the bridge back to Nim.

A row with a single heap has the same heap at both ends, so both players may take from it, and both may take any amount. That is a Nim heap. The value of a one-heap End-Nim row of $n$ counters is $\ast n$, exactly, for every $n$ checked.

Two heaps, and the rule anybody would guess #

With two heaps and nothing between them, each player owns one heap. Left eats into their own heap and Right into theirs, and the question is which of them runs out first. The obvious guess is that the larger heap wins.

The strategy behind the rule is the one the picture suggests. If Left’s heap is larger, Left takes counters down to one more than Right’s, and thereafter answers every take with an equal take; Right runs out first. If the two are equal, the second player mirrors, which is the mirror strategy in its usual disguise. It is a complete account of the two-heap game, obtained from the outcomes rather than from the values.

The values, at the size a reader can hold #

Two heaps is where a reader can check the arithmetic, and it repays the effort.

$[2, 1]$: Left may take one or two from the heap of two; Right may take the one. Left’s options are $[1, 1]$ — which is worth zero, since whoever moves takes their own heap and the opponent takes theirs — and $[1]$, a single heap of one, which is $\ast$. Right’s only option is $[2]$, which is $\ast 2$. So $[2, 1] = \{0, \ast \mid \ast 2\}$, which reduces to $\{0 \mid \ast 2\}$.

That value has no name. It is not a number, not a nimber, not up or down or a switch; it is a two-line brace expression for a position with three counters in it. A player told “this position is worth $\{0 \mid \ast 2\}$” has been told something true and useless.

Meanwhile the outcome of $[2, 1]$ is: Left wins whoever moves, and the reason fits in a clause — Left’s heap is bigger.

Where the guess stops #

Extend the same rule to whole rows — compare the two end heaps and ignore everything between — and it is wrong 2,995 times out of 5,456.

The shortest failure is $1\,1\,1$. Both ends are heaps of one, so the rule predicts a second-player win. In fact whoever moves takes the end heap they own, leaving $1\,1$, in which the opponent takes their own heap, leaving one heap of one for the first player to take: the first player wins, and the position is worth $\ast$.

The reason is that a heap in the middle belongs to nobody until it becomes an end, and it becomes an end for whichever player is next to exhaust the heap in front of it. Owning the larger end is worth something; being the player who opens the interior is worth something too, and the two can point in opposite directions. That is the whole difficulty of End-Nim, and the general rule that resolves it is Albert and Nowakowski’s, published in 2001. It is a genuine theorem about runs of heaps of one at the ends, and it is not reproduced here — this essay computes what it can check and says where the literature takes over.

The rows that read the same both ways #

There is one family whose outcomes can be settled without any search, and the argument is a group-theoretic one rather than a combinatorial one.

Reversing a row exchanges the two players’ moves, so the negative of an End-Nim row is the row read backwards. A palindrome is therefore its own negative — and a game equal to its own negative is worth zero or is confused with zero, never a win for a particular player.

That last line is worth separating from the rest. “A palindrome is zero or fuzzy” is proved by the negation argument and checked by the search. “A palindrome is worth a nimber” is only checked: 168 positions, no exceptions, no proof offered. Palindromes are self-negative and most self-negative values are not nimbers, so the pattern is not a consequence of the symmetry — and it may fail on a longer row than this census reaches.

Why no value here can be a number #

The census reports the fact and the rule proves it, in one line, for every row of every length — which is worth having, because a count over five thousand rows is evidence and a reason is not.

Look at when a player is stuck. Left is stuck when there is no leftmost heap, and Right is stuck when there is no rightmost heap, and a row has a leftmost heap exactly when it has a rightmost one — they are the same heap when there is only one. So while any counter remains on the board both players can move, and when none remains neither can. The two players run out together, always, in every position and in every follower of every position.

That is the definition of an all-small game, and every all-small game is smaller in absolute value than every positive number. So no End-Nim row is worth $\tfrac12$, or $1$, or $-\tfrac{3}{16}$; the only number an infinitesimal can equal is zero, and 361 of the rows do.

Three things follow that the count on its own does not give.

It covers every length. The census stops at four counters and six heaps; the argument does not stop anywhere, because it never mentions how many heaps there are or how large they get. The place this essay defers to the literature is the outcome rule, not this.

It says which number is available. “No numbers” and “no numbers but zero” are different claims, and the second is the true one — the first is contradicted by the two rows in the hero figure, both of which are worth zero exactly. A row worth zero can be deleted from any board it sits on without changing the answer, which is a genuinely useful thing to know about 361 of these positions and is not a way of saying they are boring.

And it explains the shape of the census rather than only its headline. If every value is infinitesimal then the values live in the same crowded neighbourhood as $\ast$, $\uparrow$ and their relatives, where the order is fine and confusion is everywhere — which is exactly the place a value theory produces 2,693 distinct answers and orders almost none of them against each other. The uselessness is not bad luck. It is what an all-small game with a lot of positions looks like from the value side.

There is a footnote to that which is really a note about instruments. This site counted the numbers here twice, in two places, and for a long time the two answers were 361 and none — the second because the test was applied to the position’s own tree rather than to the reduced form of it, and a row that reduces to zero has options confused with one another, which the raw test reads as a fight. Both counts were printed, in different figures, and neither was ever set against the other. They are now: the two censuses must agree about the same rows, and the rows worth a number must be exactly the rows the second player wins, which is the same statement made twice and is the kind of statement that cannot quietly drift.

What the argument does not do is give the outcomes. All-small is a statement about the shape of the game tree and it is compatible with any pattern of wins at all; the 4,738 rows decided for one player whoever moves are decided by something the argument above never touches. That split — a clean reason for the values and no reason at all for the outcomes — is the essay’s subject in one sentence.

Two ways a game can be solved #

End-Nim is a good place to be precise about what the word “solved” claims, because it is solved in one sense and not in another.

Its outcomes are known. A rule exists that names the winner of any position, and this essay verifies the two-heap case of it exhaustively. That is what a player wants and it is what most of the literature means by solving a game.

Its values are not usable. Every position has a value, computed here for 5,460 of them, and the values do not compress: 2,693 distinct ones, one for every other position, none of them a non-zero number and most of them longer than the position they describe.

The two are different questions and they can have different answers. Nim answers both at once, which is why it is the game everybody meets first and why it is a misleading introduction: it makes the value theory and the winning rule look like the same achievement.

End-Nim separates them completely. So does Maundy Cake, where the rule for who wins is an arithmetic function of the sides and the rule for by how much is not. Two different questions, and a game may answer either without the other.

What the solver computed, and how #

One recursion, memoised on the heap list.

$$\text{endnim}(h_1 \ldots h_n) = \{\, \text{endnim after each Left take} \mid \text{endnim after each Right take} \,\}$$

Left’s options are the $h_1$ positions reached by taking $1, 2, \ldots, h_1$ from the first heap, with the heap dropped when it empties; Right’s are the same at the other end. Everything downstream is the site’s ordinary machinery: game(), canonical(), name() and outcome(), with no End-Nim knowledge in any of them.

The census is every heap list with entries from 1 to 4 and length 1 to 6, which is $4 + 4^2 + \cdots + 4^6 = 5{,}460$ rows. Values are counted after canonicalisation, so 2,693 is a count of values and not of positions, and the number test is applied after canonicalisation too — applied before, it reads the position’s own tree, whose options are confused with one another in every row that reduces to zero, and refuses all 5,460. The two-heap rule is checked past the grid it is drawn on — 400 pairs up to twenty a side — because a rule verified only where it is drawn is a rule verified on the picture.

Where the model stops #

The census stops at four counters a heap and six heaps because the recursion’s cost is in the number of positions reachable, and every take from an end produces another row. Larger censuses are affordable one step at a time and nothing here is a statement about long rows or big heaps — though on this particular claim, as the section above argues, the census is a check on the recursion rather than the evidence, since the all-small argument covers every row of every length.

One number in the census is worth a second look before that. The outcomes split 2,369 for Left, 2,369 for Right, 361 second-player wins and 361 first-player wins — two exact ties, and neither is a coincidence. Reversing a row exchanges the players, reversal is a bijection on the census, and it maps Left wins to Right wins and fixes the other two classes. A symmetry of the game showing up as an equality of two counts is the cheapest possible check that the solver has not lost a case.

The general outcome rule is where this essay defers rather than stops. It exists, it is known, and it is more intricate than anything computed here; what the computation establishes is the shape of the problem it solves — that the answer depends on the interior of the row and not only on its two ends.

The palindromes, and why they are not a coincidence #

The palindrome result is the one piece of structure here that comes from the theory rather than from a search, and it is worth separating from the measurements around it.

Negation exchanges the two players. In End-Nim the players are distinguished only by which end they take from, so exchanging them is exactly reversing the row: $-[1, 2, 3] = [3, 2, 1]$. That is a fact about the rules, obtained by reading them, and no search is involved.

A palindrome is therefore a position with $G = -G$, and such a game is zero or confused with zero — never a win for a particular player. The search agrees on all 168 palindromes in the census, which is the check rather than the argument.

What the search adds is the part the argument does not give: every palindrome in the census is worth a nimber. That does not follow from the symmetry — most self-negative values are not nimbers — and it is reported as a measurement over 168 positions with the size of the census named, because a longer row might break it.

Where the ladder goes next #

Two directions. One is the impartial boundary: a single End-Nim heap is a Nim heap, every palindrome is worth a nimber, and yet the game as a whole is thoroughly partizan — so where exactly does the nimber behaviour end? The other is the one this game shares with Toads and Frogs: a rule that is simple to state, an outcome that has a known rule, and values that nobody would want. The two games are the site’s clearest evidence that “solved” is a claim about a question rather than about a game.