Wythoff's Game

Two piles, one rule, and losing positions ruled by the golden ratio.

The idea

Wythoff's game is played with two piles of counters. A move removes any positive number of counters from one pile, or an equal positive number from both, and the player who takes the last counter wins.

In any such game — two players, no chance, no hidden information — every position is one of two kinds. From an N-position the player about to move can force a win; from a P-position the player about to move loses against perfect play, so the previous player, who created the position, wins. Two rules determine the P-positions completely: a position is a P-position exactly when every move from it leads to an N-position, and an N-position exactly when some move from it reaches a P-position. A position with no legal moves is a P-position, and the classification builds upward from there.

That backward sweep is an algorithm, not yet a strategy. The strategy comes from the pattern: compute enough small P-positions to guess the rule that generates them, then verify the guess by checking the two properties above — no move carries a P-position to a P-position, and from every other position some move reaches one. A rule in closed form settles a large position instantly, with no game tree to search. For Wythoff's game the rule is strikingly geometric: plotted as points $(a, b)$ in the plane, the P-positions line up along two rays through the origin, of slope the golden ratio $\varphi$ and its reciprocal $1/\varphi$ — each pair appearing together with its mirror image, since the two piles play the same role. Reach for this analysis whenever a removal game asks who wins from a given position.

Ways to work on it

• Walkthrough. Build the P-positions greedily and meet their golden-ratio closed form.
• Practice. Decide whether a position is losing (a P-position).
• Hardest. From a winning position, find and verify the move to a P-position.

Not sure where to start? Take the ten-question placement test.