**Notakto（ノータクト）**をブラウザに実装した。三目並べの盤を何枚か並べ、2 人とも X だけを書く。どの盤のどのマスに書いてもよく、3 つ並んだ盤は「死んだ盤」になる。最後の盤を殺した方が負け。盤は 1〜6 枚。コンピュータは完全にプレイする。仕組みは Plambeck と Whitehead の 2013 年のノートにある 18 元の可換モノイド Q（ミゼール商）で、盤ごとに Q の元を 1 つ割り当て、全部の積が P = {a, b², bc, c²} に入れば後手勝ち。ノートは Q を「与えられたもの」とし、102 局面の値を図で載せているだけなので、ここでは全部計算し直した。モノイドは表示から Knuth–Bendix 完備化で 18 元が出る。辞書は「何枚の盤でも積で勝敗が決まる」ことを 285,480 状態の有限の幅優先探索で証明でき、モノイドを使わない素朴なゲーム探索とも 7 枚までの全部の和（約 1.5 億通り）で一致した。102 個の値のうち 1 個だけを変えた 782 通りは全部証明が通らない。一方で (Q, P) には自己同型が 4 つあり、d と ad の名前を入れ替えた辞書も同じように正しい。テスト 19 件。ソルバー内蔵パズル第 89 弾。
デモ: https://sen.ltd/portfolio/notakto/
リポジトリ: https://github.com/sen-ltd/notakto
ルール
- 普通の 3×3 の三目並べの盤を何枚か並べる。
- 2 人が交互に、どれか 1 枚の盤の空いているマスに X を書く。○は使わない。
- 縦・横・斜めに X が 3 つ並んだ盤は死ぬ。それ以降、その盤には書けない。
- 最後に残った盤を殺した人（＝最後の 3 つ並びを作った人）が負け。
どちらも同じ記号を書くので、局面はどちらの手番でも同じ意味を持つ。こういうゲームを不偏ゲーム（impartial game）と呼ぶ。最後に動いた人が負けになる決まりをミゼール（misère）と呼ぶ。
盤 1 枚の場合は 2010 年に MathOverflow で Timothy Chow が話題にし、「先手は中央に打ち、あとは相手の手から桂馬跳び（ナイト移動）の位置に打てば勝つ」「中央以外の初手は、後手が点対称の位置に返して以後 180° 回転のまねをすれば負ける」という答えが付いた。何枚の盤でも解けるようにしたのが、Thane Plambeck と Greg Whitehead の 2013 年のノート "The Secrets of Notakto: Winning at X-only Tic-Tac-Toe"（arXiv:1301.1672）。
なぜ Grundy 数ではだめか
最後に動いた人が勝ちの普通のルール（ノーマルプレイ）なら、話は簡単。Sprague–Grundy の定理により、盤 1 枚ごとに 1 つの数（Grundy 数）が決まり、和の勝敗は Grundy 数の XOR で決まる。ニムに置き換えられる。
ミゼールではこれが崩れる。ニムのミゼール版には Bouton の規則（「1 より大きい山があれば XOR が 0 なら後手勝ち、全部の山が 1 以下なら XOR が 1 なら後手勝ち」）があるので、それを盤の Grundy 数に当てはめたくなる。だが空の盤 1 枚でもう間違える。空の盤の Grundy 数は 1 なので規則は「後手勝ち」と言うが、実際は先手が中央に打って勝つ。
実際に数えると、規則の当たり外れは次のとおり（src/analysis.ts の tameGuess）。
| 盤の枚数 | 和の数 | Grundy 数＋ミゼールニムの規則が外れる数 |
|---|---|---|
| 1 | 46 | 2（4.3%） |
| 2 | 1,081 | 41（3.8%） |
| 3 | 17,296 | 638（3.7%） |
| 4 | 211,876 | 8,789（4.1%） |
正解の方は、下で説明するモノイドの規則（すべての盤の数で正しいことを証明済み）を使っている。
ミゼール商: 盤の値は 18 元のモノイドの元
Plambeck は 2005 年ごろから、ミゼールの不偏ゲームを「ゲームごとの有限の可換モノイド」で扱う方法を作ってきた（ミゼール商、misère quotient）。考え方はこう。
- 2 つの局面 G と H は、「どんな局面 X を横に足しても G + X と H + X の勝敗が同じ」なら同じものとみなす。
- このみなしで割った集合は、局面の和を掛け算とするモノイドになる。
- 各元が「後手勝ち（P）」か「先手勝ち（N）」かは決まっているので、P に入る元の集合 P ⊂ Q がある。
ノーマルプレイならこれは Grundy 数と XOR（の群）そのものになる。ミゼールでは、そのゲームに固有の、もっとややこしいモノイドになる。
ノートが示す Notakto のモノイドは
Q = ⟨ a, b, c, d | a² = 1, b³ = b, b²c = c, c³ = ac², b²d = d, cd = ad, d² = c² ⟩
の 18 元で、P = {a, b², bc, c²}。盤の 102 通り（回転・裏返しで同じものをまとめた数）それぞれに Q の元が書かれた図（Figure 7）がある。複数の盤の勝敗は、値を全部掛けて関係式で簡約し、P に入るかどうかで決まる。
たとえば空の盤は c。2 枚なら c² ∈ P で後手勝ち。3 枚なら c³ = ac² ∉ P で先手勝ち。
ノートは「Q をどう計算したかはこの文書の範囲外」として、Q も辞書も天下りに与えている。今回はここを全部確かめる。
1. モノイドを表示から作る
語（a, b, c, d の積）は可換なので、指数のベクトル [a の指数, b の指数, c の指数, d の指数] で表せる。関係式を「次数が大きい方 → 小さい方」（同じ次数なら d > c > b > a の順で比べる）の書き換え規則にし、Knuth–Bendix 完備化をかける。可換な語では、2 つの規則の左辺の lcm（成分ごとの max） が重なりの場所になる。そこを 2 通りに書き換えて結果が違えば、新しい規則を足す。
private complete() {
for (let again = true; again; ) {
again = false;
outer: for (let i = 0; i < this.rules.length; i++)
for (let j = 0; j < i; j++) {
const p = this.rules[i], q = this.rules[j];
const lcm = p.lhs.map((x, k) => Math.max(x, q.lhs[k]));
const u = this.reduce(lcm.map((x, k) => x - p.lhs[k] + p.rhs[k]));
const v = this.reduce(lcm.map((x, k) => x - q.lhs[k] + q.rhs[k]));
if (this.addRule(u, v)) { again = true; break outer; }
}
}
}
結果: 21 組の臨界対はすべて合流し、新しい規則は 1 本も足されなかった。つまりノートの 7 本の関係式は、そのままで完備な書き換え系になっている。これ以上書き換えられない語を 1 から幅優先で集めると、ちょうど 18 個。
1 a b c d ab ac ad b² bc bd c² ab² abc abd ac² bc² abc²
ノートの列挙と同じ。
2. 102 局面と並び順
盤の X の置き方は 2⁹ = 512 通り。正方形の 8 つの対称で同じものをまとめると、Burnside の補題で (512 + 2·8 + 32 + 4·64) / 8 = 102。ノートの「102 nonisomorphic positions」と合う。そのうち 3 つ並びを含まない（生きている）盤は 46 個。
Figure 7 の並びは「X の個数順、同じ個数なら、X のあるマスの番号を小さい順に並べた列の辞書順で、類の中の最小の代表」になっていることを確かめ、図の赤い値 102 個を PDF のテキスト層から読んで配列にした（src/quotient.ts の PAPER_VALUES）。テストでは先頭 12 個の代表が図と同じ盤になることを確かめている。
死んだ盤（3 つ並びを含む 56 個）は全部 1。ノートの脚注「実戦では現れない盤も含めたが、それらは全部単位元」と一致する。
3. 辞書が「何枚の盤でも」正しいことの有限の証明
ここが本題。辞書が正しいとは、任意の枚数の盤の組について「積 ∈ P ⇔ 後手勝ち」が成り立つこと。枚数に上限はないので、全部試すことはできない。でも有限の検査で証明できる。
和 S の勝敗は、その選択肢で決まる。
- S に生きた盤がなければ、手番の人はもう動けない（＝相手が最後の盤を殺した）ので手番の人の勝ち（N）。
- そうでなければ、「どの手も P の局面に行かない」とき、かつそのときに限り P。
盤 G に打つ手は、積 x = Φ(G)·r を Φ(G′)·r に変える（r は G 以外の盤の積、G′ は打った後の盤）。もし「もっと X が多い和では規則が正しい」と仮定すると、S の勝敗は次の情報だけで決まる。
- x: 全部の盤の積
- S にある盤の種類ごとに、その盤を 1 枚除いた残りの積 r
ここで種類とは (Φ(G), 打った後の値の集合 {Φ(G′)}) の組。この組が同じ盤は、勝敗の計算の上では区別がいらない。Notakto の 46 個の生きた盤は 15 種類になる。
空の和から始めて、盤を 1 枚ずつ（どの種類でも）足していく。状態（x と、種類ごとの r）は Q の元の組なので有限個しかない。全部の状態で「選択肢から決まる勝敗」と「x ∈ P」が一致すれば、空いたマスの数についての帰納法で、すべての枚数のすべての和で規則が正しい。
export function proveSums(phi: number[], classSet: number[] = LIVE): ProofResult {
const ks = kinds(phi, classSet);
const start = [ONE, ...ks.map(() => -1)]; // x と、種類ごとの r（-1 = その種類はない）
const key = (s: number[]) => String.fromCharCode(...s.map((v) => v + 1));
const seen = new Set<string>([key(start)]);
const queue = [start];
for (let q = 0; q < queue.length; q++) {
const s = queue[q];
const x = s[0];
let present = false, movesToP = false;
for (let k = 0; k < ks.length; k++) {
const r = s[k + 1];
if (r < 0) continue;
present = true;
if (ks[k].opts.some((y) => inP(Q.mul[y][r]))) movesToP = true;
}
if ((present && !movesToP) !== inP(x)) return { ok: false, /* … */ };
for (let u = 0; u < ks.length; u++) { // 種類 u の盤を 1 枚足す
const t = [Q.mul[x][ks[u].phi]];
for (let k = 0; k < ks.length; k++) {
const r = s[k + 1];
if (k === u) t.push(r < 0 ? x : Q.mul[r][ks[u].phi]);
else t.push(r < 0 ? -1 : Q.mul[r][ks[u].phi]);
}
if (!seen.has(key(t))) seen.add(key(t)), queue.push(t);
}
}
return { ok: true, /* … */ };
}
すでにある種類 u をもう 1 枚足すとき、u の「残りの積」は足す前の x になる（x = r_u·Φ(u) なので r_u·Φ(u) と書いても同じ）。
結果: 2013 年の辞書で 285,480 状態、約 5 秒、反例なし。Notakto の任意の枚数・任意の局面で、積の規則は正しい。
さらに 2 つ確かめると、Q が単に「うまくいくモノイドの 1 つ」ではなくミゼール商そのものだと言える。
- 盤の値の積で Q の 18 元が全部作れる（全射）。
- Q のどの 2 元も、何かを掛けると P に入るかどうかが分かれる（区別できない組は 0 組＝Q は既約）。
4. モノイドを使わない総当たりと突き合わせる
証明が自前のコードなので、まったく別の方法とも比べる。tools/brute.mts はモノイドを知らない。46 個の生きた盤（重複あり）の多重集合ごとに、普通にゲーム木を探索して勝敗を出し、積の規則と比べる。
最初は Map<string, boolean> でメモしていたら、6 枚の途中で RangeError: Map maximum size exceeded で落ちた。V8 の Map は約 1,670 万キーが上限。そこで多重集合を組合せ数系で番号付けして Int8Array に 1 バイトずつ持つようにした。整列した a₀ ≤ a₁ ≤ … を bᵢ = aᵢ + i で狭義単調に直すと、番号は Σ C(bᵢ, i+1) で、k 枚の多重集合がちょうど 0 〜 C(46+k−1, k)−1 に詰まる。
| 盤の枚数 | 和の数 | 後手勝ち (P) | 不一致 | 時間 |
|---|---|---|---|---|
| 1 | 46 | 18 | 0 | 1 ms |
| 2 | 1,081 | 213 | 0 | 3 ms |
| 3 | 17,296 | 3,282 | 0 | 46 ms |
| 4 | 211,876 | 42,423 | 0 | 432 ms |
| 5 | 2,118,760 | 352,876 | 0 | 6.2 s |
| 6 | 18,009,460 | 3,214,952 | 0 | 64.8 s |
| 7 | 133,784,560 | 21,167,844 | 0 | 722.1 s |
| 計 | 154,143,079 | 0 |
合計 154,143,079 通りの和で、積の規則と素朴な探索の勝敗が全部一致した。
5. 辞書はほぼ一意: 1 個変えると壊れる、でも d の名前は決まらない
辞書の 46 個の生きた盤の値のうち 1 個を、他の 17 元のどれかに変えた辞書を 46 × 17 = 782 通り作って証明にかけると、全部通らなかった（合わせて 0.7 秒）。どの値も勝敗の計算に効いている。
では辞書は一意か。ここで (Q, P) の自己同型を数えた。生成元 a, b, c, d の行き先を 18⁴ 通り全部試し、積と P を保つ全単射だけを残すと 4 個。
| 自己同型 | 辞書で変わる値 | 証明 |
|---|---|---|
| 恒等写像 | 0 | 通る |
| d → ad | 4 | 通る |
| d → bd | 4 | 通る |
| d → abd | 4 | 通る |
どれも a, b, c は動かさず、d だけを付け替える。Q が既約で辞書が全射なら、正しい辞書どうしは必ず自己同型 1 つでつながるので、正しい辞書はちょうど 4 通りある。変わるのは値が d か ad の 4 盤（隣り合う 2 つの X の盤と、それに 3 つ目を足した 3 盤）だけ。どれを「d」と呼ぶかはゲームからは決まらず、ノートの名前の付け方の一つにすぎない。1 個だけ変えると壊れるのは、d の 3 盤と ad の 1 盤をそろえて変えないと矛盾するから。
6. 文章で書かれた主張
src/analysis.ts で、ノートが文章で述べていることも探索で確かめた。
盤 1 枚の初手。 勝つ初手は中央だけ。空の盤の値は c ∉ P、中央を打った盤は c² ∈ P、角や辺を打った盤は 1 ∉ P。
桂馬跳びの戦略。 中央の後、相手がどこに打っても「そこから桂馬跳びの位置」に打てば勝つ。相手のすべての手順をたどって確かめた。ただし字面どおりではない。桂馬跳びの位置が 2 つあり、一方が 3 つ並びを完成させてしまう（その場で負ける）場面が 32 回ある（盤の向きを区別して、相手のすべての手順の中で数えた）。「3 つ並びにならない方の桂馬跳び」と読めば常に勝ち、そういう候補が 2 つ残る場面が 8 回あって、どちらを選んでも勝つ。
点対称の返し。 中央以外の初手 8 通りすべてで、後手が点対称の位置に返し、以後ずっと 180° 回転した位置に打つと、先手のどの手順に対しても後手が勝つ。最初の 2 手で「角—中央—角」や「辺—中央—辺」の線の両端が埋まるので、中央が打てなくなる（打つと 3 つ並ぶ）のが鍵。
n 枚の空の盤。 c, c², ac², c², ac², c²（1〜6 枚）。奇数枚なら先手勝ち、偶数枚なら後手勝ち。3 枚のときは、角・辺・中央のどの初手でも勝つ（c²·1 = c²、c²·c² = c² がどちらも P）。
まね（ミミック）。 2 枚の空の盤は後手勝ち。相手が片方の中央に打ったら、もう片方の中央にまねすると c²·c² = c⁴ = c² ∈ P で勝つ。ノートは「ここではまねが効く、でも一般には効かない」と書いている。実は最初の 1 手からもう効かない。相手が角か辺から打ってきたらまねは負け（1·1 = 1 ∉ P）。生きた盤 46 個のうち、同じ盤 2 枚の組が P になるのは 26 個。
Figure 5。 左の盤に左上・右上・中央（値 a）、右の盤に左上・中央（値 b）。積は ab ∉ P で、手番側の勝ち。まねして右の盤の右上に打つと両方の盤が a になり a·a = 1 で負け、という主張どおり。ノートは「正しい手を探してみて」で終わっているので答えを書いておくと、勝つ手は 4 つ: 左の盤の左中・右中・下中、または右の盤の右下。最後のものは右の盤の斜めを完成させて自分で盤を殺す手で、残った左の盤 a ∈ P を相手に渡す。
確かめていないもの。 脚注の「空の盤のミゼール標準形は {2+, 0}」「ニムの山 4 が 1 枚の盤として現れる」は、ミゼールの標準形の計算（可逆な手の除去）を実装していないので確かめていない。ただ、Grundy 数が 4 の盤はちょうど値が d の 3 盤だった、とだけ書いておく。
ノートの末尾の問い「4×4 のゲームは有限のミゼール商を持つか？」には触れていない。
UI
- 盤の枚数（1〜6）と先手・後手を選ぶ。
- ヒントを付けると、空いた各マスに W（そこに打つと相手が P の局面を受け取る＝勝ち）か L が付く。マスにマウスを乗せると、打った後の積が出る。
- 各盤の下にその盤の値、盤の列の下に積と P/N。右側には Q の 18 元が並び、P の 4 元が緑、今の積がオレンジになる。
- 下には 46 個の生きた盤とその値の一覧（辞書）があり、今プレイ中の盤が枠で囲まれる。
- コンピュータは勝てる局面では必ず P への手を打つ。負けている局面では、盤を殺さない手の中から無作為に選ぶ（相手が正解を見つけないといけない）。
テスト
19 件。主なもの:
- 102 類（Burnside とも一致）、46 の生きた盤、図の並び順。
- 18 元、関係式、可換、無限になる表示を検出すること。
- 有限の証明が 285,480 状態で通ること、Q が既約で全射なこと。
- 3 枚までの全部の和（17,296 通り）で素朴な探索と一致。
- 1 個だけ変えた 782 通りの辞書が全部落ちること、自己同型が 4 個で d だけを動かすこと、c と c² を入れ替えた壊れた辞書が落ちること（対照）。
- 盤 1 枚の初手・桂馬跳び・点対称、n 枚の空の盤、まね、Figure 5 の勝ち手 4 つ、Grundy 数の規則の失敗。
- コンピュータが N の局面から必ず P へ動くこと。
まとめ
- Notakto は盤ごとに 18 元のモノイドの値を持ち、積が P = {a, b², bc, c²} に入るかで勝敗が決まる（Plambeck–Whitehead 2013）。ノートの 7 本の関係式はそのまま完備な書き換え系で、18 元はノートの列挙どおり。
- 「何枚の盤でも積の規則が正しい」ことは、(積, 種類ごとの残りの積) の 285,480 状態を調べる有限の証明で示せる。素朴な探索とも 7 枚までの全部の和で一致する。
- 辞書の値は 1 個も動かせないが、d と ad の名前の付け方だけは自己同型 4 通りぶん自由。
- 盤 1 枚の桂馬跳びの戦略は「3 つ並びにならない方」と読めば正しい。2 枚の盤でのまねは、相手が中央から始めたときしか効かない。
参考文献:
- T. E. Plambeck, G. Whitehead, "The Secrets of Notakto: Winning at X-only Tic-Tac-Toe", arXiv:1301.1672, 2013, https://arxiv.org/abs/1301.1672（2026 年 10 月 19 日参照）
- T. Y. Chow, "Neutral tic tac toe", MathOverflow, 2010, https://mathoverflow.net/questions/24693/neutral-tic-tac-toe（2026 年 10 月 19 日参照）
- T. E. Plambeck, A. N. Siegel, "Misère quotients for impartial games", Journal of Combinatorial Theory, Series A 115 (2008), arXiv:math/0609825
デモ: https://sen.ltd/portfolio/notakto/
リポジトリ: https://github.com/sen-ltd/notakto