Combinatorial Game Theory
who wins, and by how much
Concept

Simplicity rule — where it appears

The rule that a position between two numbers is worth the simplest number strictly between them, rather than their average. It is what makes the values of cold positions computable at a glance, and it is why the numbers appearing here are dyadic rather than arbitrary.

Named by 22 essays across 4 fields — each of them below, with the objects they name alongside it.

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.

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.

positions · Hackenbush 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.

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.

values · Numbers 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.

values · Numbers 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 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.

history · Numbers 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.

values · 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.

values · Tempo 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.

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.

positions · Cutcake 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.

values · Switches Shove strips, and what each is worth. A shelf of positions with the value the recursion returns beside each. Every one is a number: Shove has no hot positions at all, which is unusual for a partizan game and is the first of the essay's three claims.

Nothing worth fighting over

Shove is a strip of coins beside a cliff, and both players have completely different moves. Every one of its 728 positions is worth a number, so nobody ever wants to move; the winner is the owner of the coin furthest from the cliff, in all 728; and the number the board is worth is not the sum of its coins — that reading is exact on 126 strips and wrong on 588 of the other 602.

positions · Shove Trees, and what each is worth. A row of blue-red Hackenbush trees with the value the recursion returns under each. Every one is a number, and none of them is the binary reading of anything a reader can see in the picture.

A tree is still a number

A Hackenbush string spells its own value in binary. Put a fork in it and the numeral has nothing to read — there is no leftmost anything. The value is still a number, in all 10,066 forests up to six edges; it is still computable, by the ordinal sum, in all 3,238 single-trunk trees; and the reading is right on 762 of them, of which 126 are the strings it was written for.

positions · Hackenbush Push and Shove over every strip up to 6 squares. The same strips under both rules. A cliff lets coins fall off and a wall does not, and the census says what that one clause is worth: both games are entirely made of numbers, they never agree on a value, and the obvious board-reading is right far more often under the wall than under the cliff.

The other way to move a row

Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.

positions · Push The bend decides it. Whether the stop reading gives the mean and temperature, against whether either wall bends below the meeting point. Both off-diagonal cells are empty on all 138 values.

The bend is the condition

The rung below offered a description of the class its stop reading is exact on — neither wall bends below the meeting point — and a route to proving it: that a bend happens precisely when some option is neither a number nor an infinitesimal. The first is exact on all 138 values, both directions, no exception. The second is half right: every bent value has such an option and 49 unbent ones do too. And the eight apparent exceptions to the first turn out to be a bookkeeping convention.

values · Switches A self-negative value costs a day. The values born by day three, by temperature, with the earliest self-negative one at each. The earliest is always the day after the temperature's own birthday, and the four temperatures with none are the four whose birthday is three.

A self-negative value costs a day

The rung below placed the thirty values equal to their own negatives on the temperature scale and asked whether being self-negative forces anything about when a value can be born. It does, exactly: the earliest self-negative value of temperature t is born the day after t itself, which accounts for the four temperatures that carry one and the four that carry none. The guess it offered — that the first value of each temperature is a self-negative one — holds at four temperatures out of five and is not the shape of the answer.

sums · Negation Seven, ten, thirteen and sixteen. The four values the rung below named, each read off the prime factorisation: one plus the largest prime plus the product of the two largest.

The size of a cake

Ω gives the sign of a Maundy Cake and says nothing about the size, and the rung below left four values — 7, 10, 13 and 16 — unaccounted for. For a one-row cake they are a formula: write the prime factors largest first and add up their running products. The rule behind it is greedy — cut by the largest prime — and it is exact on every one-row cake to two hundred and wrong on a fifth of the two-sided ones.

positions · Cutcake Cut small unless you are behind. The complete rule for the best cut in a Maundy Cake, in three cases decided by the two sides' counts of prime factors. It is exact on every cake in a sixty by sixty grid.

Cut small unless you are behind

The rung below found the greedy rule — cut at the largest prime — wrong on 104 of 552 Maundy Cakes and asked for a description of them. On all 104 the best cut is at the smallest prime, the exact opposite. A middle divisor is never needed on any cake in a sixty by sixty grid, and which of the two extremes wins is decided by Ω alone: cut small when Ω(m) + 1 ≥ Ω(n), large otherwise, and that is exact on all 3,540.

positions · Cutcake Running products, and where to stop. Six Maundy Cakes with the prime factors of the longer side, the running products those primes make, and the value the sum of them gives.

The short side only says how many

The rung below settled which cut to make in a Maundy Cake and left the value open. With the cut settled the recursion is a walk, the walk unrolls, and what it unrolls into is the running products of the long side's prime factors, largest first. The short side never enters the products at all — it decides how many of them there are and nothing else, so sixty-two different short sides give one value.

positions · Cutcake Every gap dies at the last run's rate. Three-run Push strips with each gap widened in turn, and which of four candidate rates the convergence matches. The rearmost run's rate wins every family and the compound rate wins none.

Read from the back forwards

The rung below found a two-run Push strip converging at a rate set by the back run and asked what a third run does — whether the rate is still the rearmost run's, or whether the rates compound. It is the rearmost run's, and for every gap: widen the front gap of a three-run strip, two whole runs away, and the value still dies at the last run's rate. Shove, the game one clause away, compounds.

positions · Push Term by term. Every cut of one long side, with its value written as running products beside the terms of the largest-prime cut.

The short side is not in the lemma

The closed form for a two-sided Maundy Cake rested on one unproved statement: that no divisor beats the largest prime. Written out, that statement never mentions the short side — it is an inequality between a multiset of primes and a term count — and once it is stated that way it has a two-line proof, term by term. The ladder ends in a theorem rather than a grid.

positions · Cutcake Hold the tail, vary everything in front. The grouping test: every tail against every prefix, asking whether the rate at which a widening gap stops mattering is a function of the tail alone.

Two strips that end the same way

If a Push strip's sensitivity is governed by its last run, then two strips agreeing at the far end should behave the same however different their fronts. On 78 of 80 tails they do, exactly. On two of them a single empty square in the prefix reaches across a gap that grows without bound and halves the rate — and the run reading turns out to be sound in one direction only.

positions · Push Two of three are subadditive. The birthday, the option count and the written length, each tested for subadditivity under the disjunctive sum.

Two measures bounded, and one not

A sum is born no later than its parts' birthdays together, and it has no more options than they have between them — a bound nobody had checked, and it is attained. What runs away is the length of the written form: 27 pairs of 231 exceed it, the worst by 29 characters, on a sum with exactly as many options as it was entitled to.

values · Numbers The two proofs, beside each other. Maundy Cake's rule was proved by restating its lemma so the short side vanished into a multiset of primes and a term count. Cutcake's rule takes the same five steps, with the multiset replaced by a binary length — one integer instead of a multiset — and the closing argument correspondingly shorter. The one line where they differ is which cut a reader would guess.

The obvious cut is the wrong one

Maundy Cake's rule was proved by restating its lemma so the short side vanished. Cutcake's collapses the same way — into a binary length instead of a multiset of primes — but the cut the argument needs is not the one the ladder predicted. Halving is wrong on a third of all cakes, and the smallest counterexample is six squares by two.

positions · Cutcake The same game, written twice. A position as it arises and the same position reduced. Left would never move to 0 when 2 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.

A reduction that reads a graph

The two reductions are defined as deletions from an option list, and the shared form has no option lists — a node is reached from several parents at once. Both restate as rewritings at a node, the rewriting is confluent, and its fixed point is the canonical form. What does not carry over is the sharing: four fifths of the shared nodes need a different answer under different parents.

values · Reversibility

Named alongside it

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

EnumerationPartizanValueCanonical formDyadic rationalInvariantNumbersClosed formDisjunctive sumBinaryBirthdayCounterexample

All concepts