要点

  • 大きい駒が小さい駒を覆う三目並べの変種Gobblet Gobblersは解決済みゲームとなった。先手が13手で勝つ。
  • この解は到達可能な531,557,711局面すべてに対する後退解析によるもので、非終端局面のうち引き分けはわずか208,563局面。
  • 小と大の初手はすべて勝ち、中の初手はすべて負けになる。中は相手がまだ覆える最大の駒だからだ。
  • 深さの源はスタックにある。覆う仕組みを取り除くとゲームは140万局面に縮み、最長の勝ちも10手になる。

Gobblet Gobblersはスタック機構を持つ三目並べの変種で、子ども向けゲーム（5歳以上）として販売されている。私はこれを全数解析で解き、最善手のためのウェブ局面ブラウザを作った。先手が13手で勝つ。

この解は初期局面から到達可能なすべての局面、531,557,711局面に対する後退解析である。出力は、合法的に到達できるどの局面についても正確な結果と結果までの手数を与えるテーブルベースだ。

結果項目 値
値 先手の勝ち
初期局面からの勝ちまでの手数 13手
到達可能な正規形局面数 531,557,711
引き分け局面数 208,563 (0.04%)
最長の必勝 23手

ソース: github.com/brianhliou/gobblet-gobblers

別ウィンドウで開く →

各合法手は真の結果で色分けされている。緑は勝ち、赤は負け。

ゲームの概要

3×3の盤で二人が対戦する。各プレイヤーは6個の駒（小2、中2、大2）を持ち、最初はすべて手駒にある。自分の色を縦・横・斜めのいずれかの列に3つ並べて見せれば勝ちだ。

自分の手番

手番ごとに次の2つのうち1つを行う。

  • 手駒から駒を盤上に置く、または
  • すでに盤上にある自分の駒を別のマスへ動かす。

どちらの場合も、駒は空きマスに着地するか、厳密に小さい駒（自分のものでも相手のものでも）を覆ってゴブルする。スタックは一番上だけが見える。列に数えられるのは一番上の駒だけで、持ち上げて動かせるのも一番上の駒だけだ。

小さい駒を覆う大きい駒
赤の大が青の小をゴブルする

露出のルール

駒をマスから動かすと、その下にあったものが現れる。しかもそれは自分の駒が別の場所に着地する前に起こる。相手の色の完成した列を露出させたまま放置することはできない。駒を持ち上げると相手の三目並べが現れる場合、その駒はその3マスのいずれかに戻って覆わなければならない。どこにも届かないなら、その持ち上げは非合法だ。

露出前の局面
後手の大が先手の小を隠している
唯一の合法な逃げ道の後の局面
後手は生き残るために列0へゴブルして戻すしかない

ここから最も鋭い戦術が生まれる。駒はピン付けされうる。相手の列を覆っている唯一のものであれば、動かせない。スタックは履歴を抱え、それが何手も先の指し手を制約する。手番側に合法手が一つもない場合は負けとなり、どちらも進展できない場合は反復により引き分けとなる。

見えないもの

実物のゲームでは覆われた駒は隠される。ゴブルされた駒の下を覗いてはいけないので、何があるかを記憶しておく必要があり、実際のプレイは半ば記憶ゲームだ。この解は完全情報を仮定している。双方が覆われた駒すべてを知っている前提だ。局面ブラウザも同じ理由でスタック全体を表示しており、テーブルベースが評価している局面をそのまま見られる。

後退解析

反復のルールのせいで、素直な手法は使えない。position → outcomeのキャッシュを持つ前向きミニマックスは各局面が単一の値を持つことを前提にするが、三回反復のもとでは局面の値はそこに至った経路に依存する。同じ盤面が、3回目の出現なら引き分けで、1回目なら勝負が続く。局面ごとに1つの値をキャッシュするのは不健全だ。（これはGraph History Interaction問題である。）

後退解析はグラフ全体を後ろ向きに解き、経路を一切扱わない。2段階ある。

  1. 幅優先の走査で初期局面から到達可能な正規形局面をすべて列挙し、局面をキーにする。合流（トランスポジション）は1つのノードにまとまる。
  2. 後退帰納で値を不動点まで埋める。終端局面を種として与え、変化がなくなるまで繰り返す。
// 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局面だ。

勝ちまでの手数ごとの勝ち局面数（対数スケール）。1手の約3億から23手の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つの事前計算済みビットマスクで済む。

64ビットの盤面エンコーディング

解くには370,974,636の非終端局面すべてを同時にメモリに保持する必要がある。局面からIDへのマップは独自のオープンアドレス法のテーブルで、ハッシュマップならエントリごとに抱えるポインタのオーバーヘッドを省いている（負荷率0.74で約6 GB）。不動点計算はコア間で並列に走り、各ラウンドは前のラウンドの値を読んで次を書くので、すべての局面が真の手数で解決し、勝ちまでの手数は最小になる。解析全体は14コアのノートパソコンで約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にある。