Combinatorial Game Theory
who wins, and by how much
Series

Notation — the series

9 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    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.

    part 1 · history
  2. What the notation costs to write. Every game born by each day, written in the brace notation and measured. The expressions are all distinct, which is what the notation is for, and by day three the typical one is twenty-two characters and the longest is fifty.

    Where the braces stop

    The brace notation names every game exactly — 1,474 games born by day three, 1,474 different expressions, no two alike. It also gets long: the middle one is twenty-two characters and the abbreviations everybody actually writes cover one game in twenty-three. And it has two hard edges. A game with a cycle in it has no finite expression at all, and the equation the minus sign encodes — that a game and its negative cancel — is false under misère play on every one of those 1,474.

    part 2 · history
  3. A vocabulary that is not closed under its own arithmetic. Every pair of named values added together, with the answer sorted by whether it has a name. The named vocabulary covers every game born by day two and one in twenty-three born by day three, and coverage is the wrong measurement: the notation exists so that positions can be added. A sixth of the sums of two named values at day three cannot be written without opening a brace, and the first one to escape is a sum of two of the symbols anybody learns first.

    Two names that add to nothing nameable

    The special symbols reach one game in twenty-three at day three. Coverage is the wrong measurement. The notation exists so that positions can be added, and a sixth of the sums of two named values at day three cannot be written without opening a brace — starting with a sum of two of the six symbols anybody learns first.

    part 3 · history
  4. Two numbers instead of an expression. The mean and the temperature of a position, set against its brace expression. The pair is readable in a way the expression is not and is half its length, and it is not exact: most of the games born by day three share a pair with some other game. The cost is not abstract — two games written the same way here can be separated by adding an ordinary small position to each, which is exactly the test a table of outcomes fails one level down.

    What two numbers cannot tell apart

    A thermograph summarises a position in a mean and a temperature — nine characters against the brace form's twenty-two, and readable in a way the expression is not. It is also not exact: 1,454 of the 1,474 games born by day three share a pair with some other game, 291 of them share one pair, and adding a star to two of those gives different winners.

    part 4 · history
  5. Writing a board as a sum, and as the value it is. Every sum of two, three and four games born by day two, written as the parts joined by plus signs and as the single value the sum equals, with the number of distinct values, the share that can be written without a brace, the share longer as one value than as a sum, the middle length each way and the longest single value. The single value is shorter in the middle and far longer at the top, and needs a brace more often the more parts there are.

    A board is written as a sum

    Every measurement of the brace notation so far has been of a single position, and nobody writes a single position. A board is several parts, and it can be written as the parts joined by plus signs or as the one value they add up to. Over every sum of up to four games born by day two, the one value is usually the shorter — and the share of boards that need a brace climbs with every part added, until the longest value is four times its sum.

    part 5 · history
  6. Every two-position loopy region, as two names. The 256 loopy regions of two positions, placed by the names of their onside and offside as identified against the 1,474 values born by day three. Ten names cover every side: 0, 1, −1, ∗, on, off, over, under, upon + ∗ and −upon + ∗. The largest groups are on & off with 94 regions and off & off and on & on with 53 each; 25 regions need only finite names.

    A loop is written with two names

    A region with a cycle in it has no brace expression, and every one of the 256 regions of two positions can be written anyway — as two names, the game it is when a play that never ends goes to Left and the game it is when it goes to Right. Checked against all 1,474 values born by day three, ten names cover every side, 25 regions need only finite ones, and the pair predicts every sum with a finite game, draws included: a draw arrives exactly where the two names disagree.

    part 6 · history
  7. Every region of three positions, counted. The 262,144 graphs on three positions reduced to the regions that are genuinely three positions with a cycle in them, and then split by whether the two-position vocabulary has a name for both of their sides.

    Four thousand nine hundred regions with no name

    Two positions give 256 regions and ten names cover every side of all of them. Three positions give 262,144 graphs, 110,934 genuine loopy regions — and 4,931 of those have a side that no name in the two-position vocabulary reproduces, with 3,990 of them named on one side and blank on the other. The count the earlier essay left open comes back in the affirmative.

    part 7 · history
  8. The guess, and what it covered. Two attempts to name the leftover sides out of the old vocabulary: every pair of the six stoppers, and every two-position region that is a stopper, each with small finite games added. Both cover nothing, and the count of distinct leftovers is what remains.

    The names are not built out of the old ones

    The guess was that a three-position region's missing names would be sums of two loopy ones — on plus over, and that family. Built and tried, every pair of the six stoppers covers none of the 4,931 regions that need one, and so does every two-position stopper there is, all seventy-nine of them with small games added. Thirteen names have to be invented, and forty-eight cover the whole census against ten at two positions.

    part 8 · history
  9. Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name.

    Four positions, sampled

    Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

    part 9 · history

All series