マスターマインド（4 ピン・6 色・重複あり、1,296 通りの秘密の符号を当てるゲーム）を、5 種類の一手先読み戦略と厳密な最適戦略を内蔵してブラウザに実装した。深さ優先の分枝限定法（完全木による下界・予算付き再帰・対称性での候補圧縮・集合ごとのメモ）を素の TypeScript で書き、Koyama & Lai (1993) の最適値 5,625 手（平均 4.3403）を 1 コア 107.9 秒で再現した。Ville (2013) の最適値表も MM(4,7) を除く 27 セルすべて一致し、表の外の MM(3,10) = 5,242、MM(8,2) = 1,104、MM(2,10〜16) も計算した（2 ピンは Chen & Lin / Goddard の閉じた式と全一致）。一手先読み戦略も Knuth の 5,801、Irving の 5,696、Kooi の 5,668 と公表値どおりに出たが、エントロピー戦略だけは公表値 5,723 に対して 5,722 になった。原因を追うと、木の 404 分岐のうち 375 で同点が生じ、同点の手はすべて「部分の大きさの多重集合が同じ」で、浮動小数点の
p log pの足し算順の違いが同点を丸め誤差で割っていた。部分集合の大きさの積 ∏ n^n を BigInt で比べると同点は厳密に同点になり、MM(4,6) で 5,722、MM(4,7) で 11,378（公表値 11,382）。4 通りの浮動小数点の書き方で MM(4,7) は 11,378 / 11,380 / 11,381 / 11,382 の 4 通りに割れる。5 手保証の代償はちょうど 1 手（5,626）、Knuth の初手 1122 は最適に続けても 5,702。テスト 20 件。ソルバー内蔵パズル第 74 弾。
デモ: https://sen.ltd/portfolio/mastermind/
リポジトリ: https://github.com/sen-ltd/mastermind
ルール
-
出題者は 4 本のピンを 6 色から選んで秘密の符号を作る。同じ色を何度使ってもよいので 6⁴ = 1,296 通り
-
解答者が 4 本のピンで推測するたびに、出題者は
- 黒（●）: 色も位置も合っているピンの数
- 白（○）: それ以外で、色だけ合っているピンの数（重複は両方にある回数までしか数えない）
を返す
-
黒 4 本で終了。手数が少ないほど良い
-
返事は (黒, 白) の組で 14 通り。(3, 1) は起こりえない（3 本が合っていて残り 1 本の色が「別の位置で合う」ことはない）
採点関数は素直に書ける。表にして 1,296 × 1,296 の Uint8Array に焼いておけば、以後はすべて表引きになる。
// a と s の黒・白。黒でないピンの色を数えて、共通部分の min の和が白
let black = 0;
for (let k = 0; k < p; k++) {
const x = pegs[a * p + k], y = pegs[s * p + k];
if (x === y) black++;
else { ca[x]++; cb[y]++; }
}
let white = 0;
for (let k = 0; k < c; k++) white += Math.min(ca[k], cb[k]);
戦略はすべて「集合の切り方」の話
どの時点でも、それまでの返事と矛盾しない符号の集合 S が残っている。推測 g を打つと、S は返事ごとに最大 14 個の部分に切られる。一手先読み戦略は、1,296 通りの g について S の切り方を採点し、いちばん良いものを打つ。
| 戦略 | 打つ手 |
|---|---|
| consistent | まだ秘密でありうる符号のうち辞書順で最初のもの（先読みなし） |
| maxsize (Knuth 1977) | 最大の部分が最小になる手 |
| expsize (Irving 1979) | Σ n² が最小（残る部分の期待サイズ最小） |
| entropy (Neuwirth 1982) | 切り方のエントロピー最大 |
| parts (Kooi 2005) | 空でない部分の数が最大 |
同点は「秘密でありうる手」を優先し、それでも同点なら辞書順で最初の手。どの戦略も「S だけから次の手が決まる」ので、1,296 通りの秘密に対して一斉に遊ばせるのは、戦略が作る決定木を 1 回たどるだけで済む。サンプリングではなく、全部厳密に数えられる。
const walk = (set: number[], depth: number) => {
const g = pick(set, depth);
const buckets = game.grades.map(() => [] as number[]);
for (const s of set) buckets[game.table[g * game.n + s]].push(s);
buckets.forEach((b, r) => {
if (!b.length) return;
if (r === game.win) bump(depth); // この秘密は depth 手目で当たった
else walk(b, depth + 1);
});
};
公表値の再現
結果は Kooi (2005) と Ville (2013) の表とほぼ一致した。
| 戦略 | 初手 | 総手数 | 平均 | 最悪 | 1 / 2 / 3 / … 手目で当たる数 | 可能な手だけ: 総手数 | 最悪 |
|---|---|---|---|---|---|---|---|
| 最適（厳密） | 1123 | 5,625 | 4.340 | 6 | 1 / 8 / 102 / 630 / 548 / 7 | — | — |
| consistent | 1111 | 7,471 | 5.765 | 9 | 1 / 4 / 25 / 108 / 305 / 602 / 196 / 49 / 6 | 7,471 | 9 |
| maxsize (Knuth) | 1122 | 5,801 | 4.476 | 5 | 1 / 6 / 62 / 533 / 694 | 5,828 | 6 |
| expsize (Irving) | 1123 | 5,696 | 4.395 | 6 | 1 / 10 / 54 / 645 / 583 / 3 | 5,722 | 6 |
| entropy | 1234 | 5,722 | 4.415 | 6 | 1 / 4 / 71 / 612 / 596 / 12 | 5,786 | 6 |
| parts (Kooi) | 1123 | 5,668 | 4.373 | 6 | 1 / 12 / 72 / 635 / 569 / 7 | 5,701 | 7 |
Knuth の minimax は 1122 から入り、5 手以内に必ず当てる。分布 1 / 6 / 62 / 533 / 694 は Knuth の論文そのもの。切り方全体を見る戦略は平均で勝ち、裾で負ける（most-parts は 7 個の秘密に 6 手目を使う）。「まだ秘密でありうる手」しか打たない縛りを入れると 26〜64 手悪化し、Knuth の戦略は 5 手保証も失う（5,828 手、最悪 6）。Ville が引用している 5,828 もそのまま出た。
MM(4,7)（7 色、2,401 通り）でも Ville の表 4 を再現した: consistent 12,265、maxsize 11,613、expsize 11,409、parts 11,388。
一致しなかったのはエントロピー戦略だけだった。公表値は MM(4,6) で 5,723、MM(4,7) で 11,382。こちらの実装は 5,722 と 11,378。
エントロピー戦略は 1 つの数ではない
同点が大量にある
N 個の符号を大きさ n_i の部分に切るとき、エントロピーは
$$
H = \log N - \frac{1}{N}\sum_i n_i \log n_i
$$
なので、最大化は Σ n_i log n_i の最小化、つまり整数 ∏ n_i^{n_i} の最小化と同じだ。これを BigInt で比べれば、比較は厳密になる。
export function entropyKey(sizes: Int32Array): bigint {
let k = 1n;
for (const x of sizes) if (x > 1) k *= BigInt(x) ** BigInt(x);
return k;
}
厳密に比べて木をたどると、404 回の意思決定のうち 375 回で、最高点に複数の手が並ぶ。そして並んだ手が違う大きさの切り方をしている分岐は 0 回だった（MM(4,7) でも 726 回中 687 回が同点、違う大きさの同点は 0）。同点はすべて「部分の大きさの多重集合は同じで、どの返事にどの大きさが来るかだけが違う」手同士だった。
浮動小数点は同点を丸め誤差で割る
普通に書くと、エントロピーは返事の順に p * Math.log(p) を足していく。同点の 2 手は同じ数の集まりを違う順番で足すことになるので、最後の 1 ビットがずれうる。すると「同点なら秘密でありうる手、それから辞書順」という規則ではなく、丸め誤差が勝者を決める。
4 通りの書き方で比べた。
| MM(4,6) のエントロピーの計算法 | 総手数 | 厳密版と違う手を選んだ分岐 | |
|---|---|---|---|
| 厳密（∏ n^n を BigInt で） | 5,722 | — | |
| Σ n·log2 n | 5,722 | 404 中 0 | |
| Σ p·log2 p | 5,722 | 404 中 2 | |
| Σ p·ln p | 5,723 | 404 中 4 | 公表値 |
| Σ p·log2 p（float32） | 5,722 | 404 中 4 |
| MM(4,7) のエントロピーの計算法 | 総手数 | 厳密版と違う手を選んだ分岐 | |
|---|---|---|---|
| 厳密（∏ n^n を BigInt で） | 11,378 | — | |
| Σ n·log2 n | 11,378 | 726 中 0 | |
| Σ p·log2 p | 11,382 | 726 中 10 | 公表値 |
| Σ p·ln p | 11,380 | 726 中 5 | |
| Σ p·log2 p（float32） | 11,381 | 726 中 8 |
MM(4,7) では4 通りの書き方で 4 通りの総手数が出る。どの書き方も、厳密に比べて悪い切り方を選んだことは一度もない（厳密版の木の上で数えて 0 回）。違いはすべて、本物の同点を規則ではなく丸めで割ったことから来ている。
「辞書順の最後を選ぶと 5,722」の正体
Ville の論文には脚注で「辞書順で最後の手を選ぶと 5,722 になる」とある。これはタイブレークの向きのせいではありえない。色を x → c + 1 − x と付け替える写像は全ての返事を保ち、辞書順を逆転させる。したがって「最初を選ぶ」木と「最後を選ぶ」木は鏡像で、総手数は必ず等しい。統計スクリプトは 5 戦略 × 2 ゲームすべてでこの一致を確かめ、崩れたら止まる。5,722 と 5,723 の差は向きではなく、浮動小数点だ。
教訓は小さいが一般的だ。スコアに同点が多い貪欲法を浮動小数点で書くと、再現性が足し算の順番に依存する。同点の多い比較は、整数で比べられる形に直してから比べる。
厳密な最適戦略
漸化式
残り集合 S から全部当てるまでの手数の、S の全要素にわたる合計の最小値を cost(S) とすると
$$
\mathrm{cost}(S) = |S| + \min_g \sum_{r \neq \text{win}} \mathrm{cost}(S_r)
$$
|S| はこの 1 手の分（g そのものが秘密なら、その 1 個はここで終わる）。推測には、もう秘密でありえない符号も使ってよい。
小さく保つ 4 つの工夫
- 完全木による下界: 1 手で当たる秘密は高々 1 個、当たらない返事は高々 13 通り。だから m 個の集合は、13 分木を上から詰めた完全木の外部経路長以上かかる。候補手の下界は部分ごとの下界の和で、下界の小さい候補から試す
- 予算付き再帰: 各部分は「その候補に残された予算」付きで解き、超えた時点で諦める。諦めた集合には「少なくともこれ以上」という下界をメモしておく
- 対称性: これまでの推測を全て固定する位置の置換 × 色の置換、まだ一度も打っていない色（互いに交換可能）、S のどの符号にも無い色（互いに交換可能）で候補を代表元に潰す。さらに S を全く同じに切る候補も 1 つにまとめる
- メモ: 集合（整数列を文字列化したもの）ごとに、厳密値と証明済み下界を持つ
根では候補が 1111 / 1112 / 1122 / 1123 / 1234 の 5 つに潰れる。1123 の部分の下界が最小なので最初に試され、そこで 5,625 に達する。残りの時間はほぼ「他の 4 つが 5,625 を下回れない」ことの証明に使われる。
for (const cand of cands) { // 下界の小さい順
if (cand.lb >= best) break;
let running = cand.lb;
for (const part of cand.parts) { // 大きい部分から
const plb = this.bound(part.length, depth - 1);
const rest = running - plb;
const v = this.solve(part, best - rest, depth - 1, history.concat(cand.g));
running = rest + v; // 下界を実値で置き換える
if (running >= best) break; // この候補は負け
}
if (running < best) { best = running; bestGuess = cand.g; }
}
結果、MM(4,6) は 5,625 手、43,712 集合の展開、107.9 秒（TypeScript、1 コア）。見つかった木は JSON で保存し、テストが全 1,296 通りの秘密に対して再生して 5,625 と最悪 6 を確かめる。ページの「optimal」のヒントはこの木をたどっている（木から外れた後は、残りが 40 個以下ならその場で最適を探す。ランダムな推測を重ねて作った 400 局面で計ると、40 個以下（262 局面）なら中央値 3 ms・最長 166 ms、41〜80 個（138 局面）だと最長 1,663 ms かかったので 40 で切った）。
5 手保証の値段はちょうど 1 手
最適戦略は 7 個の秘密に 6 手目を使う。深さを 5 に制限して同じ探索をすると（完全木の下界が深さ付きで「残り手数で入りきらない部分」を即座に刈る）、最良は 5,626 手。全 1,296 通りでちょうど 1 手多いだけだ。Koyama & Lai の主張どおり。
初手ごとの最適値
初手を固定して残りを厳密に解くと、「初手の良し悪し」と「その後の打ち方の良し悪し」を分けられる。
| 初手 | 部分の数 | 最大の部分 | その後を最適に打った総手数 | 平均 | 5 手以内の制約つき |
|---|---|---|---|---|---|
| 1111 | 5 | 625 | 6,318 | 4.8750 | 不可能 |
| 1112 | 11 | 317 | 5,791 | 4.4684 | 5,808 |
| 1122 | 13 | 256 | 5,702 | 4.3997 | 5,702 |
| 1123 | 14 | 276 | 5,625 | 4.3403 | 5,626 |
| 1234 | 14 | 312 | 5,673 | 4.3773 | 5,676 |
Knuth の 1122 は、その後を最適に打っても 5,702。Knuth の戦略の 5,801 は最適より 176 手多いが、そのうち初手のせいは 77 手、その後の一手先読みのせいが 99 手。1111 から始めると 5 手保証は不可能だ。(0, 0) が返る 625 通りを残り 4 手で必ず当て切る打ち方が存在しないことを、深さ制限つきの探索が証明する。次の 1 手で最大の部分を 120 個まで小さくはできるが、その先のどこかで、残り手数の完全木に収まらない部分が必ず出る。
台帳: 探索が届く全セル
同じ探索を他のピン数・色数でも回した。各セルは c^p 通りの秘密全体での最適総手数。
| ピン \ 色 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 8 | 21 | 45 | 81 | 132 | 198 | 284 | 388 | 517 | 667 | 847 | 1,051 | 1,290 | 1,556 | 1,862 |
| 3 | 18 | 73 | 206 | 451 | 854 | 1,474 | 2,359 | 3,596 | 5,242 | ||||||
| 4 | 44 | 246 | 905 | 2,463 | 5,625 | ||||||||||
| 5 | 97 | 816 | 3,954 | ||||||||||||
| 6 | 224 | 2,649 | |||||||||||||
| 7 | 496 | ||||||||||||||
| 8 | 1,104 |
太字以外の 27 セルは Ville (2013) の表 6 にあり、全部一致した。2 ピンの行は Chen & Lin / Goddard の閉じた式
$$
L(2, c) = \begin{cases} (8c^3 + 51c^2 - 74c + 48)/24 & c \text{ 偶数} \ (8c^3 + 51c^2 - 80c + 69)/24 & c \text{ 奇数} \end{cases}
$$
と c = 16 まで全部一致した（c = 2 だけは 8 で例外）。太字の MM(3,10) = 5,242 と MM(8,2) = 1,104 は Ville の表の外で、少なくとも本プロジェクトが知る範囲では公表されていない。3 本の行はどれも OEIS に無かった。いちばん重いセルは MM(3,10) の 168.8 秒。MM(4,7)（Ville の値 11,228）は、今回は最後まで走らせていない。
統計スクリプトは、3 秒以内で終わる 27 セルを毎回計算し直し、保存値・公表値・閉じた式のどれかと食い違えば止まる。
ページ
- You break the code: 色をクリック（または 1〜6 キー、Backspace、Enter）で推測する。右のパネルに、残りの候補数・残りの情報量（ビット）・6 つの戦略それぞれの次の手とその最大の部分が出る。組みかけの推測がどう切るかもその場で出る
- Watch a strategy break it: 戦略と秘密を選んで、Step で 1 手ずつ、Play to the end で最後まで
- strategy lab: 各戦略を全 1,296 通りと戦わせたときの「何手目で当たったか」のヒストグラム
スクリーンショットは 2 手目の後の局面で、残り 33 個に対して最適戦略は最大の部分が 9 になる 6165 を選び、Knuth の maxsize は最大の部分が 5 の 1563 を選んでいる。最悪を小さくすることと、合計を小さくすることは違う。
まとめ
- 戦略は決定木で評価する。 1,296 通りの秘密を一斉に流せば、平均も分布も最悪も厳密に出る。サンプリングは要らない
- 同点の多い貪欲法は、比較を整数に直す。 エントロピーは ∏ n^n の比較に落ちる。浮動小数点のままだと、同じ規則が足し算の順番で 4 通りの答えを出す
- 対称性でタイブレークの向きの影響を先に消す。 色の反転で「最初を選ぶ」と「最後を選ぶ」は同じ総手数になる。違いが出たら、それは向きではなく別の原因
- 分枝限定法は下界と予算がすべて。 完全木の下界・予算付き再帰・対称性・メモだけで、1993 年の最適値が素の TypeScript で 2 分弱
- 最適木を分解する。 初手を固定すると、Knuth の 176 手の損が初手 77 手とその後 99 手に分かれる
数値はすべて npm run stats（と重いセルは npm run optimal）が出力し、README とページ本文は npm run notes が src/stats.json から書き起こしている。手で転記した数字は 1 つも無い。テスト 20 件。ソルバー内蔵パズル第 74 弾。
参考文献:
- D. E. Knuth, "The computer as master mind", Journal of Recreational Mathematics 9 (1976–77)
- K. Koyama, T. W. Lai, "An optimal Mastermind strategy", Journal of Recreational Mathematics 25 (1993)
- B. Kooi, "Yet another Mastermind strategy", ICGA Journal 28 (2005)
- G. Ville, "An optimal Mastermind (4,7) strategy and more results in the expected case", arXiv:1305.1010 (2013)
デモ: https://sen.ltd/portfolio/mastermind/
リポジトリ: https://github.com/sen-ltd/mastermind