ハッケンブッシュ（Blue-Red-Green Hackenbush）をブラウザに実装した。地面から生えた色付きの辺を交互に切り、青（Left）は青か緑の辺、赤（Right）は赤か緑の辺を切る。地面とつながらなくなった部分は落ちる。切れなくなった方の負け。このゲームは Conway の組合せゲーム理論の入門で必ず出てくる題材で、局面ごとに 3/4 のような数、*2 のようなニム数、↑*（アップスター）のような無限小、あるいは {0 | *6, *7} のような一般の形の「値」が決まる。そこで、任意の選択肢の組を**標準形（canonical form）**に簡約するエンジンを TypeScript で一から書き、描いた絵の値・地面でしか接していない部分ごとの値・切れる全部の辺の勝ち負け（✓ / ✗）を出すようにした。自分で辺を描いて値を調べることもできる。エンジンは、Berlekamp の符号展開の規則（青赤の棒 1〜22 本の 8,388,606 本）、コロン原理と融合原理（緑だけのグラフ 329,711 個）、値を使わない素朴な勝敗探索（3 色のグラフ 131 万個）の 3 つと全部一致した。さらに 12 本までの 3 色の棒 797,160 本の値を全部求めると、同じ値の棒は 1 組もなかった。テスト 13 件。ソルバー内蔵パズル第 92 弾。
デモ: https://sen.ltd/portfolio/hackenbush/
リポジトリ: https://github.com/sen-ltd/hackenbush
ルール
- 盤は地面（太い横線）と、そこから生えた辺のグラフ。辺は青・赤・緑のどれか。ループや同じ 2 点を結ぶ複数の辺もよい。
- 青（Left）は青か緑の辺を 1 本、赤（Right）は赤か緑の辺を 1 本切る。
- 切ったあと、地面とつながらなくなった辺は全部落ちる（消える）。
- 手番で切れる辺がない方の負け（normal play）。
Berlekamp・Conway・Guy の Winning Ways の冒頭に出てくるゲームで、青と赤だけなら「何手ぶん得しているか」が数で、緑だけなら Nim の山の大きさ（ニム数）で表せる。3 色混ぜると数でもニム数でもない値が出てくる。
なぜ「値」なのか
ハッケンブッシュの局面は、地面でしか接していない部分の和になっていることが多い。和のゲームでは、手番の人がどれか 1 つの部分を選んで 1 手指す。組合せゲーム理論では各部分に値を付けると、全体の値は部分の値の足し算になり、勝敗は全体の値と 0 の大小だけで決まる。
| 値 G | 意味 |
|---|---|
| G > 0 | 青が勝つ（どちらが先手でも） |
| G < 0 | 赤が勝つ |
| G = 0 | 後手が勝つ |
| G ‖ 0（0 と比べられない） | 先手が勝つ |
たとえば青の辺 1 本は 1、赤の辺 1 本は −1、緑の辺 1 本は *（スター、先手必勝）。青の上に赤を載せた 2 本の棒は 1/2 で、赤の辺 1 本ぶんを 2 つ並べるとちょうど打ち消される（1/2 + 1/2 − 1 = 0、後手必勝）。
ゲームの値は「青が行ける局面の値の集合 | 赤が行ける局面の値の集合」で書く。緑を地面に、青をその上に載せた棒は、青は緑を切って 0、青を切って * に行け、赤は緑を切って 0 に行けるので {0, * | 0}。これは ↑* と呼ばれる値で、↑（アップ）は「0 より大きいが、どんな正の数よりも小さい」無限小。
エンジン: 標準形に簡約して id で持つ
同じ値のゲームはいろいろな書き方ができるが、標準形は 1 つに決まる。標準形にするには 2 つの操作を、何も変わらなくなるまで繰り返す。
- 支配された選択肢を消す: 青の選択肢 A ≤ B なら A は要らない（赤側は逆）。
- 可逆な選択肢を迂回する: 青の選択肢 A について、赤がそこから AR ≤ G に戻せるなら、A を AR の青の選択肢たちで置き換える。
標準形が一意なので、標準形を 1 回ずつ登録（intern）して整数 id で持てば、値が等しいことと id が等しいことが同じになる。比較 G ≤ H は Conway の再帰的な定義そのままで、id の組でメモ化する。
/** G ≤ H. */
export function le(g: GameId, h: GameId): boolean {
if (g === h) return true;
// 両方とも数なら値で比べる
...
let r = true;
for (const hr of Rs[h]) if (le(hr, g)) { r = false; break; } // H^R ≤ G があればダメ
if (r) for (const gl of Ls[g]) if (le(h, gl)) { r = false; break; } // G^L ≥ H があればダメ
leMemo.set(g * KEY + h, r);
return r;
}
簡約の本体はこう。
export function make(L0: readonly GameId[], R0: readonly GameId[]): GameId {
let L = uniq([...L0]);
let R = uniq([...R0]);
const x = numberIfAny(L, R); // 全部数で、青の最大 < 赤の最小なら「間で最も単純な数」
if (!Number.isNaN(x)) return numberGame(x);
for (;;) {
L = L.filter((a) => !L.some((b) => b !== a && le(a, b))); // 支配
R = R.filter((a) => !R.some((b) => b !== a && le(b, a)));
const cmp = new RawCompare(L, R); // まだ id のない G との比較
let changed = false;
const nL: GameId[] = [];
for (const a of L) {
const rev = Rs[a].find((ar) => cmp.xLeG(ar)); // A^R ≤ G なら A は可逆
if (rev === undefined) nL.push(a);
else { nL.push(...Ls[rev]); changed = true; }
}
// 赤側も対称に
...
if (!changed) break;
}
return intern(L, R, NaN);
}
ひとつ引っかかるのは、可逆性の判定「AR ≤ G」の G が今まさに簡約しているゲームで、まだ id がないこと。一時的に id を振ると表が汚れるので、G を選択肢のリストのまま持つ比較を別に書いた。x ≤ G と G ≤ x は互いを呼び合うが、再帰するたびに x の方が単純になるので止まる。
/** x ≤ G : G^R ≤ x がなく、x^L ≥ G もない */
xLeG(x) { ... for (const gr of this.R) if (le(gr, x)) ...; for (const xl of Ls[x]) if (this.gLeX(xl)) ... }
/** G ≤ x : x^R ≤ G がなく、G^L ≥ x もない */
gLeX(x) { ... for (const xr of Rs[x]) if (this.xLeG(xr)) ...; for (const gl of this.L) if (le(x, gl)) ... }
数は入口で見分ける。選択肢が全部数で、青の最大が赤の最小より小さければ、その値は間にある最も単純な数（整数があれば絶対値が最小の整数、なければ分母が最小の 2 進分数）で、標準形は {x − 2−k | x + 2−k} と直接作れる。青赤だけの局面はこれで比較も足し算もほぼタダになる。
値の表示は、数ならそのまま、そうでなければ左右の「止まり値（stop）」が一致するか調べ、一致したらその数 x を引いて、残りを n·↑ + *m の表（n = −6〜6、m = 0〜15）から引く。どれにも当たらなければ {L | R} と書く。
ハッケンブッシュ側: 辺のビットマスク
局面は辺のリスト（頂点 0 が地面）と、残っている辺のビットマスク。辺を切るとビットを消し、地面から辿れる辺だけ残す。ゲーム中に出てくる局面は全部「元の絵のマスク」なので、値はマスクでメモ化できる。
もう 1 つ効くのは、地面でしか接していない部分に分けて足すこと。分けずに全体の選択肢をそのまま並べると、部分の局面の組み合わせ（直積）を全部たどることになる。分けると部分ごとの局面数の和で済み、足し算は値どうしの add でメモ化される。後で示すとおり、分けて足した値と、分けずに全体から作った値は 100 万個以上のグラフで全部同じ id になった。
ページ側では、この計算を Web Worker で回し、手番の人が切れる全部の辺について「切った後の値」を出す。青の手番なら、切った後の値が ≥ 0（赤が先手で勝てない）になる辺が ✓。コンピュータは ✓ の辺からランダムに選び、✓ がなければ落ちる辺が最も少ない辺を切って粘る。
検算 1: Berlekamp の符号展開の規則
青と赤だけの棒（地面から 1 本ずつ積んだもの）の値には閉じた式がある。下から色を読み、最初に色が変わるまでは 1 ずつ（青 +1、赤 −1）、変わった後は 1 本ごとに半分ずつ足す。
- 青赤（BR）: 1 − 1/2 = 1/2
- 青青赤（BBR）: 2 − 1/2 = 3/2
- 青赤青（BRB）: 1 − 1/2 + 1/4 = 3/4
色の並びが、その数の符号展開（0 から「+ なら右へ、− なら左へ」と単純な数を辿る道順）になっている、という規則。エンジンは棒を見ずに一般のゲームとして簡約するので、これは独立な検算になる。棒の値は「下から i 本だけ残した棒」の値を選択肢に持つので、色の列の木を深さ優先でたどれば 1 本 1 回の make で済む。
1〜22 本の青赤の棒 8,388,606 本の値が全部、符号展開の規則と一致した（161 秒）。
検算 2: コロン原理と融合原理（緑だけのグラフ）
緑だけの局面はどちらも同じ手が指せる不偏ゲームなので、値はニム数 *n になる。素朴には Sprague–Grundy の mex 規則（行ける局面のニム数に含まれない最小の非負整数）で求まるが、Winning Ways には探索なしで求める 2 つの原理がある。
- 融合原理: 閉路の上の頂点は全部 1 点にまとめてよい。閉路の辺はその点のループになり、ループ 1 本は辺 1 本の棒と同じ（*1）。
- コロン原理: 木になったら、頂点の値は「各枝の (枝の先の値 + 1)」のニム和（XOR）。
実装は、Tarjan の low-link で橋を見つけ（平行辺が橋にならないよう、親を頂点でなく辺の id で覚える）、橋でない辺の両端を Union-Find でまとめ、まとめた点ごとのループ本数の偶奇と、橋でできた木を地面から再帰する。
const colon = (x: number, from: number): number => {
let g = loops[x] & 1; // ループは 1 本で *1、偶数本で打ち消す
for (const y of tree[x]) if (y !== from) g ^= colon(y, x) + 1;
return g;
};
地面と頂点 3 個（または 4 個）の上の、ループと平行辺を許した緑のグラフ全部（辺のリストとして数え、全部の辺が地面に届くもの）で、mex による総当たり・融合＋コロン・エンジン（*n として）の 3 つを比べた。
| 地面 + | 辺の数 | グラフ | 融合 = mex | エンジン = *mex |
|---|---|---|---|---|
| 頂点 3 個 | 1〜9 | 61,741 | 61,741 | 61,741 |
| 頂点 4 個 | 1〜8 | 267,970 | 267,970 | 267,970 |
全部一致。ついでに、ニム数の偶奇は必ず辺の本数の偶奇と同じだった。コロン原理を見ると当然で、辺 1 本ごとにどこかで「+1」が 1 回入り、XOR は偶奇を変えない。頂点 4 個・辺 8 本では *0 が 100,375 個、*8 が 48 個。
検算 3: 値を使わない勝敗探索
最後は 3 色混ぜた局面。値の正しさを直接確かめる手はないが、勝敗だけなら、値を一切使わない素朴な探索（「相手が先手で負ける局面に行ける手があるか」をマスクでメモ化）で求まる。エンジンの値から出した勝敗（G ≥ 0 と G ≤ 0 から L / R / P / N）と、これを比べた。
あわせて、部分に分けて足した値と、分けずに全体から作った値が同じ id になるか（和と簡約の両方の検算）、青赤だけのグラフが必ず数になるか（エンジンが数を勝手に作り損ねていないか）も見た。対象は地面と頂点 3 個の上の、色付きのグラフ全部。
| 色 | 辺の数 | グラフ | 勝敗 = 探索 | 分けた値 = 全体の値 | 数 | 異なる値 |
|---|---|---|---|---|---|---|
| 青・赤 | 1〜6 | 133,954 | 133,954 | 133,954 | 133,954 | 115 |
| 青・赤・緑 | 1〜6 | 1,178,816 | 1,178,816 | 1,178,816 | 404,951 | 2,176 |
全部一致。青赤だけの 133,954 個は全部数で、先手必勝（N）は 1 つもない（数は 0 と比べられないことがないので当然）。3 色・辺 6 本の 1,007,389 個の内訳は、数 345,501、x + *m が 372,288、x + n·↑ + *m が 102,428、それ以外の一般の形が 187,172。
さらに、小さな絵を 3 つずつランダムに作り、値を足したものの勝敗と、3 つを 1 枚に並べた局面の素朴な探索の勝敗を 20,000 組比べて、これも全部一致した。
3 色の棒 797,160 本: 同じ値は 1 組もない
緑を混ぜた棒は、数でもニム数でもない値になる。12 本までの青・赤・緑の棒（3 + 9 + … + 312 = 797,160 本）の値を全部求めた（53 秒、登録されたゲームは 797,354 個）。
| 本数 | 棒 | 異なる値 | 数 | x + *m | x ± ↑* | その他 |
|---|---|---|---|---|---|---|
| 1 | 3 | 3 | 2 | 1 | 0 | 0 |
| 2 | 9 | 9 | 4 | 3 | 2 | 0 |
| 3 | 27 | 27 | 8 | 7 | 4 | 8 |
| 4 | 81 | 81 | 16 | 15 | 8 | 42 |
| 6 | 729 | 729 | 64 | 63 | 32 | 570 |
| 8 | 6,561 | 6,561 | 256 | 255 | 128 | 5,922 |
| 10 | 59,049 | 59,049 | 1,024 | 1,023 | 512 | 56,490 |
| 12 | 531,441 | 531,441 | 4,096 | 4,095 | 2,048 | 521,202 |
分かったこと:
- 異なる値の数がいつも棒の数と同じ。n 本の棒 3n 本は全部違う値。誕生日（その値が初めて作られる世代）は 7 本までなら全部の棒で本数と同じ（テストで全数確認）、12 本でも最大は 12。
- x + *m になるのは、青赤の棒 x の上に緑を m 本載せたものだけ（と、緑だけの棒 *n）。たとえば BG = 1*、BRG = 1/2*、BGG = 1*2。本数ごとに 2n − 2 + 1 個で、表の数と合う。これは数の形を見ただけでなく、該当する文字列全部について「x は下の青赤部分の符号展開、m は緑の本数」を 1 本ずつ確かめた（外れ 0）。
- x ± ↑* になるのは、青赤の棒の上に「緑、青」（↑*）か「緑、赤」（↓*）を載せたものだけ（と、2 本の GB = ↑*、GR = ↓*）。BGB = 1↑*、RGB = −1↑*。こちらも文字列ごとに確認して外れ 0。
- それ以外は一般の形になる。いちばん小さいのは 3 本の GBB = {0, ↑* | 0}、GBR = {0, * | 0, ↑*}、GGB = {0, *, *2 | 0, *}。3 本の棒 27 本のうち 8 本がもうこの形。
「緑が一番上に来るなら数 + ニム数、緑の上に 1 本だけ色が載るなら数 ± ↑*、それ以上だと一般の形」という段階になっていて、緑がどこまで深く埋まっているかで値の複雑さが決まっている。
ページのプリセット
最初に表示される「garden」は、青赤の家（値 1）、緑の木（*4）、緑の茎に青と赤の花びら（ループ）を付けた花（{0, *, *2 | 0, *}）、赤の辺（−1）、緑 2 本の棒（*2）の和で、全体は {0 | *6, *7}。青の手番で切れる 16 本のうち勝ちを保つのは 6 本だけ、という局面になるよう、右の 2 本の棒を 4 本以下の全部の青赤の棒 × 7 種の短い棒で総当たりして選んだ（最初の版は全体が 5/4 くらい青に傾いていて、ヒントが全部 ✓ になってしまった）。
ほかに、青赤の棒（符号展開）、小さな無限小（↑* など）、青赤の図形（必ず数になる）、緑の木（コロン原理）、緑の閉路（融合原理）、ランダムを用意した。編集モードでは点をクリックして辺を引き（同じ点ならループ）、辺をクリックで消せる。30 本まで。
作っていて引っかかったところ
-
Node 26 の TypeScript 直接実行は「型を消すだけ」。
constructor(private L: GameId[])のようなパラメータプロパティは JavaScript に無い構文なのでERR_UNSUPPORTED_TYPESCRIPT_SYNTAXで落ちる。フィールド宣言と代入に書き直した。import も./cgt.tsのように拡張子付きにする。 - 値の名前は比較で見つける。↑* や ⇑ は形からも分かるが、x + n·↑ + *m は止まり値で x を引いた後、表を id で引くのがいちばん確実だった（標準形が一意なので id の一致 = 値の一致）。
- 画面の値が長くなりすぎる。3 色の和は {5/4 | {5/4 | {5/4, 5/4* | …}}} のような入れ子になる。長いときは文字を小さくし、部分ごとの値も並べて出すようにした。
まとめ
- 標準形（支配の削除と可逆な選択肢の迂回）で簡約して id で持つエンジンを TypeScript で書き、ハッケンブッシュの任意の絵の値を出した。値が等しいことは id が等しいことになる。
- エンジンは Berlekamp の符号展開の規則（青赤の棒 8,388,606 本）、融合原理とコロン原理（緑のグラフ 329,711 個）、値を使わない勝敗探索（3 色のグラフ 1,312,770 個）、ランダムな和 20,000 組の全部と一致した。
- 12 本までの 3 色の棒 797,160 本は全部違う値で、x + *m（上に緑だけ）、x ± ↑*（上に緑ともう 1 本）、それ以外の一般の形、に文字列の形できれいに分かれた。
参考文献:
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, 2nd ed., vol. 1, A K Peters, 2001（ハッケンブッシュ、コロン原理・融合原理、↑ と *）
- J. H. Conway, On Numbers and Games, 2nd ed., A K Peters, 2001
- A. N. Siegel, Combinatorial Game Theory, Graduate Studies in Mathematics 146, AMS, 2013（標準形、支配と可逆な選択肢）
デモ: https://sen.ltd/portfolio/hackenbush/
リポジトリ: https://github.com/sen-ltd/hackenbush