Combinatorial Game Theory
who wins, and by how much
The collection

Every essay — page 28

One idea per essay, ordered so that the earlier ones set up the later ones — but nothing here depends on being read in sequence.

Values

What a position is worth — numbers, and the things that are not numbers, and how to find the simplest one.

Smaller than every positive number, and not zero. Values that sit between zero and every positive number, each compared with zero and with 1/1024. Every relation drawn was computed by playing the difference, and one of them is confusion — neither greater, smaller nor equal. None of these is a number, and in a close game they are the entire margin.

Infinitesimals

Some positions are positive — Left wins them whoever moves first — and smaller than every positive number, including a millionth and a millionth of that. They are the values that decide close games, and the smallest of them is a single move's worth of nothing.

6 figures · Infinitesimals 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.

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.

5 figures · Numbers Why nobody moves in the number. A hot position added to a number. Left wins the sum whoever moves — but only by moving in the fight. Spending the move on the number instead hands the position back as a first-player win, with Right to move, which throws the win away. The theorem says this is always so, and here it is happening.

Numbers avoid numbers

In a position with a number in it and anything else, the number is never the right move. That is a theorem rather than a heuristic, and it is the closest this subject comes to advice a player can carry into a real game.

6 figures · Numbers A switch, its mean and its temperature. Positions of the form {a | b} with a above b: both players want to move there, so neither is settled. The bar spans the two options, the marked point is the mean the position is worth once the fighting is over, and the temperature is half the gap — which is exactly what moving first is worth.

Worth nothing, and worth fighting for

A switch is a position both players want to move in. Its average value can be zero while the difference between getting there first and second is enormous, and that gap is a second number every position carries.

7 figures · Switches 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.

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.

8 figures · Canonical form Tiny and miny: infinitesimals with a scale. Positions that are greater than zero and smaller than every positive number, and which are nevertheless strictly ordered among themselves — the larger the subscript, the smaller the value. Being smaller than everything positive is not one size of thing; it is a whole scale, and up sits above all of it.

Tiny, miny, and the sizes below every size

An empty two-by-four Domineering board is worth less than nothing and more than every negative number. It is not up, not down and not a fraction — it is a miny, and the minies come in sizes, strictly ordered among themselves below a floor no number reaches.

7 figures · Infinitesimals Clobber: every value smaller than every number. Blue and red stones on a small board. A move takes one of your own stones onto an orthogonally adjacent enemy stone, which is removed. Because adjacency is symmetric, a player has a move exactly when the opponent does — so no position can ever be worth a whole move to anybody, and every value that comes out is an infinitesimal.

The class where nobody runs out first

Three stones in a row — blue, blue, red — and the position is worth exactly up. Clobber cannot produce anything else, because adjacency is symmetric — a player has a move precisely when the opponent does, and a game with that shape can never be worth a whole move to anybody.

7 figures · Infinitesimals 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.

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.

4 figures · Numbers 7 positions of the same value, and how long each of them lasts. Nim positions whose heap sizes all nim-sum to zero. As games they are the same object: each is worth zero, each is a loss for the player to move, and each may be substituted for any other inside any sum without changing a single outcome. The bars are how many moves each one takes, from the shortest legal play to the longest. The value determines everything about who wins and nothing at all about when.

What a value leaves out

A value settles who wins, by how much, and what happens in every sum the position appears in. It says nothing about when. Seven positions here are worth exactly zero and interchangeable everywhere, and they run from two moves long to eighteen.

8 figures · Tempo 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. The two marks on the base line are the stops — what each player gets by moving first and playing the fight out with no tax charged at all.

Where the fight stops

Keep taking the biggest thing on offer until somebody is left facing a number, and the number reached is a stop. Every position has two of them, one for each player moving first, and between them they say how a fight ends — except for the part of it no number can reach.

8 figures · Stops 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.

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.

9 figures · Incentives What a deeper position does to the shape. Thermographs side by side, two of them, with temperature running up each panel and value across it: {{6 | 2} | {1 | −3}}, with a bend where an option's own fight cools out; {4 | −1}, straight-walled. A wall that runs straight has nothing changing hands below the meeting point; a bend is an option's own fight cooling out at a lower temperature than this position's, and it is where a decision passes from one player to the other. The two marks on each base line are the stops — what each player gets by moving first with no tax charged.

The switch a player is imagining

Every account of a hot position ends up as "worth about m, and worth t to move in", which is the switch {m+t | m−t}. For a plain fight that summary is the position exactly. For a fight with anything behind it the leftover is not a rounding error — on one position here it is a whole second fight of temperature two.

9 figures · Switches 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.

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.

8 figures · Numbers Where a switch stops being a switch. The same Left option with the Right one raised past it. While the Left option is above the Right one both players want to move, the bar spans a real fight and the temperature is half the gap. Where the two meet the position is the number plus a star — no longer a switch, and not a number either. Above that the simplicity rule takes over: the value is the simplest number strictly between the options, and there is nothing to fight about.

When a switch is not a switch

A position {a | b} with numbers on both sides is a fight only while a is above b. Sweeping the boundary with a fixed at 2 and b climbing from −2 to 3 turns up three regimes rather than the two the definition suggests: eight fights whose temperature is exactly half the gap, one position at a = b that is 2∗ and is not a number, and beyond that numbers chosen by the simplicity rule — which on 8 of 12 sampled cases is not the midpoint.

9 figures · Switches 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.

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.

8 figures · Stops

All ladders · Every object named here · The position index · Figures that play back · Search