Combinatorial Game Theory
who wins, and by how much
Series

Tempo — the series

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

    part 1 · values
  2. The value does not count the good moves. How many of a Domineering region's placements are best ones, against what the region is worth. Half the values have two regions that disagree about the count, and 52 disagree over whether there is a choice at all.

    How many moves are worth making

    A value answers who wins and by how much, and the anchor below names the quantities it discards. This is the first of them counted. Over 1,034 Domineering regions and 125 values, 63 values have two regions disagreeing about how many placements are worth making and 52 disagree over whether there is any choice at all — and the count of good moves stays near one and a half however large the region gets.

    part 2 · values
  3. What a value costs a player. The number of positions a winning strategy has to tell apart, against the number of values among them. The value compresses 4,269 positions into 128 numbers and leaves 3,308 choices to be remembered.

    What a strategy has to remember

    A value answers who wins and by how much, and it settles neither how many moves achieve it nor whether the best one is unique. Counted over every position reachable inside the catalogue of regions, the gap has a size: 4,269 positions carry 128 values between them, and a player who wants to win rather than to predict has to store 3,308 choices — twenty-six entries for every number the theory supplies.

    part 3 · values
  4. The list saturates at three. Rules added greedily, each chosen to answer the most decisions given the ones already on the list. Three rules answer 94.5 per cent, and the fourth and fifth answer not one more.

    Three rules and a tie-break

    An exhaustive table of what a Domineering strategy has to remember is 3,308 lines. Three rules applied in order answer 94.5 per cent of it — leave the opponent fewest replies, then keep the region whole, then take whichever placement comes first — and the fourth and fifth rules answer not one more. The residue is 181 decisions in which every rule scores the candidates the same and one of them is worse.

    part 4 · values
  5. Two failures, not one. The decisions a Domineering strategy has to store, split by what the two content rules do: answer them, name a worse placement, or leave two candidates standing.

    Seventy-two of them were not silence

    The rung below said its 181 unanswered decisions were all the rules falling silent and asked whether the position's value picks the placement once the geometry cannot. Seventy-two of the 181 are the rules speaking and being wrong, which is a different failure. On the 109 that really are silence, a rule chosen per value answers more than half — and the star class the rung below singled out is settled outright by leaving the younger position.

    part 5 · values
  6. Wrong by one, or by nothing. The seventy-two decisions the rules get wrong, by how many replies the named placement misses a best one.

    The price of taking the maximum

    The seventy-two decisions where a Domineering strategy's rules name the wrong placement are never wrong by more than one reply, and a third of them are the second rule's fault rather than the mobility count's. The repair that follows — keep every placement within one reply of the best — retains a best placement every time and costs thirty decisions for every one it saves.

    part 6 · values
  7. The value predicts on one residue only. Value-indexed rule selection on the silent decisions and on the seventy-two.

    Close calls nothing resolves

    The same value panel that settles 118 of the 202 silent decisions settles four of the seventy-two the rules get wrong. Every rule that helps at all must replace connectivity rather than follow it, and the cheapest one breaks twenty-six decisions for every one it saves.

    part 7 · values

All series