Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The notation is not the position

A brace form, a binary numeral, an octal code and a thermograph are four ways of writing a position down, and each throws something away. Occasionally one of them turns out to be the argument.
The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number. Particular games

Hackenbush is a numeral

Draw a stalk of coloured edges. Read it as a string, blue for one and red for zero, and the string is the binary expansion of what the position is worth. Not approximately — exactly, and the site computes it both ways and refuses to build if they disagree.

 The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake. Temperature

Reading a thermograph

A thermograph is two walls rising from a number line, closing in as the tax on moving increases, and meeting where the position stops being worth fighting over. Everything about a position's hotness is in the shape.

 The simplest number in between. A game whose options are numbers is worth the simplest number strictly between them — and simplest means born earliest, so integers come before halves and halves before quarters. It is not the midpoint, and the difference is the whole content of the rule. Values

The simplicity rule

When both players' options are numbers, the position is worth the simplest number strictly between them. Not the midpoint, not the average, and the difference between "simplest" and "middle" is the entire content of the rule.

 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.

 Grundy values for subtraction of 1, 2, 3. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none. Impartial games

Grundy sequences, and where they stop being predictable

Computing one Grundy value is a mex. Computing all of them produces a sequence, and the sequences do something nobody has fully explained — most of them eventually repeat, some of them take thousands of terms to start, and for a few nobody knows whether they ever do.

 What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut. What it costs

The game with the shortest rule is the hard one

Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.

 A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values. How it was found

A golden ratio thirty years early

Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

 The octal game ·137, read out. An octal code is a rule table. The kth digit says what a player may do after taking k tokens from one heap: end that heap, leave one heap, or split the rest into two. Three bits, one digit, and the whole family of take-away games becomes something that can be listed and swept. Impartial games

Naming a game with a number

An octal code is a rule table compressed into an integer. It turns "which game" into something that can be counted through, which is how the family was swept — and how the games nobody can solve were found.

 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.

 The numbers, by the day they are born. Zero on the first day, ±1 on the second, and thereafter the simplest number in each remaining gap. Every number reachable in finitely many days is a fraction with a power of two underneath, and every such fraction appears — which is a strange thing for a construction with no arithmetic in it to produce. Values

The day a number is born

Start with a position in which neither player can move, apply one rule, and the numbers appear — but only the fractions with a power of two underneath, and only in a particular order. That order is what "simplest" means.

 6 octal games, and which of them settle. Each row is an octal game: its code, the moves it allows, the first two dozen Grundy values, and whether a period was found in the values computed here. Guy and Smith surveyed these by hand in 1956 and conjectured that every finite octal game is eventually periodic. Seventy years and a great deal more arithmetic later, the rows in magenta are the state of that conjecture — not counterexamples, but sequences in which nothing periodic has yet appeared. How it was found

The sequence nobody has settled

Guy and Smith surveyed the octal games by hand in 1956 and conjectured that every finite one is eventually periodic. Seventy years and a great deal more arithmetic later, some of them have settled and some have not — and the evidence for the conjecture is entirely that nobody has found a counterexample they were looking for.

 The gaps of ⟨5, 7⟩, which are the moves. A Sylver Coinage position drawn as the numerical semigroup it is. Gold squares are the numbers already named; plain squares are sums of them, and so cannot be named again; magenta squares are the gaps, which are exactly the legal moves. The largest gap is the Frobenius number, marked F — past it every integer is reachable, which is why the game has finitely many moves left and must end. Out in the world

The game that is a number system

In Sylver Coinage two players name integers and nobody may name a sum of what has already been named. Its positions are not boards — they are numerical semigroups, its termination is a theorem of Sylvester's from 1884, and the question of who wins after the opening move 16 has been worth a thousand dollars since 2017.

 The days this site can compute, and the ones it cannot. Zero on the first day, ±1 on the second, and thereafter the simplest number in every remaining gap — the construction run by the game recursion, which produces only fractions with a power of two underneath however long it goes on. Below it, three objects the same recursion reaches when the stopping rule is removed, each written with its option set and the exact reason this site's machinery cannot hold it. They are named rather than drawn, which is the honest half of a figure-first collection. How it was found

The numbers came out of the game

The construction is always taught numbers first and games second, and the discovery ran the other way. Conway arrived at the number system from positions, which is why the definition quantifies over sets of previously built objects rather than over cuts — and why it produces a genuinely different collection at every finite stage.

 The same position, and two rulers to measure it with. Nim positions with the length of their input under two encodings — the heap sizes in binary, and the counters themselves — beside the work the nim-sum does. The work never changes. Which of the two lengths it is compared against decides whether the same algorithm reads as linear or as exponentially fast, and hardness claims are always made against one particular encoding. What it costs

Nim is easy, in binary

Three heaps of a thousand counters take thirty bits to write down and three thousand counters to lay out. The nim-sum does three exclusive-ors either way. Whether that counts as fast depends entirely on which of the two numbers the work is compared against.

 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.

 Grundy values for subtraction of 1, 3, 4. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none. Impartial games

Take one, three or four

A heap and a list of legal takes. It is the smallest interesting impartial game there is, and the only family in the subject where eventual periodicity is not observed, not conjectured, but guaranteed — with a bound on when it must appear.

 One position, three ways of writing it, and only one of them adds. The same positions as a sentence about who wins, as a description of the position itself, and in the notation Winning Ways introduced. The first two columns carry identical information and support no operation whatever. The third column can be added — and the sums below it are values that no manipulation of the first two columns could reach, because two of these pairs start from the same two outcomes and finish differently. How it was found

The notation was the argument

Up, star and the brace form are not abbreviations for case analyses. They are the claim that these objects add — and the arithmetic they support is arithmetic that no table of outcomes could ever produce, because two positions with identical outcomes can have different sums.

 The genus of Kayles ·77, heap by heap. One row per heap: the genus symbol, the misère outcome it implies, and whether the symbol is one a Nim heap has. A game all of whose positions are tame is played in a misère sum exactly as Nim is; a single wild heap ends that, and the normal-play Grundy value gives no warning of which heaps those will be. Where it stops

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.

 The thermograph of {6 | {5 | {4 | 0}}}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake. Temperature

A thermograph is built from its options'

The diagram is not measured, it is computed — each wall is an extremum over the options' opposite walls, shifted by the tax. That construction is why a hot follow-up lowers the temperature instead of raising it, and why two fights with the same swing can differ by a factor of two in what is at stake.

 The cold positions, written in Fibonacci base. The first several cold pairs of Wythoff's game with both heap sizes written in Fibonacci base — as sums of non-consecutive Fibonacci numbers, which every integer has exactly one of. Blue is the smaller heap and red the larger. Read as digits, the pair is a shift: the larger numeral is the smaller one with a zero appended, and the smaller one always ends in an even number of zeros. Out in the world

The digits say which move wins

Wythoff's cold positions are usually given as a pair of golden-ratio formulas. Written in Fibonacci base they are a statement about digits instead — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — and a rule about digits answers a question about a heap of a trillion.

 Mock Turtles on 8 coins: every lost position. The rows a player to move has already lost, drawn in full. A filled disc is a coin showing heads. The set is closed under turning over every coin two of its members disagree about, which is what makes it a linear code, and the count of heads in the sparsest of them is the fewest coin turns that separate two lost positions. Impartial games

The losing positions are a code

Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.

 The days this site can compute, and the ones it cannot. Zero on the first day, ±1 on the second, and thereafter the simplest number in every remaining gap — the construction run by the game recursion, which produces only fractions with a power of two underneath however long it goes on. Below it, three objects the same recursion reaches when the stopping rule is removed, each written with its option set and the exact reason this site's machinery cannot hold it. They are named rather than drawn, which is the honest half of a figure-first collection. Values

The recursion this site cannot run

Remove the stopping condition from the construction and it reaches ω, its reciprocal, and one third — none of which this site's evaluator can represent, because it interns a position from a finite list of options. The figure draws what it computes and names what it cannot, which is where the boundary belongs.

 Subtraction of 1, 3, 4 — and the window that proves the period. The Grundy values of a subtraction game, with the window that certifies the period marked. Everything after the window follows from it by induction, because a value is a mex over values at most one move back — so a finite check settles the whole infinite sequence, and the thousands of further values computed here agree with a claim that was already proved. What it costs

Four values, and the sequence is settled for ever

The Grundy values of a subtraction game repeat with period 7, and proving it needs a window of exactly four of them — one for each size of move the game allows. Everything past the window follows by induction. A finite computation has settled a claim about every heap there will ever be.

 The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number. Sums and comparison

The other sum, the one that nests

A move in one part wipes the other out entirely. That is the ordinal sum, it is what a Hackenbush stalk actually is — 1 : (−1) is a half, and 1 : (−1) : 1 is three quarters — and it is not an operation on values at all: three positions all worth zero give three different answers under it.

All themes