**ドミニアリング（Domineering、別名 Stop-Gate / Crosscram）をブラウザに実装した。組合せゲーム理論（CGT）の教科書に必ず出てくるゲームで、ルールは「V は縦、H は横にドミノを置く。置けなくなった方の負け」だけ。完全に読み切るプレイヤーと対戦でき、ヒントを付けると自分が置けるすべての手に緑（勝ちを保つ）／赤（相手に勝ちを渡す）**の点が出る。ソルバーは TypeScript だけで、ページでは Web Worker、表の計算では Node で同じファイルを動かした。H が先手の m×n は、V が先手の n×m を転置したものと同じゲームなので、「どちらが勝つか」の表は盤の形ごとに 1 回の探索で埋まる。52 マス以下・辺 30 以下の全 173 形を 1 回 4,000 万ノードの上限で解き、144 形が終わって 140 盤の勝者（V／H／先手／後手）が決まり、Nathan Bullock の公開表と 140 盤全部一致（表に直接ある 108 盤と、表に行がないので転置して読んだ 32 盤）。Bullock の表自身も転置の対称性を 121 組全部満たしている。上限に届いたのは 40〜52 マスの 29 形で、7×7 はその 1 つ。「安全手」の上界と鏡像の同一視は、6×6 で 1,195 万ノードを 281 万ノードに、5×7 で 1,380 万を 130 万に減らした。テスト 12 件。ソルバー内蔵パズル第 84 弾。
デモ: https://sen.ltd/portfolio/domineering/
リポジトリ: https://github.com/sen-ltd/domineering
ルール
マス目の盤に、2 人が交互にドミノ（2 マス分）を置く。
- **V（Left）**は縦向きにしか置けない。
- **H（Right）**は横向きにしか置けない。
- 自分の番に置ける場所がなかったら負け（normal play）。
引き分けはない。盤と先手が決まれば、勝つのは「V」「H」「先手」「後手」のどれかに必ず決まる。CGT ではこれを結果類（outcome class）と呼び、L／R／N／P と書く。この記事では Bullock の表に合わせて V／H／1／2 と書く。
CGT 的に面白いのは、盤が途中で独立した領域に分かれると、それぞれの領域が独立したゲームの「和」になることだ。2×1 の横長の盤は H だけが 1 手打てるので −1、2×2 は ±1（どちらも打ちたい「熱い」ゲーム）、2×3 は {2 | −1/2}。テストではこのあたりの手計算の値を、ソルバーの勝敗と照合している。
何ができるか
- rows／cols で 2×2〜8×8（ただしページ内は 36 マスまで）を選ぶ。「you play」で V か H、「first move」でどちらが先手か。
- ヒントを付けると、置ける手 1 つ 1 つの真ん中に点が出る。縦の手は横の境界線上、横の手は縦の境界線上に点が来るので、全部同時に出しても重ならない。
- 右上は今の局面の「手番側が勝つか」「勝つ手の数・負ける手の数」と、後で説明する安全手の上界の数字。
- 右下は空の m×n 盤で誰が勝つかの表（この記事の本題）。36 マス以下のセルはクリックするとその盤に切り替わる。
ソルバー
src/solver.ts は「手番側が勝つか」だけを厳密に答える。手番側の手のどれかが「相手の負け局面」に行けば勝ち、という素直な深さ優先探索に、次の 4 つを足した。
1. 盤を縦横 2 通りのビット列で持つ
占有状態を「行ごとのビット列（ビット = 列）」と「列ごとのビット列（ビット = 行）」の両方で持つ。すると
- H の手 = ある行で隣り合う 2 つの空きビット
- V の手 = ある列で隣り合う 2 つの空きビット
になって、両者が同じコードを、2 つの配列を入れ替えて走らせるだけになる。空きビット列 free から置ける位置は free & (free >> 1) の 1 行。
2. 置換表は鏡像 4 つの最小値をキーにする
長方形の盤は、上下反転・左右反転・その両方で縦横の向きが変わらないので、同じ勝敗になる。キーは「4 つの鏡像を 2 進数で読んだ値の最小値」。52 マスまでなら盤全体が 2^52 未満の整数で、JavaScript の double で厳密に表せるので、キーはただの number になる。4 つの鏡像のキーは、マスごとの重み（鏡像ごとに別の 2 のべき）を手ごとに足し引きして差分更新する。表は 1 バケット 2 スロット（部分木の大きい方を残すスロットと、常に上書きするスロット）。
3. history heuristic
β カットを起こした手に点を足して、次からその手を先に試す。
4. 安全手の上界
ドミニアリングのソルバーの定番（Breuker・Uiterwijk・van den Herik の 8×8 解析、Bullock の Obsequi）の簡易版。
安全手とは、相手が絶対に潰せない自分の置き場所のこと。V なら、縦に並んだ 2 つの空きマスで、両方とも左右の隣が埋まっている（か盤の外）もの。H はそこに横ドミノを置けないので、この場所は最後まで V のものだ。互いに重ならないように数える。
一方、相手がこれから打てる手の数には上限がある。相手の向きに並んだ空きマスの連なりが長さ k なら、そこに入るドミノは ⌊k/2⌋ 個まで。全部足したものを max とする。
手番 p、相手 o として:
- safe(o) ≥ max(p) なら p の負け。p が何を打っても、o は安全手で応じ続けられる。
- safe(p) > max(o) なら p の勝ち。o が打てる限りを打ち尽くしても、p にはまだ安全手が残る。
どちらかが成り立てば探索せずに決まる。ページの右上の表は、この 4 つの数をいまの局面で出している。
転置で表が半分になる
盤を転置（行と列を入れ替え）すると、縦のドミノは横のドミノになる。つまり
H が先手の m×n ＝ V が先手の n×m
なので、どの盤でも聞くことは「V が先手で勝つか」の 1 種類だけでよい。m×n のセルは (m, n) と (n, m) の 2 回の結果を組み合わせて決まる。
| V 先手で m×n に勝つ | V 先手で n×m に勝つ（＝ H 先手で m×n に勝つ） | 結果 |
|---|---|---|
| ○ | × | V（どちらが先手でも V） |
| × | ○ | H |
| ○ | ○ | 1（先手勝ち） |
| × | × | 2（後手勝ち） |
当然、公開されている表もこの対称性を満たしていないとおかしい。Bullock の表（m, n ≤ 11 の 121 組）で、(m, n) の値の V と H を入れ替えたものが (n, m) の値になっているかをテストで確かめたら、121 組全部満たしていた。「1h」（先手勝ちか H 勝ちのどちらか、まだ分からない）のような未確定のセルも、転置側はちゃんと「1v」になっている。
もう 1 つ、この対称性のおかげで、Bullock の表に行がない 12 行以上の盤（n×1、n×2、n×3）も、転置したセルを読めば照合できる。
52 マスまでの全 173 形を解いた
npm run table は、辺が 30 以下で 52 マス以下の全 173 形について「V が先手で勝つか」を、1 形 1 プロセスで並列に解く（Node 26、12 コアの Mac mini で 10 並列）。1 回の上限は 4,000 万ノード。上限に届いたものは「未解決」として表に残す。
結果:
- 173 形中 144 形が上限内に終わり、(m, n) と (n, m) の両方が終わった 140 盤の結果が決まった。内訳は V 56、H 56、先手勝ち 24、後手勝ち 4。
- 後手勝ちの 4 盤は 1×1、5×5、2×13、13×2。
- 140 盤すべてが Bullock の表と一致した。表に直接ある 108 盤と、転置して読んだ 32 盤。不一致は 0。
- 上限に届いたのは 40〜52 マスの 29 形。7×7、6×7、6×8、5×8〜5×10、4×11〜4×13、3×15〜3×17、2×22〜2×26 とその転置（ただし 22×2〜25×2 は終わり、26×2 だけ未解決）。
正方形の盤だけ抜き出すとこうなる。
| 盤 | 結果 | V 先手のノード数 |
|---|---|---|
| 1×1 | 2 | 1 |
| 2×2 | 1 | 2 |
| 3×3 | 1 | 7 |
| 4×4 | 1 | 152 |
| 5×5 | 2 | 19,403 |
| 6×6 | 1 | 2,810,547 |
| 7×7 | — | 上限（4,000 万） |
7×7 は Bullock の表では先手勝ちで、Breuker らは 2000 年に 8×8、Bullock は 2002 年に 10×10、Uiterwijk は 2016 年に 11×11 を解いている。この簡易版の上界と history heuristic だけでは 49 マスの正方形に届かない、というのがこの計算の正直な到達点だ。
終わった中で重かったもの
| 盤 | V 先手 | ノード数 |
|---|---|---|
| 4×10 | 負け | 33,153,602 |
| 14×3 | 勝ち | 29,831,474 |
| 25×2 | 勝ち | 26,945,334 |
| 10×4 | 勝ち | 24,883,511 |
| 3×14 | 負け | 19,484,744 |
広い正方形よりも、細長い帯が重い。2 行の帯を並べてみると分かりやすい。
| n | 2×n の結果 | V 先手で 2×n（V が帯を横切る向き） | V 先手で n×2（V が帯に沿う向き） |
|---|---|---|---|
| 16 | H | 負け・106,978 | 勝ち・9,345 |
| 18 | 1 | 勝ち・614,460 | 勝ち・330,379 |
| 19 | 1 | 勝ち・2,481,373 | 勝ち・18,328 |
| 20 | H | 負け・106,866 | 勝ち・93,505 |
| 21 | H | 負け・3,845,113 | 勝ち・934,554 |
| 22 | H（Bullock） | 上限 | 勝ち・155,465 |
| 25 | H（Bullock） | 上限 | 勝ち・26,945,334 |
V が帯を横切る向き（2×n）で先手を持つと、V の 1 手は 1 列をまるごと埋めて帯を 2 つに切る。切れた帯は独立したゲームの和になるが、このソルバーはそれを和として扱わず、全部まとめて探索するので、組合せが爆発する。2×n の帯は CGT の言葉では「切れた部分の値を足す」だけで扱えるので、理論的には簡単な方の盤だ。Bullock の表が 2×30 まで埋まっているのに、ここでは 2×22 で止まるのはそのせいだろう。理論で簡単な盤と、探索で簡単な盤は違う。
安全手と鏡像は効いているか
上界と鏡像の同一視を、それぞれ切ったときのノード数（V 先手）。
| 盤 | どちらもなし | 鏡像だけ | 安全手だけ | 両方 |
|---|---|---|---|---|
| 5×5 | 143,024 | 50,899 | 46,771 | 19,403 |
| 5×6 | 2,489,050 | 915,462 | 939,338 | 290,182 |
| 5×7 | 13,796,531 | 6,231,601 | 3,907,518 | 1,303,124 |
| 7×5 | 6,118,865 | 5,140,367 | 1,075,444 | 1,038,084 |
| 6×6 | 11,954,894 | 7,440,057 | 7,890,692 | 2,810,547 |
両方入れると 6×6 で 4.3 倍、5×7 で 10.6 倍ノードが減る。どちらか片方だけだと 1.2〜3.5 倍くらいで、2 つを合わせると掛け算以上に効く盤がある（5×7 は片方ずつだと 2.2 倍と 3.5 倍、両方で 10.6 倍）。鏡像で表がよく当たるようになると、上界で切れた局面の情報も鏡像側に効くからだと思う。
秒数は表に載せていない。このアブレーションは表の計算と同じマシンで同時に走らせたので、負荷が時間によって違い、秒は比べられない。ノード数はどちらの設定でも決定的（乱数なし）なので、何度回しても同じ値になる。
なお、安全手の上界は 1 ノードあたりの計算が重いので、ノード数が減ったほど秒は減らない。Breuker らや Bullock のソルバーは、もっと細かく「相手に潰されうる手」まで数える上界を使っていて、これはその一番素朴な版だ。
ページの中で解く
ページは手番が変わるたびに Worker を作り直して、手番側の全部の手について「その手を打ったら相手の負けか」を順に判定し、1 手終わるごとに結果を送ってくる（点が順に緑・赤に変わる）。置換表は 1 局面の判定のあいだ使い回すので、1 手目の反駁で作った表が 2 手目以降に効く。
上限は 1 局面 4,000 万ノードを手の数で割ったもの。空の 6×6 だと 30 手それぞれ 133 万ノードまでで、手元の Chromium では 3.4 秒・857 万ノードで 15 手が勝ち、12 手が負け、3 手が上限で灰色のまま残った。コンピュータの手番では、勝つ手があればその中からランダムに、なければ「反駁に一番ノードがかかった手」（一番しぶとい手）を打つ。
テスト
npm test（vitest）で 12 件。
- 600 個のランダム局面（4×5 まで）で、置換表も上界も手の並べ替えもない素朴なミニマックスと勝敗が一致する。
- 安全手の上界と鏡像の同一視の on/off 4 通りで、5×5 のランダム局面 150 個の勝敗が変わらない。上界が発火したときは、素朴なミニマックスとも一致する（400 局面中 50 回以上発火することも確認）。
-
analyze()が「勝つ手があるとき、かつそのときに限り」勝ちの手を出す。 - 1×1 = 0、2×2 = ±1、2×3 = {2 | −1/2} とその中の −1/2 の局面。
- 24 マス以下の全盤で「H 先手の m×n ＝ V 先手の n×m」。Bullock の表 121 組の転置対称性。
- 30 マス以下の全盤をテストの中で一から解いて Bullock の表と一致。
src/table.jsonの 140 盤も一致。
まとめ
- H 先手の m×n は V 先手の n×m。表は形ごとに 1 回の探索で埋まり、公開表もこの対称性を 121 組全部満たしている。
- 52 マスまでの 173 形のうち 144 形が 4,000 万ノード以内に終わり、140 盤が Bullock の表と全部一致（転置して読んだ 32 盤を含む）。
- 重いのは広い正方形より細長い帯。2×n は理論（CGT の和）では簡単でも、和を使わない探索では 2×22 で止まる。
- 安全手の上界と鏡像の同一視は、両方そろうと 6×6 で 4.3 倍、5×7 で 10.6 倍効く。
参考文献:
- Nathan Bullock, "Domineering: Solving Large Combinatorial Search Spaces", M.Sc. thesis, University of Alberta, 2002
- Nathan Bullock, "Updated Game Theoretic Values for Domineering Boards", http://webdocs.cs.ualberta.ca/~games/domineering/updated.html（2026 年 10 月 14 日参照）
- D. M. Breuker, J. W. H. M. Uiterwijk, H. J. van den Herik, "Solving 8×8 Domineering", Theoretical Computer Science 230, pp. 195–206, 2000
- J. W. H. M. Uiterwijk, "11×11 Domineering Is Solved: The First Player Wins", Computers and Games 2016
- Michael Lachmann, Cristopher Moore, Ivan Rapaport, "Who Wins Domineering on Rectangular Boards?", More Games of No Chance, MSRI Publications 42, 2002
- E. R. Berlekamp, J. H. Conway, R. K. Guy, "Winning Ways for Your Mathematical Plays"
デモ: https://sen.ltd/portfolio/domineering/
リポジトリ: https://github.com/sen-ltd/domineering