八進ゲーム（Kayles ほか）— Guy–Smith の周期定理で 3 桁以下の全 167 ゲームを Flammenkamp の表と突き合わせ、後年の「解決済み」13 本の周期も再現した

Posted at 2026-10-14

ケイレス（Kayles）、**ドーソンのケイレス（Dawson's Kayles）をはじめとする八進ゲーム（octal games）**をブラウザに実装した。ピンの列から隣り合うピンをまとめて倒し、倒せなくなった方の負け。どう倒してよいかは 0.77 のような八進の符号 1 つで決まる。コンピュータは Sprague–Grundy 理論で完全にプレイし、ヒントを付けると勝ち手が一覧と盤面の両方に出る。裏側では Achim Flammenkamp の八進ゲームの表を一から計算し直した。3 桁以下の符号 1,024 個は 167 個の別々のゲームにまとまり、167 個全部が Flammenkamp の表と一致（周期・前周期・最大値・後手必勝局面の数・先頭 40 項）。周期は Guy–Smith の周期定理で有限個の値から証明する。32,768 項で証明できた周期は 82 個で、これは表に載っている 74 個に、短い一覧では空欄になっている 8 個を足したもの。その後に解かれた「構造の分かっているゲーム」20 個のうち、必要な項数が 653,570 以下の 13 個を走らせ、13 個全部で公表されている周期と前周期を再現した（最大は 0.16 の周期 149,459・前周期 105,351）。符号 1,024 個→167 ゲームの対応表（compendium）は 1,016 個が添字のずらしまで込みで完全一致し、残り 8 個は先頭 1〜5 項だけが食い違っていた。テスト 12 件。ソルバー内蔵パズル第 85 弾。

デモ: https://sen.ltd/portfolio/octal-games/
リポジトリ: https://github.com/sen-ltd/octal-games

ルール

ピンが横一列に並んでいる（列は何本あってもよい）。2 人が交互に、どれか 1 列から隣り合ったピンのかたまりを倒す。倒せなくなった方の負け（normal play）。

ケイレス（Dudeney と Loyd が 1900 年代初めにパズルとして紹介）: 1 本か、隣り合う 2 本を倒す。どこから倒してもよいので、列の真ん中を倒すと列が 2 つに分かれる。
ドーソンのケイレス: いつも隣り合う 2 本ちょうどを倒す。

列が分かれると、それぞれの列は独立したゲームになり、局面全体は「独立なゲームの和」になる。ここで効くのが Sprague–Grundy の定理だ。

八進の符号

Guy と Smith（1956）は、この種のゲームを 1 つの数で書き表した。符号は d₀.d₁d₂d₃… で、d_k は「1 列から k 本取ったあと何が残ってよいか」を 3 ビットで表す。

ビット	意味
1	列が丸ごと消えてよい（列の長さがちょうど k）
2	1 列が残ってよい（端から取る）
4	2 列が残ってよい（真ん中から取る）

ケイレスは 1 本でも 2 本でも「消える／1 列残る／2 列残る」が全部許されるので d₁ = d₂ = 1+2+4 = 7、つまり 0.77。ドーソンのケイレスは 2 本ちょうどなので 0.07。各桁が 0〜7 なので「八進」と呼ぶ。先頭の d₀ = 4 は「何も取らずに列を 2 つに割ってよい」という意味で、4.344 のようなゲームになる（デモでは、ピンの間の点線をクリックすると割れる）。

src/octal.ts の parseOctal が符号を桁の配列にし、legalMoves が「どの列の、どこから、何本」の手を全部並べる。

Sprague–Grundy 値

不偏ゲーム（両者の打てる手が同じゲーム）の局面には Grundy 値が 1 つ決まり、局面は大きさがその値の Nim の山と同じに振る舞う。長さ n の列の値 G(n) は

1 列 a が残る手の値は G(a)、2 列 a, b が残る手の値は G(a) XOR G(b)
G(n) = それらの値に含まれない最小の非負整数（mex）

で、列がいくつもある局面の値は各列の値の XOR（nim 和）。nim 和が 0 なら手番側の負け、0 でなければ nim 和を 0 にする手が勝ち手になる。デモの右の数字 G=… が各列の値で、ステータス行が nim 和。

for (let h = 0; h < n; h++) {
  for (let k = 0; k <= t && k <= h; k++) {
    const d = digits[k];
    if (d === 0) continue;
    const r = h - k;
    if (d & 1 && r === 0) seen[0] = h;
    if (d & 2 && r >= 1) seen[g[r]] = h;
    if (d & 4 && r >= 2) {
      for (let a = 1, b = r - 1; a <= b; a++, b--) seen[g[a] ^ g[b]] = h;
    }
  }
  let v = 0;
  while (seen[v] === h) v++;
  g[h] = v;
}

seen を毎回クリアせず「何番目の n で印を付けたか」を入れておくのが唯一の工夫で、あとは素直な O(n²) だ。真ん中から取る手（ビット 4）の分け方を全部見るので、n 項計算するのに n²/4 回くらい XOR する。

コンピュータの手は「nim 和が 0 になる手があればそのどれか、なければ適当な手」。理論が正しいことはテストで確かめている。0.77・0.07・0.137・4.344・0.6 の 5 ゲームで、7 本以下の列 3 つまでの全 119 局面について、Grundy 値を使わない素朴なゲーム木探索の勝敗と「nim 和 ≠ 0」が一致する。

周期と、その証明

ケイレスの値を並べるとこうなる。

n:    0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
G(n): 0 1 2 3 1 4 3 2 1 4 2  6  4  1 ...

規則は見えないが、n = 71 から先は周期 12 になる（n = 72 からの 12 個で書くと 4 1 2 8 1 4 7 2 1 8 2 7。最後の例外は n = 70 で、周期どおりなら 2 のところが 6）。こういう「前周期 v のあと周期 p」の形を最終的に周期的という。有限桁の八進ゲームで決着がついたものは、今のところ全部この形になっている。

周期は有限個の値から証明できる。Guy–Smith の周期定理:

取る本数の最大を t とする。G(n + p) = G(n) が v ≤ n < 2v + p + t のすべての n で成り立てば、n ≥ v のすべてで成り立つ。

理由は、長い列 n + p から 2 列 a, c（a ≤ c）を残す手では、長い方の c が少なくとも (n + p − t)/2 本あるからだ。n が十分大きければ c − p もまだ前周期より先にあり、帰納法の仮定で G(c − p) = G(c)。だから n + p の手と n の手が 1 対 1 に対応して、値の集合が同じになる。

1 つだけ細かい点がある。v = 0 のときに c − p = 0 になると「2 列残る手」が「1 列残る手」に化けてしまうので、実装では v の代わりに max(v, 1) を使った。必要な項数は

2·max(v, 1) + 2p + t

で、ケイレス（v = 71, p = 12, t = 2）なら 168 項。provePeriod は p = 1, 2, … の順に、計算した範囲の後ろから「G(n + p) ≠ G(n) になる最後の n」を探して v を決め、上の式が計算した項数に収まった最初の p を返す。小さい p から試すので、返る周期は最小周期になる（最小周期の倍数が先に証明されることはない）。

Flammenkamp の表と突き合わせる

Achim Flammenkamp（ビーレフェルト大学）は 3 桁以下の八進ゲームを網羅した表を公開している。

compendium: 3 桁以下の符号 1,024 個（0.abc と 4.abc）を、それぞれ「同じゲーム」である代表（standard form）に対応させた表。
easy_octal: 代表 167 個の一覧。周期と前周期の和が 250 以下のもの（74 個）は周期・前周期・最大値・負け局面の数を、残り 93 個は「最大値 ≥ …」と先頭 40 項を載せている。
known structure: 93 個のうち、その後の計算で周期が分かった 20 個（1956 年の 0.45 から 2012 年の 4.xxx まで）。

npm run literature がこれらをダウンロードして src/literature.json に事実だけを抜き出し、npm run table が計算して src/results.json にまとめる。計算は Node 26、12 コアの Mac mini で 1 ゲーム 1 プロセス。

1. 代表 167 個: 全部一致

167 個それぞれ 32,768 項計算した（合計 331 秒）。

	個数
Flammenkamp が周期を載せている 74 個: 周期・前周期・最大値・負け局面の数・先頭 40 項が全部一致	74
そのほか、32,768 項で周期が証明できたもの	8
周期が見つからない（32,768 項では未決着）	85
先頭 40 項まで含めて表と矛盾しないもの	167 / 167

「負け局面の数」は、周期の中に 0 があれば「1 周期あたりの 0 の数」（表では *5 のように星付き）、なければ前周期の中の 0 の数。ドーソンのケイレス 0.07 は周期 34、前周期 53、最大値 9、1 周期に負け局面 5 個で、表の p=34 v= 53 max = 9 lost = *5 とそのまま一致する。

追加の 8 個は 0.45、0.055、0.156、0.165、0.356、0.644、4.344、4.364。一覧で空欄なのは「周期と前周期の和が 250 を超えると書かない」という表の決まりのせいで、どれも known structure 側に正解が載っている。8 個とも周期・前周期がそれと一致した。

2. known structure の 20 個: 走らせた 13 個が全部一致

必要な項数 2v + 2p + t を表の値から計算し、ちょうどそれだけ（+16）計算した。

ゲーム	決着	周期	前周期	必要な項数	秒
0.45	1956	20	498	1,038	0.01
0.055	1976	148	259	817	0.01
4.344	2012	51	998	2,101	0.03
0.644	1976	442	3,256	7,399	0.15
0.156	1967	349	3,479	7,659	0.12
0.165	1976	1,550	5,181	13,465	0.32
0.356	1976	142	7,315	14,917	0.42
4.364	2012	62	11,687	23,501	1.71
0.127	1988	4	46,578	93,167	8.08
4.064	2012	16,132	94,272	220,811	158.06
0.16	1988	149,459	105,351	509,622	254.87
4.406	2012	44	294,097	588,285	895.33
0.56	1988	144	326,640	653,570	751.64

13 個全部で、こちらの provePeriod が出した最小周期と前周期が表と一致した。周期の短さと前周期の長さが噛み合っていないのが面白い。0.127 は周期たった 4 なのに、そこに落ち着くまで 46,578 項かかる。0.56 は周期 144 で前周期が 32 万。逆に 0.16 は周期そのものが 14 万 9 千ある。

最大値と負け局面の数も表の別の列と照合できた。0.127 の負け局面 1,190 個、0.16 の 7 個、4.064 の最大値 111、0.644 の最大値 64 はどれも表と同じ。

残り 7 個（0.376、0.354、0.054、0.104、0.454、0.106、4.404）は前周期が 227 万〜4,654 億で、O(n²) の素直な計算では届かない。0.106 は周期 3,282 億・前周期 4,654 億で、Flammenkamp たちは「まれな値（sparse values）」だけを追う手法でこれを出している。

3. compendium の 1,024 個: 1,016 個が完全一致、8 個が先頭だけずれる

符号が違っても同じゲームになることがある。たとえば 0.07 と 0.137（ドーソンのチェス）は、値の列が 1 つずれるだけで同じ。

0.07 : 0011203110332240522330113021104527401120
0.137:  011203110332240522330113021104527401120

compendium の対応が正しいかを、1,024 個全部について 2,048 項で確かめた。「同じ」の判定は、添字を ±4 までずらして（ずらした分の先頭は 0 で埋める）全項が一致すること。

1,016 個: 対応先と添字のずらしまで込みで完全に一致（ずれ 0 が 862 個、+1 が 58、−1 が 92、+2 が 3、+3 が 1）。
8 個: どのずらしでも完全には一致しない。0.102、0.112、0.121、0.123、0.131、0.132、0.312、0.331。

8 個を調べると、どれも先頭 1〜5 項だけが違い、その先は 167 個のどれかと同じ列だった。たとえば 0.131 は

0.131: 0112 0011 0011 0011 ...
0.02 : 0001 1001 1001 1001 ...

で、5 項目以降は 0.02 を 1 つずらしたものと一致する。さらにこのうち 5 個（0.121、0.123、0.132、0.312、0.331）は、compendium では「自分自身が代表（---）」と書かれているのに、代表 167 個の一覧には載っていない。残り 3 個（0.102、0.112、0.131）は compendium の対応先と先頭だけ違う。

先頭の数項が違えば局面の勝敗も変わるので、厳密には別のゲームだ。ただ周期・前周期の議論で興味があるのは「最終的にどう振る舞うか」なので、表としては先頭の違いを無視して同じ組にまとめたのだと思う。「同じ」の定義をはっきり書いた方がよい、という程度の指摘になる。

対戦画面

game で既製のゲーム（ケイレス、ドーソンのケイレス、ドーソンのチェス 0.137、Officers 0.6、0.45、0.156、4.344）を選ぶか、code に符号を直接入れる（4.xxx も可）。
rows で列の長さ（13 8 5 のように複数）、you move で先手か後手か。
ピンを 2 回クリックすると、その間のかたまりを倒す（1 本だけなら同じピンを 2 回、ケイレスのように 1 本取りしかない符号なら 1 回）。
右上はそのゲームの G(0), G(1), … を色付きで並べたもの。周期が 40 以下なら 1 行 = 1 周期で折り返すので、周期部分は縦に同じ色がそろい、前周期（枠付き）だけが乱れて見える。周期はブラウザ内の 8,192 項で証明し、足りないものは事前計算の結果を出す。
右下は代表 167 個の一覧で、行をクリックするとそのゲームで対戦できる。

テスト

npm test で 12 件。

符号の解釈（.6 → 0.6、末尾の 0 を落とす、2.5 や 0.8 は拒否）。
ケイレス: 周期 12・前周期 71 が 168 項で証明される。160 項では何も証明されない。Officers 0.6 は 3,000 項で何も証明されない。
0.137 の値が 0.07 を 1 つずらしたものと 600 項一致。
Flammenkamp が周期を載せている 74 個を、テストの中で 1,200 項から計算し直して周期・前周期・最大値・負け局面の数・先頭 40 項が一致。
5 ゲーム × 119 局面で nim 和と素朴なゲーム木探索の勝敗が一致。勝ち手は nim 和 ≠ 0 のときだけ出て、指すと必ず nim 和 0 になる。
src/results.json: 167 個全部一致、走らせた known structure 全部一致、compendium は 1,016 個完全一致と上の 8 個。

まとめ

八進ゲームは符号 1 つで決まり、Grundy 値は mex と XOR だけで計算できる。完全なプレイヤーは「nim 和を 0 にする」だけ。
周期は 2·max(v,1) + 2p + t 項で証明できる。ケイレスなら 168 項。
3 桁以下の代表 167 個が Flammenkamp の表と全部一致し、32,768 項で 82 個の周期を証明した。
その後に解かれた 20 個のうち 13 個（必要項数 653,570 以下）を走らせ、13 個とも公表値を再現した。最大は 0.16 の周期 149,459。
compendium は 1,016 / 1,024 が完全一致。残り 8 個は先頭 1〜5 項だけが違う、最終的には同じ振る舞いのゲームだった。

参考文献:

Achim Flammenkamp, "Sprague-Grundy Values of Octal-Games", http://wwwhomes.uni-bielefeld.de/achim/octal.html（2026 年 10 月 15 日参照）
R. K. Guy, C. A. B. Smith, "The G-values of various games", Proc. Cambridge Philos. Soc. 52, pp. 514–526, 1956
E. R. Berlekamp, J. H. Conway, R. K. Guy, "Winning Ways for Your Mathematical Plays", 第 4 章
A. Gangolli, T. Plambeck, "A Note on Periodicity in Some Octal Games", International Journal of Game Theory 18, 1989
H. E. Dudeney, "The Canterbury Puzzles", 1907（Kayles の原型）

デモ: https://sen.ltd/portfolio/octal-games/
リポジトリ: https://github.com/sen-ltd/octal-games

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up