Combinatorial Game Theory
who wins, and by how much
Series

Wythoff's game — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Wythoff's game, and the line the losing squares lie on. A queen moves left, down, or diagonally down-left any distance, and whoever cannot move loses. Every square carries the Grundy value the mex rule gives it. The squares worth nothing — the ones a player wants to hand over — lie along two lines whose slopes are the golden ratio and its reciprocal, in a game with no geometry and no continuous quantity in its rules.

    Wythoff's game, and the ratio nobody put there

    Two heaps, three kinds of move, and losing positions that lie along a line of irrational slope. Nothing in the rules mentions a ratio, a length or a continuous quantity — and the golden ratio comes out anyway.

    part 1 · impartial
  2. A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values.

    A golden ratio thirty years early

    Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

    part 2 · history
  3. The cold positions, written in Fibonacci base. The first several cold pairs of Wythoff's game with both heap sizes written in Fibonacci base — as sums of non-consecutive Fibonacci numbers, which every integer has exactly one of. Blue is the smaller heap and red the larger. Read as digits, the pair is a shift: the larger numeral is the smaller one with a zero appended, and the smaller one always ends in an even number of zeros.

    The digits say which move wins

    Wythoff's cold positions are usually given as a pair of golden-ratio formulas. Written in Fibonacci base they are a statement about digits instead — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — and a rule about digits answers a question about a heap of a trillion.

    part 3 · applied
  4. One set, described three ways that share no arithmetic. Wythoff's cold positions can be stated as the Beatty pairs of the golden ratio, as a greedy construction over the integers that mentions no constant, and as a condition on Fibonacci numerals. None of the three consults the game. The fourth column is the game — a mex table over the moves — and all four name the same set of cold pairs over the whole square, which is what the figure counts.

    A set with three descriptions, and a function with none

    Wythoff's cold positions can be written three ways that share no arithmetic — an irrational constant, a greedy rule, a condition on Fibonacci digits — and all three are exact. The same game's Grundy values have no closed form at all. Both facts are about one table, and the gap between them is the subject.

    part 4 · applied

All series