2025-11-19T22:58:13.964427

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

Komak, Miyadera, Murakami
In this paper, we study 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. The player who removes the last stone or stones is the winner. Equivalently, we consider a single chess queen placed somewhere on a large grid of squares. Each player can move the queen toward the upper-left corner of the grid, either vertically, horizontally, or diagonally, in any number of steps. The winner is the player who moves the queen into the upper-left corner, the position (0,0) in our coordinate system. We call (0,0) the terminal position of Wythoff's game. In our variant of Wythoff's game, we have a set of positions {(0,0),(1,0),(0,1),(1,1),(2,0),(0,2)} as the terminal set. If a player moves the queen into this terminal set, that player is the winner of the game. The P-positions of this variant are described by the P-positions of Wythoff's game and Hofstadter's G-Sequence. This variant has two remarkable properties. For a position (x,y) with x >= 8 or y >= 8, the Grundy number of the position (x,y) is 1 in this variant if and only if (x,y) is a P-position of Wythoff's game. There is another remarkable property.For a position (x,y) with x >= 8 or y >= 8, (x,y) is a P-position of of the misere version of this variant if and only if (x,y) is a P-position of of Wythoff's game.
academic

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

基本信息

  • 论文ID: 2510.11767
  • 标题: A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
  • 作者: Kahori Komaki, Ryohei Miyadera, Aoi Murakami
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月13日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.11767

摘要

本文研究了经典Wythoff游戏的一个变体。经典Wythoff游戏涉及两堆石子，两名玩家轮流从一堆或两堆中移除石子，当同时从两堆移除时必须移除相同数量。移除最后一颗或最后几颗石子的玩家获胜。等价地，可以将其视为在大网格上移动国际象棋皇后，每位玩家可以垂直、水平或对角线方向移动皇后任意步数朝向左上角(0,0)。

在本文的变体中，终端位置集合扩展为{(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}。该变体的P位置通过Wythoff游戏的P位置和Hofstadter的G序列来描述。该变体具有两个显著性质：对于x≥8或y≥8的位置(x,y)，该变体中位置(x,y)的Grundy数为1当且仅当(x,y)是Wythoff游戏的P位置；对于x≥8或y≥8的位置(x,y)，(x,y)是该变体的misère版本的P位置当且仅当(x,y)是Wythoff游戏的P位置。

研究背景与动机

问题定义

本研究旨在分析和解决经典Wythoff游戏的一个新变体，其中终端条件从单一位置(0,0)扩展为一个包含6个位置的集合。这种扩展看似简单，但显著改变了游戏的复杂性和策略结构。

重要性

  1. 理论意义：Wythoff游戏是组合博弈论的经典问题，其P位置与黄金比例φ=(1+√5)/2密切相关。研究其变体有助于深入理解组合游戏的结构性质。
  2. 数学联系：本研究建立了Hofstadter的G序列与组合游戏理论之间的新联系，这在以往研究中较少涉及。
  3. 方法创新：通过引入函数g(n)和Hofstadter的G序列，为分析复杂终端条件的组合游戏提供了新的数学工具。

现有方法局限性

经典Wythoff游戏的P位置有明确的闭式表达式，但当终端条件变为多个位置的集合时，传统分析方法难以直接应用。现有的组合游戏理论缺乏处理这类扩展终端条件的系统性方法。

核心贡献

  1. 定义了新的游戏变体：将Wythoff游戏的终端位置从单点(0,0)扩展为集合{(x,y): x+y≤2}
  2. 建立了P位置的完整刻画：通过引入函数g(n)和Hofstadter的G序列，给出了该变体P位置的精确公式
  3. 发现了两个重要性质：
    • 对于x≥8或y≥8的位置，该变体的Grundy数为1当且仅当该位置是原Wythoff游戏的P位置
    • 对于x≥8或y≥8的位置，该位置是misère版本的P位置当且仅当它是原Wythoff游戏的P位置
  4. 建立了与Hofstadter G序列的联系：证明了函数g(n)可以通过Hofstadter的G序列递归定义

方法详解

任务定义

输入：游戏位置(x,y)，其中x,y∈ℤ≥0 输出：判断该位置是P位置（前一个玩家的获胜位置）还是N位置（下一个玩家的获胜位置） 约束：移动规则与经典Wythoff游戏相同，但终端集合为{(x,y): x+y≤2}

核心数学框架

1. 函数g(n)的定义

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  如果 ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 对某个m∈ℤ≥0
  1         其他情况
}

2. P位置集合的刻画

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}，其中：

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

3. 与Hofstadter G序列的联系

对于n≥2：

g(n) = {
  1 - g(h(n-1))  如果 h(n-2) < h(n-1)
  1              其他情况
}

其中h是Hofstadter的G序列：h(0)=0, h(n)=n-h(h(n-1))

技术创新点

  1. 序列分解技术：通过将自然数分解为下Wythoff序列A₁={⌊nφ⌋}和上Wythoff序列A₂={⌊n(φ+1)⌋}，建立了系统的分析框架。
  2. 递归函数设计：函数g(n)的设计巧妙地捕捉了终端集合扩展对P位置分布的影响。
  3. Grundy数分析：通过计算Grundy数，建立了该变体与原游戏之间的深层联系。

实验设置

理论验证方法

本文采用纯理论证明方法，通过以下步骤验证结果：

  1. 完备性证明：证明从任何非P位置都可以移动到P位置
  2. 一致性证明：证明从P位置无法移动到另一个P位置
  3. 计算验证：对小规模情况进行穷举验证

具体验证范围

  • 对于位置坐标x,y≤7的所有情况进行了完整的穷举分析
  • 对于x≥8或y≥8的情况，通过理论证明建立了与原Wythoff游戏的等价关系

实验结果

主要理论结果

定理1：P位置的完整刻画

集合P₁是该游戏变体的P位置集合，这通过Lemma 8和Lemma 12得到证明：

  • Lemma 8：从P₁中的位置无法移动到P₁中的其他位置
  • Lemma 12：从任何不在P₁中的位置都可以移动到P₁中的某个位置

定理2：与原Wythoff游戏的关系

对于x≥8或y≥8的位置(x,y)：

  • 该变体中G₂(x,y,1)=0当且仅当原游戏中G₀(x,y)=0
  • 这建立了两个游戏在"大"位置上的等价性

定理3：Misère版本的性质

Misère版本（输入终端集合的玩家败）的P位置与原游戏加单石堆的和游戏的P位置相同。

小规模验证结果

通过穷举验证，确定了以下小规模P位置集合：

  • 集合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)}
  • 集合B：{(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
  • 集合C：{(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

关键发现

  1. 边界效应：在x,y≤7的范围内，P位置分布与原Wythoff游戏显著不同
  2. 渐近行为：当坐标足够大时，该变体的行为收敛到原Wythoff游戏
  3. 序列性质：函数g(n)的取值模式与Hofstadter G序列的增长性质密切相关

相关工作

Wythoff游戏理论

经典Wythoff游戏由W.A. Wythoff于1907年提出，其P位置与黄金比例的关系是组合数学的经典结果。相关研究包括：

  • Rayleigh定理：建立了下上Wythoff序列的分割性质
  • 各种Wythoff游戏变体的研究

Hofstadter序列理论

Hofstadter在《Gödel, Escher, Bach》中定义了多个递归序列，其中G序列具有特殊的数论性质：

  • Gault和Clint (1988)的递归函数研究
  • Granville和Rasson (1988)的奇异递归关系分析

组合博弈论

本文属于公平组合游戏理论范畴：

  • Sprague-Grundy定理及其应用
  • P位置和N位置的判定方法
  • Misère游戏的理论框架

结论与讨论

主要结论

  1. 完整解决方案：给出了Wythoff游戏扩展终端变体的P位置完整刻画
  2. 深层联系：揭示了该变体与Hofstadter G序列之间的本质联系
  3. 渐近等价性：证明了在大坐标情况下，该变体与原游戏的等价关系

局限性

  1. 复杂性：函数g(n)的定义相对复杂，不如原Wythoff游戏的闭式解那样优雅
  2. 计算效率：判定P位置需要计算Hofstadter序列，可能存在计算复杂度问题
  3. 推广性：方法是否能推广到其他终端集合尚不明确

未来方向

  1. 更一般的终端集合：研究任意终端集合的Wythoff游戏变体
  2. 算法优化：开发更高效的P位置判定算法
  3. 其他递归序列：探索其他著名递归序列在组合游戏中的应用

深度评价

优点

  1. 理论深度：建立了组合游戏理论与递归序列理论之间的新联系，具有重要的理论价值
  2. 方法创新：函数g(n)的设计巧妙，通过递归定义捕捉了复杂的游戏结构
  3. 证明完整：提供了完整的数学证明，包括大量技术引理的详细论证
  4. 结果深刻：发现的渐近等价性质为理解复杂组合游戏提供了新视角

不足

  1. 表述复杂：函数g(n)的定义较为抽象，可能影响结果的直观理解
  2. 实用性有限：虽然理论上完整，但在实际应用中的价值尚不明确
  3. 推广困难：方法的特殊性可能限制其在其他问题上的应用

影响力

  1. 学术价值：为组合博弈论和递归序列理论的交叉研究开辟了新方向
  2. 方法论贡献：提供了分析复杂终端条件组合游戏的新工具
  3. 理论完整性：丰富了Wythoff游戏变体的理论体系

适用场景

  1. 理论研究：适合组合数学和博弈论的理论研究
  2. 算法设计：为设计相关游戏的最优策略算法提供理论基础
  3. 教学应用：可作为展示递归序列与组合问题联系的优秀案例

参考文献

  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

本论文在组合博弈论领域做出了重要的理论贡献，通过巧妙地结合Hofstadter G序列，为分析复杂终端条件的Wythoff游戏变体提供了完整的数学框架。虽然在实用性方面存在一定局限，但其理论深度和方法创新性使其成为该领域的重要研究成果。