1×n Konane（コナネ）— 2002 年の論文の表 749 マスを全部計算し直したら 7 マスが違い、分解予想には書かれていない例外があった

ハワイの石取りゲーム **Konane（コナネ）**を一列（1×n）に限って、組合せゲーム理論の正確な値を出すエンジン付きでブラウザに実装した。黒（Left）と白（Right）が交互に、自分の石で隣の相手の石を飛び越えて向こうの空きマスに着地し、飛び越えた石を取る。同じ向きなら続けて何回でも跳べる。跳べなくなった方の負け。石を選ぶと着地点ごとに勝ち筋か負け筋かを ✓／✗ で表示し、コンピュータと対戦できる。検算の対象は Chan・Tsai の論文 "1×n Konane: A Summary of Results"（More Games of No Chance, 2002）で、8 つの表（15 枚）の 749 マスを全部計算し直した。742 マスは一致し、7 マスが違った。どれも分割をしない計算でも同じ値になった。Table 7 の 2 マスは、論文自身が書いている対称性 S(2i, 2j, 2k) = −S(2k, 2j, 2i) とも両立しない。本文の式は、印刷どおりだと成り立たないものが 4 つあり、表から読み直すと全部成り立った。「2 マス空けた列は和に分解できる」という予想は、論文が挙げた例外 28 件では確かに分解しなかった。ところが論文が挙げていない S(1, 2j··, 2k) の 49 件と S(3, 4··, 2k) の 5 件でも分解しなかった。高速化には、黄金比の重みで「石は列の端から 1 マスより外へは出られない」ことを示す論法（コンウェイの兵隊の 1 次元版）を使い、互いに届かない部分に分けて足している。テスト 16 件。ソルバー内蔵パズル第 96 弾。

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

ルール

本来の Konane は 18×18 などの盤に黒白の石を市松模様に敷きつめ、中央付近の 2 個を取り除いてから始める。この記事で扱うのは、そこから一列だけを切り出した 1×n Konane である。

• 手番の人は自分の石を 1 つ選び、隣にある相手の石を飛び越えて、その向こうの空きマスに着地する。飛び越えた石は取り除く。
• 着地した先の隣にまた相手の石があり、その向こうが空いていれば、同じ向きに続けて跳んでもいい（途中で止めてもいい）。向きは変えられない。
• 跳べなくなった方の負け。

石は 1 回に 2 マスずつしか動かないので、石の色はマスの偶奇で決まったままになる。論文にならって偶数マスを白（Right）、奇数マスを黒（Left）とする。こう決めると、局面は「どのマスに石があるか」だけで表せる。隣り合う 2 つの石はいつも色が違う。

論文の記法 S(k, m, n) は、k 個・m 個・n 個の石がすき間なく並んだ 3 つの塊を、空きマス 1 つずつで区切った列である。左端は白から始める。たとえば S(4, 2, 3) は ○●○●·●○·●○● になる。S(k, m··, n) は 2 つ目と 3 つ目の間だけ空きマスが 2 つの列を表す。

値の計算

各局面の値を、選択肢の値から 1 回ずつ計算する。値は標準形（支配される選択肢を消し、可逆な選択肢を迂回した形）にして番号を振るので、等しいゲームは同じ番号になる。エンジン（src/cgt.ts）は #375 ハッケンブッシュ、#377 クロバー、#378 トップリング・ドミノと共通である。

対称性も使う。

• 列を 1 マスずらすと全部の石の色が入れ替わるので、値は符号が反転する。
• 列を左右反転しても、−x の偶奇は x と同じなので色は変わらない。値も変わらない。

この 2 つで、メモの鍵は代表 1 つにまとめられる。

黄金比で「届かない部分」に分ける

列全体をそのまま探索すると、列が 30 マスを超えたあたりから局面数が急に増えて重くなった。そこで、互いに絶対に干渉しない部分に列を分け、値を足すようにした。干渉しないことを保証するのに、コンウェイの兵隊（Conway's soldiers）の 1 次元版の論法を使う。

マス x にある石に重み φ^x を付ける（φ は黄金比、φ² = φ + 1）。

• 右向きのジャンプ（x−2 の石が x−1 を跳んで x へ）では、重みは φ^(x−2) + φ^(x−1) から φ^x に変わる。この 2 つは等しいので、合計は変わらない。
• 左向きのジャンプでは合計が減る。
• 一番右の石を b とすると、有限の列の重みの合計は φ^b(1 + φ^−1 + φ^−2 + …) = φ^(b+2) より真に小さい。

マス b + 2 に石が 1 つ置かれた時点で、合計は φ^(b+2) 以上になってしまう。だから、どちらがどう跳んでも、石は列の端から 1 マスより外に出られない。この議論に色は関係しない（両方の手番を合わせれば、物理的に可能なジャンプは全部どちらかの手になる）。

あとは、塊ごとに「端から 1 マス外まで実際に届くか」（advancesRight）を探索で判定すればよい。隣り合う部分の届く範囲が 2 マス以上離れていれば、跳ぶことも、跳ばれることも、着地点をふさぐこともないので、列はそれらの和になる。空きマスが 3 つあれば必ず分かれる。1 つか 2 つの場合は、分かれることも分かれないこともある。デモでは、分かれた部分を点線の枠で囲み、部分ごとの値を表示している。

この分割が正しいことは、13 マス以下の全 8,192 列で、分割しない計算（valueWhole）と値が 1 つも違わないことで確かめた（そのうち 5,902 列は分割される）。テストでは、10 マス以下の全列で到達できる局面を全部たどり、「端から 1 マス以内」が実際に守られていること、それが advancesRight の答えと一致することも確認している。勝敗は、値を使わない素朴な勝ち負け探索とも全列で一致した。

この結果、論文の 15 枚の表の 749 マスは約 40 秒で全部埋まった。

表 749 マスの照合

生成した表を論文と同じ並び（左端が k、上端が n、左上が m）で出力し、PDF を画像にしたページと 1 マスずつ目で突き合わせた。742 マスが一致した。Table 2 の「1↑3∗」は、CGSuite と同じく 3·↑ と読めば 1 + 3·↑ + ∗ で一致する。

違ったのは次の 7 マスである。

マス	論文	計算	場所
S(5, 6, 6)	17/4	13/4	Table 2（m = 6）
S(5, 6, 8)	9/2	17/4	Table 2（m = 6）
S(5, 6, 10)	5	9/2	Table 2（m = 6）
S(10, 2, 14)	1/64	−1/64	Table 7（m = 2）
S(14, 2, 10)	1/16	1/64	Table 7（m = 2）
S(12, 4, 14)	−1/16	−1/64	Table 8（m = 4）
S(14, 4, 12)	1/16	1/64	Table 8（m = 4）

• Table 2 の 5 行目は、正しい列が 5/4, 9/4, 13/4, 17/4, 9/2, 5, 5∗ のところ、論文では 5/4, 9/4, 17/4, 9/2, 5, 5, 5∗ になっている。13/4 が抜けて 1 マスずつ左に詰まり、5 が 2 回出ている。
• Table 7 は、S(10, 2, 14) = 1/64 と S(14, 2, 10) = 1/16 の組になっている。論文はこの節で S(2i, 2j, 2k) = −S(2k, 2j, 2i) と書いているので、この 2 つは符号違いの同じ大きさでなければならない。計算では −1/64 と 1/64 で、この対称性を満たす。
• Table 8 の組は論文の中で対称性を満たしてはいるが、大きさが 1/16 ではなく 1/64 だった。

7 マスはすべて、分割をしない全体探索（tools/disputes.mts）でも同じ値になった。分割の論法に間違いがあって出た差ではない。

本文の式と予想

論文の本文の式・予想はすべて src/chan-tsai.ts にコードとして書き、各部 14 個以下のすべての引数で検査した。

主張	成立
Ernst: S(2k+1) = k, S(2k) = k·∗	14 / 14
Scott: S(2j+1, 2k+1) = j + k	49 / 49
Scott: S(2j+1, 2k)（j = 0 で k·↑ + k·∗ など）	49 / 49
Scott: S(2j, 2k), j ≤ k	28 / 28
奇奇奇: S(2i+1, 2j+1, 2k+1) = i + j + k	343 / 343
奇偶偶の予想	137 / 137

ここまでは全部成り立った。成り立たなかったのは次の 4 つで、どれも表を見ると直し方がわかる。

偶奇偶（Table 4）: 本文は「i, k ≥ j なら S(2i, 2j+1, 2k) = (j+1) + (k+i)·∗」としているが、これは 188 件中 91 件しか成り立たない。たとえば S(2, 3, 2) は 2 ではなく 0 になる。表の枠線のとおり i, k ≥ j + 2 に条件を絞ると、91 / 91 で成り立つ。

奇偶奇（Table 5・6）: 本文は「i ≥ k を仮定する」と書いたあと、2k+1 = 2i+3 から 2i+1+j の範囲について −2^(−k−1) を与えている。仮定と範囲で k と i の大小が逆で、添字が崩れている。印刷どおりに読むと 196 件中 61 件しか合わない。表から d = k − i として読み直すと、次の式で 196 / 196 になる。

• d = 0 なら 0（ただし S(1, 2, 1) = ∗2）
• 1 ≤ d ≤ j なら −2^(d−j−1)
• d > j なら −(d − j)

偶偶偶（Table 7・8）: i < j < k の場合の (j − k) + k·∗ は、表では一貫して (i − j) + k·∗ になっている（S(2, 8, 10) は −1∗ ではなく −3∗）。k = j の場合の (j − k − 1) も、表では i − j + 1 である。印刷どおりだと 2j ≡ 2 (mod 4) で 68 件中 41 件、2j ≡ 0 (mod 4) で 35 件中 25 件しか成り立たない。読み直すと 62 / 62 と 45 / 45 になった。

偶偶偶の予想: 「i, k > j なら S(2i, 2j, 2k) = S(2(i−j), 2, 2(k−j))」（4 の倍数側は 4）は、外側の長さを 2j 減らしている。だが表と合うのは 2j − 2（4 の倍数側は 2j − 4）減らした場合だった。たとえば S(8, 6, 14) = −1/4∗ は S(2, 2, 8) = −1/2 ではなく、S(4, 2, 10) = −1/4∗ に等しい。印刷どおりだと 20 件中 16 件と 10 件中 4 件、ずらし幅を直すと 55 / 55 になった。

読み直した式は表を見て合わせたものなので、論文の範囲（各部 14 まで）を超えて成り立つかは、ここでは主張しない。

分解予想の例外

論文の中心にあるのは、2 つ目と 3 つ目の塊の間を 2 マス空けた列 S(k, m··, n) についての予想である。

S(k, m··, n) は S(k, m) + S(n) に分解する。ただし S(2j, 2j··, 2k)（j は奇数）を除く。

黄金比の論法からわかるとおり、空きが 3 マスなら必ず分解する。2 マスでは、両側の塊が長さ 2 以上なら届く範囲が重なるので、構造としては分けられない。それでも値が足し算になるかどうかを問うのがこの予想である。3 つ目の塊は、置かれたマスの色のまま S(n) か −S(n) として足した。

	件数	分解する
例外族 S(2j, 2j··, 2k), j 奇数	28	0（論文どおり全部分解しない）
それ以外	2,716	2,662

論文が挙げていない例外が 54 件あった。

• S(1, 2j··, 2k) は 49 件すべて分解しない。しかも値はどれも、空きを 1 マスに詰めた S(1, 2j + 2k) と同じ（= (j+k)·↑ + (j+k)·∗）だった。たとえば S(1, 2··, 2) は ↑∗ + ∗ = ↑ ではなく ⇑ になる。左端の白 1 個が、2 マスの空きを越えて右の塊まで ↑ を積み上げる。
• S(3, 4··, 2k)（2k ≥ 6）の 5 件も分解しない。たとえば S(3, 4··, 6) は 1/4∗ ではなく 1/8 になる。

論文自身が「ほかにも例外がある可能性はまだある」と書いており、それが具体的に見つかったことになる。

実装メモ

• src/konane.ts: 局面は「最初の石のマスの偶奇 + 0/1 の文字列」。options は両端に 1 マスずつ空きを足した配列で手を生成する（黄金比の論法から、それより外には着地しない）。
• src/tables.ts と tools/sweep.mts: 論文の 15 枚の表のレイアウト。小さい列から順に計算し、1 マス終わるたびに runs/tables.json を書く。
• tools/checks.mts: 主張ごとに引数を小さい順に回す。主張が何も言わない引数は「対象外」として数える。
• tools/report.mts: runs/*.json から、デモの右パネル（src/findings.json）と数字の要約（runs/summary.json）を作る。この記事の数字はそこから取っている。

まとめ

• 1×n Konane の石の色はマスの偶奇で決まるので、局面は 0/1 の列で表せる。ずらすと値の符号が反転し、反転させても値は変わらない。
• 黄金比の重みで、石は列の端から 1 マスより外に出られない。だから届かない部分に分けて値を足せる。13 マス以下の全 8,192 列で分割なしの計算と一致した。
• Chan・Tsai の表 749 マスのうち 742 マスは一致した。違った 7 マスのうち 3 マスは Table 2 の 1 行のずれ、2 マスは論文自身の対称性と矛盾する組だった。
• 本文の式 4 つは印刷どおりでは成り立たず、表から読み直すと全部成り立った。分解予想には、S(1, 2j··, 2k) と S(3, 4··, 2k) という書かれていない例外があった。