Wythoff's game

Last updated January 23, 2023

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

An equivalent description of the game is that a single chess queen is placed somewhere on a large grid of squares, and each player can move the queen towards the lower left corner of the grid: south, west, or southwest, any number of steps. The winner is the player who moves the queen into the corner. The two Cartesian coordinates of the queen correspond to the sizes of two piles in the formulation of the game involving removing counters from piles.

Martin Gardner in his March 1977 "Mathematical Games column" in Scientific American claims that the game was played in China under the name 捡石子 jiǎn shízǐ ("picking stones").^[1] The Dutch mathematician W. A. Wythoff published a mathematical analysis of the game in 1907.^[2]

Optimal strategy

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:

(0,0) is a cold position.
Any position from which a cold position can be reached in a single move is a hot position.
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.

Formula for cold positions

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

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

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

{\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.

Related Research Articles

In mathematics and computer science, the floor function is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the least integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

<span class="mw-page-title-main">Prime-counting function</span> Function representing the number of primes less than or equal to a given number

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by $π$ (x).

The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci numbers form complementary instances of Lucas sequences.

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be.

In number theory, a branch of mathematics, a highly cototient number is a positive integer $which is above 1 and has more solutions to the equation$

In mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinitely long sequence of characters. Such a sequence can be generated by considering a game of English billiards on a square table. The struck ball will successively hit the vertical and horizontal edges labelled 0 and 1 generating a sequence of letters. This sequence is a Sturmian word.

A Fibonacci word is a specific sequence of binary digits. The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.

In number theory, Mills' constant is defined as the smallest positive real number A such that the floor function of the double exponential function

Fokker periodicity blocks are a concept in tuning theory used to mathematically relate musical intervals in just intonation to those in equal tuning. They are named after Adriaan Daniël Fokker. These are included as the primary subset of what Erv Wilson refers to as constant structures, where "each interval occurs always subtended by the same number of steps".

In mathematics, trailing zeros are a sequence of 0 in the decimal representation of a number, after which no other digits follow.

In mathematics, the Fibonacci numbers form a sequence defined recursively by:

In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.

In mathematics, Abel's summation formula, introduced by Niels Henrik Abel, is intensively used in analytic number theory and the study of special functions to compute series.

Subtract-a-square is a two-player mathematical subtraction game. It is played by two people with a pile of coins between them. The players take turns removing coins from the pile, always removing a non-zero square number of coins. The game is usually played as a normal play game, which means that the player who removes the last coin wins. It is an impartial game, meaning that the set of moves available from any position does not depend on whose turn it is. Solomon W. Golomb credits the invention of this game to Richard A. Epstein.

In mathematics, the Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence defined by the Fibonacci recurrence can be derived by shifting a row of the array.

The metallic means of the successive natural numbers are the continued fractions:

In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory showing that, in a certain sense, these sets cannot be very large. In the game of subtract a square, the positions where the next player loses form a square-difference-free set. Another square-difference-free set is obtained by doubling the Moser–de Bruijn sequence.

In number theory, the totient summatory function $is a summatory function of Euler's totient function defined by:$

In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses (misère). Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.

For an integer $, the minimal polynomial of is the non-zero monic polynomial of degree for and degree for with integer coefficients, such that . Here denotes the Euler's totient function. In particular, for one has and$

References

↑ Wythoff's game at Cut-the-knot, quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers
↑ Wythoff, W. A. (1907), "A modification of the game of nim", Nieuw Archief voor Wiskunde, 7 (2): 199–202

External links

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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Wythoff's game at Cut-the-knot, quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers

[2] Wythoff, W. A. (1907), "A modification of the game of nim", Nieuw Archief voor Wiskunde, 7 (2): 199–202

[1]

[2]