Wythoff's game

A visualization of Wythoff's game of Nim. The bottom leftmost square is position (1,1) and the red squares are cold positions. Note that the winning square is not included in the picture.

Any position in the game can be described by a pair of integers (n, m) with n ≤ m, describing the size of both piles in the position or the coordinates of the queen. The strategy of the game revolves around cold positions and hot positions: in a cold position, the player whose turn it is to move will lose with best play, while in a hot position, the player whose turn it is to move will win with best play. The optimal strategy from a hot position is to move to any reachable cold position.

The classification of positions into hot and cold can be carried out recursively with the following three rules:

1. (0,0) is a cold position.
2. Any position from which a cold position can be reached in a single move is a hot position.
3. If every move leads to a hot position, then a position is cold.

For instance, all positions of the form (0, m) and (m, m) with m > 0 are hot, by rule 2. However, the position (1,2) is cold, because the only positions that can be reached from it, (0,1), (0,2), (1,0) and (1,1), are all hot. The cold positions (n, m) with the smallest values of n and m are (0, 0), (1, 2), (3, 5), (4, 7), (6, 10) and (8, 13). (sequence A066096 and A090909 in OEIS) (Also see OEIS: A072061)

For misère game of this game, (0, 1) and (2, 2) are cold positions, and a position (n, m) with m, n > 2 is cold if and only if (n, m) in normal game is cold.

Wythoff discovered that the cold positions follow a regular pattern determined by the golden ratio. Specifically, if k is any natural number and

${\displaystyle n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,}$

${\displaystyle m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\,}$

where φ is the golden ratio and we are using the floor function, then (n_k, m_k) is the k^th cold position. These two sequences of numbers are recorded in the Online Encyclopedia of Integer Sequences as OEIS: A000201 and OEIS: A001950, respectively.

The two sequences n_k and m_k are the Beatty sequences associated with the equation

${\displaystyle {\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.}$

As is true in general for pairs of Beatty sequences, these two sequences are complementary: each positive integer appears exactly once in either sequence.

• Nim
• Grundy's game
• Subtract a square
• Wythoff array

• Weisstein, Eric W. "Wythoff's Game". MathWorld.
• Grime, James. "Wythoff's Game (Get Home)" (video). YouTube. Brady Haran. Archived from the original on 2021-12-15. Retrieved 21 August 2017.