Wythoff's game
Combinatorial game theory · all families · data
Also known as: Wythoff Nim, Wythoff’s Nim, tsyan-shidzi (choosing/picking stones), jiǎn shízǐ (捡石子).
First player wins from any starting position not on the golden-ratio P-position diagonal; the standard non-trivial start is a first-player (N-position) win
| Result | First player wins |
| Strength | Strong |
| Method | Mathematical proof |
| Year | 1907 |
| Solved by | Willem Abraham Wythoff |
| Source | Wythoff 1907 |
| Board | Two heaps of counters (unbounded, non-negative integer sizes) |
| Distance to result | Game ends in finitely many moves; no fixed ply count (depends on heap sizes), but the full P-position structure is known in closed form for all positions |
Solution history
Section titled “Solution history”| Date | Size or opening | Result | Strength | Credit | Source |
|---|---|---|---|---|---|
| 1907 | standard game | first player wins | Strong | Willem Abraham Wythoff | source |
One row, derived from the record’s year, solver and primary source; no fuller history is recorded yet.
References
Section titled “References”- W. A. Wythoff, “A modification of the game of Nim,” Nieuw Archief voor Wiskunde, 2nd ser., vol. 7(2)/8, pp. 199-202, 1907/1909
- Wythoff’s Game — Wolfram MathWorld
- Wythoff’s game — Wikipedia
- Winning Wythoff’s game — Chalkdust Magazine
Resources
Section titled “Resources”Write-ups
Wythoff’s game is a two-player impartial combinatorial game (normal play: last player to take a counter wins). From two heaps, a player removes any positive number of counters from one heap, or an equal positive number from both heaps. Wythoff (1907) gave a complete closed-form solution: the cold/losing P-positions (a loss for the player to move) are exactly the pairs (n_k, m_k) = (floor(kphi), floor(kphi^2)) = (floor(kphi), floor(kphi)+k) for k >= 0, where phi = (1+sqrt5)/2 is the golden ratio. These two coordinate sequences are complementary Beatty sequences (since 1/phi + 1/phi^2 = 1): (0,0),(1,2),(3,5),(4,7),(6,10),(8,13),… Every other position is an N-position (a win for the player to move), so the FIRST player wins from any non-P start; the optimal strategy is to move to a reachable P-position. Because the result is a value/strategy for EVERY reachable position (a full closed-form “tablebase”), not merely the initial position, this is a STRONG solution. The proof is mathematical (induction establishing the P/N partition), not a computer search. State-space and game-tree complexity are unbounded (heaps are arbitrarily large integers), so no finite figure applies. Historical note: the game predates Wythoff under the Chinese name tsyan-shidzi / jiǎn shízǐ (“choosing/picking stones”), per Martin Gardner; Wythoff is credited with the first published mathematical analysis. Many later papers analyze variants (Blocking Wythoff Nim, generalized/diagonal Wythoff Nim, queen-reflection modifications), but the classical game’s headline solution is Wythoff 1907.