マイクロ将棋: 密ランクでの再実行がメモリを8.8倍削減
要点
- 4×5の持ち駒あり将棋であるマイクロ将棋は、いまだ未解決である。私は各陣にking、pawn、goldを置いた縮小版を解いた: 869,287,068局面にわたって引き分けだった。
- 最初のソルバーはすべての先行局面の辺を保存し、60.5 GiBを必要とした。先行局面を必要に応じて生成する密ランクでの再実行では6.86 GiBで済み、1.46倍高速に動いた。
- ゲーム全体では到達可能局面がおよそ5×10¹⁴あり、スケーラブルなソルバーはさらに大きい空間をインデックスする: ペタバイト規模だ。
- 10,000コアなら約3〜6週間なので、次の一歩はより小規模な分散リハーサルである。
マイクロ将棋は、各陣にKing、Gold、Silver、Bishop、Pawnの5駒を持つ4×5の持ち駒あり将棋の変種だ。盤の大きさではどうぶつしょうぎやShogi4より上、5五将棋より下に位置する。
ゲーム全体はまだ未解決だ。今手元にあるのは、解くための予算を具体化する実測の結果である: 各陣にKing、Pawn、Goldを置いたK+P+Gの縮小ゲームは、初期局面から引き分けだ。正規化された到達可能局面は869,287,068、詰みまでの最大距離は155手で、最初の64GBクラウド実行にぎりぎり収まった。
この数字はShogi4の21億局面の閉じた実行と並べると控えめに見えるかもしれない。KPGはより小さく、SilverとBishopを除いている。この実行の意味は、マイクロ将棋の手軽なソルバーがすでにメモリの壁に突き当たったのがまさにここだという点にある。Shogi4方式の密ランクソルバーは、同じ結果を約6.86 GiBで再現し、しかも速く終わった。
規模の比較:
| ゲームまたは実行 | 状態 | 規模 |
|---|---|---|
| どうぶつしょうぎ | ゲーム全体が解決済み | 到達可能局面 246,803,167 |
| マイクロ将棋 KPG | 縮小ゲームが解決済み | 到達可能局面 869,287,068 |
| Shogi4の最大の閉じた実行 | 縮小ゲームが解決済み | 2,100,849,024局面 |
| マイクロ将棋全体 | 推定、未実行 | 到達可能局面 約5×10¹⁴ |
ルールは下で直接試せる。ビューアは合法手、取ったときの裏返し昇格、どちらの面でも打てる打ち駒、king捕獲による終端局面を強制する。テーブルベースの値は表示しない。
ゲームについて
各陣は自陣の段にS G B Kを並べ、kingの前にpawnを置いて始まる。駒は将棋の対応駒と同じように動く: King、Gold、Silver、Bishop、Pawn、それに裏面のRook、Lance、Tokin、Knightだ。
マイクロ将棋には昇格ゾーンがない。その代わり、king以外のすべての駒は駒を取ると裏返る。組はGold/Rook、Silver/Lance、Bishop/Tokin、Pawn/Knightである。
取られた駒は取った側の持ち駒になる。持ち駒はどちらの面を上にしても、空いているどのマスにも打てる。二歩の禁止も、打ち歩詰めの禁止も、最終段の制限もない。
私が見つけた資料では勝利条件は詰みと定義されている。ソルバーはこれをking捕獲としてモデル化しており、どうぶつしょうぎで使ったのと同じ終端の約束だ。千日手は資料ではいまだルールの穴なので、このモデルでは未解決の循環は引き分けとする。
実測した実行
駒を減らしたマイクロ将棋は有用だが、ゲーム全体の終盤の切片ではない。打ち駒が取った駒を再循環させるため、K+P+Gの解は同じ盤とルール機構を持つ、より小さな兄弟ゲームである。
現在の較正の梯子はこうなっている:
| 段 | 各陣の駒 | 正規化到達可能数 | 初期局面 | 勝ち / 負け / 引き分け | 最大DTM | 平均分岐数 |
|---|---|---|---|---|---|---|
| KP | K, P | 457,993 | 引き分け | 135,804 / 2,956 / 319,233 | 29 | 6.86 |
| KPG | K, P, G | 869,287,068 | 引き分け | 606,922,331 / 142,074,547 / 120,290,190 | 155 | 11.79 |
KPGの実行は、真のスケーリング問題を露わにするほど大きな最初のマイクロ将棋の段だった。私は当初1億3000万局面あたりを予想していた。完了した実測値は8億6900万だった。最初の試行では具体的なバグも見つかった: 先行局面のオフセットをu32で保存しており、逆向きグラフが2³²辺の境界を越えていたのだ。
それを修正した後、CSR保存方式の実行は64GBのHetznerマシンで完了した:
| 項目 | 値 |
|---|---|
| マシン | 16 vCPU、61 GiB RAM、64 GiB スワップ |
| 経過実時間 | 4:21:08 |
| コアの解決時間 | 3:26:25 |
| ピークRSS | 約60.5 GiB |
| 合法手の総数 | 10,250,756,260 |
| 伝播した解決済み子局面の辺 | 4,567,032,875 |
| 伝播速度 | 92.7 ns/辺 |
| 生のテーブルダンプ | 17,385,741,380 バイト |
| 圧縮したテーブルのバックアップ | 2,181,879,983 バイト |
| 監査 | 合格 |
テーブルは引き分けがちだが動きがある。約69.82%の局面が手番側の勝ち、16.34%が負け、13.84%が引き分けだ。決着のつく局面の多くは早く終わる: DTMの中央値は2、p90は16、p99は54で、DTM 155に達する勝ち局面はわずか11しかない。
密ランクの結果
64GBの実行は有用な較正だったが、より重要な結果は再実行のほうだった。手法を「到達可能な先行局面の辺をすべて保存する」から「局面を密にランク付けし、先行局面を必要に応じて生成する」へ変えたのだ。
そのソルバーは到達可能局面を列挙し、局面キーから密なidへのHashMapを保存し、先行局面の辺を圧縮疎行形式のリストで保存する。メモリに収まる限り、検証しやすく高速だ。だがグラフが数十億辺になると、それ自体が問題になる。
Shogi4の設計はスケーラブルな形をとる: 局面を直接整数スロットにランク付けし、平坦な配列に保存し、手を戻して先行局面を必要に応じて生成する。到達不能な配置にスロットを費やし、ランク/逆ランクにCPUを費やすが、巨大な到達可能キーのマップと保存された逆向きグラフを避けられる。
私はKPG専用の密ランカーとオンデマンドの先行局面生成器でKPGを再実行した:
| 手法 | インデックス | 先行局面 | ピークメモリ | 時間 |
|---|---|---|---|---|
| 到達可能 + CSR | 到達可能id 8億6900万 | 逆向きグラフを保存 | 約60.5 GiB | 全実行 4:21:08 |
| 密ランク、第1版 | ランクスロット 20.4億 | 必要に応じて生成、鏡像の重複あり | 約6.86 GiB | 合計 3:31:48 |
| 密ランク、鏡像対応 | ランクスロット 20.4億 | 必要に応じて生成、重複排除不要 | 約6.86 GiB | 合計 2:21:04 |
密ランクの領域は2,037,557,340スロット、つまりKPGの到達可能数の2.34倍だ。これがトレードオフである: テーブルには穴があるが、ソルバーはもう逆向きグラフを抱えない。
どちらの密ランク実行も、監査済みCSRの値と一致した。第1版の密ランク実行では、より小さな効率上のバグも見つかった: 子局面ごとに鏡像の両方向を生成し、正規化して半分を捨てていたのだ。鏡像対応の再実行は81.6億件の重複した先行局面idを取り除き、伝播を9,229秒から4,961秒に短縮した。
最終の密ランク実行が有用な比較点になる: 値は同じ、メモリは8.8分の1、1コアでのCSRのコア解決より1.46倍高速だ。
ゲーム全体の規模見積もり
マイクロ将棋の全配置による厳密な上限はこうなる:
3,915,109,365,634,620
この数え方は田中がどうぶつしょうぎで用いたモデルと同じだ: kingは盤上に残り、king以外の駒は盤上か持ち駒にあり、持ち駒には所有者はあるが面はなく、盤上の駒には所有者と面がある。
到達可能数はまだ推定値だ。どうぶつしょうぎと5五将棋から挟み込むと、到達可能局面はおよそ3.0×10¹⁴から6.2×10¹⁴、点推定では5×10¹⁴あたりになる。
やりにくいのは作業用インデックスだ。公開するテーブルベースは、解いた後で到達可能局面だけを保存できる。だがスケーラブルなソルバーは、約5×10¹⁴個のキーに対して到達可能局面のみの最小完全ハッシュを構築するのはおそらく無理だ。実用的なランカーは代わりに配置全体の領域にまたがる。
そこで2つの異なる予算が出てくる:
| 基準 | 意味 | 最小の勝ち/負け/引き分けテーブル | 計算量 | コスト見積もり |
|---|---|---|---|---|
| 到達可能数の下限 | 理想的な到達可能局面のみのテーブル | 約134 TB | 約150コア年 | ベアメタルで約1万〜1.5万ドル |
| 配置ランク | 実用的な密ランクの作業領域 | 約1 PB | 約660〜1,200コア年 | ベアメタルで約4万〜7万ドル、クラウドで約15万〜28万ドル |
今日計画を立てるなら、私は2行目を基準にする。Shogi4の作業が明るみに出したのと同じ教訓だ: 「到達可能局面」は最終的な圧縮成果物にとっては正しい数字だが、密なテーブルベースの構築では、計算中はふつうより大きなランク領域の代価を払うことになる。
実時間で言えば、配置ランクの見積もりは1コアで数百年、1,000コアで約8〜14か月、10,000コアならおよそ3〜6週間で、これに工学的なオーバーヘッドと検証の再実行が加わる。メモリの数字は平坦な値テーブルの分で、クラスタ全体のフットプリントではない。実際の実行にはカウンタ、キュー、チェックポイント、シャッフル用の領域も必要になる。
だからこそマイクロ将棋はShogi4より後の標的になる。コストを見積もれるほど小さいが、気軽なクラウド実行でアーキテクチャのバグを発見するには高くつくほど大きいのだ。
実行によって変わったこと
KPG以前、マイクロ将棋の計画はほぼKPとどうぶつしょうぎからのスケーリング論だった。KPG以後、主な不確実性はより狭まっている:
- 現在の到達可能
HashMap+ CSRのソルバーはKPGまでの較正的な問いには答えられるが、64GBでは限界ぎりぎりで、ここで止まる。 - 密ランクとオンデマンドの先行局面生成は、Shogi4固有の細部ではなく、マイクロ将棋の本番向けの正しい形である。
- メモリのトレードオフは実測された: 同じKPGの値で60.5 GiBから6.86 GiBへ。
- 鏡像の扱いは測るに値するほど重要だ。対称な重複先行局面の生成は、第1版の密ランク実行で伝播時間をほぼ倍にしていた。
- 完全な解決は、到達可能局面の推定ではなく、配置ランクの領域を基準に予算を組むべきだ。
残る作業は名前を挙げるのは簡単で、やるのはなお大変だ: 一次資料か独立したエンジンでルールを確認し、到達可能数の挟み込みを厳密な数え上げに置き換え、駒の全構成に対するバケット化した密ランク/逆ランクを構築し、マイクロ将棋の完全な逆手生成を実装し、完全なテーブルベースに支払う前に小規模な分散リハーサルを走らせる。
今のところ得られたのは、較正済みの状況報告だ: KPGは解かれ監査され、スケーラブルな手法は同じデータで検証され、マイクロ将棋の完全な解決はノートPC規模ではなくPB規模に見える。
関連リソース:
- マイクロ将棋ビューア: 上に埋め込んだ合法手ビューア。
- brianhliou/micro-shogi: ルールエンジン、較正用ソルバー、状態空間の列挙器、ビューア。
- Shogi4の解決に向けて: より小さい4×4の持ち駒あり将棋の実行と完全解決の設計。
- どうぶつしょうぎを解く: 一つ下の完全に解決済みの段。