Turning Corners（長方形の 4 隅を裏返す）— コインの値が nim 積になることを、mex の定義から 104 万枚・全局面 1 億通りで確かめた

Turning Corners をブラウザに実装した。盤にコインが並び、表（金色）と裏がある。1 手で表のコイン (a, b) と、その左上のマス (a′, b′) を選び、長方形の 4 隅を裏返す。(a, b) は必ず表 → 裏になり、ほかの 3 枚はどちら向きでもよい。動かせなくなった方の負け。Winning Ways 14 章のコイン裏返しゲームの一つで、マス (a, b) のコインの値は nim 積 a ⊗ b、局面の値は表のコインの値の XOR になる。コインを選ぶと反対側の隅ごとに勝ち筋 ✓／負け筋 ✗ が出て、コンピュータと対戦できる。この「a ⊗ b になる」を、理論を信じずに 3 段階で確かめた。(1) 1 枚のコインの値を mex の定義どおりに 1023 × 1023 = 1,046,529 枚計算し、Fermat 2 冪を使う速い掛け算と全部一致（定義どおりだと 18 分、速い方は 2.3 秒）。(2) XOR 規則すら仮定せず、5 × 5 盤の 2^25 = 33,554,432 局面すべてを含む 10 種類の盤、計 1 億 906 万局面の値を mex で直接求めて、表のコインの値の XOR と全部一致。(3) 2 つのコインゲームの積の値は g(x) ⊗ h(y) になるという Tartan 定理を、Nim・Ruler・Mock Turtles の 6 通りの積で確かめた。おまけに、最大 7 枚まで裏返せる Mogul の 24 枚盤の負け局面 4,096 個は、ゲームを使わずに作った貪欲な符号（lexicode）と一致し、重み分布 1, 759, 2576, 759, 1 の 拡張 Golay 符号だった。テスト 12 件。ソルバー内蔵パズル第 99 弾。

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

ルール

• n × n の盤にコインがあり、表と裏がある。行と列は 1 から数える。
• 手番の人は表のコイン (a, b) を 1 枚選び、その左上のマス (a′, b′)（a′ < a, b′ < b）を選ぶ。長方形の 4 隅 (a, b), (a′, b), (a, b′), (a′, b′) を裏返す。
• (a, b) は表 → 裏になる。ほかの 3 枚は表でも裏でもよく、ただ向きが変わる。
• 盤の外側に「0 行目」「0 列目」の縁があり、そこを角に選んでもよい。縁にはコインがないので、そのときは 2 枚（同じ行か列の 2 枚）や 1 枚（(a, b) だけ）を裏返すことになる。
• 全部裏になって動かせなくなった方の負け。

選んだコインが必ず表 → 裏になり、それが右下の角なので、行優先で数えた「表の位置の二進数」は毎手減る。だからゲームは必ず終わる。

デモでは表のコインをクリックすると、左上のマスと縁に ✓（そこを角にすると XOR が 0 になる＝勝ち筋）と ✗ が付く。マウスを載せると裏返る 4 隅を点線の長方形で示す。コンピュータは勝ち筋があればそれを指し、なければいちばん値の小さい表のコインを 1 枚だけ裏返して粘る。

コイン 1 枚の値が nim 積になる

コイン裏返しゲームには便利な性質がある。裏のコインを表にするのは、同じ場所に表のコインをもう 1 枚足すのと同じで、同じゲーム 2 つの和は 0（後手必勝）になるから打ち消し合う。だから局面は「表のコイン 1 枚ずつの局面」の和で、値はそれぞれの値の XOR になる。

すると、(a, b) に表が 1 枚だけある局面の値 v(a, b) は、1 手で行ける局面の値の mex で

v(a, b) = mex { v(a′, b) ⊕ v(a, b′) ⊕ v(a′, b′) : 0 ≤ a′ < a, 0 ≤ b′ < b }
v(0, ·) = v(·, 0) = 0

になる。これは Conway が On Numbers and Games で与えた nim 積の定義そのものだ。nim 和（XOR）と nim 積で、0〜2^(2^k) − 1 の数は 4, 16, 256, 65536, … 個の元を持つ体になる。

⊗	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7
2	2	3	1	8	10	11	9
3	3	1	2	12	15	13	14
4	4	8	12	6	2	14	10

2 ⊗ 2 = 3、4 ⊗ 4 = 6、2 ⊗ 4 = 8。デモの「values」にチェックを入れると、各コインにこの値が書かれる。

速い掛け算

定義どおりに mex を取ると (a, b) 1 マスに a·b 通り、n × n 全体で約 n⁴/4 回の XOR がかかる。実際に使うのは Fermat 2 冪 F = 2^(2^k)（2, 4, 16, 256, 65536, …）の性質だ。

• x < F なら F ⊗ x = F · x（普通の掛け算）
• F ⊗ F = 3F/2（= F ⊕ F/2）

a = a₁·F ⊕ a₀、b = b₁·F ⊕ b₀ と上下半分に分けると

a ⊗ b = ((a₁⊕a₀)⊗(b₁⊕b₀) ⊕ a₀⊗b₀) · F  ⊕  (a₀⊗b₀ ⊕ (a₁⊗b₁)⊗(F/2))

で、半分の大きさの積 3 回（と F/2 を掛ける 1 回）に落ちる。Karatsuba と同じ形だ。逆数は q 元体で x^(q−2)、平方根は 2 乗が Frobenius 写像なので x^(q/2) で求まる。デモの計算機で 2^32 未満の数の積・逆数・平方根を出せる。

function mulLevel(a: number, b: number, half: number): number {
  if (a < 2 || b < 2) return a * b;
  const F = 2 ** half;
  const a1 = Math.floor(a / F), a0 = a % F;
  const b1 = Math.floor(b / F), b0 = b % F;
  const h = half / 2;
  if (a1 === 0 && b1 === 0) return mulLevel(a0, b0, h);
  const p = mulLevel(a0, b0, h);
  const q = mulLevel(a1, b1, h);
  const s = mulLevel(a1 ^ a0, b1 ^ b0, h);
  const lo = p ^ (h >= 1 ? mulLevel(q, F / 2, h) : q);
  return (s ^ p) * F + lo;
}

2^31 以上の値に << や ^ を使うと符号付き 32 ビットに化けるので、上位半分は * F と Math.floor(a / F) で扱い、XOR の結果は >>> 0 で戻している。

確かめ方 1：mex の定義どおりに 104 万枚

cornersByMex(n) は上の mex の式をそのまま 1 ≤ a, b < n で計算する。印付けの配列にスタンプ（何マス目の印か）を書いて、毎回クリアしないで済ませている。

範囲	コインの枚数	mex（定義）	速い掛け算	不一致
1..511 × 1..511	261,121	85.8 秒	0.34 秒	0
1..1023 × 1..1023	1,046,529	1,082.9 秒	2.3 秒	0

（Node.js 26、1 スレッド。511 の方は他の計算と同時に、1023 の方は 511 の計算と並行して走らせた。）

OEIS A051775（nim 積の表を反対角線順に並べたもの、b-file 1,891 項 = 反対角線 0〜60）と A051917（1〜255 の nim 逆数）も全部一致した。

1 つ目に気づくのは、64 × 64 の表は閉じていないこと。0〜63 どうしの積は 255 まで出る（4 ⊗ 16 = 64、5 ⊗ 51 = 255 など）。体になるのは 2^(2^k) の区切りだけで、デモの表も 16 × 16 と 256 × 256 は「体」、64 × 64 は「次の体にはみ出す」と表示している。511 までの積は 65,535（2^16 体のいちばん上）まで届いた。

確かめ方 2：XOR 規則も仮定しない

上の mex は「局面の値は表のコインの XOR」を前提にしている。そこで、前提を使わずに全局面の値を mex で直接求める fullPosition も書いた。局面は k 枚のコインの表裏の 2^k 通りで、手は「最上位の表のビットを下げる XOR マスク」だから、局面の番号を昇順に 1 回なめるだけで全部の値が決まる。

for (let s = 1; s < N; s++) {
  stamp++;
  let rest = s;
  while (rest) {                       // 表のコインそれぞれについて
    const low = rest & -rest;
    const i = 31 - Math.clz32(low);
    rest ^= low;
    for (const m of masks[i]) seen[gv[s ^ m]] = stamp;   // 手 m の行き先の値
  }
  let m = 0;
  while (seen[m] === stamp) m++;
  gv[s] = m;
}

ゲーム	盤	局面数	値 0 の局面	不一致	時間
Turning Corners	3 × 8	16,777,216	1,048,576	0	15.0 秒
Turning Corners	4 × 6	16,777,216	1,048,576	0	53.1 秒
Turning Corners	5 × 5	33,554,432	2,097,152	0	108.6 秒
Rugs（Ruler × Ruler）	5 × 5	33,554,432	2,097,152	0	31.1 秒
Ruler	22 枚	4,194,304	131,072	0	4.1 秒
Mock Turtles	20 枚	1,048,576	16,384	0	3.3 秒
Mogul	14 枚	16,384	8	0	0.4 秒
Mock Turtles × Mock Turtles	4 × 5	1,048,576	65,536	0	1.2 秒
Ruler × Mock Turtles	4 × 5	1,048,576	65,536	0	0.9 秒
Twins × Mock Turtles	5 × 4	1,048,576	65,536	0	0.7 秒

計 109,068,288 局面で、定義どおりの値と「表のコインの値の XOR」が全部一致した。値 0 の局面数がきれいな 2 冪になるのも XOR 規則の帰結で、局面 → 値は GF(2) 上の線形写像だから、負け局面はその核で 2^(k − 階数) 個ある。5 × 5 の Turning Corners は 25 枚の値 a ⊗ b（a, b ≤ 5）が 0〜15 の 4 ビットを張るので 2^25 / 16 = 2,097,152。

テストではさらに、値を一切使わない素朴な勝ち負け探索（game.ts の手の生成をそのまま使うメモ化再帰）で 3 × 3 と 2 × 5 の全局面を解き、「値が 0 ⇔ 手番の負け」と一致することを見ている。デモの ✓／✗ を出しているのと同じコードの検算だ。

確かめ方 3：Tartan 定理

Turning Corners は 1 次元のゲームの「積」になっている。1 次元の Twins（ちょうど 2 枚裏返す。0 番のコインに値がないので Nim と同じで、コイン x の値は x）を 2 つ掛けると、横の手 {a′, a} と縦の手 {b′, b} の直積 = 長方形の 4 隅を裏返すゲームになる。

一般に 1 次元のコイン裏返しゲーム G, H の積 G × H は、G の手 A（裏返すコインの集合）と H の手 B を 1 つずつ選び、A × B のコインを全部裏返すゲーム。Tartan 定理は、その (x, y) のコインの値が g(x) ⊗ h(y) になると言う。nim 積が出てくるのは Turning Corners だけではない。

1 次元のゲームは 3 つ使った。

ゲーム	手	コイン x の値	確認
Twins	2 枚（x と左の 1 枚）	x	1,024 枚
Ruler	x で終わる連続した何枚でも	x を割る最大の 2 冪	OEIS A006519 と 1,024 枚一致
Mock Turtles	3 枚まで	悪数（1 の個数が奇数の数）1, 2, 4, 7, 8, 11, …	OEIS A000069 と 513 枚一致

1 次元の値を OEIS と比べたとき、最初は Ruler が 1,024 枚中 1,023 枚食い違った。手（裏返す集合）を「いちばん上のコインを先頭に置いた配列」で表し、mex では先頭以外の XOR を取る約束にしていたのに、Ruler だけ連続区間を左端から並べていたためで、値が 1, 1, 2, 1, 4, … と 1 つずれていた。積の mex（productValues）は集合の全部を XOR するので並び順に影響されず、壊れていたのは 1 次元の側だけだった。

この 3 つの 6 通りの積（Twins × Twins, Twins × Ruler, Twins × Mock Turtles, Ruler × Ruler, Ruler × Mock Turtles, Mock Turtles × Mock Turtles）について、積のゲームの 1 枚の値を手を全部列挙する mex で 32 × 32 まで求め、g(x) ⊗ h(y) と比べた。計 6,017 枚で不一致 0。Ruler × Ruler（Winning Ways の "Rugs"）は値が 2 冪どうしの nim 積なので 128 までしか出ず、Mock Turtles × Mock Turtles は 255 まで出る。

おまけ：Mogul の負け局面は Golay 符号

1 次元で「最大 d − 1 枚まで裏返せる」ゲームを考える（Mock Turtles は d = 4、Moebius は d = 6、Mogul は d = 8）。

• 2 つの負け局面は、1 手（d − 1 枚以下の裏返し）で移り合えない。移れたら片方が勝ち局面になってしまう。だから負け局面どうしは少なくとも d 枚違う。
• 局面を二進数とみて小さい順に見ると、「それより小さい負け局面のどれとも d 枚以上違う」局面がちょうど負け局面になる。

これは符号理論のlexicode（辞書式に貪欲に拾った、最小距離 d の符号）の作り方と同じで、Conway と Sloane が 1986 年の論文 "Lexicographic codes: error-correcting codes from game theory" で示した対応だ。lexicode(n, d) はゲームを使わず、拾った語のハミング球（半径 d − 1）に印を付けながら 2^n 語をなめるだけで符号を作る。

ゲーム	コイン	負け局面	lexicode	最小重み	重み分布
Mock Turtles	16	2,048	2,048（全部一致）	4	1, 140, 448, 870, 448, 140, 1
Moebius	18	512	512（全部一致）	6	1, 102, 153, 153, 102, 1
Mogul	24	4,096	4,096（全部一致）	8	1, 759, 2576, 759, 1

Mock Turtles の 16 枚は拡張 Hamming 符号 [16, 11, 4]、Mogul の 24 枚は重み分布が 1 + 759y⁸ + 2576y¹² + 759y¹⁶ + y²⁴ の [24, 12, 8] 符号で、これは拡張 Golay 符号（この分布を持つ [24, 12, 8] 符号は Golay 符号だけ）。重み 8 の 759 語はシュタイナー系 S(5, 8, 24) のブロック（octad）だ。Mogul のコインの値は 1, 2, 4, 8, 16, 32, 64, 127, 128, 256, 512, 911, … と mex で出て、24 枚の値がちょうど 12 ビットを張る。

lexicode の構成は 24 ビットだと 4,096 語 × 半径 7 の球 536,155 語 = 約 22 億回の印付けで 35 秒、負け局面側（値の XOR が 0 になる集合を Gray 符号順に数える）は 0.2 秒だった。

有限体としての検算

nim 積が本当に体になっているかも数えた。

• 256 未満：全 16,777,216 組で結合法則と分配法則が成り立つ。
• 65,536 未満：65,535 個の 0 でない元すべてに逆数があり（x ⊗ x^(q−2) = 1）、258 の累乗が 0 以外の全元を 1 回ずつ通る（258 が乗法群の最小の生成元。256 未満は部分体 F₂₅₆ に入っていて生成元になれない）。
• 2^32 未満：乱数 200,000 組で結合法則・分配法則。
• Fermat 2 冪 F = 2, 4, 16, 256, 65536 で F ⊗ F = 3, 6, 24, 384, 98304 = 3F/2。

もう一つ、2 はどの有限 nim 体でも 3 乗数にならない。q = 2^(2^k) なら q − 1 は 3 で割り切れるので、0 でない元のうち 3 乗数は 1/3 だけ（65,536 元体で 21,845 個）。2 が 3 乗数かどうかは 2^((q−1)/3) = 1 かどうかで判定でき、q = 4, 16, 256, 65536, 2^32 で 2, 3, 2, 3, 2 と 1 にならなかった。2 ⊗ 2 = 3、2 ⊗ 3 = 1 なので 2 の位数は 3 で、(q − 1)/3 乗は (q − 1)/3 を 3 で割った余り（1 か 2）で 2 か 3 に決まる。Conway は順序数まで nim 積を伸ばして、2 の 3 乗根が最初の無限順序数 ω になる（ω³ = 2）ことを示している。ここで確かめたのは有限の側だけ。

実装メモ

• src/nim.ts: Fermat 2 冪による nim 積（2^32 未満）、累乗、逆数、平方根、表。
• src/coins.ts: 1 次元ゲーム（Twins, Ruler, 「k 枚まで」）、1 枚の値の mex、積のゲームの mex、全局面の mex（fullPosition）、Turning Corners の mex（cornersByMex）、核の重み分布、lexicode。
• src/game.ts: 対局用。盤、手、勝ち筋（XOR を 0 にする手）、コンピュータ。
• tools/compute.mts: 記事の表の計算をまとめて実行し、ジョブごとに runs/compute.json を書き直す（6.5 分）。tools/corners.mts が 1023 × 1023 の mex。
• tools/report.mts: デモの右パネル（src/findings.json）の生成。

まとめ

• Turning Corners はコイン 1 枚の値が a ⊗ b で、局面の値は表の XOR。デモでは反対側の隅すべてに ✓／✗ を付けた。
• 1 枚の値の mex の式は nim 積の定義そのもの。1023 × 1023 の 104 万枚を定義どおりに計算し、Fermat 2 冪の掛け算と全部一致した。
• 「局面の値は XOR」も仮定せず、5 × 5 の 2^25 局面を含む 10 盤・1 億 906 万局面を mex で解いて一致。
• Nim・Ruler・Mock Turtles の 6 通りの積で Tartan 定理 v(x, y) = g(x) ⊗ h(y) が成り立った。
• 「7 枚まで裏返す」Mogul の 24 枚盤の負け局面は、ゲーム抜きの貪欲符号と同じ 4,096 語で、重み 759 / 2576 / 759 の拡張 Golay 符号だった。