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

ホフスタッター G 数列で定義されたウィスオフゲームの変種

基本情報

  • 論文ID: 2510.11767
  • タイトル: A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
  • 著者: 小牧香織、宮寺良平、村上葵
  • 分類: math.CO（組合数学）
  • 発表日: 2025年10月13日（arXiv プレプリント）
  • 論文リンク: https://arxiv.org/abs/2510.11767

要約

本論文は古典的なウィスオフゲームの変種を研究している。古典的なウィスオフゲームは2つの石の山を扱い、2人のプレイヤーが交互に1つまたは2つの山から石を取り除き、両方の山から取り除く場合は同じ数を取り除く必要がある。最後の石を取り除いたプレイヤーが勝利する。同等に、これは大きなグリッド上でチェスのクイーンを移動させることとして見なすことができ、各プレイヤーは垂直、水平、または対角線方向に左上隅(0,0)に向かって任意のステップ数だけクイーンを移動させることができる。

本論文の変種では、終端位置の集合を{(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}に拡張している。この変種のP位置はウィスオフゲームのP位置とホフスタッターのG数列を通じて記述される。この変種は2つの顕著な性質を持つ：x≥8またはy≥8の位置(x,y)に対して、この変種における位置(x,y)のグランディ数が1であることは、(x,y)がウィスオフゲームのP位置であることと同値である；x≥8またはy≥8の位置(x,y)に対して、(x,y)がこの変種のミゼール版のP位置であることは、(x,y)がウィスオフゲームのP位置であることと同値である。

研究背景と動機

問題定義

本研究は古典的なウィスオフゲームの新しい変種を分析・解決することを目的としており、終端条件を単一位置(0,0)から6つの位置を含む集合に拡張している。この拡張は一見単純に見えるが、ゲームの複雑性と戦略構造を大きく変える。

重要性

  1. 理論的意義：ウィスオフゲームは組合博弈論の古典的問題であり、そのP位置は黄金比φ=(1+√5)/2と密接に関連している。その変種を研究することは、組合ゲームの構造的性質をより深く理解するのに役立つ。
  2. 数学的関連性：本研究はホフスタッターのG数列と組合ゲーム理論の間に新しい関連性を確立し、これは先行研究ではあまり扱われていない。
  3. 方法論の革新：関数g(n)とホフスタッターのG数列を導入することで、複雑な終端条件を持つ組合ゲームを分析するための新しい数学的ツールを提供する。

既存方法の限界

古典的なウィスオフゲームのP位置には明確な閉形式表現があるが、終端条件が複数の位置の集合になると、従来の分析方法は直接適用することが難しい。既存の組合ゲーム理論には、このような拡張終端条件を扱うための体系的な方法が欠けている。

核心的貢献

  1. 新しいゲーム変種の定義：ウィスオフゲームの終端位置を単一点(0,0)から集合{(x,y): x+y≤2}に拡張
  2. P位置の完全な特性化の確立：関数g(n)とホフスタッターのG数列を導入することで、この変種のP位置の正確な公式を提供
  3. 2つの重要な性質の発見：
    • x≥8またはy≥8の位置に対して、この変種のグランディ数が1であることは、その位置が元のウィスオフゲームのP位置であることと同値
    • x≥8またはy≥8の位置に対して、その位置がミゼール版のP位置であることは、それが元のウィスオフゲームのP位置であることと同値
  4. ホフスタッター G 数列との関連性の確立：関数g(n)がホフスタッターのG数列を通じて再帰的に定義できることを証明

方法の詳細説明

タスク定義

入力：ゲーム位置(x,y)、ここでx,y∈ℤ≥0 出力：その位置がP位置（前のプレイヤーの勝利位置）であるか、N位置（次のプレイヤーの勝利位置）であるかを判定 制約：移動規則は古典的なウィスオフゲームと同じだが、終端集合は{(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. ホフスタッター G 数列との関連性

n≥2に対して：

g(n) = {
  1 - g(h(n-1))  h(n-2) < h(n-1) の場合
  1              その他の場合
}

ここでhはホフスタッターのG数列：h(0)=0, h(n)=n-h(h(n-1))

技術的革新点

  1. 数列分解技術：自然数を下ウィスオフ数列A₁={⌊nφ⌋}と上ウィスオフ数列A₂={⌊n(φ+1)⌋}に分解することで、体系的な分析フレームワークを確立
  2. 再帰関数設計：関数g(n)の設計は巧妙で、終端集合の拡張がP位置の分布に与える影響を再帰的に捉える
  3. グランディ数分析：グランディ数を計算することで、この変種と元のゲーム間の深層的な関連性を確立

実験設定

理論検証方法

本論文は純粋な理論的証明方法を採用し、以下のステップを通じて結果を検証している：

  1. 完全性の証明：任意の非P位置からP位置への移動が可能であることを証明
  2. 一貫性の証明：P位置から別のP位置への移動が不可能であることを証明
  3. 計算検証：小規模ケースについて網羅的な検証を実施

具体的な検証範囲

  • 位置座標x,y≤7のすべてのケースについて完全な網羅的分析を実施
  • x≥8またはy≥8のケースについて、理論的証明を通じて元のウィスオフゲームとの等価性を確立

実験結果

主要な理論的結果

定理1：P位置の完全な特性化

集合P₁はこのゲーム変種のP位置集合であり、これはLemma 8とLemma 12を通じて証明される：

  • Lemma 8：P₁内の位置からP₁内の他の位置への移動は不可能
  • Lemma 12：P₁に含まれない任意の位置からP₁内のある位置への移動が可能

定理2：元のウィスオフゲームとの関係

x≥8またはy≥8の位置(x,y)に対して：

  • この変種におけるG₂(x,y,1)=0は、元のゲームにおけるG₀(x,y)=0と同値
  • これは2つのゲーム間の「大きな」位置での等価性を確立

定理3：ミゼール版の性質

ミゼール版（終端集合に入るプレイヤーが敗北）の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位置の分布は元のウィスオフゲームと大きく異なる
  2. 漸近的振る舞い：座標が十分に大きい場合、この変種の振る舞いは元のウィスオフゲームに収束する
  3. 数列の性質：関数g(n)の値のパターンはホフスタッター G 数列の増長性質と密接に関連している

関連研究

ウィスオフゲーム理論

古典的なウィスオフゲームはW.A. Wythoffにより1907年に提案され、そのP位置と黄金比の関係は組合数学の古典的な結果である。関連研究には以下が含まれる：

  • レイリー定理：下上ウィスオフ数列の分割性質を確立
  • 様々なウィスオフゲーム変種の研究

ホフスタッター数列理論

ホフスタッターは『ゲーデル、エッシャー、バッハ』で複数の再帰数列を定義し、その中でG数列は特別な数論的性質を持つ：

  • Gault と Clint (1988) の再帰関数研究
  • Granville と Rasson (1988) の特異再帰関係分析

組合博弈論

本論文は公平組合ゲーム理論の範疇に属する：

  • Sprague-Grundy定理とその応用
  • P位置とN位置の判定方法
  • ミゼールゲームの理論的フレームワーク

結論と考察

主要な結論

  1. 完全な解決策：拡張終端変種のウィスオフゲームのP位置の完全な特性化を提供
  2. 深層的関連性：この変種とホフスタッター G 数列間の本質的な関連性を明らかにした
  3. 漸近的等価性：大きな座標の場合、この変種と元のゲーム間の等価性を証明

限界

  1. 複雑性：関数g(n)の定義は相対的に複雑で、元のウィスオフゲームの閉形式解ほど優雅ではない
  2. 計算効率：P位置の判定にはホフスタッター数列の計算が必要であり、計算複雑度の問題が存在する可能性がある
  3. 推広性：方法が他の終端集合に推広可能かどうかは不明確である

今後の方向性

  1. より一般的な終端集合：任意の終端集合を持つウィスオフゲーム変種の研究
  2. アルゴリズムの最適化：より効率的なP位置判定アルゴリズムの開発
  3. 他の再帰数列：組合ゲームにおける他の著名な再帰数列の応用の探索

深層的評価

長所

  1. 理論的深さ：組合ゲーム理論と再帰数列理論間に新しい関連性を確立し、重要な理論的価値を持つ
  2. 方法論の革新：関数g(n)の設計は巧妙で、複雑なゲーム構造を再帰的に捉える
  3. 証明の完全性：完全な数学的証明を提供し、多くの技術的補題の詳細な論証を含む
  4. 結果の深刻性：発見された漸近等価性は複雑な組合ゲームを理解するための新しい視点を提供

不足

  1. 表現の複雑性：関数g(n)の定義は比較的抽象的で、結果の直感的理解に影響する可能性がある
  2. 実用性の限定：理論的には完全だが、実際の応用における価値はまだ不明確である
  3. 推広の困難性：方法の特殊性は他の問題への応用を制限する可能性がある

影響力

  1. 学術的価値：組合博弈論と再帰数列理論の交差研究に新しい方向を開く
  2. 方法論的貢献：複雑な終端条件を持つ組合ゲームを分析するための新しいツールを提供
  3. 理論的完全性：ウィスオフゲーム変種の理論体系を豊かにする

適用シーン

  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

本論文は組合博弈論の領域において重要な理論的貢献を行い、ホフスタッター G 数列を巧妙に組み合わせることで、複雑な終端条件を持つウィスオフゲーム変種を分析するための完全な数学的フレームワークを提供している。実用性の面では一定の限界があるが、その理論的深さと方法論の革新性により、この分野の重要な研究成果となっている。