Wythoff's Game with a Pass

#G4 INTEGERS 25 (2025) WYTHOFF’S GAME WITH A PASS Ryohei Miyadera Keimei Gakuin Junior and High School, Kobe City, Japan [email protected] Hikaru Manabe University of Tuskuba, Tsukuba City, Japan [email protected] Masanori Fukui [email protected] [email protected] Received: 8/14/25, Accepted:10/27/25 , Published: 11/5/25 Abstract This paper describes Wythoff’s game with a pass, which is a variant of the classical Wythoff’s game. The classical form is played with two piles of stones, from which two players take turns to remove stones from one or both piles. When removing stones from both piles, an equal number must be removed from each pile. The player who removes the last stone or stones wins. In Wythoff’s game with a pass, we modify the standard rules to allow for a one-time pass, that is, a pass move that may be used at most once in a game but not from the terminal position. Once either player uses a pass, it is no longer available We denote the position of the game by (x, y, p), where xand yare the numbers of stones in the two piles, p= 1 if a pass is available, and p= 0 otherwise. The authors prove that for (x, y, 1) with x≥9 or y≥9, (x, y, 1) is a P-position (the previous player’s winning position) if and only if the Grundy number of (x, y, 0) is 1. They also prove, using the result of U. Blass and A.S. Fraenkel, that the Euclidean distance between each previous player’s winning position in Wythoff’s game with a pass and a nearby previous player’s winning position in Wythoff’s game without a pass is within √20. 1. Introduction Let Z≥0and Nbe the sets of non-negative integers and natural numbers, respectively. An interesting but challenging question in combinatorial game theory has DOI: 10.5281/zenodo.17535339 2 been determining what happens when standard game rules are modified to allow aone-time pass. This pass move may be used at most once in the game and not from the terminal position. Once either player has used a pass, it is no longer available for use. In the case of classical Nim, the introduction of the pass alters the mathematical structure of the game, considerably increasing its complexity, and finding the formula that describes the set of previous players’ positions remains an important open question that has defied traditional approaches to solving it. The late mathematician David Gale offered a monetary prize to the first person who developed a solution for the three-pile classical Nim with a pass. In [9] (p. 370), Morrison, Friedman, and Landsberg conjectured that “solvable combinatorial games are structurally unstable to perturbations, while generic, complex games will be structurally stable.”One way to introduce such a perturbation is to allow a pass. However, the authors of the present article reported some games as counterexamples to this conjecture in [5], [7], and [8]. These games are solvable because there are simple formulas for the Grundy numbers, and even when we introduce a pass move to the games, there are simple formulas for P-positions. Based on the research in [5], [7], and [8], the authors of the present article propose the following view on the combinatorial game with a pass. Some games have specific mathematical structures that prevent the perturbation caused by the pass from spreading to other positions, and these games have formulas for P-positions, even if a pass is introduced. However, the mathematical structures of some games permit the perturbation caused by the pass to spread all over the positions. Here, we present research on Wythoff’s game with a pass. Wythoff’s game with a pass presents a perfect example of specific mathematical structures that prevent the perturbation caused by the pass from spreading to other positions. For other research on combinatorial games with a pass, see [3], [4], and [6]. In [3] and [6], Chan, Low, Locke, and Wong described the set of previous players’ positions of Nim with a pass when the number of stones in each pile is at most four. This study shows that the impact of perturbation is small when the number of stones in each pile is small. In [4], it was proven that the arithmetic periodicity of the G-sequence can occur when we add a single pass move to precisely one pile in finite octal games, although finite octal games are not arithmetic periodic. Therefore, in this case, regularity, not perturbation, occurs by adding a single pass to the finite octal games. For completeness, we briefly review some of the necessary concepts in combinatorial game theory by referring to [1] and [10]. Definition 1. Let xand ybe non-negative integers. We represent them in base 2, so that x=Pn i=0 xi2iand y=Pn i=0 yi2iwith xi, yi∈ {0,1}. We define the 3 nim-sum x⊕yby x⊕y= n X i=0 wi2i, where wi=xi+yi(mod 2). Wythoff’s game is an impartial game without drawings; only two outcome classes are possible. Definition 2. A position is referred to as a P-position if it is the winning position for the previous player (the player who has just moved), as long as the player plays correctly at each stage. A position is referred to as an N-position if it is the winning position for the next player, as long as they play correctly at each stage. Definition 3. The disjunctive sum of the two games, denoted by G+H, is a super game in which a player may move either in Gor Hbut not in both. Definition 4. For any position pin game G, a set of positions can be reached by a single move in G, which we denote as move(p). Definition 5. The minimum excluded value (mex) of a set Sof nonnegative integers is the least nonnegative integer that is not in S. Definition 6. Let pbe a position in the impartial game. The associated Grundy number is denoted by G(p) and is recursively defined by G(p) = mex({G(h) : h∈ move(p)}). The next result demonstrates the usefulness of the Sprague–Grundy theory for impartial games. Theorem 1 ([1]).Let Gand Hbe impartial rulesets, and GGand GHbe the Grundy numbers of game gplayed under the rules of Gand game hplayed under those of H. Then, we obtain the following: (i)for any position gin G, we have that GG(g) = 0 if and only if gis the Pposition; (ii)the Grundy number of positions {g,h}in game G+His GG(g)⊕GH(h). Using Theorem 1, we can determine the P-position by calculating the Grundy numbers and the P-position of the sum of the two games by calculating the Grundy numbers of the two games. 2. Wythoff’s Game In this section, we review some of the theorems of Wyhoff’s game for later use. For the details of Wythoff’s game, see [11]. 4 Definition 7. Wythoff’s game is played with two piles of stones. Two players take turns removing stones from one or both piles. When removing stones from both piles, the number of stones removed from each pile should be equal. The player who removes the last stone or stones wins. 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 upper-left corner of the grid, either vertically, horizontally, or diagonally, for any number of steps. The winner is the player who moves the queen to the upper-left corner. Figure 1 shows the grid of squares, and we denote by (x, y) the number of stones in the first and second piles or the position of the queen, where the horizontal and vertical coordinates are denoted by xand y. Figure 2 shows the moves that the queen can make in Wythoff’s game. Figure 1 Figure 2 Theorem 2 ([11]).The set of P-positions of the game in Definition 7 is {(⌊nϕ⌋,⌊nϕ⌋+n) : n∈Z≥0}∪{(⌊nϕ⌋+n, ⌊nϕ⌋) : n∈Z≥0}, where ϕ=1+√5 2. Theorem 2 is a well-known fact in Wythoff’s game. Theorem 3 ([2]).Let {(an, bn) : n∈Z≥0}={(x, y) : G(x, y) = 1}. Here, we assume that anis increasing. Then, we obtain |bn−(⌊nϕ⌋+n)|≤ 4 and ⌊nϕ⌋−1≤an≤ ⌊nϕ⌋+ 2. Theorem 3 is Corollary 5.14 of [2]. Corollary 1. For any position (x, y)with G(x, y)=1, there exists a position (v, w) such that G(v, w)=0and p(x−v)2+ (y−w)2≤√20. Proof. This follows directly from Theorems 2 and 3. 5 3. Wythoff’s Game with a Pass and the Sum of Wythoff’s Game and a Pile of One Stone In this section, we define a new variant of Wythoff’s game and compare it to the sum of Wythoff’s game and a pile of one stone. Definition 8. Wythoff’s game with a pass is played like the ordinary Wythoff’s game, with the option of a single pass that can be used by exactly one player. Once a pass is used, it cannot be used again. The pass can be used at any time up to the penultimate move, but it cannot be used at the end of the game. The player who cannot make a move loses. We denote by G1the Grundy number of this game. Here, we introduce the sum of the traditional Wythoff’s game and a pile of one stone. We need this game to study P-positions of Wythoff’s Game with a Pass. Definition 9. Applying Definition 3, we define the sum of the classical Wythoff’s game without a pass and the game of a pile of one stone. We denote by G2the Grundy number of this game. We denote the position of the game in Definition 8 and the game in Definition 9 by three coordinates {x, y, p}. The coordinates x, y define the number of stones in the first and second piles, or, if we use a queen in the game, the position of the queen on the chessboard. For the game in Definition 8, the additional parameter p denotes whether the pass is still available (p= 1) or has already been used (p= 0). For the game in Definition 9, the parameter p= 1 if there is a stone in the third pile, and p= 0 if there is no stone in the third pile. Note that when p= 0, the games in Definitions 8 and 9 are the classical Wythoff’s game. Definition 10. For any x, y ∈Z≥0and p= 0,1, let M1(x, y, p) = {(u, y, p) : u < x and u∈Z≥0}, M2(x, y, p) = {(x, v, p) : v < y and v∈Z≥0}, M3(x, y, p) = {(x−t, y −t, p):1≤t≤min(x, y) and t∈Z≥0}, M4(x, y, p) = ({(x, y, 0)}( if x+y > 0 and p= 1), ∅( if x+y= 0 or p= 0), and M′ 4(x, y, p) = ({(x, y, 0)}( if p= 1), ∅( if p= 0). 6 The sets M1(x, y, p), M2(x, y, p), and M3(x, y, p) are the sets of horizontal, vertical, and diagonal moves, respectively. Set M4(x, y, p) is the set of the pass move of Wythoff’s game with a pass in Definition 8, and Set M′ 4(x, y, p) is the set of moves in the third pile of the game in Definition 9. Note that M4(x, y, p) is empty if and only if x+y= 0 or p= 0, and M′ 4(x, y, p) is empty if and only if p= 0. Next, we define move1and move2, which are moves of the games in Definitions 8 and 9, respectively. Definition 11. For any x, y ∈Z≥0and p= 0,1, let move1(x, y, p) = M1(x, y, p)∪M2(x, y, p)∪M3(x, y, p)∪M4(x, y, p) and move2(x, y, p) = M1(x, y, p)∪M2(x, y, p)∪M3(x, y, p)∪M′ 4(x, y, p). 4. The Positions (x, y, p) such that x, y ≤8 This section aims to determine P-positions and N-positions in the set {(x, y, p) : x, y ≤8}in Lemma 1. We now define three sets, A,B, and C, and study them. These sets have mathematical structures that prevent the perturbation caused by the pass from spreading to other positions. In Figures 3, 4, 5, 6, 7, 8, 9, the Grundy numbers of each point are printed, but these Grundy numbers have nothing to do with the argument in this section. Definition 12. Let A={(0,0,0),(1,2,0),(2,1,0),(3,5,0),(4,7,0),(5,3,0),(7,4,0)}, B={(0,0,1),(1,3,1),(3,1,1),(2,5,1),(5,2,1),(4,8,1),(8,4,1),(6,7,1),(7,6,1)}, and C={(0,1,1),(1,0,1),(2,2,1),(3,6,1),(6,3,1),(4,8,1),(8,4,1),(5,7,1),(7,5,1)}. In Figures 3, 4, and 5, we have the sets of Grundy numbers {G1(x, y, 0) : x, y ≤8}, {G1(x, y, 1) : x, y ≤8}, and {G2(x, y, 1) : x, y ≤8}, respectively. Here, sets A,B, and Care printed in red. 7 0 1 2 3 4 5 6 7 8 0 0 1 2 3 4 5 6 7 8 1 1 2 0 4 5 3 7 8 6 2 2 0 1 5 3 4 8 6 7 3 3 4 5 6 2 0 1 9 10 4 4 5 3 2 7 6 9 0 1 5 5 3 4 0 6 8 10 1 2 6 6 7 8 1 9 10 3 4 5 7 7 8 6 9 0 1 4 5 3 8 8 6 7 10 1 2 5 3 4 Figure 3: Set A 0 1 2 3 4 5 6 7 8 0 0 2 1 4 3 6 5 8 7 1 2 1 3 0 6 4 8 7 5 2 1 3 2 6 4 0 7 5 8 3 4 0 6 3 1 2 9 10 11 4 3 6 4 1 5 7 10 2 0 5 6 4 0 2 7 9 11 3 1 6 5 8 7 9 10 11 4 0 6 7 8 7 5 10 2 3 0 6 4 8 7 5 8 11 0 1 6 4 10 Figure 4: Set B 0 1 2 3 4 5 6 7 8 0 1 0 3 2 5 4 7 6 9 1 0 3 1 5 4 2 6 9 7 2 3 1 0 4 2 5 9 7 6 3 2 5 4 7 3 1 0 8 11 4 5 4 2 3 6 7 8 1 0 5 4 2 5 1 7 9 11 0 3 6 7 6 9 0 8 11 2 5 4 7 6 9 7 8 1 0 5 4 2 8 9 7 6 11 0 3 4 2 5 Figure 5: Set C Figure 6: From P not P 0 1 2 3 4 5 6 7 8 0 0 2 1 4 3 6 5 8 7 1 2 1 3 0 6 4 8 7 5 2 1 3 2 6 4 0 7 5 8 3 4 0 6 3 1 2 9 10 11 4 3 6 4 1 5 7 10 2 0 5 6 4 0 2 7 9 11 3 1 6 5 8 7 9 10 11 4 0 6 7 8 7 5 10 2 3 0 6 4 8 7 5 8 11 0 1 6 4 10 Figure 7: Horizontal 0 1 2 3 4 5 6 7 8 0 0 2 1 4 3 6 5 8 7 1 2 1 3 0 6 4 8 7 5 2 1 3 2 6 4 0 7 5 8 3 4 0 6 3 1 2 9 10 11 4 3 6 4 1 5 7 10 2 0 5 6 4 0 2 7 9 11 3 1 6 5 8 7 9 10 11 4 0 6 7 8 7 5 10 2 3 0 6 4 8 7 5 8 11 0 1 6 4 10 Figure 8: Vertical 0 1 2 3 4 5 6 7 8 0 0 2 1 4 3 6 5 8 7 1 2 1 3 0 6 4 8 7 5 2 1 3 2 6 4 0 7 5 8 3 4 0 6 3 1 2 9 10 11 4 3 6 4 1 5 7 10 2 0 5 6 4 0 2 7 9 11 3 1 6 5 8 7 9 10 11 4 0 6 7 8 7 5 10 2 3 0 6 4 8 7 5 8 11 0 1 6 4 10 Figure 9: Daiagonal Lemma 1. (i)The set Ain Definition 12 is the set of P-positions (x, y, 0) of the game in Definition 8 such that x, y ≤8and the pass is not available. (ii)The set Bin Definition 12 is the set of P-positions (x, y, 1) of the game in Definition 8 such that x, y ≤8and the pass is available. (iii)The set Cin Definition 12 is the set of P-positions (x, y, 1) of the game in Definition 9 such that x, y ≤8and the third coordinate is 1. Proof. (i) Since the pass is not available, by using Theorem 2 for x, y ≤8 we obtain Set A. 8 (ii) Let U={(x, y, 1) : x, y ≤8}. Since we need to prove that the set P-positions of the game in Definitions 8 in Uis Bwhen a pass is available, we need to prove that move1(x, y, 1) ∩(A∪B) = ∅(1) for any (x, y, 1) ∈Band move1(x, y, 1) ∩(A∪B)=∅(2) for any (x, y, 1) ∈U−B. First, we prove Relation (1). Suppose that we start with the position (7,6,1). Then, the horizontal, vertical, and diagonal moves from this position are described in Figure 6, and it is easy to see that M1(7,6,1) ∩B=∅,M2(7,6,1) ∩B=∅, and M3(7,6,1) ∩B=∅. Since M4(7,6,1) = {(7,6,0)}and (7,6,0) /∈A, we obtain M4(7,6,1) ∩A=∅. Therefore, move1(7,6,1) ∩(A∪B) = ∅. Similarly, for any (x, y, 1) ∈B, it is easy to show that M1(x, y, 1) ∩B=∅,M2(x, y, 1) ∩B=∅, and M3(x, y, 1)∩B=∅. By comparing Figure 3 and Figure 4, we obtain M4(x, y, 1)∩A= ∅. Therefore, we obtain Relation (1). Next, we prove Relation (2). Let (x, y, 1) ∈U−B. For (8, y, 1) with y= 0,1,2,3 and y= 5,6,7,8, it is clear that M1(x, y, 1) ∩B=∅. In this way, for all blue positions (x, y, 1) in Figure 7, we obtain M1(x, y, 1) ∩B=∅. Similarly, for all blue positions (x, y, 1) in Figure 8, we obtain M2(x, y, 1)∩B=∅and for all blue positions (x, y, 1) in Figure 9, we obtain M3(x, y, 1) ∩B=∅. The positions in U−Bthat do not belong to the set of blue positions in Figures 7, 8, and 9 are (1,2,1) and (2,1,1). Since (1,2,0) and (2,1,0) belong to the set Ain Figure 3, M4(1,2,1) ∩A=∅and M4(2,1,1) ∩A=∅. Therefore, we obtain Relation (2). (iii) By a method that is very similar to the one used in (ii), we can prove (iii). Therefore, the details are omitted. 5. The Set of P-positions of Wythoff’s Game with a Pass In this section, we determine the set of P-positions of Wythoff’s game with a pass. We use the similarity between the set of P-positions of Wythoff’s game with a pass and the set of P-positions of the game in Definition 9. Let P0={(x, y, 0) : G1(x, y, 0) = 0},P1={(x, y, 1) : G1(x, y, 1) = 0}, and P2={(x, y, 1) : G2(x, y, 1) = 0}. Lemma 2. Let x, y ∈Z≥0such that x≥9or y≥9. Then, we obtain the following: (i)if y≤8, then M1(x, y, 1) ∩B=∅,M1(x, y, 1) ∩C=∅, and M2(x, y, 1) ∩C= M2(x, y, 1) ∩B=∅; (ii)if x≤8, then M2(x, y, 1) ∩B=∅,M2(x, y, 1) ∩C=∅, and M1(x, y, 1) ∩C= M1(x, y, 1) ∩B=∅; 9 (iii)if x≤y+ 4 and y≤x+ 4, then M3(x, y, 1) ∩B=∅and M3(x, y, 1) ∩C=∅; (iv)if x≥y+ 5 or y≥x+ 5, then M3(x, y, 1) ∩B=M3(x, y, 1) ∩C=∅. Proof. (i) Suppose that x≥9 and y≤8. Then, by Definition 12, there exist u, u′∈Z≥0such that 1 ≤u, u′≤8, (u, y, 1) ∈B, and (u′, y, 1) ∈C. Then, we obtain (u, y, 1) ∈M1(x, y, 1) ∩Band (u′, y, 1) ∈M1(x, y, 1) ∩C. Since x≥9, M2(x, y, 1) ⊂ {(x, v, 1) : v∈Z≥0} ⊂ (B∪C)c, where (B∪C)cis the complement of the set B∪C. Hence, M2(x, y, 1) ∩C=M2(x, y, 1) ∩B=∅. (ii) Suppose that y≥9 and x≤8. Then, (ii) follows directly from (i), because this game is symmetrical with respect to the first and second coordinates. (iii) Suppose that x≤y+ 4 and y≤x+ 4. By Definition 12, for any a∈Z≥0such that −4≤a≤4, there exist u, u′, v, v′∈Z≥0such that u=v+a,u′=v′+a, (u, v, 1) ∈B, and (u′, v′,1) ∈C. Then, (u, v, 1) ∈B∩M3(x, y, 1) and (u′, v′,1) ∈ C∩M3(x, y, 1). Therefore, M3(x, y, 1) ∩B=∅and M3(x, y, 1) ∩C=∅. (iv) We have two cases. Case 1: Suppose that x≥y+ 5. There is no u, v ∈Z≥0such that u≥v+ 5 and (u, v, 1) ∈B∪C. Hence, M3(x, y, 1) ∩B=M3(x, y, 1) ∩C=∅. Case 2: Suppose that y≥x+ 5. Since this game is symmetrical with respect to the first and the second coordinates, M3(x, y, 1) ∩B=M3(x, y, 1) ∩C=∅. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 2 1 4 3 6 5 8 7 1 2 1 3 0 6 4 8 7 5 2 1 3 2 6 4 0 7 5 8 3 4 0 6 3 1 2 9 10 11 4 3 6 4 1 5 7 10 2 0 5 6 4 0 2 7 9 11 3 1 6 5 8 7 9 10 11 4 0 6 7 8 7 5 10 2 3 0 6 4 8 7 5 8 11 0 1 6 4 10 9 10 11 12 13 14 Figure 10: Set B and other positions 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 0 3 2 5 4 7 6 9 1 0 3 1 5 4 2 6 9 7 2 3 1 0 4 2 5 9 7 6 3 2 5 4 7 3 1 0 8 11 4 5 4 2 3 6 7 8 1 0 5 4 2 5 1 7 9 11 0 3 6 7 6 9 0 8 11 2 5 4 7 6 9 7 8 1 0 5 4 2 8 9 7 6 11 0 3 4 2 5 9 10 11 12 13 14 Figure 11: Set C and other positions Lemma 3. For x, y ∈Z≥0such that x≥9or y≥9, we obtain the following: (i)M1(x, y, 1) ∩B=∅if and only if M1(x, y, 1) ∩C=∅; (ii)M2(x, y, 1) ∩B=∅if and only if M2(x, y, 1) ∩C=∅; (iii)M3(x, y, 1) ∩B=∅if and only if M3(x, y, 1) ∩C=∅. Proof. By Lemma 2, we obtain (i), (i), and (iii).