3人ダイヤモンドゲーム（チャイニーズチェッカー）を解く

ダイヤモンドゲーム（チャイニーズチェッカー）は六芒星の上を駆け抜けるレースだ。自分の駒を一つの角から向かい側の角へ動かす。取りも駒得もなく、あるのは移動とブロックだけだ。

ダイヤモンドゲームの盤 — 写真： Wesley Fryer, CC BY 2.0、Wikimedia Commons より。編集済み。

Nathan Sturtevant による2019年の成果が、2人用の基準点になっている。彼は片側6駒の6×6盤までのダイヤモンドゲームを強解決し、完了した最大サイズでは 2,313,100,389,600 局面を網羅した。彼が解いたどのサイズも先手勝ちであり、明言されている次の目標は6駒の7×7だ。

3人になると、解く対象そのものが変わる。もう自分が勝てないプレイヤーでも、どちらの相手を勝たせるかは選べる。そのプレイヤーは キングメーカー だ。

私は3人用として最小の2つの盤面を段階的に解いた。各自1駒（到達可能な局面1,245）と各自3駒（配置×手番の状態14,841,300,390）だ。ここでの強解決とは、序盤からの探索ではなく、完全なルールモデル上での厳密なテーブルベースを意味する。

どちらの初期局面からも、自分の勝ちを強制できるプレイヤーはおらず、任意の2人が残る1人を負けに追い込めて、どのプレイヤーもどちらの相手にも勝ちを渡せる。引き分けは3駒で初めて現れ、これは Sturtevant が2人用で見つけたのと同じ閾値だが、対称な初期局面から単独で引き分けを強制できるプレイヤーはいない。

テーブルベースを探索する、ソルバーと再現性パッケージを読む、圧縮済みテーブルベース成果物をダウンロードする、のいずれも可能だ。

このゲームについて

解法よりルールが知りたい場合は、3人でのダイヤモンドゲームの遊び方で標準の121穴盤における配置、動かし方、勝利条件を扱っている。

3人は一つ飛ばしの角に座り、向かい側の角を目指して競う。盤は中央の六角形と6つの三角形の角からなる。1駒版は13マスで、配置がすっきり見える。

1駒盤の配置

色のついた円が駒で、薄く塗った輪郭のマスがゴールだ。A は右上の角から出発して左下の赤いゴールを目指し、B と C も同じ盤上でそれぞれの対角線を走る。3駒盤は各角を3マスに拡大し（全体で37マス）、各プレイヤーに3駒を与える。

駒は隣接する空きマスへ1歩進むか、隣接する駒（自分のものでも相手のものでもよい）を越えてその先の空きマスへジャンプし、ジャンプを連鎖させて1手で盤を横断できる。取りは一切ない。自分のゴールの角を埋めれば勝ちだ。

この連鎖ジャンプのルールは過小評価しやすい。下の1駒盤では、C の何気ない1歩が橋を作ってしまう。すると A は C と B を飛び越えて1手でゴールに入れる。

連鎖ジャンプの手順

3人になると「誰が勝つか」が崩れる理由

2人ならゼロサムゲームになる。どの局面も勝ち、負け、引き分けのいずれかで、「解けた」とは単一の値のことだ。3人ではそれが崩れる。A がもう勝てないなら、どの手も A 自身の成績にとっては等しく悪い。しかしその手は、B と C のどちらが勝つかを選ぶことはできる。

計算すべき対象は支配構造だ。どのプレイヤーが、単独または味方と組んで、どの結果を強制できるか。私は同じグラフ上で通常の2人用強制テーブルを計算する。

単独： あるプレイヤーは他の2人を相手に自分の勝ちを強制できるか。
実現： プレイヤー i と j が協力して j の勝ちを強制できるか。
ペア排除： 2人が残る1人を負けに追い込めるか。
妨害引き分け： あるプレイヤーは負けるのではなく繰り返しを強制できるか。

キングメーカーはこれらのテーブルから導かれる。プレイヤー i が j の勝ちを実現でき、かつ j が単独ではその勝ちを強制できないとき、i は j のキングメーカーだ。強制に関する問いは標準的なもので、新しいのは実在する3人ゲームの厳密なテーブルベースをこの観点で読むことにある。

アルゴリズムはどう変わるか

後退解析の基本操作は古典的なままだ。2人ゲームではどの局面も一つのスカラー、すなわち手番側にとっての勝ち、負け、引き分けだ。後ろ向きの規則は単純だ。

# Two-player retrograde, schematically.
if any(child is LOSS for child in moves(position)):
    position = WIN
elif all(child is WIN for child in moves(position)):
    position = LOSS
else:
    position = DRAW

3人では「相手の勝ち」がもう一つの結果ではなくなる。A が負けているとき、A は B と C のどちらが勝つか気にしないかもしれないが、テーブルベースは気にしなければならない。その選択がキングメーカーだ。

だから私は3人用の単一の値を計算しない。同じグラフ上で2人用の強制に関する問いを束にして計算する。

def can_force(position, max_side, objective):
    if terminal(position):
        return objective_holds(position)

    if position.turn in max_side:
        return any(can_force(child, max_side, objective)
                   for child in moves(position))
    else:
        return all(can_force(child, max_side, objective)
                   for child in moves(position))

実際のソルバーはその規則を再帰ではなくループ付き後退解析として実装する。終端状態から始めて先行局面をたどって後ろに進み、MAX 状態は子のどれかが勝ちなら勝ちと印を付け、すべての子が負けなら負けと印を付け、未解決の状態は引き分けとして残す。

can_force(s, {A}, "A wins") は A が B と C を相手に勝てるかを問う。can_force(s, {A, B}, "B wins") は A が B の勝ちを助けられるかを問う。can_force(s, {A, B}, "C loses") は A と B が C を締め出せるかを問う。

引き分けの問いは同じ解から出てくる。A が勝ちを強制できず、相手連合も A を終端の負けに追い込めないなら、その状態は A にとって引き分けだ。Sturtevant が用い、ここでも採用した同一局面反復による引き分けルールの下での判定である。

局面の解けた値は、それらの答えの重なりだ。

entry = {
    "solo":   {A: A_can_force_A_win,
               B: B_can_force_B_win,
               C: C_can_force_C_win},
    "enable": {A_to_B: AB_can_force_B_win,
               A_to_C: AC_can_force_C_win,
               B_to_A: AB_can_force_A_win,
               B_to_C: BC_can_force_C_win,
               C_to_A: AC_can_force_A_win,
               C_to_B: BC_can_force_B_win},
    "pairout": {A: BC_can_force_A_out,
                 B: AC_can_force_B_out,
                 C: AB_can_force_C_out},
    "draw":   {A: A_can_force_draw,
               B: B_can_force_draw,
               C: C_can_force_draw},
}

それがアルゴリズム上の違いだ。2人用の後退解析は一つの値のテーブルを計算する。3人ダイヤモンドゲームは通常の後退解析テーブルをいくつも計算し、その重なりを支配として読む。単独勝ち、実現された勝ち、ペアによる支配、キングメーカー、妨害引き分けだ。

段階1：1駒

1駒のゲームは到達可能な局面が1,245ある。1駒ではゴールを塞ぎ切れないので、引き分けは存在しない。その役割は校正だ。独立した2つの方法で解いて手作業で検証できるほど小さい。

到達可能な局面はすべて次の4種類のいずれかに分類される。

支配の型	局面数
終端（誰かが勝っている）	171
単独勝ち（あるプレイヤーが自分の勝ちを強制）	834
キングメーカー（負けている側が勝者を決める）	240
妨害引き分け	0
到達可能な合計	1,245

到達可能な局面の5分の1が、すでにキングメーカーの領域だ。以下はその240局面のうちの一つと、そこからの合法な2つの選択肢である。

小型盤のキングメーカー局面

手番は B で、B は勝てない。ある手は A に必勝を渡し、別の手は C に必勝を渡す。B は負けているのに、なおゲームを決めている。

単独強制の層は後退解析の第9ラウンドで解決する。順序付きのキングメーカーの問いはより長く、第13および第15ラウンドまで続く。単に「このプレイヤーは勝てるか」ではなく「このプレイヤーはあのプレイヤーの勝ちを助けられるか」という、より具体的な結果を問うためだ。初期局面の判定は3駒のゲームと一致する。単独勝ちなし、どのペアも第三者を締め出せ、順序付きキングメーカー関係は6通りすべてが成立している。

段階2：3駒

3駒の初期局面

結果と規模

各自3駒、37マス、配置と手番を数えて 14,841,300,390 局面。この数は角のレーンが許すあらゆる配置を数え上げたもので、初期局面から到達できる局面だけではない。このゲームは十分に可逆なので両者はほぼ一致し、ソルバーはそのすべてにラベルを付ける。これは私が見つけられた限りで、3人ダイヤモンドゲームの盤面に対する初の厳密な強解決だ。この主張の範囲は意図的に限定している。見つかった最も近い先行研究は解析的なもの（3人 Nim）、近似的で確率的なもの（多人数 Can’t Stop）、あるいは3人 Otrio の実行可能性調査だった。

量	値
局面数	14,841,300,390
単独での勝ち／負け／引き分け（プレイヤーごと）	950,015,894 / 13,890,307,418 / 956,384

「プレイヤーごと」の行は、3回回転対称性により A、B、C で同じだ。一人の視点から読むとよい。局面の6.4%で、そのプレイヤーは他の2人を相手に自分の勝ちを強制できる。93.6%では、他の2人がそのプレイヤーを締め出せる。引き分けはまれだが実在する。行の合計は局面数にぴったり一致しない。列挙された配置のうち20,694個は2つのゴールの角が同時に埋まっており、合法な対局では生じないため、ソルバーは勝ち・負け・引き分けではなく非合法と印を付ける。

段階1と比べると、3駒は規模を変えるが初期局面の支配構造は変えない。

変わらない点： 対称な初期局面はどちらの段階でも純粋なキングメーカーだ。単独勝ちなし、任意の2人が第三者を締め出し、6通りのキングメーカー関係がすべて成立する。
新しい点： 引き分け。単独のプレイヤーが永続的なブロックを強制できる。1駒では不可能だった。
より深い点： 1駒の単独層は9ラウンドで解決するが、3駒の単独層は53ラウンドかかり、解決のピークは終端から1手のところではなく第10〜13ラウンドにある。

初期局面はキングメーカーのまま

3駒の初期局面は1駒の初期局面とまったく同じに評価される。自分の勝ちを強制できるプレイヤーはいない。どの2人も第三者を締め出せる。単独で引き分けを強制できるプレイヤーはいない。順序付きキングメーカー関係は6通りすべて成立する。A は B にも C にも勝ちを渡せ、B は A にも C にも渡せ、C は A にも B にも渡せる。

その均衡はしばらく続く。初期局面からの幅優先探索では、深さ8 までに到達するすべての局面がまだキングメーカーの類に属する。深さ9 で最初の非キングメーカー局面が現れる。新たに到達した1,906,964局面のうち、41が単独勝ちで1が妨害引き分けだ。残る1,906,922はキングメーカーのままである。

下のウィジェットは最短の2つの証拠を示す。これを良い序盤の指し方として読まないでほしい。テーブルベースのラベルが変わる最初の到達可能な局面にすぎない。

どちらの手順も出発点は同じだ。序盤の B の手が異なり、9手後にラベルが分かれる。

A の最初の単独勝ち： その局面は A が自分の勝ちを強制できる局面になっている。
A による最初の妨害引き分け： その局面は A がまだ勝てないが、繰り返しを強制できる局面になっている。

これは到達可能性に関する事実で、最善の序盤についての主張ではない。対称な初期局面から深さ9まで、テーブルベースが単独勝ちや妨害引き分けのラベルに出会わないということだ。

引き分けとキングメーカー

1駒盤には引き分け局面が一つもなかった。3駒盤には プレイヤーごとに956,384の単独引き分け局面 と 全体で2,869,152の妨害引き分け局面 があり、そこでは一方のプレイヤーが負けるのではなく繰り返しを強制できる。Sturtevant は2人用で同じ閾値を見つけている。

148億局面すべてを、その支配構造が語る内容で分類すると次のようになる。

支配の型	局面数	割合
キングメーカー（誰も勝ちを強制できず、誰かが選ぶ）	11,988,362,862	80.8%
単独勝ち（あるプレイヤーが自分の勝ちを強制）	2,814,699,759	19.0%
終端（誰かが勝っている）	35,368,617	0.24%
妨害引き分け（単独のプレイヤーが引き分けを強制）	2,869,152	0.019%
その他	0	0%

最後の行が重要だ。強制に関する問いはゲーム全体を分類し、決定不能な残余はない。キングメーカーの領域が支配的だ。5局面のうち4つで、解けた値は誰が勝つかではなく誰が決めるかの問題になる。

テーブルベースの2つの例

次の2つのウィジェットはパズルとして意図したものではない。テーブルベースの結果に具体的な局面を結び付けるために盤を置いてある。重要なのはステータス表示とタブだ。

3駒でしか存在しない種類の 妨害引き分け：

手番は C だが、ラベルが語っているのは A の守りの力だ。A に必勝はなく、A がブロックの循環を使える状態に保つなら、他の2人は A を終端の負けに追い込めない。これは対称な初期局面が決して与えない選択肢だ。自分の勝ちを持たない単独のプレイヤーが、引き分けを握っている。

これを手の絞り込みの例として使ってほしい。A 対残り2人というテーブルベースの問いの下では、C には A を引き分け領域に留める手がちょうど一つしかない。他のたいていの C の手は A により良い結果を許し、単独勝ちを強制させてしまう。C が引き分けを保つ手を指した後、A にはブロックの循環を維持できる応手がある。循環のタブが検証の記録を示す。さらに6手進むと、同じ盤面と同じ手番が戻ってくる。

決定的なキングメーカー：

手番は A で、A は勝てない。ここに引き分けの仕掛けはない。一方のタブは C に必勝を与え、もう一方は B に必勝を与える。A は負けているが、それでも勝者を選ぶ。

このテーブルベースは能力と振る舞いを切り離している。無関心なプレイヤーが同点をどう処理するかを仮定せずに、何が強制できるかを述べる。同じ状態グラフの上に別の方針パスを載せることもできる。通常の自己利益、引き分けを好む妨害者、あるいは A は B を、B は C を、C は A を勝たせたいという循環的な好みだ。そうしたパスは多くのキングメーカー局面を特定の勝者へと収束させるが、その答えは好みに依存するもので、強解決の一部ではない。

もう一つの拡張は目的そのものを変える。この解法は最初のプレイヤーがゴールを埋めた時点で終わる。プレイヤーが2位になることを気にするなら、順位づけの目的関数か、最初の勝者の後も続くルールが必要だ。それは別のものを測ることになる。誰が勝てるかだけでなく、2位への動機づけがブロックやキングメイキングをどう変えるかである。

段階3：6駒

自然な次の段階は各自6駒だが、盤の取り決めが問題になる。Sturtevant の完了済み最大の結果は2人用の 6×6／6駒 のプレイ領域の菱形だ。彼が明言する未解決目標は 7×7／6駒 である。3人では、その7×7のプレイ領域の背後にある対称な星形の幾何が同等の6駒目標になる。73マス、3人、各自6駒だ。

6駒の目標盤

出典	人数	駒数	盤モデル	状況
Sturtevant 6×6	2	6	偶数のプレイ領域の菱形	解決済み
Sturtevant 7×7	2	6	奇数、星形と整合するプレイ領域	未解決
この段階	3	6	73マスの3人用星形	未解決

その3人用星形盤について、設定は次のとおり厳密だ。

量	値
盤	73マス
駒数	1人あたり6

レーン制限つきの上限は厳密に計算し、ここでは表示用に丸めている。

量	丸めた値
レーン制限つき配置×手番の状態数	≈1.30×10²¹
C3正規化した状態数	≈4.33×10²⁰
段階2からの増加	約876億倍

上限は段階2で使ったのと同じレーン制限つきの列挙器から得たもので、「駒がどこにでも置ける」という素朴な数え方ではない。各プレイヤーの6駒はそのプレイヤー専用の2つの角と共有される37マスの中央に限られ、各プレイヤーが共有中央に何駒置くかで場合分けして和をとる。さらに厳密な3回回転対称性により、配置×手番の状態数を3で割る。到達可能性が桁違いに問題を救ってくれることはない。ダイヤモンドゲームは取りがなく可逆で、より小さい盤では到達可能な割合がレーン制限つき空間全体にすぐ近づく。

現在の解法を素朴に拡大するのは手が届かない。段階2の最終テーブルベースは14.84 GBで、同じ表現を6駒にすると約1.3ゼタバイトになる。段階2の計算実行は7.4時間だったが、正規化状態数だけを掛けると数千万マシン年になり、しかもこれは分岐の増大、メモリ帯域、チェックポイント、I/Oを考慮する前の数字だ。

6駒は今後の課題で、長く回すことではなく新たな検討段階から始まる。より強い圧縮、外部メモリまたは分散の後退解析、到達可能性を考慮したインデックス、より良いコストモデル、そしておそらく資金か提供された計算資源だ。工学的な問いがゲーム理論の問いと同じくらい面白くなる。

ソルバーの実行の様子

この解法は148億局面に対する Rust の後退解析だ。局面を密な配列スロットに順位付けし、手はその場で生成し、代表的な4つの強制層を解き、残る8つを回転から導き、結果をローカルのテーブルベースに詰める。工学的な選択が4つ重要だった。

インデックス

148億値のフラットな配列が機能するのは、盤が算術だけで配列スロットへ、またそこから戻せる場合だけだ。各配置は密な順位に写され、手はその場で生成される。ハッシュマップもポインタもなく、メモリの大きな塊へのインデックス算術だけだ。

波面

カウンター法が終端から32コア全体へ外向きに広がる。各局面は2つのアトミックなバイトを持つ。その値と、未解決の手の数だ。勝ちへ向かう手は即座に解決する。負けへ向かう手はカウンターを減らす。カウンターがゼロになればすべての手が悪かったことを意味する。このゲームは取りがなく可逆なので、逆向きの手は無料で得られる。

対称性

支配構造は12個の強制の問いだ。各プレイヤーの単独、順序付き各ペアの実現、各プレイヤーのペア排除である。妨害引き分けのラベルは単独層の引き分け結果だ。盤の3回回転対称性により12の問いは4つの代表に畳まれ、残る8つはラベルの付け替えで従う。私はこの畳み込みをインデックスではなく問いの束に使った。ソルバーは層ごとに148億局面の配列を完全に保持し、12層ではなく4層を計算する。正規化状態数が与えるのと同じ3分の1の係数だ。鏡映は固定された手番順 A→B→C を A→C→B に反転させるため、有効な対称性ではない。

私はこれを実行前に、1駒盤で両方の畳み込みを試して捉えた。回転と鏡映を含む6回対称性は解けた値を壊し、3回回転だけは保存した。

計算の実行

各強制層のアトミック配列は解いている間およそ30 GBを使う。完了した層はカウンターを捨てて1バイトの値配列だけを残すので、最後に同時に保持する4層は約60 GBになる。作業は散在するアトミック書き込みなので、適した機械はGPUではなく大きなCPUマシンだ。Hetzner の CCX53 を借りた。32 vCPU、128 GB RAM、波面の配列をページングせずに常駐させられるだけのメモリ余裕がある。

実行には運用の配管も必要だった。代表層ごとにチェックポイントを取り、SSHが切れてもきれいに再開し、ラウンドごとの進捗を流して、借りた時間を燃やしているのではなく前進していると分かるようにすることだ。ローカルで作り、コードをマシンへ送り、tmux の下で実行し、htop でメモリを見張り、詰めたテーブルベースをコピーして戻した後にマシンを落とした。最終実行は約7.4時間で終わり、費用は数ユーロ。最終テーブルベースは14.84 GBに収まる。

検証

この結果を信頼できるのは、大規模実行の前に小さな検査を通り、実行後に大きなテーブルベースの検査を通ったからだ。

第一に、この数え上げモデルは 2*C(m²,k)*C(m²-k,k) を用いて Sturtevant の表1の局面数の列を8行すべて厳密に再現する。これは自分の星形盤の数を信じる前に、2人用の基準を理解するための関門だった。

第二に、1駒の3人ゲームは複数の方法で網羅的に解けるほど小さい。独立した2つの Python 後退解析と Rust ソルバーは、すべての状態で一致する。この比較は実際のバグを捕まえた。最初の Python の手生成器は、ジャンプの連鎖が出発点に戻ることを許していたが、これは形を変えたパスだ。それを禁止した後、ソルバー群はプレイヤーごとに勝ち335、負け910、引き分け0で一致し、到達可能なキングメーカー局面は240だった。

第三に、対称性の畳み込みを直接テストした。3回回転は解けた値を保存し、鏡映は保存しない。固定された A→B→C の手番順を反転させるからだ。n=2 の順位付け器も局面を往復変換でき、期待される4,947,100,130の正規化配置を与える。

最後に、詰めたテーブルベースを読み戻して解析する。支配の型ごとのバケットは厳密に14,841,300,390状態に合計され、プレイヤーごとの引き分け数は対称性により妨害引き分けのバケットと一致し、上記の初期局面や深さ9の証拠は手作業のラベルではなくテーブルベースへの問い合わせから来ている。14.84 GBの生のテーブルベース全体はライブの探索ツールから提供され、圧縮されたリリース成果物として公開されている。公開リポジトリにはソルバー、検証用ハーネス、静的な証拠、探索ツールのコードが含まれる。

結論

3人目を加えると、「誰が勝つか」は局面の性質ではなくなる。負けたプレイヤーがなお勝者を決められる。計算できるのは力の分布だ。誰が自分の勝ちを強制できるか、誰が味方を必要とするか、誰が他人の勝利を選ぶ立場に置かれるか。

解けた2つの初期局面は、7桁も規模が離れていながら一致する。引き分けは3駒で入ってくるが、対称な初期局面からは決して生じない。

3人では、解決済みゲームは誰が勝つかだけでなく、誰が決めるかを教えてくれる。

参考資料：

Sturtevant, “On Strongly Solving Chinese Checkers”（Advances in Computer Games, 2019）：本稿が拡張する2人用の解法。著者版PDF。
3人用テーブルベースのライブ探索ツール：3駒の完全なテーブルベースに対する厳密な問い合わせ。
brianhliou/chinese-checkers-3p：Rust ソルバー、検証用ハーネス、探索ツール、公開された再現性の記録。
テーブルベース成果物 v1：圧縮済みテーブルベースファイルとマニフェスト。