Combinatorial Game Theory
who wins, and by how much
Concept

Kayles — where it appears

The octal game ·77, in which a player knocks down one pin or two adjacent pins from a row, splitting it or not. Its Grundy values settle into a period of twelve only from heap 71, with fourteen exceptions, and under misère play it is the standard example of a wild game.

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

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 The formula as the limit of periodic games. Lasker's Nim above eight versions of it with the number of counters that may be taken bounded at one to eight. Each bounded game is periodic and agrees with Lasker's formula on its first few heaps; the region of agreement grows with the bound.

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.

impartial · Lasker What a held pass can tell apart. Nim heaps, Kayles rows and heaps of Dawson's chess of sizes one to 8, grouped by whether any company of up to two of them gives a different outcome with a held pass on the board. The groups outnumber both the Grundy values and the pairs of Grundy value and held-pass value.

What a component would have to carry

For a held pass to be decided by a summary of each component, the summary must separate every pair of components some company tells apart. The Grundy value does not — Nim 1 and Kayles 8 are equal games that a held pass separates beside a single Nim heap of two. Nor does the Grundy value with the component's own held-pass value: Kayles 3 and Kayles 6 agree on both and are split by a company of two Nim heaps. Over twenty-four components, fifteen classes against fourteen pairs, and the gap widens as the pool grows.

limits · Pass The closure that is enough. A grid for Dawson's chess with heaps up to 9: rows are the largest positions classified, from one heap to four; columns the largest tests, from none to five heaps. Each cell is the number of classes found. The counts stop growing at two-heap tests and three-heap positions.

Two heaps of testing are enough

A misère quotient is computed by testing positions against positions, and the universe used to find twelve classes of Dawson's chess was every position of up to four heaps tested against every other — 511,225 outcomes. Varied one size at a time, the count stops growing at tests of two heaps and positions of three: 12,100 outcomes find the same twelve classes. The narrower universe the earlier essay drew did not merge anything; it held fewer positions. And the corner that is enough moves: for Kayles at heap twelve, two-heap tests miss a class.

complexity · Misere cost 12 classes, 7 questions. A grid for Dawson's chess with heaps up to nine: rows are the 12 misère classes of positions of at most four heaps, columns the 7 tests a greedy search chose, and each cell the outcome — N for the player to move, P for the other — when the test is added to the class.

Twelve classes, seven questions

Twelve misère classes of Dawson's chess were found by testing 715 positions against 715 others. Seven of those tests are enough to tell every class from every other — a greedy choice against a floor of four, since each test is one yes-or-no question. Kayles needs nine of 715 and Nim sixteen. The seven cost almost nothing to use and cannot be found without the whole closure, and they do not carry: the tests found with heaps up to seven tell apart only seven of the twelve classes with heaps up to nine.

complexity · Misere cost

Named alongside it

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

Exhaustive searchMisère quotientBounded universeDawsonGrundy valueIndistinguishabilityMisère playNimComplexityCounterexampleDisjunctive sumEquality

All concepts