Shogi4: APKから復元したルールと21億局面
要点
- 4×4の打ち駒将棋であるShogi4は、公開ウェブからルールが失われていた。公式Androidアプリを逆コンパイルして復元した。
- ソルバーを構築して検証し、21億局面の閉じた部分ゲーム（2枚の王と他の各駒1枚ずつ）を解決した。
- 打つ手によって駒が盤上に残り続けるため、ゲーム全体は4×10¹⁴スロットの単一テーブルになる。約50 TB、130〜190コア年、クラウド計算費用で$10,000〜$15,000に相当する。
- 分散設計は閉じたゲームで検証済みだが、実行はしていない。完全解決は、ほとんど誰もプレイしないゲームについて1つの数値を確認するだけのものだ。
Shogi4はOca Studiosによるパブリックドメインの4×4打ち駒将棋で、そのルールは公開ウェブから消えていた。私は公式Androidパッケージからルールを復元し、その復元ルールを軸に強解ソルバー用のエンジンを構築した。
これは完全解決ではない。検証済みソルバー、21億局面の閉じた部分ゲーム、そして閉じたゲームでテスト済みだが本番規模では一度も走らせていないシャード分割の外部メモリ設計である。その境界こそが面白いところだ。Shogi4はどうぶつしょうぎの一段上にあり、打つ手によってゲームの解決が分散システムの問題へと変わる最初の段である。
下でルールを直接試せる。ビューアは打つ手、成り、味方飛び越えを含めて合法手のみを許すが、理論値は表示しない。
以降の記事では、テスト済みだが本番規模では未実行のゲーム全体ソルバー設計と、実際に解決済みの最大の閉じた部分ゲームを分けて述べる。
ルール
Shogi4のルールをエンジン水準の精度で記した二次資料は存在しない。印刷して遊ぶ用のPDFはアーカイブされておらず、発行元のサーバーは停止している。私は公式Androidパッケージからルールを復元した。Python/Kivy製のアプリで、ゲームコードはバイトコードのgzip圧縮tarball実体を持つ.mp3として同梱されていた。逆コンパイルすると、そのget_possible_squaresとcan_take_square関数が正典のルールセットである。復元した完全なルールはMistboardに掲載している。この要約だけで解決の話は追える。
ゲームは4×4の盤、各陣営5枚の駒で行われ、すべての駒は1手に1マス動く。
初期局面。駒の所属は色ではなく向きで示される。
| 駒 | 動き |
|---|---|
| 王（ツル／キジ） | 8方向のいずれかへ1マス（王と同じ） |
| コイ | 前方へ1マス |
| キツネ | 縦横へ1マス |
| タヌキ | 斜めへ1マス |
| バク | 前方または前斜めへ1マス |
3つのルールが、Shogi4をどうぶつしょうぎの流用ではなく独自のエンジンを要するものにしている。
- 打つ手。 取られた駒は陣営を変え、持ち駒から空いている任意のマスへ戻るため、駒の総量は保存される。制限は相手の最奥列に打てないことだけだ。
- 成り。 最奥列に到達した駒は必ず成る。コイ、バク、タヌキは銀将の動きに、キツネは金将の動きになる。成った駒を取ると元の駒に戻る。
- 味方飛び越え。 合法な移動方向の隣接マスに味方の駒がある場合、その駒を飛び越えて2マス先へ着地できる。味方1枚まで、連続はなく、敵駒は飛び越えられない。どうぶつしょうぎには対応する規則がない。
王を取れば勝ちとなる。王手も詰みもなく、取られる位置へ動くことも合法で、王の進入による勝ちもない。どうぶつしょうぎと比べ、駒が1枚多い点、盤が広い点、成りの種類が多い点、打つ手の制限、味方飛び越えの規則があり、新しいエンジンが必要になる。
Shogi4の完全解決が分散問題になる理由
強解では、後退解析によってすべての局面に値（勝ち、負け、引き分け）を割り当てる。終了局面、ここでは王が取られた局面から逆向きに進める。ある手で負けの局面に到達できれば勝ち、すべての手が勝ちの局面に至れば負け、それ以外は引き分けとなる。
チェスでは駒を取ると駒が減るだけなので、解決はどんどん小さくなる終盤の階段に分解でき、下から順に解ける。打つ手はその構造を壊す。取られた駒は戻ってきて駒の総量は固定され、グラフは1つの強連結な循環になり、単一の対象として解かなければならない。その対象は巨大だ。
| 量 | 値 |
|---|---|
| 全配置の上限（厳密値） | 205,148,532,253,680 |
| 初期局面から到達可能 | ~3×10¹³ |
| 密ランク索引の定義域N | 410,297,064,507,360 |
ソルバーは局面を密ランク、すなわち局面と整数の全単射で索引付けするので、値のテーブルはフラットな配列になり、参照はO(1)になる。索引はすべての合法配置を覆う必要があるため、サイズを決めるのは到達可能数ではなくN（約4×10¹⁴）だ。1スロット2ビットで約100 TB、厳密な左右対称の折り畳み後で約50 TBになる。これにより完全解決はRAM内の作業ではなく分散・外部メモリ計算となる。
完全解決の設計
ソルバーはプッシュ型だ。各局面は未確定の子の数のカウンタを持つ。終端局面（次の手で王が取られる局面）を勝ちとして種にし、そこから値が逆向きに流れる。負けへ至る手を持つ局面はただちに勝ちになり、カウンタが0になった局面、つまりすべての子が勝ちになった局面は負けになる。値は確定から未確定へ一方向にしか動かないので、この計算は単調な不動点である。
1台を超えて拡張するため、ランク空間をシャードに分割し、各シャードが自分のスロットの値とカウンタを所有する。局面が確定すると、逆手生成によって先行局面を作り、それぞれをその所有シャードへのメッセージとして送る。このルーティングがシャッフルであり、作業の大半を占める。1局面あたり約7件の先行メッセージ、本番規模で15〜30 PBになる。
各シャードは密ランクテーブルの一区画を所有する。メッセージは計算を先行局面の所有シャードへ移動させる。
ワーカーはバリアの背後でスーパーステップ単位に進む。各ワーカーは現ラウンドのメッセージを処理し、確定できるものを確定し、次のラウンドを送出する。不動点が単調なので、最終テーブルは空間のシャード分割方法やメッセージの到着順に依存しない。シャード分割はスケジュールを変えるだけで答えは変えず、その性質こそがこの計算を安全に分散できる理由だ。
計算量よりもストレージがこの計算の形を決める。値の配列はシャードに分割してディスク上に置き、常駐させずスーパーステップごとにストリームして破棄する。厳密な左右の折り畳みはストレージと作業量を半分にする。
検証
エンジンは、逆コンパイルしたアプリを独立にPythonへ移植したものと突き合わせて検証している。索引と値は別々に検証する。
手の生成。 perft（初期局面から各深さでの手の木のノード数）は桁まで一致する。
| 深さ | 局面数 |
|---|---|
| 1 | 8 |
| 2 | 64 |
| 3 | 626 |
| 4 | 6,304 |
| 5 | 68,723 |
| 6 | 769,014 |
別途、ランダム対局（打つ手、成り、駒取り、飛び越え）にわたる4,000局面の差分テストでは、2つのエンジン間で手のリストの不一致は0件だった。
索引。 密ランクは検証済みの全単射だ。rankしてunrankすると、すべての小ゲーム索引で恒等写像になり、列挙される局面は直接列挙の結果と一致する。その完全ゲームの定義域は、独立に数えた配置数のちょうど2倍である。この列挙器はどうぶつしょうぎで検証済みで、Tanakaの公表値1,567,925,964局面と持ち駒別の内訳全体を再現する。
値。 3つのソルバー（Pythonで2つのアルゴリズム、Rustで1つ）がすべての閉じた部分ゲームで一致する。局所整合性の監査では違反は0件で、すべての勝ちには負けへ至る手があり、すべての負けは勝ちへ至る手のみを持ち、すべての引き分けはどちらも持たない。左右鏡映は厳密に成立して不一致は0件、先行局面生成器は真の逆辺と一致する。
完全に解決した小さな閉じたゲームは、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枚の結果、負けが0件というのは健全性チェックになる。王だけなら、手番側は常に強制的に取られる展開を避けられる。
ノートパソコン上で完全解決設計のリスクを下げる
クラスタを借りる前に、ノートパソコン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（専用vCPU 16、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 | 到達可能キー869M件 | 逆グラフを保存 | 約60.5 GiB | 中核の解決12,385秒 |
| 密ランク＋逆手 | ランクスロット2.04B | 必要に応じて生成 | 約6.86 GiB | 総解決時間8,464秒 |
これが工学上の取引だ。密ランクは逆グラフの保存を避けるためにスロットとrank/unrankのCPUを費やす。この段ではメモリが8.8分の1になり、逆グラフの構築と保持を避けたのでシングルコアの実行は1.46倍速く終わった。
実行しなかった理由
エンジン、分散設計、検証、校正は完了している。完全解決を仕上げるのに必要なのは別のアイデアではなく、借りる計算資源だ。
その支出は基準を満たさない。技術は既知なので結果から論文にはならない。ゲームはマイナーなので、その値への需要もほとんどない。自腹で買えるのは1つの数値、つまりほとんど誰もプレイしないゲームのゲーム理論的な値だけだ。
このプロジェクトの価値は能力そのものだった。ルールは復元され、ソルバーは構築・検証され、分散経路はクラスタでの本番実行の前に閉じたゲームで検証されている。ゲームを解決すれば値が確認されるが、手法は変わらない。
関連資料:
- Shogi4ビューア：合法手のみの自由対局。
- Shogi4のルール：復元した完全なルールセット。
- brianhliou/shogi4：Rustエンジン、ソルバー、検証用ハーネス。
- どうぶつしょうぎを解く：完全に解決した一段下の題材。