Where the nimbers run out

End-Nim is Nim with the heaps in a row and only the two end heaps available. It is partizan by the shape of that rule — the two players face the same options, so it is impartial after all, until the row is looked at as a position and the two ends are seen to be two different things a player might take from.

Taking from the ends evaluated it and closed with a question about the 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?

It ends at once. Not at some interesting depth in the row, and not on some describable family: at two heaps, three quarters of the rows have already stopped being worth nimbers.

Seven and a half per cent #

Over rows of at most six heaps of at most four counters there are 5,460 positions. Four hundred and ten of them are worth nimbers.

The number is small and the way it gets small is worth reading before it is explained. Four hundred and ten of 5,460 is one row in thirteen, and the rung below’s framing — a single heap is a Nim heap, every palindrome is a nimber — invites a reader to picture the impartial part as a substantial core with partizan behaviour growing around it. It is the other way round. The impartial part is a thin residue that the first extra heap has already mostly destroyed.

The decay by length is sharp and then slow. Every one-heap row is a nimber, because a single End-Nim heap is a Nim heap and both ends of it are the same heap. At two heaps the share is a quarter, at four it is under a tenth, at six it is one row in fifteen.

Meanwhile the number of distinct values goes 4, 13, 47, 179, 641, 2,053. So the impartial part of the game is not merely a minority; it is a shrinking minority inside a population that is growing by a factor of three a heap.

What being worth a nimber means here #

The reading needs care, because End-Nim’s move rule is symmetric between the players and a game with a symmetric rule is usually called impartial outright.

It is impartial: Left and Right have identical options from every position. What that buys is a Grundy value, by Sprague–Grundy, and a Grundy value is a nimber — so every End-Nim position is worth a nimber, and the count above would be 5,460.

That is not what the count is measuring. The values here are partizan values, computed by the general recursion and reduced to canonical form, and asking whether one of them is a nimber asks whether the canonical form is that of a Nim heap. For an impartial game those two readings agree, so the 410 are the rows whose partizan canonical form is a nimber and the other 5,050 are rows whose partizan canonical form is something else.

The resolution is that End-Nim as drawn here is not impartial. The row is ordered, and taking from the left end and taking from the right end are different moves; the site’s convention gives one end to each player, which is what makes a row of four heaps a partizan position and what makes 1,2,3,4 and 4,3,2,1 negatives of one another rather than the same game.

So the question the rung below asked is a question about a convention, and the convention is the interesting one: it is what turns a game every account calls impartial into a game with 2,693 values in it.

The palindromes, which are sufficient and are not the reason #

A row that reads the same backwards is worth a nimber. That is the rung below’s observation and the sweep confirms it without exception — all 168 palindromic rows here are worth nimbers, and the census asserts it, so a palindrome worth anything else would stop the build.

The argument is a mirror strategy and it is short. If the row is a palindrome then it is equal to its own reverse, and its reverse is its negative, so the row is its own negative — and a game equal to its own negative is a second-player win in the doubled game and sits in the two-torsion of the group. Every nimber is in that subgroup, which is why the conclusion is available.

But the subgroup is larger than the nimbers, so the argument gives less than the observation claims, and the sweep says how much less by going the other way: 242 rows are worth nimbers and are not palindromes.

That is more than the palindromes. 1,2,1,3 is worth nought and reads 3,1,2,1 backwards. 4,2,3,1 is worth nought. 1,2,2,1,4 is worth star.

So the palindrome condition is sufficient, is far from necessary, and — the part worth carrying — is not the mechanism. Whatever makes a row worth a nimber, it is something 242 asymmetric rows also have, and nothing on this page says what.

Five nimbers, and one of them is nearly all of it #

The nimbers that occur are 0, ∗, ∗2, ∗3 and ∗4. Nothing above ∗4 appears in 5,460 rows, and the distribution is lopsided: 361 rows are worth nought, nineteen are worth star, four are worth ∗2, ten ∗3 and sixteen ∗4.

Three hundred and sixty-one of the 410 are second-player wins worth exactly nought, and 361 is also the count of rows worth a number of any kind. That is not two facts: the only number End-Nim ever produces is nought.

That is a strong statement about the game and it is easy to see once stated. A row worth a positive number would be a row Left wins moving second with something to spare — a row in which Left can afford to pass — and there is no such row, because every move in End-Nim removes counters from an end and every position with counters in it has a move for both players. The game has no way to bank an advantage; it can only be won or lost.

So End-Nim’s values are nought, four other nimbers, and 2,688 things that are neither numbers nor nimbers. It is a game with almost no arithmetic in it at all.

Every row is all-small, which is the stronger statement #

The claim that nought is the only number End-Nim produces is true and is weaker than what is actually the case, and the stronger statement is available from the move rule alone rather than from a census.

A game is all-small when, in every position reachable from it, either both players have a move or neither does. End-Nim satisfies that by inspection. A row with counters in it has a leftmost heap and a rightmost heap — possibly the same heap — so Left has a move and Right has a move. A row with no counters gives neither player anything. There is no third case, because a heap that empties disappears and the row shortens rather than stalling.

So every End-Nim position is all-small, and an all-small game is infinitesimal: smaller than every positive number and larger than every negative one. The sweep says so on all 5,460 rows without exception, and it says it twice — every row passes the all-small test, and every row’s two stops are zero, so no row has anywhere for a fight to end other than level.

That upgrades the earlier observation considerably. The only number is nought leaves room for a row worth $\{2 \mid 0\}$, which is not a number and is worth about a point. Every value is infinitesimal does not: all 2,693 values in the game are crowded into the gap between the negative numbers and the positive ones, and the whole 2,693 could be added together a thousand times over without reaching a single counter’s worth of advantage.

Which is why End-Nim has no arithmetic and not merely no numbers. A game with numbers in it lets a player trade — take four points here, concede three there — and the trade is what makes a value useful away from the board it came from. Here there is nothing to trade, and every one of the 2,693 values is a statement about who moves rather than about how much anything is worth.

The one place the two readings can be compared #

There is a way to hold the impartial and the partizan readings of End-Nim side by side, and it is worth doing because it makes the size of the difference concrete.

Give the row to the impartial recursion — both players may take from either end — and every position gets a Grundy value, and a row of six heaps of at most four gets one of a handful of them. Give the same row to the partizan recursion with the ends assigned, and it gets one of 2,053 values.

The two are answers to different questions about the same drawing, and the partizan answer is not a refinement of the impartial one: a row worth ∗3 under the partizan reading need not have Grundy value 3 under the impartial one, because the impartial game allows moves the partizan game forbids.

So there are two End-Nims and the literature’s is the impartial one. Albert and Nowakowski’s analysis, which the rung below records and does not reproduce, is of the partizan version — and the reason it is a paper rather than a paragraph is exactly the 2,053.

Where the interesting values are #

The 2,688 are not exotic in shape, and they are also not as varied as the count suggests: every one of them is an infinitesimal, for the reason the section above gives. Their count grows like the number of rows.

What is worth noticing is where they concentrate. Rows of two heaps have thirteen distinct values between sixteen positions; rows of six have 2,053 between 4,096. So the ratio of values to positions climbs from four fifths to a half and then keeps falling slowly — the rows are not repeating themselves much, which means End-Nim is producing genuinely new values with almost every arrangement rather than a small set of values many times over.

That is the opposite of what most of the games on this site do. Clobber rows of seven squares produce fifty-six distinct values between 3,272 positions; Toads and Frogs produces 113 between 3,270. End-Nim produces 2,053 between 4,096, which makes it the most value-rich small game in the sweep by a wide margin.

A game with a symmetric move rule and no arithmetic behind it turns out to be the one that reaches furthest into the value space. That is not a paradox, and the mechanism is the ordering: the sequence of heaps is the position, permuting it changes the game, and there are a great many sequences.

What a solver would do with this #

The counts have a practical reading and it is not encouraging.

A solver for a partizan game wants a shortcut, and the shortcut every impartial game offers is a single number per component. End-Nim offers it on 7.5 per cent of rows, and the 7.5 per cent are not the rows that turn up: a row in play has usually had counters taken off one end, which breaks whatever symmetry it had.

Worse, the rows that do carry nimbers are cheap to recognise only in the palindromic case. Checking whether a row reads the same backwards is a glance; checking whether it is one of the 242 means evaluating it, which is the work the shortcut was meant to avoid.

So the impartial theory buys End-Nim almost nothing, and the reason is worth separating from the count. It is not that the values are hard; it is that the game has no components. A row is a single indivisible object — it never falls apart during play — so there is nothing for a per-component number to be a number of, and Sprague–Grundy’s whole purpose is to collapse a sum.

What the census does not say #

Three limits, and the first bounds every number above.

Heaps of at most four. Every count is over rows whose heaps are one, two, three or four counters. A row of two heaps of a hundred is a different position from a row of two heaps of four and this sweep does not contain it; the two-heap rule covers that family exactly and it is the only family covered.

Being a nimber is a property of the canonical form. A row worth ∗3 is a row whose canonical form is that of a Nim heap of three, which is a stronger statement than the row plays like a Nim heap of three in this company. The two coincide for values, since equal values are interchangeable in every company, so the distinction does not bite here — but it is why the test is a form comparison rather than a play-out.

The count of five nimbers is a count about this sweep. Nothing above ∗4 occurs among rows of at most six heaps of at most four counters, and nothing here says ∗5 is unreachable. A row of eight heaps has more room in it, and whether the set of nimbers reached grows with the row or stops at five is a computation of the same shape and one size larger.

And the palindrome argument is stated and not the whole of it. The mirror strategy shows a palindrome is its own negative; getting from there to worth a nimber uses the fact that the two-torsion of day-two values contains non-nimbers, so the implication in the sweep is stronger than the argument given. Why every palindromic End-Nim row lands on a nimber rather than on one of the other self-negative values is not answered here.

The convention, named #

Normal play. A row is a sequence of positive heaps; a move takes any positive number of counters from the leftmost or rightmost heap, and removing a heap entirely exposes the next one. Left takes from the left end and Right from the right, which is the convention that makes the game partizan and which is the whole reason this page has anything to count.

Every value is computed by the recursion and reduced to canonical form. A value is called a nimber when its canonical form is that of a Nim heap, read off the name the reduction produces rather than tested by comparison against a list.

Where the ladder goes next #

The endnim anchor has two rungs: the game with its two-heap rule, and now how little of it the impartial theory reaches.

The rung above is the 242, and it is the rows that are their own mirror. The obvious first guess — that the nimber rows are the rows worth the same as their own reverses, which is to say the rows equal to their own negatives — turns out to be exactly right at this size: 410 rows are their own negatives, 410 are worth nimbers, and they are the same 410. That is more than the group law promises, since the two-torsion of the value group contains games that are not nimbers, so it is a fact about End-Nim rather than about games. What it does not deliver is the shortcut this page wanted, because deciding whether a row is worth the same as its reverse means evaluating both.

Two neighbours are worth the trip. Where the impartial theory stops is the general account of what one number per position can and cannot carry, and End-Nim is its sharpest example: a game whose rule is symmetric, whose convention is not, and whose values are almost never nimbers. And the values that are their own negatives is the subgroup the palindrome argument lands in, which is larger than the nimbers and is why the argument gives less than the observation.