Combinatorial Game Theory
who wins, and by how much
Series

Canonical form — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. The same game, written twice. A position as it arises and the same position reduced. Left would never move to −1 when 0 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.

    Canonical form

    Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.

    part 1 · values
  2. 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.

    part 2 · values
  3. A factor, and it grows. The ratio between reducing and deciding, by the number of options the form carries.

    A factor, and not an overhead

    Deciding who wins a form searches the form's own tree. Reducing it to canonical form searches a difference game for every comparison, and a difference game is a sum. Over 256 forms the reduction expands 5.46 times as many positions — and the ratio runs from 0.58 at one option to 9.80 at eight.

    part 3 · values

All series