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

要点

3人用ダイヤモンドゲーム（チャイニーズチェッカー）の最小の2ボードを強解決した。各自1駒（1,245局面）と各自3駒（148億局面）だ。2人用は6×6まで解決済みだが、3人用は未解決だった。

初期局面からは、どのプレイヤーも勝ちを強制できない。どの2人でも残る1人を負けに追い込めるし、どのプレイヤーもどちらの相手にでも勝ちを譲れる。

5局面のうち4局面では、勝てないプレイヤーがそれでも勝者を選ぶ。

引き分けは2人用と同じく3駒で初めて現れる。解決には借りた32コアのマシンで7.4時間かかった。14.84 GBのテーブルベースは公開中で、自由に探索できる。

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

ダイヤモンドゲーム（チャイニーズチェッカー）のボード — 写真： 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の配置×手番状態）である。ここでいう強解決とは、完全なルールモデル上の厳密なテーブルベースのことで、初期局面からの探索ではない。

引き分けは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： 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がすでに負けているなら、BとCのどちらが勝つかはAにとってどうでもいいかもしれない。だがテーブルベースはそれを区別しなければならない。その選択がキングメーカーである。

だから、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人用ダイヤモンドゲーム（チャイニーズチェッカー）では通常の後退解析の表をいくつか計算し、その重なりを支配として読む。単独勝ち、援助による勝ち、2人での支配、キングメーカー、スポイラー引き分けだ。

第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ラウンドまでかかる。問いが狭いからだ。このプレイヤーは、あの別のプレイヤーの勝ちを手助けできるか。

第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人でも残る1人を締め出せ、6つのキングメーカー関係がすべて成り立つ。
新しい点： 引き分け。単独のプレイヤーが永続的なブロックを強制できる。1駒では不可能だった。
深くなった点： 1駒の単独層は9ラウンドで決着する。3駒の単独層は53ラウンドかかり、決着のピークは終端から1手のところではなく、第10から13ラウンドにある。

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

3駒の初期局面は1駒の初期局面とまったく同じ評価になり、単独で引き分けを強制できるプレイヤーもいない。

この均衡はしばらく続く。初期局面から幅優先探索をすると、深さ8までの到達可能局面はすべてキングメーカーのクラスに入っている。深さ9で、キングメーカー以外の局面が初めて現れる。新たに到達した1,906,964局面のうち、41が単独勝ち、1がスポイラー引き分けだ。残りの1,906,922局面はキングメーカーのままである。

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

2つの手順は同じように始まる。序盤のBの手が異なり、9手後にラベルが分かれる。

Aの最初の単独勝ち： Aが自分の勝ちを強制できる局面になっている。
Aによる最初のスポイラー引き分け： Aはまだ勝てないが、反復は強制できる局面になっている。

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

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対残りというテーブルベースの問いのもとでは、Aを引き分けの領域にとどめるCの手はちょうど1つしかない。Cのほかの手はたいてい、Aにもっと良い結果、つまり単独勝ちの強制を許してしまう。Cが引き分けを保つ手を指した後、Aにはブロックの循環を保つ応手がある。循環タブがその裏付けで、あと6手で同じ盤面、同じ手番に戻る。

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

Aの手番で、Aは勝てない。ここに引き分けの抜け道はない。一方のタブはCに勝ちの強制を与え、もう一方はBに与える。Aは負けているが、勝者を選ぶのはAだ。

このテーブルベースは、能力と振る舞いを分けている。結果が変わらないプレイヤーが同等の手からどれを選ぶかを仮定せずに、何を強制できるかを述べる。同じ状態グラフの上に、別の方針の計算を載せることもできる。普通の自己利益、引き分けを好むスポイラー、あるいはAはBを、BはCを、CはAを勝たせたいという循環的な選好などだ。そうした計算をすれば多くのキングメーカー局面が特定の勝者に収束し、その勝者は選んだ選好によって変わる。強解決はどの選好も仮定していない。

もうひとつの拡張は、目的そのものを変える。今回の解析は、最初のプレイヤーがゴールを埋めた時点で終わる。2位になることにも意味があるなら、順位を目的にするか、最初の勝者が出た後も続けるルールが必要になる。そうすれば、2位を狙う動機がブロックやキングメイキングをどう変えるかを測れる。

第3段：6駒

自然な次の段は各自6駒だが、ボードの取り決めが問題になる。Sturtevantが完了した最大の結果は、2人用の6×6 / 6駒のゲーム用ひし形だ。彼が挙げる未解決の目標は7×7 / 6駒である。3人用でこれに相当する6駒の目標は、その7×7のゲーム領域の元になる対称な星形で、73マス、3人、各自6駒となる。

6駒の目標ボード

基準	プレイヤー数	駒数	ボードモデル	状況
Sturtevant 6×6	2	6	偶数のゲーム用ひし形	解決済み
Sturtevant 7×7	2	6	奇数、星形と両立するゲーム領域	未解決
この段	3	6	73マスの3人用星形	未解決

この3人用星形ボードの設定は、次のとおり厳密に決まっている。

項目	値
ボード	73マス
駒数	プレイヤーごとに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つのアトミックなバイトを持つ。値と、未解決の手の数だ。勝ちへ進む手があれば、すぐに決着する。負けへ進む手はカウンターを1減らす。カウンターが0になれば、どの手も悪かったということだ。取りがなく可逆なゲームなので、逆向きの手はただで手に入る。

対称性

支配構造は12の強制問題からなる。各プレイヤーの単独、順序付きの各ペアの援助、各プレイヤーに対する2対1だ。スポイラー引き分けのラベルは、単独層の引き分けの結果にあたる。ボードの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駒で現れるが、対称な初期局面からは決して生じない。

参考資料：

Sturtevant「On Strongly Solving Chinese Checkers」（Advances in Computer Games, 2019）：今回の解析が拡張した2人用の解決。著者版PDF。
3人用テーブルベースの局面ブラウザ（公開中）：3駒のテーブルベース全体への厳密な問い合わせ。
brianhliou/chinese-checkers-3p：Rustのソルバー、検証用ハーネス、局面ブラウザ、公開の再現メモ。
テーブルベース成果物 v1：圧縮したテーブルベースのファイルとマニフェスト。