マイクロ将棋は4×5の持ち駒あり将棋変種で、各陣営に王将・金将・銀将・角行・歩兵の5枚がある。盤の大きさではどうぶつしょうぎやShogi4の上、5五将棋の下に位置する。

完全なゲームはまだ未解決だ。今あるのは、解析予算を具体的にする実測結果である。各陣営が王将・歩兵・金将を持つK+P+G縮小ゲームは、初期局面から引き分けだ。正規化した到達可能局面は869,287,068、最大DTM（詰みまでの手数）は155手、そして最初の64GBクラウド実行にぎりぎり収まった。

この数字はShogi4の21億局面のクローズド実行と並べると控えめに見えるかもしれない。KPGはより小さく、銀将と角行を除いている。この実行の要点は、ここがマイクロ将棋の手軽なソルバーがすでにメモリの壁にぶつかった地点だということだ。Shogi4方式の密ランクソルバーは同じ結果を約6.86GiBで再現し、しかも速く終わった。

規模の比較：

ゲームまたは実行 状態 規模
どうぶつしょうぎ 完全解決済み 到達可能局面 246,803,167
マイクロ将棋 KPG 縮小ゲーム解決済み 到達可能局面 869,287,068
Shogi4 最大のクローズド実行 縮小ゲーム解決済み 2,100,849,024 局面
マイクロ将棋（完全版） 推定、未実行 到達可能局面 約5×10¹⁴

下でルールを直接試せる。ビューアは合法手、取ったときの反転による成り、どちらの面でも打てること、王将を取る終端局面を実装している。テーブルベースの値は表示しない。

別ウィンドウで開く →

ゲームについて

各陣営は自陣の段にS G B Kを並べ、王将の前に歩兵を置いて始める。駒は将棋の対応する駒と同じ動きをする。王将、金将、銀将、角行、歩兵、そして裏面の飛車、香車、と金、桂馬だ。

マイクロ将棋には成りゾーンがない。代わりに、王将以外のすべての駒は駒を取ると反転する。組み合わせは金/飛、銀/香、角/と、歩/桂だ。

取った駒は取った側の持ち駒になる。持ち駒はどちらの面を上にしても空きマスに打てる。二歩も打ち歩詰めの禁止も最終段の制限もない。

見つけた資料では勝利条件を詰みと定義している。ソルバーはそれを王将の捕獲としてモデル化しており、どうぶつしょうぎで使ったのと同じ終端の約束だ。千日手は資料上まだルールの空白なので、このモデルでは解消されないサイクルは引き分けとする。

実測した実行

駒を減らしたマイクロ将棋は有用だが、完全なゲームの終盤の一部というわけではない。打つことで取った駒が再循環するので、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億3千万局面程度を予想していた。完了時の数は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 到達可能な8億6900万のid 逆向きグラフを保存 約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

この数はTanakaがどうぶつしょうぎで用いたのと同じモデルによる。王将は盤上に残り、王将以外の駒は盤上か持ち駒のいずれかにあり、持ち駒は所有者を持つが面を持たず、盤上の駒は所有者と面を持つ。

到達可能数はまだ推定値だ。どうぶつしょうぎと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規模に見える。

資料：