Grundy のゲームをブラウザに実装した。1 手で山を 1 つ選び、大きさの違う 2 つの山に分ける。1 個と 2 個の山はもう分けられず、最後に分けた方が勝ち。山の大きさ n ごとに Grundy 値 G(n) があり、山が何個あっても値の XOR が 0 かどうかで勝敗が決まる。山を選ぶと切れる場所ごとに勝ち筋 ✓／負け筋 ✗ が出て、コンピュータと対戦できる。検算の題材は Achim Flammenkamp の公開ページで、そこには「疎な値」を持つ山 1287 個の全リスト、最大値が更新される山の一覧、山 0〜2^35 での値ごとの出現回数と最後の位置が載っている。値を「疎」と「普通」に分ける疎空間の方法で G(0)〜G(2^26 = 67,108,864) を Node.js で 1,017 秒かけて計算し、疎な山 1287 個は位置も値も全部一致、最大値の一覧は 75/75（OEIS A180120/A180121 は 76/76）、2^35 までの頻度表の疎な値 148 行も出現回数・最後の位置まで一致した。最後の 13 個の疎な山がすべて 4,746 万〜4,840 万に固まっている理由と、いちばん長い走査が「値 256 が初めて出る山」でちょうど止まることも計算から読めた。テスト 11 件。ソルバー内蔵パズル第 98 弾。
デモ: https://sen.ltd/portfolio/grundys-game/
リポジトリ: https://github.com/sen-ltd/grundys-game
ルール
- 石の山がいくつかある。手番の人は山を 1 つ選び、大きさの違う 2 つの山に分ける。6 個の山なら 1 + 5 か 2 + 4 で、3 + 3 は禁止。
- 1 個と 2 個の山は分けられない（2 個は 1 + 1 になってしまう）。
- 分けられる山がなくなって手番が回ってきた方の負け。つまり最後に分けた方の勝ち。
P. M. Grundy が 1939 年に Eureka（ケンブリッジの学生誌）で取り上げたゲームで、Winning Ways の 4 章にも出てくる。石を取らずに分けるだけなので「石取り」の形をしていないが、Sprague–Grundy の理論がそのまま使える。
山を足し合わせる
- 大きさ n の山の Grundy 値は G(n) = mex { G(a) ⊕ G(n − a) : 1 ≤ a < n − a }。分けた 2 山の値の XOR を全部の分け方について集め、そこに含まれない最小の非負整数（mex）を取る。
- 山が何個あっても局面の値は各山の G の XOR。0 なら手番の人の負け、0 でなければ勝ちで、XOR を 0 にする分け方が必ずある。
G は 0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3, 2, 1, 3, 2, 4, 3, 0, … と始まる（OEIS A002188）。デモは山を 1〜4 個置き、山を選ぶと石と石のすき間ごとに、そこで切ったあとの XOR が 0 なら ✓、そうでなければ ✗ を付ける。真ん中（等分）のすき間は点線で、クリックできない。コンピュータは ✓ の手があればそれを指し、なければいちばん大きい山から 1 個だけ切り離して粘る。
テストでは、値を使わない素朴な勝敗探索（山の多重集合をキーにしたメモ化）で石 24 個以下の全局面 7,338 通りを解き、XOR 規則と一致することを確かめた。
G(n) = 0 は 42 回しかない
負け局面になる単独の山（G(n) = 0）は 0, 1, 2, 4, 7, 10, 20, 23, 26, 50, 53, 270, … と続き、最後は 1222。OEIS A036685 の 42 項と一致し、2^26 まで計算してもそれ以降は 1 つも出なかった。G(n) が最終的に周期的になるかどうかは分かっていない（周期的なら 0 がもう出ないのは自然だが、証明はない）。
デモの下の図は n ≤ 30,000 の G(n) で、ページを開いたときに 30,000 項を約 0.3 秒で計算している。値はほぼ 3 刻みの帯に並んでゆっくり上がっていく。
疎空間：普通の値と疎な値
定義どおりに計算すると、山 n ごとに n/2 通りの分け方を見るので全体で O(N²) になる。手元の計測（tools/bench.mts）では N を倍にすると 4 倍かかり、N = 400,000 で 65.5 秒だった。この調子で 2^26 まで行くと、単純な外挿で 3 週間ほどかかる。
そこで Winning Ways と Flammenkamp の疎空間（sparse space）を使う。
- 値 v の最下位ビット以外の 1 の個数が奇数なら「普通（common）」、偶数なら「疎（sparse）」と呼ぶ。マスクで書くと m = 0111…10 と v の AND のパリティ。
- このとき 普通 ⊕ 普通 と 疎 ⊕ 疎 は疎、普通 ⊕ 疎 は普通になる（パリティは XOR で足し算になるから）。
- 実際の G(n) はほとんどが普通の値で、疎な値を持つ山は 2^26 までに 1,287 個しかない。
これを使うと山 n の計算は 2 段になる。
- 普通の値の選択肢は、疎な山をちょうど 1 つ含む分け方からしか出ない。だから既知の疎な山 r（1,300 個弱）について G(r) ⊕ G(n − r) に印を付ければ、普通の値の選択肢は全部そろう。印の付かない最小の普通の値を c とする。
- c より小さい疎な値が選択肢に入っていないと、G(n) は c にならない。そこで分け方 a = 1, 2, … を順に見て値に印を付け、c 未満の疎な値が全部出そろったところで止める（G(n) = c）。分け方を見尽くしても出ない疎な値があれば、その最小のものが G(n) で、n は新しい疎な山になる。
2 段目の走査がどこで止まるかは何も仮定していないので、結果は定義どおりの値と同じになる。テストで 20,000 までの全項と、途中で区切って再開した場合を突き合わせている。速さは N を倍にすると 2 倍で、N = 400,000 が 6.8 秒、2^26 が 1,017 秒（Node.js 26、1 スレッド）。
Flammenkamp の表と突き合わせる
Flammenkamp のページ（Sprague-Grundy Values of Grundy's Game）には、2012 年に 2^38 余りまで計算した結果として、次の 3 つの表が載っている。HTML からそのまま抜き出して tools/data/flammenkamp.json に保存し、2^26 までの計算結果と比べた。
| 比べたもの | 出典 | 一致 |
|---|---|---|
| 疎な値を持つ山と、その値 | Flammenkamp の 1287 個のリスト | 1287 / 1287（同じリスト）。最後は G(48,399,022) = 259 |
| 最大値が更新される山（2^26 まで） | Flammenkamp の一覧 / OEIS A180120・A180121 | 75 / 75 と 76 / 76。最後は G(50,666,285) = 280 |
| 疎な値ごとの出現回数と最後の山 | 山 0〜2^35 の頻度表 | 148 / 148 行 |
| G = 0 の山 | OEIS A036685 | 同じ 42 個、最後は 1222 |
| G(0)〜G(200,000) | OEIS A002188 の a-file | 200,001 / 200,001 |
頻度表は 2^35 までのものなので、普通の値の回数は 2^26 の計算とは比べられない。しかし疎な値は 4,840 万より先に 1 つも出てこないので、疎な値の行に限れば 2^26 までの数え上げとぴったり同じになるはずで、実際に 148 行すべて（出現 0 回の値も含む）で回数と最後の位置が一致した。逆に言うと、これで「2^26 から 2^35 の間に疎な山は出ない」という Flammenkamp の結果とも矛盾がない。
最大値の一覧のうち 2^26 を超える次の項は G(475,094,020) = 281 で、OEIS ではその後 Tomas Rokicki の計算で G(36,285,802,857,632) = 310 まで伸びている。
最後の 13 個はなぜ 4,700 万台に固まるのか
疎な山の分布は極端に偏っている。
| 範囲 | 疎な山の数 |
|---|---|
| n ≤ 1,000 | 205 |
| n ≤ 10,000 | 873 |
| n ≤ 100,000 | 1,274（最後は 82,860） |
| 100,000 < n ≤ 2^26 | 13（47,461,861 〜 48,399,022） |
8 万から 4,746 万まで 1 つも出ず、そのあと 100 万の幅に 13 個が固まっている。しかもその 13 個の値は 258〜265 だけ。計算結果を見ると理由が読める。
- 258〜265 は疎な値で、256 以上の値。2 つの値の XOR が 256 以上になるには、どちらかが 256 以上でなければならない（どちらも 256 未満なら XOR も 256 未満）。
- 値が 256 以上の山は、この辺りでやっと現れ始める。G = 256 が初めて出るのは n = 7,250,049、それを超える値が初めて出るのは 47,339,607（257）、47,342,322（262）、47,342,972（263）。
- 山の値（の mex 候補 c）が 258 を超えるようになると、2 段目の走査は「258 を作る分け方」を探さないといけない。作れる分け方は 256 以上の値の山を含むものに限られ、そういう山はまだ少ない。見つからなければ 258 がそのまま G(n) になり、疎な山が生まれる。
実際、計算全体でいちばん長い走査は n = 47,342,435 で起き、分け方 a = 1 から a = 7,250,049 まで見たところで止まった。7,250,049 は値 256 が初めて出る山そのもの。つまりこの山では、必要な疎な値を作れる分け方が「最初の 256 の山を切り出す」ものしかなく、そこに着くまで 725 万通りを見たことになる。256 以上の値の山が増えると疎な値は再び作れるようになり、4,840 万から先は 2^38 まで疎な山が出ない（Flammenkamp の計算）。
走査の長さ
2 段目の走査の長さ（普通の値の山について、何通りの分け方を見たか）は、
- 平均 3,126.5。Flammenkamp のページには「平均して 3130 個の普通の値を確かめる必要があった」とあり、2^38 までの統計欄にも 3129.46 とある。ほぼ同じ量を測っているはず。
- 最大 7,250,049（2^26 まで）。ページの統計欄の最大は 50,657,340 で、範囲が 4,000 倍以上広い。
平均はチェックポイントごとに見ても 3,119〜3,136 の間でほとんど動かず、計算量は N に比例する。
細かい食い違い
ページの履歴欄には「1992 年 1 月までに 80·10^6 まで計算し、それまで知られていた 1264 個に加えて 13 個の新しい疎な値を見つけた」とある。13 個は 100,000 より上の 13 個とぴったり合う。ただ、100,000 以下の疎な山は（n = 0 を含めて）1,274 個で、同じページのリスト自体も 1,274 + 13 = 1,287 になっている。1264 + 13 = 1277 はリストより 10 少なく、どこで数え方が違うのかはページからは分からなかった。
テスト
- 疎空間の計算が定義どおりの O(n²) の計算と 20,000 まで一致し、途中で区切って再開しても同じ
- OEIS A002188 の b-file（20,001 項）と一致
- 100,000 までで、G = 0 の山が A036685、最大値の更新が A180120/A180121、疎な山が Flammenkamp のリストの先頭 1,274 個と一致
- 出現回数の合計と最後の位置のつじつま
- 値の 2 つのクラスが XOR で正しく閉じている（普通 ⊕ 普通 = 疎 など、0〜511 の全組）
- 石 24 個以下の全局面で XOR 規則が値を使わない勝敗探索と一致し、勝ち手が XOR を 0 にする
- 分け方の列挙（等分しない、1 と 2 は分けない）
実装メモ
-
src/grundy.ts: 定義どおりの計算naiveValues、疎空間の掃引Sweep（疎な山・最大値・頻度・最後の位置・走査の長さを記録）、対局用のmoves/winningMove。 -
tools/compute.mts: 2^26 までの掃引。2^21 ごとにruns/compute.jsonを書き直すので、途中で止めてもそこまでの結果が残る。 -
tools/report.mts: Flammenkamp の表・OEIS との比較と、デモの右パネル（src/findings.json）の生成。記事の数字はここから取っている。 -
tools/bench.mts: 定義どおりの計算との速度比較。
まとめ
- Grundy のゲームは、山が何個あっても Grundy 値の XOR で勝敗が決まる。デモでは切れる場所すべてに ✓／✗ を付けた。
- 値を最下位ビット以外のパリティで「普通」と「疎」に分けると、普通の選択肢は疎な山 1,300 個弱を回るだけでそろい、残りは平均 3,100 通りほどの走査で済む。O(N²) が O(N) になり、2^26 まで 17 分。
- Flammenkamp の疎な山 1287 個は位置も値も全部一致し、最大値の一覧、2^35 までの頻度表の疎な値、OEIS の 4 数列も一致した。
- 最後の 13 個の疎な山が 4,746 万〜4,840 万に固まるのは、値 256 以上の山が現れたばかりで、258〜265 を作れる分け方がまだ少ないから。いちばん長い走査は、ちょうど最初の 256 の山で止まった。