微型將棋是 4×5 的打入類將棋變體，每方五子：玉將、金將、銀將、角行、步兵。以棋盤大小論，它大於動物將棋與 Shogi4，小於五五將棋。

完整遊戲仍未被解決。我目前擁有的是一次實測跑分，讓求解預算變得具體：K+P+G 縮減版遊戲，每方有玉將、步兵、金將，從起始局面為和棋。它有 869,287,068 個標準化可達局面，最大將死距離為 155 著，而且剛好塞進第一次 64 GB 的雲端執行。

和 Shogi4 那次 21 億局面的封閉執行相比，這個數字看來不大。KPG 比較小：它移除了銀將與角行。這次執行的重點在於，微型將棋那個方便好用的求解器正是在這裡撞上記憶體牆。一個 Shogi4 風格的稠密編號求解器用約 6.86 GiB 重現了同樣的結果，而且更快完成。

對照規模：

遊戲或執行 狀態 規模
動物將棋 完整遊戲已解出 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.69 億。第一次嘗試也找出一個具體錯誤：前驅偏移量以 u32 儲存，而反向圖已超過 2³² 條邊的界線。

修好之後，儲存式 CSR 的執行在一台 64 GB 的 Hetzner 機器上完成：

項目 數值
機器 16 vCPU、61 GiB 記憶體、64 GiB 交換空間
實際經過時間 4:21:08
核心求解時間 3:26:25
尖峰 RSS 約 60.5 GiB
合法著法總數 10,250,756,260
已傳播的已解子節點邊數 4,567,032,875
傳播速率 92.7 奈秒／邊
原始表格輸出 17,385,741,380 位元組
壓縮後的表格備份 2,181,879,983 位元組
稽核 通過

這張表偏和棋但很活躍。約 69.82% 的局面是行棋方勝，16.34% 是負，13.84% 是和棋。多數已定局面很快結束：DTM 中位數為 2，p90 為 16，p99 為 54，只有 11 個獲勝局面達到 DTM 155。

稠密編號的結果

64 GB 那次執行是有用的校準，但更重要的結果是重跑。它把方法從「儲存每一條可達前驅邊」改成「把局面稠密編號，並按需生成前驅」。

那個求解器會枚舉可達局面，儲存一個從局面鍵到稠密 id 的 HashMap，並儲存一份前驅邊的壓縮稀疏列表。只要塞得進記憶體，它就容易驗證而且很快。一旦圖有數十億條邊，它就變成問題本身。

Shogi4 的設計採用可擴展的形態：直接把局面編號成一個整數槽位、儲存平坦陣列，並透過回退著法按需生成前驅。這樣會把槽位花在不可達的擺法上，也會把 CPU 花在編號與反編號上，但避免了龐大的可達鍵映射與儲存式反向圖。

我用一個專為 KPG 設計的稠密編號器與按需前驅生成器重跑了 KPG：

方法 索引 前驅 尖峰記憶體 時間
可達集 + CSR 8.69 億個可達 id 儲存式反向圖 約 60.5 GiB 完整執行 4:21:08
稠密編號，第一版 20.4 億個編號槽位 按需生成，含鏡像重複 約 6.86 GiB 總計 3:31:48
稠密編號，鏡像感知版 20.4 億個編號槽位 按需生成，無需去重 約 6.86 GiB 總計 2:21:04

稠密編號的定義域是 2,037,557,340 個槽位，即 KPG 可達局面數的 2.34 倍。這就是取捨：表格中有空洞，但求解器不再背著反向圖。

兩次稠密執行都與經稽核的 CSR 數值相符。第一次稠密執行還抓到一個較小的效率錯誤：它為每個子節點生成了兩種鏡像方向、標準化後丟掉一半。鏡像感知的重跑移除了 81.6 億個重複的前驅 id，把傳播時間從 9,229 秒降到 4,961 秒。

最後那次稠密執行才是有用的比較基準：數值相同、記憶體少 8.8 倍，而且在單核上比 CSR 核心求解快 1.46 倍。

完整遊戲的規模估算

微型將棋所有擺法的精確上界是：

3,915,109,365,634,620

這個計數採用田中在動物將棋上使用的同一模型：玉將留在盤上，非玉棋子可在盤上或持駒中，持駒有歸屬方但沒有面向，盤上棋子有歸屬方也有面向。

可達局面數仍是估計值。以動物將棋與五五將棋做夾擠，可得大約 3.0×10¹⁴ 到 6.2×10¹⁴ 個可達局面，點估計約 5×10¹⁴。

尷尬的部分在於工作用的索引。已發佈的殘局庫可以在求解之後只儲存可達局面。可擴展的求解器大概無法為約 5×10¹⁴ 個鍵建立僅含可達局面的最小完美哈希。實務上的編號器只能涵蓋整個擺法定義域。

這就給出兩種不同的預算：

基準 含義 最小勝／負／和表格 計算量 成本估計
可達局面下限 理想中僅含可達局面的表格 約 134 TB 約 150 核心年 實體機約 1 萬至 1.5 萬美元
擺法編號 實務上的稠密編號工作定義域 約 1 PB 約 660 至 1,200 核心年 實體機約 4 萬至 7 萬美元，雲端約 15 萬至 28 萬美元

第二列才是我今天會據以規劃的那一列。這正是 Shogi4 的工作逼出的同一個教訓：「可達局面」是最終壓縮成品的正確數字，但稠密殘局庫在建構過程中，通常得為更大的編號定義域付出代價。

換算成實際時間，擺法編號的估計在單核上是數百年，在 1,000 核上約 8 到 14 個月，在 10,000 核上大約 3 到 6 週，而且還沒加上工程開銷與驗證重跑。記憶體數字指的是平坦的值表，不是整個叢集的佔用量。實際執行還需要計數器、佇列、檢查點與洗牌空間。

這就是微型將棋比 Shogi4 更靠後的目標的原因。它小到可以算出成本，但又大到隨手在雲端跑一次會是發現架構錯誤的昂貴方式。

這些執行改變了什麼

在 KPG 之前，微型將棋的計畫主要是從 KP 與動物將棋外推的擴展性論證。在 KPG 之後，關鍵的不確定性縮小了：

  • 目前的可達 HashMap + CSR 求解器可以回答到 KPG 為止的校準問題，但它在 64 GB 上已經勉強，到此為止。
  • 稠密編號加上按需前驅，才是微型將棋正確的生產形態，而不只是 Shogi4 的實作細節。
  • 記憶體的取捨已經實測：在同樣的 KPG 數值下，從 60.5 GiB 降到 6.86 GiB。
  • 鏡像處理重要到值得量測。在第一次稠密執行中，生成對稱的重複前驅幾乎讓傳播時間翻倍。
  • 完整求解的預算應以擺法編號定義域為基準，而非可達局面的估計值。

剩下的工作很容易列舉，但做起來仍相當可觀：對照原始資料或獨立引擎確認規則、以精確計數取代可達局面的夾擠區間、為完整棋子組合建立分桶式稠密編號／反編號、實作完整微型將棋的回退著法生成，並在為完整殘局庫付費之前先做一次較小規模的分散式演練。

目前為止，結果是一份經過校準的進度報告：KPG 已解出並稽核完成、可擴展的方法已在同一批資料上測試過，而完整的微型將棋求解看起來是 PB 等級，而非筆電等級。

資源：