Combinatorial Game Theory
who wins, and by how much
Theme

The thread: Not every game is a number

Some positions are worth a half or a quarter. Others are worth something no number can express, and the ones that are not numbers are where the subject becomes interesting.
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.

 Domineering on 2 by 3. Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. The two players see different games on the same board, which is what partizan means — and the value that results is not a number. Particular games

Domineering

One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.

 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.

 Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks. Particular games

Toads and Frogs

Toads shuffle right, frogs shuffle left, and either may jump over one of the other. A strip six cells long is worth exactly up. Another six-cell strip is worth exactly down. Nobody has a formula for which.

 Cooling {5 | 1}, one degree at a time. The same position under a rising tax on moving. Each bar is what Left gets moving first and what Right gets moving first, once every move costs the tax. The bars close as the tax rises, and at the temperature they meet — and from there on the position is worth its mean value and neither player wants to touch it. Temperature

Cooling

Charge a tax on every move and a fight becomes a number. The height of tax at which that happens is the temperature — so cooling is not a technique for finding the temperature, it is what the temperature is.

 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. Values

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.

 a cycle of three: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is. Where it stops

An outcome with no value behind it

Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches.

 Col and Snort on a path of four. One graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion. Particular games

One board, two rules

Col forbids painting next to your own colour. Snort forbids painting next to your opponent's. One word differs, the boards are identical, and the values that come out are not the same kind of object.

 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.

 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. Values

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.

 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.

 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.

 Nim-multiplication below 16, and every field axiom checked. The nim-product, defined by taking the least value the product is not forced to be — the same manoeuvre as the mex rule, applied to a product rather than to a move. The result is that these values are not merely a group under nim-addition but a field: every axiom is checked over the whole table here, including an inverse for every non-zero value, and the sizes at which the axioms fail are reported rather than avoided. Impartial games

The nimbers multiply

Nim-addition is exclusive-or and everybody meets it first. There is also a multiplication, defined by the same take-the-least-value-not-forced manoeuvre as the mex — and it makes the nimbers below sixteen a field, with every axiom checked here and an inverse for every non-zero value.

 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. Values

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.

 A grid of coins, and a multiplication table. The Grundy values of a two-dimensional coin-turning game, computed from its own move rules by a mex at every cell. Down the left and across the top are the one-coin values of the two one-dimensional games it is built from. Every cell is the nimber product of its two edge values — the multiplication defined for the nimber field on algebraic grounds — and beside the grid are the three combining rules a reader would try first, each killed on a named cell. Impartial games

The tartan theorem

The nimbers are a field, with a multiplication defined by a mex-style rule that looks like an algebraist's amusement. Lay two coin-turning games on a grid and the Grundy value of each square is the nimber product of its two coordinates — which is the point at which the multiplication stops being a curiosity and starts computing answers.

 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.

 Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks. Particular games

The strip nobody has a formula for

Some toads, a gap, some frogs. Two counts and a spacing is the whole description, and the values that come out of it are integers, stars, switches with eighth-point options and a down — four classes inside one two-parameter family, which is why nobody has written the formula.

 Maundy Cake: the pieces must be equal. The same cake as Cutcake, cut by the same two players, with one extra rule: a cut must divide the cake into equal pieces, and every piece stays in play. The values are still whole numbers, but the arithmetic that decides them is not Cutcake's — it counts prime factors rather than binary digits. Particular games

Maundy Cake

Cutcake with one word added: a cut must divide the piece into equal parts. The values are still whole numbers, and the rule this site has been repeating about them is false — over all 1,296 cakes to 36×36 the largest-odd-divisor account has 946 counterexamples. What survives is a count of prime factors, and it says who wins without saying by how much.

 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. Values

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.

 Small Domineering boards and what they are worth. Every value here was computed from the moves rather than looked up. Even on boards this small the values are switches and infinitesimals rather than numbers, which is the ordinary situation for a partizan game and the reason the theory needs more than arithmetic. Particular games

The values of every small board

Thirty Domineering rectangles, every value computed from the moves rather than looked up. The 1×n row obeys a formula and the 2×n row does not: its outcomes run L N N R three times over and then 2×13 comes out worth exactly 0, and its temperatures climb to 19/16 and fall back without settling.

 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.

 Amazons on one line. A one-dimensional Amazons board: an amazon slides along the row and shoots along the row, and the square the arrow lands on is burnt for the rest of the game. The whole board fits in a sentence, and the values it produces are already of several different kinds. Particular games

Amazons on one line

A board one square high is small enough to evaluate completely: every strip from two to ten squares with one amazon a side is 37,886 positions taking 81 distinct values, and every one of them is an integer, a switch, a number plus a star, or a bare star. Not one is a fraction — and forcing the arrow onto the square just vacated, which takes a freedom away rather than adding one, produces 1,196 that are.

 The values born by day three that are their own negatives. Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two. The nimbers do, and they are not the only ones: a switch symmetric about zero is unchanged by negation, and so is anything whose Left options are the negatives of its Right options. Each row carries the value, whether it is a nimber, and its outcome. Sums and comparison

The values that are their own negatives

Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two in a group whose elements otherwise have infinite order. The nimbers do. So does ±1, on sight. Over the 1,474 values born by day three there are 30 of them and only four are nimbers, every one of the 900 sums of two is another, and the equality test and a symmetry of the written form agree 1,474 times out of 1,474.

 End-Nim: a player at each end of the row. Rows of heaps in which Left may take from the leftmost heap and Right from the rightmost. The value beside each row was computed by the game recursion and reduced to canonical form; the outcome beside it says who wins. A single heap is a Nim heap, because both players may take from it — and that is the last thing about this game that looks like Nim. Particular games

Taking from the ends

End-Nim is Nim's board with a player at each end, and it takes one sentence to state. Not one of its 5,460 small positions is worth a non-zero number — the game is all-small, so zero is the only number any of them can reach — and there are 2,693 distinct values between them. The outcome says a great deal more: 4,738 of those positions are won by the same player whoever moves, and on two heaps the rule is that the larger end wins.

All themes