A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence

Basic Information

• Paper ID: 2510.11767
• Title: A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
• Authors: Kahori Komaki, Ryohei Miyadera, Aoi Murakami
• Classification: math.CO (Combinatorics)
• Publication Date: October 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.11767

Abstract

This paper investigates a variant of the classical Wythoff's game. The classical Wythoff's game involves two piles of stones, where two players alternately remove stones from one or both piles, and when removing from both piles simultaneously, they must remove equal quantities. The player who removes the last stone(s) wins. Equivalently, this can be viewed as moving a chess queen on a large grid, where each player can move the queen any number of steps vertically, horizontally, or diagonally toward the upper-left corner (0,0).

In the variant presented in this paper, the set of terminal positions is extended to {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}. The P-positions of this variant are characterized through the P-positions of Wythoff's game and Hofstadter's G-sequence. The variant exhibits two remarkable properties: for positions (x,y) with x≥8 or y≥8, the Grundy number of position (x,y) in this variant equals 1 if and only if (x,y) is a P-position in Wythoff's game; for positions (x,y) with x≥8 or y≥8, (x,y) is a P-position in the misère version of this variant if and only if (x,y) is a P-position in Wythoff's game.

Research Background and Motivation

Problem Definition

This research aims to analyze and solve a new variant of the classical Wythoff's game, where the terminal condition is extended from a single position (0,0) to a set containing six positions. This seemingly simple extension significantly alters the game's complexity and strategic structure.

Significance

1. Theoretical Value: Wythoff's game is a classical problem in combinatorial game theory, with its P-positions closely related to the golden ratio φ=(1+√5)/2. Studying its variants contributes to a deeper understanding of the structural properties of combinatorial games.
2. Mathematical Connection: This research establishes a novel connection between Hofstadter's G-sequence and combinatorial game theory, which has been rarely explored in previous studies.
3. Methodological Innovation: By introducing the function g(n) and Hofstadter's G-sequence, this work provides new mathematical tools for analyzing combinatorial games with complex terminal conditions.

Limitations of Existing Methods

While the P-positions of classical Wythoff's game have explicit closed-form expressions, when the terminal condition becomes a set of multiple positions, traditional analytical methods cannot be directly applied. Existing combinatorial game theory lacks systematic methods for handling such extended terminal conditions.

Core Contributions

1. Defined a new game variant: Extended the terminal positions of Wythoff's game from a single point (0,0) to the set {(x,y): x+y≤2}
2. Established complete characterization of P-positions: Through introducing the function g(n) and Hofstadter's G-sequence, provided precise formulas for the P-positions of this variant
3. Discovered two important properties:
   • For positions with x≥8 or y≥8, the Grundy number in this variant equals 1 if and only if the position is a P-position in the original Wythoff's game
   • For positions with x≥8 or y≥8, a position is a P-position in the misère version if and only if it is a P-position in the original Wythoff's game
4. Established connection with Hofstadter's G-sequence: Proved that the function g(n) can be recursively defined through Hofstadter's G-sequence

Methodology Details

Task Definition

Input: Game position (x,y), where x,y∈ℤ≥0 Output: Determine whether the position is a P-position (previous player's winning position) or an N-position (next player's winning position) Constraints: Movement rules are identical to classical Wythoff's game, but the terminal set is {(x,y): x+y≤2}

Core Mathematical Framework

1. Definition of Function g(n)

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  if ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 for some m∈ℤ≥0
  1         otherwise
}

2. Characterization of P-Position Set

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}, where:

• P₁,₁ = {(⌊nφ⌋ + g(n) - 1, ⌊n(φ+1)⌋ + g(n)) : n ∈ ℤ≥0}
• P₁,₂ = {(⌊n(φ+1)⌋ + g(n), ⌊nφ⌋ + g(n) - 1) : n ∈ ℤ≥0}

3. Connection with Hofstadter's G-Sequence

For n≥2:

g(n) = {
  1 - g(h(n-1))  if h(n-2) < h(n-1)
  1              otherwise
}

where h is Hofstadter's G-sequence: h(0)=0, h(n)=n-h(h(n-1))

Technical Innovations

1. Sequence Decomposition Technique: By decomposing natural numbers into the lower Wythoff sequence A₁={⌊nφ⌋} and the upper Wythoff sequence A₂={⌊n(φ+1)⌋}, established a systematic analytical framework.
2. Recursive Function Design: The design of function g(n) cleverly captures the impact of terminal set extension on the distribution of P-positions.
3. Grundy Number Analysis: Through computing Grundy numbers, established deep connections between this variant and the original game.

Experimental Setup

Theoretical Verification Methods

This paper employs pure theoretical proof methods, verifying results through the following steps:

1. Completeness Proof: Proved that from any non-P-position, one can move to a P-position
2. Consistency Proof: Proved that from a P-position, one cannot move to another P-position
3. Computational Verification: Performed exhaustive verification for small-scale cases

Specific Verification Scope

• Complete exhaustive analysis for all positions with coordinates x,y≤7
• For cases with x≥8 or y≥8, established equivalence with the original Wythoff's game through theoretical proof

Experimental Results

Main Theoretical Results

Theorem 1: Complete Characterization of P-Positions

The set P₁ is the complete set of P-positions for this game variant, proved through Lemma 8 and Lemma 12:

• Lemma 8: From a position in P₁, one cannot move to another position in P₁
• Lemma 12: From any position not in P₁, one can move to some position in P₁

Theorem 2: Relationship with Original Wythoff's Game

For positions (x,y) with x≥8 or y≥8:

• G₂(x,y,1)=0 in this variant if and only if G₀(x,y)=0 in the original game
• This establishes equivalence between the two games at "large" positions

Theorem 3: Properties of Misère Version

The P-positions of the misère version (where the player entering the terminal set loses) are identical to the P-positions of the original game combined with a single-pile game.

Small-Scale Verification Results

Through exhaustive verification, the following small-scale P-position sets were determined:

• Set A: {(0,0,1), (0,1,1), (0,2,1), (1,0,1), (1,1,1), (2,0,1), (3,6,1), (6,3,1), (4,8,1), (8,4,1)}
• Set B: {(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
• Set C: {(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

Key Findings

1. Boundary Effects: Within the range x,y≤7, the distribution of P-positions differs significantly from the original Wythoff's game
2. Asymptotic Behavior: When coordinates are sufficiently large, the variant's behavior converges to the original Wythoff's game
3. Sequence Properties: The value pattern of function g(n) is closely related to the growth properties of Hofstadter's G-sequence

Related Work

Wythoff's Game Theory

The classical Wythoff's game was proposed by W.A. Wythoff in 1907, and the relationship between its P-positions and the golden ratio is a classical result in combinatorial mathematics. Related research includes:

• Rayleigh's Theorem: Established partition properties of lower and upper Wythoff sequences
• Research on various Wythoff game variants

Hofstadter Sequence Theory

Hofstadter defined multiple recursive sequences in "Gödel, Escher, Bach," among which the G-sequence possesses special number-theoretic properties:

• Gault and Clint (1988) research on recursive functions
• Granville and Rasson (1988) analysis of singular recursive relations

Combinatorial Game Theory

This paper belongs to the field of impartial combinatorial game theory:

• Sprague-Grundy Theorem and its applications
• Determination methods for P-positions and N-positions
• Theoretical framework for misère games

Conclusions and Discussion

Main Conclusions

1. Complete Solution: Provided complete characterization of P-positions for the Wythoff game variant with extended terminal conditions
2. Deep Connections: Revealed the essential relationship between this variant and Hofstadter's G-sequence
3. Asymptotic Equivalence: Proved the equivalence between this variant and the original game at large coordinates

Limitations

1. Complexity: The definition of function g(n) is relatively complex, lacking the elegance of the original Wythoff game's closed-form solution
2. Computational Efficiency: Determining P-positions requires computing Hofstadter's sequence, which may present computational complexity issues
3. Generalizability: Whether the method can be generalized to other terminal sets remains unclear

Future Directions

1. More General Terminal Sets: Study Wythoff game variants with arbitrary terminal sets
2. Algorithm Optimization: Develop more efficient algorithms for determining P-positions
3. Other Recursive Sequences: Explore applications of other famous recursive sequences in combinatorial games

In-Depth Evaluation

Strengths

1. Theoretical Depth: Established novel connections between combinatorial game theory and recursive sequence theory, possessing significant theoretical value
2. Methodological Innovation: The design of function g(n) is ingenious, capturing complex game structures through recursive definition
3. Complete Proofs: Provided rigorous mathematical proofs, including detailed arguments for numerous technical lemmas
4. Profound Results: The discovered asymptotic equivalence property provides new perspectives for understanding complex combinatorial games

Weaknesses

1. Complex Presentation: The definition of function g(n) is relatively abstract, potentially affecting intuitive understanding of the results
2. Limited Practical Value: While theoretically complete, the practical applicability remains unclear
3. Difficult Generalization: The specificity of the method may limit its application to other problems

Impact

1. Academic Value: Opens new directions for cross-disciplinary research between combinatorial game theory and recursive sequence theory
2. Methodological Contribution: Provides new tools for analyzing combinatorial games with complex terminal conditions
3. Theoretical Completeness: Enriches the theoretical system of Wythoff game variants

Applicable Scenarios

1. Theoretical Research: Suitable for theoretical research in combinatorial mathematics and game theory
2. Algorithm Design: Provides theoretical foundation for designing optimal strategy algorithms for related games
3. Educational Applications: Serves as an excellent case study demonstrating connections between recursive sequences and combinatorial problems

References

1. M.H. Albert, R.J. Nowakowski, and D. Wolfe: Lessons In Play, A K Peters/CRC Press, 2007
2. D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980
3. W.A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wiskd, 7 (1907), 199-202
4. V. Granville and J.-P. Rasson, A strange recursive relation, J. Number Theory 30 (1988), 238–241

This paper makes important theoretical contributions to the field of combinatorial game theory. By ingeniously combining Hofstadter's G-sequence, it provides a complete mathematical framework for analyzing Wythoff game variants with complex terminal conditions. While possessing certain limitations in practical applicability, its theoretical depth and methodological innovation make it a significant research achievement in this field.