Hex（ヘックス）をブラウザに実装した。六角形のマスでできたひし形の盤に交互に石を置き、赤（先手）は上と下の辺を、青は左と右の辺を自分の石の鎖でつなげば勝ち。盤が埋まると必ずどちらか一方だけがつながっているので、引き分けは起こらない。「先手必勝」は戦略泥棒の論法で分かるが、どこに打てば勝てるかは教えてくれない。そこで完全読みのソルバーを書き、ヒントを付けると空いた全部のマスに「ここに打てば勝ち（緑）／負け（赤）」が出るようにした。1 × 1〜5 × 5 の盤では全部の初手の勝敗を計算し、Hayward ら（2003 年の論文 Solving 7×7 Hex）の図 2 と 1 マスずつ照合して、51 マス全部が一致した。5 × 5 の勝ちの初手は 25 マス中 13 マス。枝刈りの規則は 2 つだけで、4 × 4 の全初手の合計ノード数を 1,613,807 から 6,077 に減らした。一方で、よく効くはずの history heuristic は 4 × 4 で 3.0 倍、5 × 5 の中央で 1.64 倍ノードを増やした。「つないだら負け」の misère Hex（リバース Hex）も付けた。テスト 11 件。ソルバー内蔵パズル第 91 弾。
デモ: https://sen.ltd/portfolio/hex-game/
リポジトリ: https://github.com/sen-ltd/hex-game
ルール
- n × n のひし形の盤。各マスは 6 つの隣を持つ（端は少ない）。
- 赤と青が交互に、空いたマスに自分の色の石を 1 つ置く。赤が先手。
- 赤は上の辺と下の辺を、青は左の辺と右の辺を、自分の石の鎖でつないだら勝ち。
1942 年に Piet Hein が考案し、1948 年に John Nash が独立に再発見した。Nash はプリンストンでこのゲームを広め、「先手必勝」の証明を与えたとされる。
なぜ引き分けがないのか
盤が全部埋まったとき、赤が上下をつないでいないなら、赤の石の塊は上の辺から下の辺まで届いていない。そうなると、赤の塊の「下側の縁」をなぞる青の石の列が左から右まで続いている。六角形の盤では 1 マスが 6 つの隣を持ち、4 マスが 1 点で接することがないので、「斜めにすり抜ける」ことができない。正方形の盤だと、斜めに接する 2 組の石が互いに交差したことになって、両方つながっていない局面が作れてしまう。
テストではこれを、2 × 2〜7 × 7 のランダムに埋めた盤 300 枚ずつで「ちょうど片方だけがつながっている」と確かめている（never draws）。
なぜ先手必勝なのか（でも勝ち手は分からない）
戦略泥棒の論法。後手に必勝法があったとする。先手はまず適当な 1 手を打ち、あとは「自分が後手だったら」としてその必勝法に従う。必勝法が最初の余分な石の場所に打てと言ったら、別の適当な場所に打つ。Hex では余分な石は損にならない（自分の石が多くて困ることはない）ので、先手はこれで勝ててしまう。必勝法が両方にあることはないので、矛盾。引き分けもないので、先手必勝。
この論法は「先手に必勝法がある」とは言うが、それが何かは言わない。どの初手なら勝てるかは、盤を実際に解かないと分からない。
ソルバー
局面の値は「手番の人が勝てるか」の 1 ビットだけ（引き分けがないので）。探索は置換表付きの素朴な深さ優先探索で、1 ビットの答えを返す。
行を整数で持つ
色ごとに、各行を 1 つの小さな整数（ビット c が c 列目）で持つ。マスの集合の「隣」は、この隣接（(r, c±1)、(r−1, c)、(r−1, c+1)、(r+1, c)、(r+1, c−1)）に合わせた数回のシフトで出る。
private dilate(src: Int32Array, dst: Int32Array) {
const n = this.n, full = this.full;
for (let r = 0; r < n; r++) {
const m = src[r];
let d = m | ((m << 1) & full) | (m >> 1);
if (r > 0) d |= src[r - 1] | (src[r - 1] >> 1);
if (r < n - 1) d |= src[r + 1] | ((src[r + 1] << 1) & full);
dst[r] = d;
}
}
「置けば鎖が完成するマス」は、片方の辺から届く自分の石（塗りつぶし）の隣と、もう片方の辺から届く石の隣の、共通部分の空きマスになる。塗りつぶしは dilate して自分の石と AND を取るのを、変化がなくなるまで繰り返すだけ。
置換表
キーは赤と青の石のビット列を double に入れたもの（53 マスまで正確なので 7 × 7 まで）。盤を 180° 回すと同じゲームになる（赤の上下・青の左右がそれぞれ入れ替わるだけ）ので、回した盤とキーの小さい方を使い、1 エントリを共有する。
枝刈り 1: 即勝ち・一本の脅し・二本の脅し
- 自分に「置けば完成するマス」があれば勝ち。
- 相手に完成するマスが 2 つあれば負け（1 つしかふさげない）。
- 相手に 1 つなら、そこが唯一の手。
枝刈り 2: 「二本の脅しを作るマス」への対応だけを候補にする
もう一歩先を読む。
- 自分に「置くと完成するマスが 2 つできるマス」があれば勝ち（相手は 1 つしかふさげない）。
- 相手が x に置くと完成するマスが 2 つ以上（集合 Y）できるなら、それは相手の脅しで、自分は {x} ∪ Y の中に打たなければ負ける。|Y| ≥ 3 なら Y のどの 2 つでも脅しは成立するので、必ず打つべきなのは x そのものだけになる。
- 候補手は、全部の脅しの「打つべき範囲」の共通部分。
なぜ範囲の外に打っても無駄なのか。相手の脅しは「相手が 1 手先に打てば、その範囲（キャリア）の中だけで必ずつながる」ものなので、範囲の外の手は範囲の中に何の影響も与えない。では範囲の外の手で自分が先につなげばよいかというと、それもできない。自分の鎖は相手の鎖を横切らなければならないので、相手が必ずつながれる局面で自分がつながることはない。
private candidates(p: Player, o: Player, list: Int8Array, empties: number): number {
// p first: a cell that leaves two completing cells wins outright
this.analyze(p);
if (this.doubleThreats(null) > 0) return -1;
this.analyze(o);
const must = this.mustRows[empties];
must.fill(this.full);
const threats = this.doubleThreats(must);
return this.fillOrder(p, list, threats ? must : null, empties);
}
この判定は 1 ノードあたりの計算が重い。最初の実装は空きマスごとに石を仮に置いて「完成するマス」を数え直していて、5 × 5 の (0, 1) は 4,209,953 ノードに 27.2 秒、1 秒あたり約 15 万ノードだった（枝刈りの無い misère の探索は 4 × 4 で 1 秒あたり約 140 万ノード）。そこで差分で数える形に直した。相手が x に置いて新しくできる完成マスは、
- x がどちらの辺の「届く範囲」にも触れていなければ、ない（いまの完成マスは 0 個だと分かっている）。
- x が上の辺側の範囲に触れるなら、「下の辺側から届く範囲に接するマス」のうち、x と x につながる石の塊に隣接するマスだけ。
石の塊ごとに「塊＋隣」の行マスクを先に作っておけば、x ごとの計算は数行の AND で済む。枝刈りの中身は同じなので、ノード数は前の版とまったく同じになる（5 × 5 の (0, 1) が両方とも 4,209,953 ノード。表の 5 × 5 の数字は前の版で回したもの）。
結果: どの初手なら勝てるか
記録は全部 runs/ に 1 初手 1 行の JSON で残してある（tools/solve-openings.mts）。初手ごとに置換表を新しくするので、ノード数は実行順に左右されない。
| 盤 | 勝ちの初手 | 図 2 と一致 | 全初手の合計ノード |
|---|---|---|---|
| 1 × 1 | 1 / 1 | 1 / 1 | 0 |
| 2 × 2 | 2 / 4（鈍角の角） | 4 / 4 | 6 |
| 3 × 3 | 5 / 9 | 9 / 9 | 54 |
| 4 × 4 | 4 / 16（短い対角線ちょうど） | 16 / 16 | 6,077 |
| 5 × 5 | 13 / 25 | 25 / 25 | 229,135,972 |
| 6 × 6 | — | — | 18 初手とも 2,000 万ノード以内に決着せず |
5 × 5 は 13 マスを解き、残る 12 マスは 180° 回した盤と同じゲームなので回したマスの結果を使った（盤も図 2 も 180° 対称であることはテストで確かめている）。
4 × 4 の結果がきれいで、勝てる初手は短い対角線（鈍角の角から鈍角の角へ）の 4 マスだけ。
. . . W
. . W .
. W . .
W . . .
5 × 5（W が勝ちの初手、行 0 が上の辺）:
. . . . W
. W W W W
. W W W .
W W W W .
W . . . .
論文の図 2 との照合
Hayward, Björnsson, Johanson, Kan, Po, van Rijswijck の Solving 7×7 Hex: Virtual Connections and Game-State Reduction（Advances in Computer Games, 2004）の図 2 には、1 × 1〜6 × 6 の全初手について「そこに初手を打ったら、最善同士でどちらが勝つか」が石の色で描いてある。6 × 6 は van Rijswijck が 2002 年に計算機で出したもの。
照合には 2 つ注意がいる。
- 論文は White（白）が先手で、盤をダイヤ形（左右に鋭角の角が来る向き）に描いている。先手の辺は右上と左下。
- 図は画像なので、ページを 400 dpi で描き出し、目で読んで転記した。
src/literature.tsに、ダイヤの段ごとに「F（先手勝ち）／S（後手勝ち）」の文字列で置いてある。
こちらの盤の鋭角の角 (0, 0) をダイヤの右端、(n−1, n−1) を左端、(0, n−1) を上端、(n−1, 0) を下端に置くと、こちらの先手の辺（行 0 と行 n−1）がちょうど右上と左下に来る。ダイヤの段 k は r − c = k − (n−1) のマスで、段の中は r + c の大きい順に左から並ぶ。
export function diamondCells(n: number): [number, number][][] {
const levels: [number, number][][] = [];
for (let k = 0; k < 2 * n - 1; k++) {
const d = k - (n - 1); // r - c
const level: [number, number][] = [];
for (let r = 0; r < n; r++) {
const c = r - d;
if (c >= 0 && c < n) level.push([r, c]);
}
level.sort((a, b) => b[0] + b[1] - (a[0] + a[1])); // left to right: r + c descending
levels.push(level);
}
return levels;
}
テストは「各段のマス数が図の文字数と同じ」「全マスがちょうど 1 回ずつ出てくる」ことを確かめてから比べる。結果は 1 × 1〜5 × 5 の 51 マス全部が一致。鋭角と鈍角を取り違えていたら 2 × 2（鈍角が勝ち・鋭角が負け）の 4 マスが全部食い違うので、その種の向きの誤りは最初の盤で見つかる。
文献にある規則性
図からも計算からも、論文やその後の文献が挙げている規則性が読み取れる。テストで 2 × 2〜5 × 5（こちらの計算）と 6 × 6（図）について確かめた。
- 鋭角の角への初手は負け（Beck, 1969。n ≥ 2 の全部の盤で証明されている）。
- 鋭角の角の隣で、先手自身の辺にあるマスも負け（Beck, n ≥ 3）。
- 短い対角線のマスは全部勝ち、先手自身の辺のマスは（短い対角線の 1 マスを除いて）全部負け。論文が 7 × 7 以下で観察して「一般に成り立つかは興味深い問題」と書いているもの。
5 × 5 で重いのはどの初手か
| 初手 | 結果 | ノード |
|---|---|---|
| (1, 4) | 勝ち | 34,663,791 |
| (0, 4)（鈍角の角） | 勝ち | 31,409,592 |
| (1, 1) | 勝ち | 31,323,533 |
| (2, 0) | 負け | 20,498,236 |
| (2, 2)（中央） | 勝ち | 9,941,706 |
| (0, 1) | 負け | 4,209,953 |
勝ちの初手が重い。勝ちを示すには、青のすべての応手（24 通り）に対して赤の勝ち手を見つけなければならない。負けの初手は青の勝ち手を 1 つ見つければ済む。例外は中央で、勝ちの初手の中で一番軽い（ほかの勝ちの初手は 2,143 万〜3,466 万ノードで、その半分以下）。理由までは確かめていない。
枝刈りの効き目
全初手の合計ノード数（初手ごとに置換表を新しくした）。
| 盤 | 素朴な探索 | 枝刈り 1 | 枝刈り 1 + 2 | 1 + 2 + history |
|---|---|---|---|---|
| 3 × 3 | 2,535 | 601 | 54 | 63 |
| 4 × 4 | 1,613,807 | 209,118 | 6,077 | 18,359 |
4 × 4 では、枝刈り 1 で 7.7 分の 1、枝刈り 2 を足すとさらに 34 分の 1、合計で 266 分の 1 になる。5 × 5 では差がもっと開き、(0, 1) は枝刈り 1 だけだと 2 億ノードの上限でも決着しなかった（枝刈り 2 なら 4,209,953 ノード）。
意外だったのは history heuristic（過去に枝を切った手を先に試す、チェスなどでよく効く手順序）で、Hex ではノード数を増やした。4 × 4 で 6,077 → 18,359（3.0 倍）、5 × 5 の (0, 1) で 4,209,953 → 5,159,438（1.23 倍）、中央で 9,941,706 → 16,327,774（1.64 倍）。既定の手順序は「中央から近い順」で、Hex の勝ち手は中央寄りにあることが多い。history は「前に枝を切ったマス」を優先するので、端の方の「たまたま一度効いたマス」に探索を引っ張っていく。
6 × 6 は届かなかった
6 × 6 の 18 初手（残りは 180° 回転）を、1 初手あたり 2,000 万ノード（1 本 65〜118 秒）の上限で回したが、1 つも決着しなかった。鋭角の角 (0, 0) のように理論的に負けと分かっている初手でもだめだった。負けを示すには、青の勝ち手を見つけたうえで、その後の赤の全部の手に対して青の勝ちを示す必要がある。
Hayward らが 7 × 7 を解いたのは、ここで使った「二本の脅し」を一般化した**仮想連結（virtual connection）**を、AND・OR の合成規則で盤全体について計算する方法（H-search）による。二本の脅しは、その一番浅い場合（キャリアが 3 マス以下の半連結）にあたる。5 × 5 まではこれで足りるが、6 × 6 ではブリッジ（共通の空きマスを 2 つ持つ 2 つの石）や辺のテンプレートを鎖としてつなぐ必要がある。ページの対戦も 5 × 5 までにした。
misère Hex: つないだら負け
「自分の辺をつないだ方が負け」にした変種。盤が埋まると必ずどちらかがつながるので、これも引き分けがない。Lagarias と Sleator（1999）が「n が偶数なら先手、奇数なら後手が勝つ」ことを示している（負ける側は最後の 1 マスまで負けを引き延ばせる、という論法）。また、偶数の盤では鋭角の角が勝ちの初手になる。
| 盤 | 先手必勝？ | 勝ちの初手 | ノード |
|---|---|---|---|
| 2 × 2 | はい | 2 / 4（鋭角の角） | 24 |
| 3 × 3 | いいえ | 0 / 9 | 2,279 |
| 4 × 4 | はい | 14 / 16（(1, 2) と (2, 1) 以外） | 16,468,500 |
どちらの定理も成り立っている。通常の Hex では負けの鋭角の角が、misère では勝ちに変わる。4 × 4 で負けの 2 マスは、通常の Hex で勝ちだった短い対角線の内側の 2 マス。misère の探索には「二本の脅し」が使えない（脅しは「つながってしまう危険」なので逆向きになる）ので素朴な探索のままで、4 × 4 で 1,647 万ノードかかった。
ページの作り
- 探索は Web Worker で、空きマスを中央から順に 1 マスずつ解いては結果を送る。1 マスあたり 15 万ノードの上限を付け、超えたマスは「?」で出す。
- 5 × 5 の空の盤は計算済みの表から即座に出す。1 手目の後も、その初手が勝ちなら青のどの応手も負けなので、表から全マス赤の点を出せる（厳密）。
- それ以降は Worker の探索。スクリーンショットの局面（赤が中央、青が (1, 3)、赤が (3, 1)、青が (2, 1)）は 110,374 ノード・約 0.5 秒で全 21 マスが決まり、赤の勝ち手は 3 つ。
- コンピュータは、勝ちのマスが見つかった時点でそこに打つ。勝ちが無ければ上限超えのマス、それも無ければ一番中央の負けのマスに打つ。
テスト（11 件）
- 盤の形（鋭角の角の隣は 2 つ、鈍角の角は 3 つ、内側は 6 つ）
- 引き分けがないこと（2 × 2〜7 × 7 のランダムに埋めた盤 300 枚ずつ）
- 行マスクで求めた「完成するマス」が、1 マスずつ石を置いて確かめた結果と一致すること（3 × 3〜6 × 6）
- 枝刈り 0・1・2 と history ありの全部が、置換表も枝刈りも無い素朴なミニマックスと、ランダムな 3 × 3・4 × 4 の局面で一致すること
- misère Hex も素朴なミニマックスと一致すること
- ノード上限で打ち切っても盤が元のままであること
- 図 2 の転記がダイヤの段の形に合い、全部のマスを 1 回ずつ通り、180° 対称であること
- 図 2 と、n ≤ 4 をその場で解き直した結果、
openings.jsonの全部が一致すること - 文献の規則性（Beck の 2 つ、短い対角線、先手の辺）
- misère の偶奇の定理
まとめ
- Hex には引き分けがなく、戦略泥棒の論法で先手必勝だが、勝ち手は解かないと分からない。1 × 1〜5 × 5 の全初手を解いて、Hayward ら（2004）の図 2 と 51 マス全部が一致した。5 × 5 の勝ちの初手は 13 / 25、4 × 4 は短い対角線の 4 マスだけ。
- 「相手の二本の脅しのキャリアに打つ」という 1 つの規則で 4 × 4 の全初手の合計ノードが 34 分の 1 になった（素朴な探索から通算で 266 分の 1）。一方 history heuristic は 4 × 4 で 3.0 倍、5 × 5 の中央で 1.64 倍ノードを増やした。
- 6 × 6 は 1 初手 2,000 万ノードでは 1 つも決着しなかった。ここから先は仮想連結（H-search）が要る。misère Hex は 2 × 2〜4 × 4 で Lagarias–Sleator の偶奇の定理どおり。
参考文献:
- R. Hayward, Y. Björnsson, M. Johanson, M. Kan, N. Po, J. van Rijswijck, "Solving 7×7 Hex: Virtual Connections and Game-State Reduction", H. J. van den Herik, H. Iida (eds.), Advances in Computer Games, IFIP vol. 263, Kluwer, 2004（図 2 は p. 263。2026 年 10 月 21 日参照、図は目で転記）
- P. Henderson, Playing and Solving the Game of Hex, PhD thesis, University of Alberta, 2010（§2.7: Beck の鋭角の角の結果、misère Hex）
- J. Lagarias, D. Sleator, "Who wins misère Hex?", E. Berlekamp, T. Rodgers (eds.), The Mathemagician and Pied Puzzler, A K Peters, 1999, pp. 237–240
デモ: https://sen.ltd/portfolio/hex-game/
リポジトリ: https://github.com/sen-ltd/hex-game