What is Wythoff's game?
Wythoff's game is played with two heaps. On your turn you either take any number of objects from one heap, as in Nim, or take the same number from both heaps at once. The player who takes the last object wins: this game is always played the normal way round, so the misère switch and the starting piles option of the standard game do not apply.
The heap sizes come from the size option in the table setup: 5 and 7 (small), 9 and 12 (medium, the default) or 14 and 20 (large). A well-known way to picture the game is a chess queen that may only move left, down or diagonally down and left: the two heaps are her distances from the two edges of the board, and whoever moves her into the corner wins.
Rule changes
| Rule | Standard Nim | Wythoff's game |
|---|---|---|
| Heaps | Standard NimSeveral heaps: 1, 3, 5 and 7 objects by default, or another set chosen in the table setup. | Wythoff's gameTwo heaps: 5 and 7, 9 and 12 (default) or 14 and 20, chosen as the size in the table setup. |
| Moves | Standard NimTake one or more objects from one heap. | Wythoff's gameEither take one or more objects from one heap, or take the same number from both heaps. |
| Goal | Standard NimMisère play by default: whoever takes the last object loses. The setup can switch to normal play, where taking the last object wins. | Wythoff's gameAlways normal play: whoever takes the last object wins. |
| Winning play | Standard NimLeave the heaps with a nim-sum (the bitwise XOR of their sizes) of zero, with a twist in the misère endgame. | Wythoff's gameThe positions that lose for the player to move are the pairs 1 and 2, 3 and 5, 4 and 7, 6 and 10, 8 and 13 and so on: the k-th pair is the whole parts of k × φ and k × φ², where φ is the golden ratio. No starting position here is such a pair, so the first player can win. |
History
The Dutch mathematician Willem Abraham Wythoff published the game and its solution in 1907, in the article “A modification of the game of nim” in Nieuw Archief voor Wiskunde. He showed that the losing positions follow the golden ratio. The smaller and larger numbers of the losing pairs form two Beatty sequences that between them list every positive whole number exactly once, which is why the game turns up in writing on number theory as well as on games.
Martin Gardner wrote about the game in his Mathematical Games magazine column in March 1977, and said there that it was played in China under the name jiǎn shízǐ, “picking stones”. We know of no other source for that claim.