Genus — where it appears
Named by 16 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
Tame and wild
The genus is a Grundy value with a tail — the misère values of the position with 0, 1, 2, … heaps of ∗2 added — and a game is tame when its symbols are the ones Nim heaps have. Computed here for seven games over heaps 1 to 14: Kayles goes wild at heap 5, Dawson's chess at heap 9, the octal game ·6 at heap 7, and heaps 3 and 11 of Dawson's chess are both worth ∗2 under normal play with only one of them tame.
Two misère outcomes are not enough
Knowing who wins each part does not say who wins the sum. Over 676 sums built from a pool of twenty-six positions, nine of the sixteen pairs of outcome classes settle the answer under normal play and not one of the sixteen settles it under misère — and the nine that work are theorems about a value being zero, which is exactly the thing misère play does not have.
What a tame heap may be replaced by
Calling a heap tame is only worth anything because a tame heap can be swapped for a Nim position with the same genus in any misère sum. The swap is not always a single heap: Kayles' heap of eight is worth ∗ under normal play and carries the genus of 2 + 3, and substituting ∗ instead gets three of the twenty-eight Kayles pairs wrong.
Two ways to end with no bound
Sylver Coinage and the hydra are both guaranteed to finish and neither will say when. The difference is that one of them carries its own bound: every move in Sylver removes at least one gap, the gaps can be counted in a moment, and over ten openings the longest play uses every single one. The hydra has no decreasing quantity a solver can hold — three hydras of five nodes each take seven chops, twenty-one, and a number past two hundred and seventy-nine that this machine never reaches.
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.
The rule the symbols follow
Two genus symbols make a third by three lines and no lookup table: the base exclusive-ors, the sum is fickle only when every component is, and the symbol follows. Checked on 252 pairs across nine games it is right on 238 — and the fourteen failures are exactly the fourteen pairs with a wild heap in them, which is the boundary the genus is defined up to arriving as a measurement.
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.
The wild side does not close
The rung below asked for the wild composition table and for two things about it: whether the wild genus symbols form a small closed set, and whether that set is a misère quotient in disguise. Building the table needed a wider sweep — nine counters a heap gives a diagonal rather than a table — and both answers are no. Not one of the twelve entries is a symbol any wild heap carries, and two wild heaps added together are tame two thirds of the time.
Closing the wild side
The twenty-two wild genus symbols are not closed under addition, and the rung below offered two answers: a monoid nobody had guessed, or no algebra at any size. Neither. Five of the six games with wild heaps close at three or four heaps, with closures of two to five symbols, and the sixth is still growing.
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.
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.
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.
No number bounds it
Sylver Coinage cannot be given a termination measure in the natural numbers: from {2} the game can last one move, two, or any number the second player chooses. The measure proposed for it — the gap count beside the number of distinct primes the named numbers share — rises on {4} + 6. Count the primes with their repeats and it falls on every one of 42,519 moves checked, and it is exact: the game tree is ω squared tall, and the height of a position is ω times the prime factors of its gcd plus the gaps that are left.
Start at four
Every order a program could compute had made the Sylver Coinage search that finishes dearer than trying the smallest move first, and the free oracle that puts a winning move first costs under a third of it. Two orders a game program would actually use do better: a history table of numbers that have won before wins back 27 per cent of that gap, and a fixed order learned on small positions the same on larger ones. Both are learning one thing. Trying the smallest move first, but from four, wins back 31 per cent and beats smallest first on 1,695 of 1,766 positions — because naming 2 leaves a two-generator semigroup, which is symmetric and never lost for the opponent, unless 3 is already reachable.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Grundy valueMisère playMisère quotientExhaustive searchOctal gameDawsonImpartialNimTameWildOutcome classDisjunctive sum