Every essay — page 16
Impartial games
Both players have the same moves. Every such position is a Nim heap, and the theorem that says so is the field's first.
One split is enough
A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.
The formula is a limit
Cap the take in Lasker's Nim at k counters and the game is a finite rule table, 4.33…3, whose Grundy sequence repeats with period k + 1 rounded up to even and follows Lasker's formula until the cap bites. The formula is what those periods converge to. And the same column of codes, with a free split in front, holds Kayles itself: the rule 4.4 on a heap of n + 1 is Kayles on a row of n.
Cram with the last move losing
Under misère play every Cram rectangle to twenty squares is tame at the start except 3 × 6 and 4 × 5, and twelve of the fifteen boards two rows deep behave like one counter or none. The pairing that settles even boards under normal play hands the misère game to the first player, who wins by any vertical domino. And the tame boards are not tame inside: wild positions appear on boards as small as 3 × 4, always at ten empty squares, the length at which the strip goes wild.
A rare class exclusive-or respects
The rare values of ·007 were measured by rank — everything outside the twenty-two commonest — and found getting commoner. A sparse-space argument needs a different split: a rare class closed under nothing and a common class closed under exclusive-or, which is to say a parity of bits. Over every parity of every bit, ·007 and ·6 have no class that thins. Across the 79 growing octal codes of up to three digits, one does: ·354, whose odd values fall from 288 in its first two thousand heaps to seven in its last ten thousand.
The pairs are read from the bottom bits
Some matching of Welter's coins reads the position's value, and usually only one does — but which? The rule is short: pair the two coins whose squares agree in the most low-order bits, and repeat. It reads the value on every one of 3,696 positions of two to eight coins, where no other natural rule manages half. And it has a proof two lines long, because x − 1 flips a number's trailing bits, so a pair's animating value depends on where its squares part on the binary trie read from the bottom. What it is not is a strategy: a move from a lost position can be answered inside its pair only two times in five.
The odd values keep coming
·354 is the one growing octal code of up to three digits whose values have a class that thins: 288 odd values in the first two thousand heaps, seven between ten and twenty thousand, the last of those at 18,908. A sparse-space argument needs that class to stop. Taken to a hundred thousand heaps it does not: 48 more odd values arrive after twenty thousand, every block of ten thousand holds some, and the last in range is at 99,600. They keep no schedule a remainder can see, their gaps are spread like arrivals, and most of them are one number, 37 — each one a heap where every split that could have reached 37 misses it.
One square for every coin
Nim's strategy has two halves: every heap has exactly one target, the nim-sum of the others, and the heaps carrying the top bit of the nim-sum are the ones that can reach it. Welter's game keeps the first half on every one of 18,470 coins tried — one square per coin makes the value nought, and the winning moves are the coins above theirs — and the square is found by walking up the binary trie from the value of the other coins. It loses the second half. And at four coins it loses nothing: the losses and the winning moves are Nim's exactly, by a two-line proof, while at six coins no Welter loss is ever a Nim loss, because the last bit of a losing position is a count of pairs.
Two takes, one line
A subtraction game with two legal takes, a and b, has a Grundy sequence that fits in one sentence: cut the heap's remainder modulo a + b into blocks of a, alternate nought and one, and turn every even block at or past b into a two. The proof is three cases long and holds for every pair. Add a third take and the sentence has no successor — but it does not vanish. The period of a three-take game is a sum of two of its takes six times in seven, which sum is decided by the third take's remainder modulo the first two's period, and the long irregular periods cluster on the one arrangement where the third take is the other two added together.
The third take is the other two
A subtraction game whose third take is its first two added together was where the long irregular periods of three-take games clustered, and the question was whether that one arrangement has a formula or is where the formulas stop. It has one. Divide out any common factor and look at the heap one short of the middle take: if it would be a loss when only the smallest take is allowed, the period is the smallest take times twice the middle take plus a remainder, otherwise it is short and the whole sequence is two bands of blocks. The formula gives the exact period of every one of the 3,160 games to eighty.
Where it stops
Misère play and loopy games: the two places the theory itself gives way — values that stop composing, and a recursion with no bottom.
Misère play
Change one word — the player who cannot move wins — and the games are identical, the strategies are not, and almost every theorem of the normal-play theory stops being true. It is the cheapest possible modification and the most expensive.
Loopy games
The whole theory assumes play stops. Allow a position to recur and the induction that every value rests on has nothing to stand on — and a fifth outcome appears that normal-play theory has no name for.
What survives misère play
Misère play destroys the value theory, and something much smaller grows back. Fix one game, look only at sums of its own positions, and the classes that behave alike form a monoid — computed here, and larger than the normal-play answer every time.
Start at the end and work backwards
When play can return to where it started there is no bottom for the recursion to stand on. What replaces it begins at the positions where somebody has already lost and propagates outwards — and the positions it never reaches are exactly the draws. There is no test for a draw, and there does not need to be.
An outcome with no value behind it
Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches.
The condition the recursion rests on
Not that the moves run out, and not that the options are few. Poker Nim's heaps can grow without bound and it ends; the game called `on` has one option and never does. What every game value needs is that no infinite run of moves exists — and there are three separate ways to fail it.
All ladders · Every object named here · The position index · Figures that play back · Search