Combinatorial Game Theory
who wins, and by how much
Concept

Tame — where it appears

An impartial position whose genus symbol is one of Nim's own, so misère play treats it exactly as Nim would. It is the class the genus theory works on, and the boundary is sharp: the composition rule for symbols is exact on tame pairs and wrong on almost every pair with a wild component.

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

Also named here as wild — the same set of essays touches all of them, so they are one junction rather than several.

The genus of a sum. Every pair of heaps up to 9 counters, from nine impartial games, filed by the genus symbols of its two parts. The claim under test is that the file determines the answer; it does, and neither half of the symbol determines it alone.

The genus of a sum

A genus symbol is meant to be carried one per heap, so that a solver never has to look at the heap again. That is a claim that the pair of symbols determines the sum's, and across nine games and 405 pairs it holds without exception — while the bases alone determine it in only 38 of 50 cases and the superscripts alone in 70 of 74. Both halves of the symbol are load-bearing, and two wild heaps can add to a tame sum.

limits · Genus A function on the wild side too. Every pair of heaps filed by the pair of genus symbols it is made from. No file holds two different sums, including the sixteen with a wild symbol in them.

A function with no formula

The rule that composes genus symbols is exact on tame pairs and wrong on all fourteen wild ones, which looked like an exact boundary. Two heaps further it is wrong on 34 of 35 and right on one — Kayles' five and nine — so the boundary was a boundary of the pool. What survives is stronger and stranger: the pair of symbols still determines the sum on the wild side, and no rule of that shape describes it.

limits · Genus The same rules under the convention they were posed in. Dawson's chess under misère play, which is how Dawson posed it. Under normal play every position of the game collapses onto one of a handful of nimbers however large the heaps are allowed to get. Under misère play the positions that behave alike form classes whose number grows with the heap limit, and a heap carries a genus rather than a value. The first wild heap is where the two accounts stop resembling each other, and the classification doubles at exactly the limit that admits it.

The convention Dawson actually used

Dawson published his puzzle as a problem where running out of moves loses you the game, and every compact result about ·137 is about the other convention. Under his own, nine values become a classification that doubles the moment a wild heap enters the range, and a heap stops carrying a number at all.

history · Dawson A staircase, not a slope. The number of misère classes of Dawson's chess positions as the largest heap allowed rises from three to 16, computed with positions of at most three heaps and tests of at most two. The count stays flat for several heaps at a time and then jumps.

A staircase, not a slope

With the misère closure cut forty-fold, Dawson's chess can be classified at heaps far beyond nine. The count of classes is a staircase: six from heap three to eight, twelve from nine to twelve, seventeen from thirteen to sixteen. Normal play steps once in that range, from four to eight at heap thirteen, where a Grundy value of four first appears. Misère play steps there too, and once more at heap nine, where normal play does not move at all — the first wild heap. Heaps eleven, fifteen and sixteen are also wild and move nothing.

complexity · Misere cost Misère Cram, board by board. The normal-play value and misère genus of every Cram rectangle with at least two rows and at most twenty squares. 12 are fickle, 4 × 4 is firm, and 3 × 6 and 4 × 5 are wild.

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.

impartial · Cram A staircase, not a slope. The number of misère classes of Dawson's chess positions as the largest heap allowed rises from three to 20, computed with positions of at most three heaps and tests of at most two. The count stays flat for several heaps at a time and then jumps.

A heap that loses under both endings

The misère classes of Dawson's chess climb in steps, and the two steps to heap sixteen landed on first appearances: the first wild heap and the first Grundy value of four. Run on to twenty, the count sits at seventeen through heap nineteen and then jumps to twenty-four, on a heap worth nought whose genus is tame. Heap twenty is the first heap that loses for the mover under both endings, it behaves like two Nim heaps of two, and most of what it adds is a new way of telling old positions apart. What every step to twenty shares is a genus no smaller heap has. The search that finds this stops at twenty-one, when the positions it remembers outgrow the table that holds them.

complexity · Misere cost

Named alongside it

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

GenusMisère playWildGrundy valueMisère quotientOctal gameDawsonExhaustive searchBounded universeComplexityDisjunctive sumSubstitution

All concepts