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 4 essays across 3 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 rung below's composition rule 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

Named alongside it

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

GenusGrundy valueMisère playMisère quotientWildOctal gameDawsonDisjunctive sumExhaustive searchBounded universeComplexityCounterexample

All concepts