Shogi4はOca Studiosによるパブリックドメインの4×4持ち駒あり将棋だが、そのルールは公開ウェブから消えてしまった。私は公式のAndroidパッケージからルールを復元し、復元したルールを軸に強解決エンジンを構築した。

これは完全解決ではない。検証済みのソルバー、21億局面の閉じた部分ゲーム、そして閉じたゲームで試験したがフルスケールでは一度も走らせていないシャード分割の外部メモリ設計である。その境界こそが面白いところだ。Shogi4はどうぶつしょうぎのひとつ上の段であり、ここでは駒を打つルールがゲームの解決を分散システムの問題に変えてしまう。

ルールは下で直接試せる。ビューアは打つ手、成り、味方飛び越えを含めて合法手を強制するが、理論値は表示しない。

単独で開く →

以降では、試験済みだがフルスケールでは未実行の完全解決ソルバーの設計と、実際に解き終えた最大の閉じた部分ゲームとを分けて述べる。

ルール

Shogi4のルールをエンジン並みの精度で記した二次資料は存在しない。印刷して遊ぶ用のPDFはアーカイブされず、パブリッシャーのサーバーも停止している。私は公式のAndroidパッケージからルールを復元した。Python/Kivy製のアプリで、ゲームコードは.mp3として同梱されていたが、実体はバイトコードをgzip圧縮したtarballだった。逆コンパイルすると、そのget_possible_squaresとcan_take_squareという関数が決定版のルールセットである。復元したルールの全文はMistboardにある。ここでの要約は解決の話を追うには十分だ。

ゲームは4×4の盤で、各陣営5枚の駒を使い、すべて1手に1マスずつ動く。

4×4盤のShogi4の初期局面。先手のツル、キツネ、タヌキ、バク、コイが上向き、後手の駒が下向きに置かれている 初期局面。駒の所属は色ではなく向きで表す。

駒 動き
王（ツル／キジ） 8方向のいずれかに1マス（王将と同じ）
コイ 前に1マス
キツネ 縦横に1マス
タヌキ 斜めに1マス
バク 前または斜め前に1マス

3つのルールにより、Shogi4はどうぶつしょうぎの流用ではなく独自のエンジンを要する。

  • 打つ手。 取られた駒は持ち主が入れ替わり、持ち駒から任意の空きマスに戻るので、駒の総数は保存される。唯一の制限は、相手の最奥段には打てないことだ。
  • 成り。 最奥段に到達した駒は必ず成る。コイ、バク、タヌキは銀将の動きに、キツネは金将になる。成った駒は取られると元に戻る。
  • 味方飛び越え。 合法な移動方向の隣接マスに味方の駒がいる場合、その駒を飛び越えて2マス先に着地できる。飛び越せるのは味方1枚だけで、連続はできず、敵の駒は飛び越せない。どうぶつしょうぎに対応するルールはない。

王を取れば勝ちだ。王手も詰みもなく、取られる位置に動くことも合法で、王が敵陣に入っての勝ちもない。どうぶつしょうぎと比べて、駒が1枚多いこと、盤が広いこと、成りの種類が多いこと、打つ手の制限、味方飛び越えのルールがあり、新しいエンジンが必要になる。

Shogi4の完全解決が分散問題になる理由

強解決では、後退解析によってすべての局面に値（勝ち、負け、引き分け）を与える。終了局面、ここでは王が取られた局面から逆向きに進めていく。ある局面は、どれかの手が負けに至れば勝ち、すべての手が勝ちに至れば負け、それ以外は引き分けだ。

チェスでは駒を取ると盤上から消えるだけなので、解決はどんどん小さくなる終盤のはしごに分解でき、下から順に解ける。打つ手はその構造を壊す。取った駒は戻ってきて駒の総数は固定され、グラフはひとつの強連結な循環になり、丸ごと一体として解かねばならない。その対象は巨大だ。

量 値
全配置による上界（厳密） 205,148,532,253,680
初期局面から到達可能 ~3×10¹³
密ランク索引の定義域 N 410,297,064,507,360

ソルバーは局面を密ランク、すなわち局面から整数への全単射で索引付けするので、値の表は平坦な配列になり、参照はO(1)になる。索引はあらゆる合法な配置を覆う必要があるため、サイズを決めるのは到達可能な数ではなくN（約4×10¹⁴）だ。1スロット2ビットで約100TB、厳密な左右対称の折り畳み後で約50TBになる。したがって完全解決はRAM内のジョブではなく、分散かつ外部メモリの計算になる。

完全解決の設計

ソルバーはプッシュ型だ。各局面は未確定の子局面のカウンタを持つ。終端局面（次の手で王を取られる局面）を勝ちとして種にし、そこから値が逆向きに伝播する。負けへ進む手を持つ局面は即座に勝ちになり、カウンタが0になった局面、つまりすべての子が勝ちになった局面は負けになる。値は確定から未確定へしか動かないので、この計算は単調な不動点である。

1台を超えてスケールさせるため、ランク空間をシャードに分割し、各シャードが担当スロットの値とカウンタを保持する。ある局面が確定すると、逆向きの手生成で先行局面を作り、それぞれを担当シャードへのメッセージとして送る。このルーティングがシャッフルであり、作業の大半を占める。1局面あたり約7通の先行局面メッセージ、フルスケールで15〜30PBになる。

シャード分割した後退解析ソルバーのスーパーステップ。確定した値が先行局面を生成し、メッセージが密ランクでシャッフルされ、各シャードがディスク上の値配列とカウンタ配列を更新し、バリアの後に次のラウンドが始まる 各シャードは密ランク表の一部を担当する。メッセージは計算を先行局面の担当シャードへ運ぶ。

ワーカーはバリアを挟んでスーパーステップ単位で進む。各ワーカーは現在のラウンドのメッセージを処理し、確定できるものを確定し、次のラウンドを送出する。不動点が単調なので、最終的な表は空間の分割の仕方にもメッセージの到着順にも依存しない。シャード分割はスケジュールを変えるだけで答えは変えない。この性質こそがこの計算を安全に分散できる理由だ。

計算量よりもストレージのほうが計算の形を決める。値の配列はシャードに分かれてディスク上にあり、常駐させるのではなくスーパーステップごとにストリーミングして捨てる。厳密な左右の折り畳みはストレージも作業量も半分にする。

検証

エンジンは、逆コンパイルしたアプリを独立にPythonへ移植したものと照合している。索引と値は別々に検証する。

手生成。 perft（初期局面から各深さまでの手の木のノード数）は桁まで一致する。

深さ 局面数
1 8
2 64
3 626
4 6,304
5 68,723
6 769,014

別途、ランダム対局（打つ手、成り、駒取り、飛び越え）にわたる4,000局面の差分テストでも、2つのエンジン間で手のリストの不一致はゼロだった。

索引。 密ランクは検証済みの全単射だ。rankしてからunrankすると、すべての小さいゲームの索引で恒等になり、列挙される局面は直接列挙したものと一致する。完全ゲームでの定義域は、独立に数えた配置数のちょうど2倍だ。この列挙器はどうぶつしょうぎで検証しており、田中による公表値である1,567,925,964局面と持ち駒別の内訳全体を再現する。

値。 3つのソルバー（Pythonで2つのアルゴリズム、Rustで1つ）はすべての閉じた部分ゲームで一致する。局所整合性の監査では違反ゼロだった。すべての勝ちには負けへ進む手があり、すべての負けは勝ちへ進む手しか持たず、すべての引き分けはそのどちらも持たない。左右の鏡映も完全に成り立ち不一致ゼロで、先行局面生成器は真の逆辺と一致する。

完全に解けた小さい閉じたゲームは、Shogi4にとって初のゲーム理論的結果である（値は手番側から見たもの）。

部分ゲーム 局面数 勝ち 負け 引き分け
王2枚 480 35.0% 0% 65.0%
王2枚＋コイ 24,480 75.9% 23.3% 0.7%
王2枚＋キツネ 24,480 76.7% 23.3% 0%
王2枚＋タヌキ 24,480 76.2% 23.8% 0%
王2枚＋コイ＋キツネ 1,164,704 74.5% 17.8% 7.7%

王2枚の結果に負けがないのは健全性の確認になる。王だけなら手番側は常に強制的に取られるのを避けられる。

ノートパソコンで完全解決の設計のリスクを下げる

クラスタを借りる前に、分散設計をノートパソコン1台で、インメモリのソルバーを正解として試験した。

  • 合流性。 シャード分割したソルバーは、1、4、16、64シャードのいずれでも単一マシンの結果を再現する。伝播は最大54スーパーステップで、これは最長の強制手順の深さだ。単調不動点の議論はシャード数が結果に影響しないと言い、テストもそれを裏づける。
  • 検証。 1回の整合性パスで、解決にかかる費用より小さいコストで表全体を保証できる。{王2枚＋コイ＋キツネ}では解決に5.5秒、監査に3.0秒かかるので、検証は解決の55%であり、値を壊すと必ず検出される（それぞれ1〜5件の局所違反として現れる）。
  • 復旧。 クラッシュ後の再実行は各スーパーステップをバイト単位で再現する。これを作る過程で本物のバグが見つかった。先行局面をハッシュ集合から集めていたため、再実行の順序が元と食い違っていたのだ。出力をソートするとソルバーが決定的になり、これが冪等な復旧に必要なものだった。

最大の閉じたゲームの実行

設計が検証できたので、より大きな閉じたゲームを解いた。王2枚に各種類1枚ずつ（コイ、キツネ、タヌキ、バク）を加えた2,100,849,024局面だ。これは縮小したゲームであって、Shogi4全体の一部ではない。打つ手が駒の総数を保存するため、本来のゲームは各種類1枚ずつの構成には決して到達しないからだ。中核部分を大規模に検証するのに使えた、最大の閉じたゲームである。

   
インスタンス Hetzner Cloud CCX43（専有16 vCPU、64 GB）
OS Ubuntu 26.04
モード シングルスレッド、完全にメモリ内
ピークメモリ 約15 GB（作業キューは32ビットランクに詰めた）
実時間 5.3時間
費用 約2ドル

これは単一マシンのインメモリ解決であり、分散経路の実行ではない。約15 GBならノートパソコンにも収まるが、5時間ぶん自分のマシンを空けておくために借りたサーバーで走らせただけだ。手番側から見た結果は次の通り。

結果 局面数 割合
勝ち 1,662,776,212 79.15%
負け 339,566,116 16.16%
引き分け 98,506,696 4.69%

合計は局面総数と厳密に一致し、監査も通過する。

この実行は、作業集合のサイズに対する1辺あたりのコストの較正にもなる。

局面数 1辺あたりのns
1,164,704 327
51,461,568 493
2,100,849,024 697

21億の実行は、値の配列（約14 GB）がCPUキャッシュから溢れる初めてのケースであり、697 ns/辺が完全解決を見積もる基準になる。キャッシュに収まるベンチマークはこの種のジョブを過小評価する。

完全解決にかかる費用

697 ns/辺という基準と4×10¹⁴の索引から、完全解決はおおよそ作業用ストレージ50〜100 TB、計算130〜190コア年、すなわち約100万コア時、クラウド換算で10,000〜15,000ドルになる。

この数字にたどり着くまでに2回の訂正があった。生の局面数が最初は1桁ずれていた。次に、密ランク索引が覆わねばならない配置の定義域（約4×10¹⁴、約13倍大きい）ではなく、到達可能な局面（約3×10¹³）に対して容量を見積もってしまっていた。

この索引は扱いにくいが不可欠な部分だ。小さなソルバーなら到達可能な局面を列挙し、局面キーから表のスロットへのHashMapを保持できる。この規模では、そのマップを作ること自体がすでに大きすぎる。スケールする版はすべての配置に数学的なアドレスを与える。rank(position) -> integerだ。非合法または到達不能な配置にスロットを無駄遣いするが、そのかわりテーブルベースがシャード分割、ストリーミング、チェックポイント、監査のできる平坦な配列になる。

同じトレードオフは後退のステップにも現れる。小さなインメモリのソルバーなら、すべての先行辺を圧縮行格納（CSR）のリストに持ち、その逆グラフを直接たどれる。完全なソルバーは1辺につき1行を保存する余裕がない。かわりに先行局面を必要に応じて生成する。手の形を戻し、各先行局面をrankし、そのランクを担当するシャードへ更新を送るのだ。1辺あたりのCPUは増えるが、それがメモリ律速の近道と外部メモリのソルバーとの違いである。

この見積もりの後、関連する4×5のマイクロ将棋の段でこのトレードオフをそのまま測った。各陣営K+P+Gで、到達可能な正規化局面は869,287,068。到達可能HashMap＋CSR保存のソルバーは中核の解決にピークRSS約60.5 GiBと12,385秒を要した。KPG専用の密ランク＋逆手生成のソルバーは2,037,557,340スロットのランク定義域（到達可能数の2.34倍）を使い、同じ値の集計をピークRSS約6.86 GiB、総解決時間8,464秒で再現した。

手法 索引 先行局面 ピークメモリ シングルコア時間
到達可能＋CSR 到達可能キー8.69億 逆グラフを保存 約60.5 GiB 中核の解決12,385秒
密ランク＋逆手生成 ランクスロット20.4億 必要に応じて生成 約6.86 GiB 総解決時間8,464秒

これが工学上のトレードオフだ。密ランクはスロットとrank/unrankのCPUを費やして、逆グラフの保存を避ける。この段ではメモリが8.8分の1になり、逆グラフの構築と保持を避けたぶんシングルコアの実行も1.46倍速く終わった。

実行しないままにしている理由

エンジン、分散設計、検証、較正は終わっている。完全解決を仕上げるのに必要なのは借りる計算資源であって、新しい着想ではない。

その支出は基準を満たさない。手法は既知なので結果から論文は出ないし、ゲームは無名なのでその値への需要もほとんどない。自費で買えるのは数字ひとつ、ほとんど誰も遊ばないゲームのゲーム理論的な値だけだ。

このプロジェクトの価値は能力そのものだった。ルールは復元され、ソルバーは作られて検証され、分散経路はクラスタでの完全実行の前に閉じたゲームで確認済みだ。ゲームを解けば値が確定するが、方法は変わらない。

資料：