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 8 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 A line of losses. Positions made of up to 28 heaps of two and up to 28 heaps of four with a held pass, the losses filled. They are the empty board, four-heaps alone at 7, 13, 19 and 25, and a single diagonal line: 2k + 3 heaps of two beside 2k heaps of four.

The table closes, until heaps of four

Classes that no company can tell apart always combine, so the question left by the held pass is not whether it has an algebra but whether the algebra is finite. Computed the way a misère quotient is, it is: four classes for heaps of one where misère play needs two, eleven for heaps up to two, fourteen up to three, nineteen for Kayles rows up to five. Admit Nim heaps of four and the table never closes — a single line of losses, 2k + 3 heaps of two beside 2k heaps of four, gives every count of twos a class of its own. And at the bottom of every closed table sits the normal-play group, with the loss moved to nim-sum one: on a crowded board the held pass is a heap of one.

limits · Pass Six rulesets, and the heaps that stop mattering. Single heaps of six impartial rulesets classified under three-player play with one player against a coalition of two. Nim's heaps fall into three classes; subtraction {1, 2} keeps five, Kayles six, subtraction {1, 3} ten, subtraction {2, 3} twelve and Dawson's Kayles ten before every larger heap is interchangeable, and three rulesets have a smaller heap that joins the large class early.

A coalition counts to three

Three-player Nim with one player against two collapses to six classes, because every heap of two or more is a store of tempo either side can draw on. Put the same coalition on games whose heaps are not all stores and it does not collapse: subtraction {1, 2} keeps five kinds of heap, Kayles six, subtraction {1, 3} ten and {2, 3} twelve, each count settling as the range grows. Past a threshold the large heaps are interchangeable again — and in every one of the five, unlike Nim, a single large heap hands the game to the coalition. The classes neither refine the two-player values nor coarsen them: {1, 3} has two Grundy values and ten coalition classes.

limits · Multiplayer Ten classes, and a rule to name them. The classes of subtraction {1, 2} with one player against two: a grid of heaps of one counted modulo three against no other heap, a heap of two or a heap of three, each cell giving the lone player's result with each player to move, and a tenth class — anything with a heap of four or more, or two heaps from two and three — won by the coalition.

Units modulo three, and one choice

Nim's rule for one player against two has a shape: count the heaps that always last one move, modulo three, allow one heap that offers a choice, and give any second choice to the coalition. Subtraction {1, 2} has exactly that table — ten classes, nine of them a count of ones against nothing, a two or a three — and so do Kayles, where a heap of three is a heap of two with a unit beside it, and Dawson's Kayles. Subtraction {1, 3} and {2, 3} do not: a board with two choices on it can still be the lone player's, and the short key fails. And {2, 3} and Dawson's Kayles give every heap to ten exactly the same menu of game lengths, so what a coalition reads is not how long a heap can last.

limits · Multiplayer

Named alongside it

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

Exhaustive searchMisère quotientIndistinguishabilityNimDawsonDisjunctive sumBounded universeGrundy valueMisère playSubtraction gameComplexityCounterexample

All concepts