Combinatorial Game Theory
who wins, and by how much
Theme

The thread: Equal, better, or neither

Two positions can be equal, one can be better, or the pair can be genuinely incomparable — a fourth relation with its own symbol. Deciding which is a search rather than a look, and equality quantifies over every game there is.
Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does. Sums and comparison

Comparing positions

One position is worth at least another when the second player wins their difference. That is the only definition there is, it is a computation rather than a judgement, and it produces an order in which some pairs are simply not comparable.

 Every impartial position is a Nim heap. A heap in a subtraction game, its Grundy value, and the Nim heap it is equivalent to. The equivalence is exact: the two positions have the same options up to value, so they behave identically in any sum, which is the Sprague–Grundy theorem. Impartial games

Every impartial game is a Nim heap

Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.

 The same game, written twice. A position as it arises and the same position reduced. Left would never move to −1 when 0 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form. Values

Canonical form

Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.

 The misère quotient of Nim, heaps up to 2. Each row and column is a class of positions that no sum in this universe can tell apart, and each entry is the class their sum falls into. The shaded classes are the ones a player wants to hand over. Under normal play the same positions need only the Nim values; the extra classes here are what misère play costs. Where it stops

What survives misère play

Misère play destroys the value theory, and something much smaller grows back. Fix one game, look only at sums of its own positions, and the classes that behave alike form a monoid — computed here, and larger than the normal-play answer every time.

 One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow. What it costs

A position reached eleven ways is one position

A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.

 The Grundy values of ·137, and the exceptions to its period. An octal game's Grundy sequence, with the periodic part in gold and the exceptions in magenta. The exceptions are the point: a sequence described as eventually periodic contains values that disagree with the value one period later and always will, so the period is a statement about a tail and not about the sequence. The rule used to identify an exception is printed, because published lists of them differ by which convention was used. How it was found

A chess problem that turned out to be an octal game

Dawson posed it in 1934 as a puzzle about pawns. It is the octal game ·137, its Grundy sequence is eventually periodic with period 34 from heap 52 — and the word doing the work in that sentence is eventually, because five values below the start disagree with their repeats and always will.

 How many ups, bracketed. Every position here is all-small, so no number says anything about it and the yardstick has to be ↑ instead. Each bar spans the multiples of ↑ the position lies between: the largest it is at least, and the smallest it is at most. Four of the seven are pinned to a single multiple of ↑; the rest keep a band that comparison cannot narrow, the widest being ∗ at four ups of slack. Sums and comparison

How many ups

When every component of a position is smaller than every positive number, no number can decide it. What decides it is a count of ups — and comparison can pin that count down exactly, except when a star is present, when it cannot.

 Every position has an exact opposite. A position beside its negative, which is the same game with the players exchanged, and the sum of the two. The sum is worth zero every time — a second-player win — because the second player can answer each move with its mirror image. It is the fact that makes values a group, and it is what lets one position be subtracted from another. Sums and comparison

Turn the board through a right angle

A two-by-four Domineering board is worth something no number can express, and Right is ahead on it. Turn a second board through a right angle, put the two side by side, and the total is exactly zero. Every position has an exact opposite, and that single fact is what makes subtraction — and therefore comparison — possible at all.

 Folding a 4×4 board by its symmetries. The size of a Domineering solver's table when positions related by a board symmetry are stored once. The saving rises toward the size of the symmetry group and stops there — it is a constant factor by construction, and no board is large enough to make it anything else. What it costs

What counts as the same position, and what that is worth

Folding a 4×4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522 — a saving of 3.75, against a ceiling of exactly 4. An orbit cannot be larger than the group acting on it, so this is the one saving in the subject that can never change an exponent.

 Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer. Sums and comparison

Comparing two positions means playing a third

There is no way to look at two games and see which is better. The question "is G at least H?" is answered by building G − H and asking who wins it — so the most basic operation in the theory is a decision problem, and every canonical form is built out of them.

 The same game, written twice. A position as it arises and the same position reduced. Three of the options are dominated — a sibling is at least as good for the player who owns them — so they can go. The two games are equal — checked, not assumed — and the second is the canonical form. Values

Two hundred and fifty-six ways to write twenty-two things

Every game whose options come from the four born on day one — there are 256 of them, and between them they carry 22 values. The reduction that collapses one to the other has choices in it at every step, and uniqueness is the claim that none of the choices matters.

 Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does. Sums and comparison

Confused is not the same as unknown

Two positions can be neither greater, nor smaller, nor equal. That is a fourth relation with its own symbol, it is a fact about the pair rather than a limit of the method, and it is what makes a game worth playing — a position is a first-player win exactly when it is confused with zero.

 The context that tells them apart. Two positions put into the same company, one context at a time. Each column is a game X; each cell is the outcome class of that side added to X. Equality means every column agrees, for every X there is — so a single disagreeing column is a disproof, and agreement across a bounded list of contexts is evidence rather than proof. The proof is that the difference is zero. Sums and comparison

Equal in every company

Two games are equal when no third game can tell them apart — a quantifier over every position there is, discharged by one finite test. A search over 184 contexts separates all 5,790 unequal pairs it is handed and still calls two different games the same, which is exactly why G − H = 0 is a theorem and an exhaustive search is not.

 Kayles ·77: what each heap may be replaced by. Each heap with its genus, the Nim position carrying that genus, and the Nim heap a reader would substitute from the normal-play value alone. The two columns agree except where the genus belongs to no single heap — and there the second one is wrong, in sums, by exactly the amount the census counts. Where it stops

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.

 Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer. Values

What a move is worth to the player making it

The gain from a move is the option minus the position it was played from — and that is a game rather than a number, so two moves can be incomparable instead of one of them being best. Temperature is what happens when the largest of those games is asked for a single number.

 Classes needed, as the heaps get bigger — Dawson's chess ·137. How many kinds of position there are, against how large a heap the universe allows. Under normal play the answer stops growing as soon as the Grundy values stop growing. Under misère play it does not stop, and every new class is a pair of positions that behave identically under normal play and differently under misère. What it costs

The cost is in the closure, not in the positions

Under normal play, Dawson's chess needs four classes for every heap up to twelve, because its Grundy values stay at three or below there. Under misère play the same game needs six, then twelve, and the number rises with the universe rather than with the position — which is a different kind of expense entirely.

 How old a form is, and how old its value is. Every one of the 256 forms born by day two, placed by the depth it is written at and by the birthday of the value it carries. Nothing sits above the diagonal, because a form cannot be younger than the value in it; the diagonal holds the forms written at exactly their value's birthday, and everything below it is a position written older than it needs to be. The count in each cell was obtained by canonicalising all 256 forms and measuring both depths. Values

How old a value is

A form's depth bounds the birthday of the value inside it, and reducing to canonical form attains the bound — for all 22 values born by day two, with no exception. Twenty-four of the 256 forms are older than what they are worth. The same reduction that makes the bound tight is what puts day three within reach: 98 option sets a side instead of four million, 9,604 forms, 1,474 values, a quarter of a second.

 Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in. What it costs

Knowing who wins, and knowing what it is worth

Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.

 Swapping a branch for another of the same value. The ordinal sum of a base with a branch, and the same sum with the branch replaced by a heap of a different game carrying the same Grundy value. The two are compared by playing their difference, not by inspection — and they agree every time, which is what the colon principle claims and what the partizan case denies. Sums and comparison

When the nested sum only sees the value

The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.

 How often one value is above another. The partial order counted on two successive days. The proportion of pairs that can be compared at all falls sharply, and so does the proportion of values that can be compared with zero — which is the proportion of positions whose winner does not depend on who moves. Sums and comparison

How rare it is to be bigger

Values are partially ordered, and 'partially' does most of the work. On day two, 179 of 231 pairs can be compared and 13 of the 22 values can be compared with zero. One day later the shares are 60% and 29%, and the largest set of mutually incomparable values found rises from four to at least twenty-three. Comparison is the exception; confusion is what values normally do to one another.

 The fight never runs backwards. Each of the 22 values born by day two, drawn from its right stop to its left stop — what Right gets moving first, and what Left gets moving first, once the fight has been played out to a number. Every bar runs the same way. The left stop is never below the right one, which is what "both players are trying to improve their own position" amounts to, and the cold rows, where the two coincide, are drawn as a single point. Values

The fight never runs backwards

Left's stop is never below Right's — in every one of 1,780 distinct values, computed twice by two independently written routes, with nothing that disagreed anywhere. The inequality is what makes a mean value well defined and a fight a fight; and where it collapses to equality, 433 of the 460 cold positions turn out not to be numbers at all.

 Options handed to Left in 1 | −1. A position, and one candidate option after another added to it. Where the gift is one the player would never take the value does not move at all; where it is one they would, it does. The last column is the value of the enlarged form, computed by the same recursion as the original. Values

An option nobody would take

Every reduction of a form deletes. The gift horse principle adds: a move may be handed to a player for nothing, provided it is one they would never choose. Over all 484 additions to the values born by day two, 283 leave the value exactly where it was and the 201 that move it are precisely the ones the condition forbids — with the boundary at *not better*, which is a weaker demand than *worse*.

 How much company equality needs. Each row restricts the quantifier in the definition of equality to the games named, and counts how many of the 22 values born by day two survive as distinct. The bar is the same number drawn; the jump from nine numbers to four games is the whole argument. Where it stops

Equal in this company

Equality quantifies over every game there is, and the quantifier can be made smaller. Restricted to a company of nine numbers, the twenty-two values born by day two collapse to seventeen; restricted to four games — nought, one, minus one and star — they stay twenty-two, and no three of the four will do. The company that decides equality is tiny, and it has to contain a star.

 What the reduction collapses. Each reduced form with the values that reduce to it. The largest class is the one that reduces to zero and it holds every infinitesimal on the list, which is exactly what the reduction is for — against a hot background, none of them is distinguishable from nothing. Sums and comparison

What is left when the small change is thrown away

Canonical form answers a demanding question: which positions are interchangeable inside every sum whatever. A player with a hot board does not have every sum — an infinitesimal difference cannot decide anything against a genuine fight — so there is a coarser question with an exact answer. The reduced canonical form takes the 1,474 values born by day three to 61, with 292 of them collapsing to zero, and it is a homomorphism on all 8,100 pairs tested only when a second pass is made.

All themes