Wythoff（ワイトホフ）のゲームをブラウザに実装した。クイーンは左・下・左下の斜めにだけ何マスでも動けて、隅 (0, 0) に入れた方が勝ち。盤に複数のクイーンを置き、1 手で 1 個だけ動かすルールにすると、各マスの Grundy 値 g(x, y) の XOR が 0 かどうかで勝敗が決まる。クイーンを選ぶと行き先ごとに勝ち筋 ✓／負け筋 ✗ を表示し、コンピュータと対戦できる。検算の題材は 2 つ。1 つ目は「表のどの行も、ある列から先は g(x, y + p) = g(x, y) + p になる」という Dress・Flammenkamp・Pink（1999）の加法的周期性で、OEIS には行 0–45 の前周期（A046874）、行 0–53 の周期（A046875）、同じ周期が続く行数（A046876）が載っている。行 0–460 を 1,400 万列まで計算し、行 0–452 の周期と前周期に「この先も繰り返す」ことの証明（状態の一致）を付けた。OEIS の値は 46/46・54/54・19/19 で一致し、A046876 の未確定項「a(20) ≥ 12」は、行 261–403 の 143 行が周期 196,608 で、行 404 から周期が 393,216 に変わるので a(20) = 143 と決まった。2 つ目は Nivasch の論文（Games of No Chance 3, 2009）の表 2–4 で、31 行・24 行・10 行（＋ 600 行目以降版の 10 行）が全部一致し、表 4 は座標まで同じセルが出た。テスト 11 件。ソルバー内蔵パズル第 97 弾。
デモ: https://sen.ltd/portfolio/wythoff/
リポジトリ: https://github.com/sen-ltd/wythoff
ルール
- 盤は右上に無限に広がる 1/4 平面。クイーンは左・下・左下の斜めのどれかに、何マスでも進める（戻れない）。
- 2 つの山から石を取るゲームと同じもの。座標 (x, y) を 2 つの山の石の数と見ると、「片方の山から何個でも取る」か「両方の山から同じ数だけ取る」。
- 動けなくなった方（クイーンが全部 (0, 0) にいて手番が回ってきた方）の負け。つまり最後に動かした方の勝ち。
クイーン 1 個なら、負け局面（手番の人が負ける局面）は Wythoff の対 (⌊nφ⌋, ⌊nφ²⌋) とその鏡像だけ。φ は黄金比で、(0, 0), (1, 2), (3, 5), (4, 7), (6, 10), … になる。
クイーンを足し合わせる
デモは盤に 1〜4 個のクイーンを置き、手番ごとにどれか 1 個だけを動かす。こうするとゲームの「和」になり、Sprague–Grundy の定理がそのまま使える。
- マス (x, y) の Grundy 値 g(x, y) は、そこから行けるマスの値に含まれない最小の非負整数（mex）。
- クイーンが何個あっても、局面の値は各クイーンの g の XOR。XOR が 0 なら手番の人の負け、0 でなければ勝ちで、XOR を 0 にする手が必ずある。
右パネルに各クイーンの g と XOR を出し、クイーンを選ぶと行き先のマスに、動かした後の XOR が 0 になるなら ✓、ならないなら ✗ を付けている。コンピュータは ✓ の手があればそれを指し、なければ 1 マスだけ動かして粘る。テストでは、7 × 7 盤の 2 クイーンの全局面（2,401 通り）を値を使わない勝敗探索で解き、XOR 規則と一致することを確かめた。
値 0 の位置には公式があるが、1 以上の値には公式がない。下のヒートマップは 200 × 200 の値で、スライダーで選んだ値のマスだけ明るくなる。どの値も傾き φ と 1/φ の 2 本の線の近くに集まっていて、Nivasch の論文はこれを定理として示している（後述）。
行は加法的に周期的
行 x を固定して y を動かすと、ある列から先は
g(x, y + p) = g(x, y) + p
が成り立つ。これが加法的周期性で、Dress・Flammenkamp・Pink（1999）が証明した。p が周期、成り立ち始める列が前周期。たとえば行 3 は前周期 8、周期 6、行 10 は前周期 224、周期 24 になる。デモの右下では、選んだ行の g(x, y) − y を点で打ち、前周期を網掛け、周期ごとに縦線を引いている（行 40 までをブラウザ内で計算する）。
OEIS には 3 本の数列がある。
| 数列 | 内容 | 載っている範囲 |
|---|---|---|
| A046874 | 行 x の前周期 | 行 0–45 |
| A046875 | 行 x の周期 | 行 0–53 |
| A046876 | 同じ周期が何行続くか | 19 個と、「a(20) ≥ 12（S. A. Irvine, 2021）」 |
周期は 1, 3, 3, 6, 12, 24, 12, 24, … と 3·2^k の形で、1 段ずつ倍になっていく。A046876 は 1, 2, 1, 1, 1, 1, 4, 2, 3, 2, 3, 23, 24, 3, 20, 18, 84, 25, 43 で、20 個目（行 261 から始まる周期 196,608 の行が何行続くか）が分かっていない。行 261 の前周期は 264 万列なので、そこまで計算しないとこの範囲の行は 1 行も確定しない。
メモリが列数に依存しない掃引
表を全部持つと、行 460 × 1,400 万列で 64 億マスになる。そこで列を 1 本ずつ進め、各列で行 0–460 を下から計算する。
行 x・列 y の値に必要なのは、同じ行の左側、同じ列の下側、同じ斜めの左下にある値だけ。しかも x ≤ y では y − 2x ≤ g(x, y) ≤ y + x が成り立つので、効いてくる値はすべて [y − 2X, y + X] の幅 3X 程度の窓に入る（X は最上段の行）。だから「行 x で使った値」「列 y で使った値」「斜め d で使った値」を、それぞれ W ≥ 4X + 2 ビットのリングバッファ（値 mod W でビットを立てる）にしておけば足りる。
ただし、この窓の不等式は仮定していない。
- mex の探索はその行自身の mex から始める。行 x にそれより小さい値は全部出ているので、和集合の mex がそれより小さくなることはない。
- 行の mex が y − 2X を下回ったり、値が y + X を上回ったりしたら例外を投げる。リングの値が混ざらないために必要なのはこの 2 つだけ。
1,400 万列を通して例外は一度も出なかった。速度は 1 マスあたり約 0.33 µs（Node.js、1 スレッド）で、行 0–460 × 1,400 万列が 2,156 秒（36 分）。
周期の検出と「証明」
各行で残差 r(y) = g(x, y) − y を、候補の周期 P ∈ {1, 3, 6, 12, …, 786,432} ごとに r(y − P) と比べ、最後に食い違った列を覚えておく。正しい周期では食い違いが前周期で止まり、間違った候補ではいつまでも食い違いが出る。最後の食い違いから P を引いて 1 を足したものが前周期になる。
これだけだと「1,400 万列までは周期的に見えた」にすぎない。そこで状態の一致で証明を付けた。
- 列 y での行 x の状態とは、行の mex − y と、mex から y + X までのどの値をもう使ったか（どちらも y からの相対値）。次の値はこの状態と、列 y・斜めから入ってくる下の行の値だけで決まる。
- 下の行がすべて周期的（周期は 786,432 = 3·2^18 の約数）で、その前周期が c − x 以下なら、列 c と列 c + 786,432 には同じ入力が（値を 786,432 ずらした形で）入ってくる。
- そこで行 x の状態が列 c と列 c + 786,432 で一致していれば、それ以降の計算は完全に同じことの繰り返しになり、行 x はずっと周期的になる。
チェックポイントを 98,304 列ごとに取り、これを行 0 から順に帰納的に当てていくと、行 0–452 の全部に証明が付いた。行 453–460 は、証明に必要な「チェックポイント + 786,432 + 周期」が 1,400 万列を少しはみ出したので数に入れていない。報告する周期は、証明の列から 786,432 列以上食い違いのない最小の候補にしている。行が 786,432 で周期的なら、間違った候補は 786,432 列の窓ごとに必ず 1 回は食い違うので、これで取り違えることはない（その窓が計算した範囲に収まっていることもスクリプトで確かめている）。
結果
| OEIS | ここでの計算 | |
|---|---|---|
| A046874（前周期） | 行 0–45 | 46 / 46 一致、行 0–452 まで |
| A046875（周期） | 行 0–53 | 54 / 54 一致、行 0–452 まで |
| A046876（同じ周期の続く行数） | 19 個、a(20) ≥ 12 | 19 / 19 一致、a(20) = 143、a(21) ≥ 49 |
行 261 から行 403 までの 143 行が周期 196,608 で、行 404（前周期 9,566,285）から周期が 393,216 に倍になる。この周期は計算した最後の行 452（前周期 12,706,872）まで続いていて、a(21) は 49 以上。先に行 0–360 を 1,100 万列まで回した計算とも、共通の 361 行で周期・前周期が全部一致した。
周期が本当に最小か
候補は 1 と 3·2^k に限っている（OEIS の項は全部この形）。証明された周期 P = 3·2^k の約数のうち、小さい候補が食い違い続けたことで消えないのは 2^k だけなので、2^k が実は周期だったら報告した P は 3 倍大きすぎることになる。そこで各行について 2^k だけを追うもう一回の掃引（tools/minimal.mts）を回した。結果は、行 0–452 のすべてで 2^k が前周期より後で食い違った（1,333 万列、867 秒）。報告した周期はどれも最小で、a(20) = 143 はこれで確定する。
この確認には意味がある。行 261–403 の周期の候補は 65,536 か 196,608、行 404 以降は 131,072 か 393,216 なので、run の境目（行 403 と 404）は 2^k の確認がなくても動かないが、run の途中に 65,536 の行が 1 本でも混ざっていれば a(20) は 143 より小さくなる。
ほかに分かったこと。
- 周期が下がるのは行 5 → 6 の 24 → 12 の 1 回だけで、あとは単調に倍になる。
- 前周期が下がるのも行 31 → 32 の 4,422 → 4,419 の 1 回だけ（これは OEIS の範囲内）。
- 前周期は x が倍になるとおよそ 7–8 倍になる（行 90 で 126,851、行 180 で 981,737、行 360 で 7,103,333）。x³ に近い伸び方で、a(21) を決めるには周期が 786,432 に変わる行を見つけ、その前周期 + 3 周期ほどの列まで回す必要がある。
Nivasch の表 2–4
G. Nivasch, More on the Sprague–Grundy function for Wythoff's game（Games of No Chance 3, 2009）は、値 g の位置を a ≤ b の側だけ a の小さい順に並べた列 (aₙ, bₙ) を考え、dₙ = bₙ − aₙ（どの斜めにいるか）が n からどれだけずれるかを調べている。値 0 なら dₙ = n ぴったりで、論文の定理は「どの g でも dₙ − n は有界」。実験として 3 つの表がある。
| 表 | 内容 | 一致 |
|---|---|---|
| 2 | g ≤ 30、aₙ ≤ 5·10⁶ の範囲で dₙ − n の最小値・最大値と、それぞれ最初に現れる n | 31 / 31 行 |
| 3 | g = 7–30、n ≥ 100 に限った dₙ − n の最大値と n | 24 / 24 行 |
| 4 | 最も近い値 0 のマスからのマンハッタン距離 1–10 ごとに、値が最大のセル（g ≤ 199、行 ≤ 10⁶）。行 600 以上に限った版も | 10 / 10 と 10 / 10、セルの座標まで一致 |
表 2 の最小値の列は、PDF のテキストを抜き出すと負号が落ちて 4, 6, 8, … と正の数に見える。計算すると −4, −6, −8, … で、論文の図 9（dₙ − n のヒストグラム、−30 から 30）とも合う。
この計算には表全体は要らない。行 r で値 g が入るマスは、前の行で置いた点の鏡像か、まだ使われていない斜めのうち最小のものから順に「列が空いている」「小さい値がまだ置かれていない」を確かめて最初に通るマスになる。斜めはほぼ順番に埋まっていくので、1 行 1 値あたり数ステップで済む。表 2・3 は 500 万行 × 31 値で 8 秒、表 4 は 100 万行 × 200 値で 32 秒だった。
テスト
- 定義どおりの表が OEIS A317205（Blass・Fraenkel の表 2、50 行）、A004481（反対角線 100 本）、A047708（対角線 400 項）と一致する
- どの行・列・斜めにも同じ値が 2 回出ず、x ≤ y で y − 2x ≤ g ≤ y + x
- 値 0 のマスが Wythoff の対で、貪欲に作った対と ⌊nφ⌋ の整数計算が 10,000 組一致する
- 2 クイーンの全局面で XOR 規則が勝敗探索と一致する
- 列ごとの掃引が定義どおりの表と一致し、行 0–53 の周期と行 0–45 の前周期が OEIS と一致する
- 周期に入った行の状態が周期だけずらすと一致し、ずれ幅が違うと一致しない
- 行ごとの g 点の計算が定義と一致し、Nivasch の表 2 の小さい n の項を再現する
実装メモ
-
src/wythoff.ts: 定義どおりの表、Wythoff の対、列ごとの掃引Sweep（リングバッファ、周期候補ごとの最後の食い違い、rowState）。 -
src/gpoints.ts: 値 g の点を行ごとに求める（Nivasch の表用）。 -
tools/periods.mts: 掃引と証明。tools/minimal.mtsは周期が最小かの確認。チェックポイントごとにruns/periods.jsonを書き直すので、途中で止めてもそこまでの結果が残る。 -
tools/nivasch.mts、tools/report.mts: 論文の表の再計算と、デモの右パネル（src/findings.json）の生成。記事の数字はここから取っている。
まとめ
- Wythoff のゲームは、複数のクイーンを同時に置くと Grundy 値の XOR で勝敗が決まる。デモではすべての手に ✓／✗ を付けた。
- 行の値は「行の mex から探す」「窓を外れたら止まる」の 2 つで、列数に依存しないメモリで掃引できる。行 0–460 を 1,400 万列まで 36 分。
- 周期は、下の行が周期的なときに状態が一致すれば以降ずっと繰り返す、という形で行ごとに証明を付けた。OEIS の 3 数列は全部一致し、A046876 の a(20) は「12 以上」から 143 に決まった。
- Nivasch（2009）の表 2–4 は全行一致した。