Combinatorial Game Theory
who wins, and by how much
Concept

End-Nim — where it appears

Nim with the heaps in a row, where a move may only take from the leftmost or rightmost heap. Giving one end to each player makes it partizan, and it is then the most value-rich small game on this site — thousands of distinct values and almost no arithmetic.

Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.

End-Nim: a player at each end of the row. Rows of heaps in which Left may take from the leftmost heap and Right from the rightmost. The value beside each row was computed by the game recursion and reduced to canonical form; the outcome beside it says who wins. A single heap is a Nim heap, because both players may take from it — and that is the last thing about this game that looks like Nim.

Taking from the ends

End-Nim is Nim's board with a player at each end, and it takes one sentence to state. Not one of its 5,460 small positions is worth a non-zero number — the game is all-small, so zero is the only number any of them can reach — and there are 2,693 distinct values between them. The outcome says a great deal more: 4,738 of those positions are won by the same player whoever moves, and on two heaps the rule is that the larger end wins.

positions · End-Nim How old a value is, against how big a board it takes to show it. For each birthday, the range of sizes of the smallest position exhibiting a value of that age. The bars do not march rightwards: values born on the last day of the sweep are shown by six-piece positions, and values born on the fourth need up to fifteen.

The cheapest way to show a value

Eleven thousand positions from fifteen rulesets reach 1,193 values, and for each of them there is a smallest board that shows it. Set against the birthday the two measures agree hardly at all — until the numbers are taken out, at which point they agree rather well, and the whole apparent independence turns out to be a fact about integers.

values · Realisability Three counts, and two of them are the same number. Rows of End-Nim that read the same backwards, rows equal to their own negative, and rows worth a nimber. The second and third counts are identical over every row in the sweep, so being its own negative is exactly the condition for being worth a nimber in this game.

The rows that are their own mirror

Four hundred and ten End-Nim rows are worth nimbers and 168 of them are palindromes, so a condition covering the other 242 was outstanding. It is that the row is equal to its own negative — and on this game that condition is not merely sufficient but exact, which is more than the group law promises and is a fact about End-Nim rather than about games.

positions · End-Nim Two thousand values and no temperature. Every End-Nim row of up to six heaps, with its temperature. Not one of the 5,460 is hot, every one of them is worth an infinitesimal, and the 361 worth numbers are 361 rows worth nought.

A game with nothing at stake

The rung below explained a coincidence with a claim it did not compute: that End-Nim carries no hot self-negative values. The census says something stronger. Not one of 10,919 rows across three shapes of board is hot, every one of them is worth an infinitesimal, and the 361 rows the earlier census called numbers are 361 rows worth nought. The reason is one line of the rule, and 2,693 distinct values sit underneath it.

positions · End-Nim The birthday is a floor. How many more pieces a value's cheapest exhibit needs than the value has days. It is never fewer, on any of the 728 non-number values, and it is exactly none on 476 of them.

The birthday is a floor

The rung below measured a correlation of 0.73 between a value's birthday and the size of its cheapest exhibit, and asked which values are dearer than the birthday suggests. The relation is not a trend. Over all 728 non-number values the exhibit is never smaller than the birthday and is exactly the birthday on 476 of them, and the excess on the other 252 belongs to the game rather than to the value — the ruleset accounts for 40 per cent of its variance.

values · Realisability The trend, running backwards. The excess grouped by the width of the value's canonical form. Values with wide option lists are exhibited nearer their birthdays than narrow ones, which is the opposite of what the proposal predicted.

Wider costs less

The rung below found the cheapest exhibit of a value never smaller than its birthday, exactly equal on two thirds, and the ruleset explaining 40 per cent of the rest. The variable it proposed for the remainder was the width of the form. Width and excess correlate at −0.39: the wider the value, the closer to its birthday it is exhibited, and inside a ruleset the relation cannot even agree on a sign.

values · Realisability

Named alongside it

The objects these essays reach for when they reach for this one.

Canonical formEnumerationCounterexampleValueBirthdayExhaustive searchHackenbushInvariantNimberPartizanRealisabilityCorrelation

All concepts