ゴブレットゴブラーズを解く
ゴブレットゴブラーズは積み重ねの仕組みを持つ三目並べの変種で、子ども向けゲーム（5歳以上）として販売されている。私はこれを完全に解き、最善手を探索できるウェブ版エクスプローラを作った。先手が13手で勝ちである。
この解析は初期局面から到達可能なすべての局面、531,557,711局面を対象とした後退解析である。出力は、合法的に到達できる任意の局面について正確な結果と結果までの距離を与えるテーブルベースだ。
| 項目 | 結果 |
|---|---|
| 結果 | 先手勝ち |
| 初期局面からの勝ちまでの距離 | 13手 |
| 到達可能な正規化局面数 | 531,557,711 |
| 引き分け局面数 | 208,563 (0.04%) |
| 最も深い必勝 | 23手 |
ソース： github.com/brianhliou/gobblet-gobblers
各合法手は真の結果によって色分けされている。緑は勝ち、赤は負け。
ゲームの概要
3×3の盤、2人で対戦する。各プレイヤーは6個の駒（小2個、中2個、大2個）を持ち、最初は6個すべてが手駒である。自分の色を縦・横・斜めのいずれかに3つ並べて見せれば勝ちだ。
手番の行動
各手番では次の2つのうち1つを行う。
- 手駒から駒を盤上に置く、または
- すでに盤上にある自分の駒を別のマスへ動かす。
いずれの場合も駒は空きマスに着地するか、自分か相手の厳密に小さい駒を覆ってゴブルする。スタックは一番上だけが見え、並びに数えられるのも一番上の駒だけで、持ち上げて動かせるのも一番上の駒だけだ。
露出のルール
駒をマスから動かすと、その下にあったものが露出する。しかもそれは自分の駒が別の場所に着地する前に起こる。相手の色の完成した並びを露出させたまま放置することはできない。駒を持ち上げると相手の三目並べが露出する場合、その駒はその3マスのいずれかに戻って覆わなければならない。どのマスにも届かないなら、その持ち上げは非合法だ。
最も鋭い戦術はここから生まれる。駒はピンされることがある。相手の並びを覆っている唯一の存在なので動けないのだ。スタックはその後の多くの手を制約する履歴を抱える。手番側に合法手がまったくない場合はその側の負けであり、どちらも進展できない場合は繰り返しによる引き分けとなる。
見えない情報
実物のゲームでは覆われた駒は隠される。ゴブルされた駒の下を覗いてはいけないので、何があるかを記憶しておく必要があり、実際の対戦はある程度記憶ゲームになる。今回の解析は完全情報を前提とし、双方が覆われた駒をすべて知っているものとした。エクスプローラが全スタックを表示するのも同じ理由で、テーブルベースが評価しているのと同じ局面を正確に見られるようにしている。
後退解析
繰り返しのルールがあるため、素直な手法は使えない。position → outcome のキャッシュを用いた前向きのミニマックスは各局面に単一の値があると仮定するが、3回の繰り返しのもとでは局面の値はそこに至った経路に依存する。同じ盤面でも3回目の出現なら引き分け、1回目なら勝負が続く。局面ごとに1つの値をキャッシュするのは不健全だ。（これはGraph History Interaction問題である。）
後退解析はグラフ全体を後ろから解き、経路は一切関与しない。2つの段階がある。
- 幅優先の走査で初期局面から到達可能なすべての正規化局面を、局面をキーとして列挙する。合流（トランスポジション）は1つのノードにまとまる。
- 後退帰納で不動点に達するまで値を埋める。終端局面を種として与え、変化がなくなるまで繰り返す。
// one round over the still-unknown positions
for &pos in &unknown {
let mut win = false; // a move reaches a loss for the opponent
let mut all_children_decided_win = true;
for child in moves(pos) {
match value[child] {
Loss => { win = true; break; }
Unknown => all_children_decided_win = false,
Win => {}
}
}
if win { set(pos, Win) }
else if all_children_decided_win { set(pos, Loss) }
// else leave Unknown: it resolves in a later round, or it's a draw
}
引き分けに特別な処理は不要だ。不動点が決して解決しない局面、つまりどちらも結果を強制できない循環に閉じ込められた局面がそれである。解析のどこにも繰り返しのカウンタは現れない。局面が引き分けになるのは、最善手が負けを避けるには永遠に繰り返すしかない場合に限られ、それが未解決集合そのものだ。これはチェスやチェッカーの終盤テーブルベースを支える手法と同じである。
結果
初期局面から到達可能な正規化局面は531,557,711で、初期局面は先手の13手勝ちである。370,974,636の非終端局面では結果がほぼ均等に分かれ、185,455,752が先手勝ち、185,310,321が後手勝ち、引き分けはわずか208,563（0.04%）だ。到達可能なすべての局面はどちらかの必勝か引き分けであり、未決着のものは残らない。
注目すべき発見
ほとんどの勝ちは即決で、23手までの細い尾がある。 全局面の83%では手番側に即座に勝てる手が既に存在する。それを超えると、勝ち局面は距離が伸びるにつれて急速に減り、ほぼ例外なく奇数手に落ちる。尾は23手の必勝1つに絞られ、これがゲーム中最も深く、到達する局面はわずか9つだ。
その最も深い勝ちは極限まで鋭い。この局面で先手には26の合法手があり、勝ちを保つのはちょうど1つ（中央のスタックから中を滑らせる手）だけで、残りの25手は負けになる。しかも勝ちまではまだ23手ある。
序盤はサイズによって全か無かであり、しかも単調ではない。 27通りの初手のうち、小の配置と大の配置はすべて勝ちだが、中の配置はすべて負けで、後手に必勝を渡してしまう。中は相手がまだゴブルできる最大の駒だ。これに大で応じれば、中央から唯一の勝ちとなる応手となり、決して露出しない駒でそのマスを取り、中は下に埋まる。大はまったくゴブルされないし、小は覆うために大きい駒を使う価値がない。取られを招くのは中間のサイズだけである。
勝ち手が1つだけの場合も多い。 勝ち局面の12.7%では勝ちを保つ手が1つしかなく、他のすべての手は勝ちを逃す。上で挙げた最も深い勝ちは極端な例で、26手中1つだけが救いの手だ。
局面の4分の1近くにピンされた駒がある。 局面の22.8%では、ある駒を持ち上げると相手の三目並べが露出するため、露出のルールがその駒を縛りつけている。
引き分けは終盤の現象である。 208,563の引き分けは後半に集中している。91%は12個の駒のうち少なくとも8個が盤上にあり、最も多いのは10個だ。どちらも結果を強制せずに動かし合える局面である。
実装
状態全体は u64 に収まる。9マスをそれぞれ6ビット（小・中・大の所有者を2ビットずつ）と手番1ビットである。手は1バイト、取り消しは2バイト、勝ち判定は事前計算した8つのビットマスクで行う。
解くには370,974,636の非終端局面すべてを同時にメモリに保持する必要がある。局面からIDへのマップは、ハッシュマップならエントリごとに抱えるポインタのオーバーヘッドを省くための自作のオープンアドレス法テーブルだ（負荷率0.74で約6 GB）。不動点計算はコア間で並列に走り、各ラウンドは前ラウンドの値を読んで次を書くので、すべての局面が真の距離で解決し、勝ちまでの距離は最小値になる。解析全体は14コアのノートPCで約30分、ピークは12 GB未満だ。
提供するのが第二の問題だ。テーブルはサーバーレス関数に収まらないので、最小完全ハッシュで370,974,636の正規化キーを衝突なし・キー非保存で密な範囲に写し（1キーあたり約3.5ビット）、加えて局面ごとに結果までの距離を1バイト持たせ、合計531 MBを小さなRustサービスがRAMに保持している。
Browser (game logic in WebAssembly)
│ POST /lookup/batch [canonical keys]
▼
Tablebase service (MPH in RAM)
│ outcome + distance per position
▼
Browser colors each move
ブラウザはゲームのロジックをWebAssemblyで動かし、評価のときだけサービスを呼ぶ。終端局面は自分で判定するので、テーブルベースには届かない。
深さを生むもの
露出のルールが深さの源のように見える。相手の並びを覆う唯一の駒としてピンされた駒、即座に負ける持ち上げ。しかしそうではない。このルールを外してすべての持ち上げを許して解き直しても、ほとんど何も変わらない。同じ370,974,636局面、同じ13手の序盤の勝ち、最も深い勝ちは23手から25手へとわずかに伸びるだけだ。このルールは全体の5分の1の指し手リストを形作るが、結論を変えることはまれである。良い手はもとから並びを露出させないからだ。
源は積み重ねであり、それを外すと証明できる。覆いを無効にして各駒を空きマスだけに限定して解き直すと、ゲームは崩壊する。370,974,636ではなく1,433,602局面、最も深い勝ちは10手まで下がり、引き分けは1つもない。理由は、何も取られないからだ。ゴブルは駒を覆うだけで、取り除かない。チェス盤が取り合いによって終盤へ単純化していくように駒数が減ることはないので、3×3の盤は決して落ち着かない。どうぶつしょうぎは別の経路で同じところから深さを得ている。取った駒が持ち駒として戻るので、こちらも駒が尽きることがない。
先手が13手で勝つ。gobblet.brianhliou.com のエクスプローラはテーブルベースに基づいて指し、すべての合法手を真の結果で色分けし、結果までの距離を表示する。ソルバーは GitHub にある。