Wythoff's game

From Wikipedia, the free encyclopedia

Wythoff's game is a two-player mathematical game of strategy, played with two piles of counters. Players take turns removing counters from one or both piles; in the latter case, the numbers of counters removed from each pile must be equal. The game ends when one person removes the last counter or counters, thus winning.

The game is claimed to have been played in China under the name tsyan-shidzi (choosing stones).^[1] The Dutch mathematician W. A. Wythoff, published a mathematical analysis of the game in 1907.

1 Mathematical theory
2 See also
3 External links
4 References

[edit] Mathematical theory

'Cold' combinations are pairs of integers (n, m) with n ≤ m describing the size of both piles in a position that is a losing position for the first player to make a move. Obviously, none of the combinations (0, m) and (n, n) represent cold positions. Cold positions can be determined recursively as those from which no smaller cold combination can be reached.

The first cold combination is (1, 2). From this combination, three other combinations can be reached: (0, 1), (0, 2) and (1, 1). None of these are cold combinations. The first few safe combinations are (1, 2), (3, 5), (4, 7), (6, 10), ... These are captured in the On-Line Encyclopedia of Integer Sequences as A000201 and A001950. Wythoff discovered that the cold combinations follow a regular pattern determined by the Golden ratio.