簡而言之

  • 微型將棋是 4×5 的打入型將棋，至今仍未被解決。我求解了一個縮減版本，每方只有王、步兵與金將：結果為和棋，共 869,287,068 個局面。
  • 第一版求解程式儲存了每一條前驅邊，需要 60.5 GiB。改用稠密排名、按需生成前驅的重跑只用了 6.86 GiB，而且快了 1.46 倍。
  • 完整遊戲大約有 5×10¹⁴ 個可達局面，而可擴展的求解程式索引的空間還要更大：PB 級。
  • 在 10,000 個核心上大約需要 3 到 6 週，因此下一步是先做一次規模較小的分散式演練。

微型將棋 是 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

這個計數採用 Tanaka 用於動物將棋的同一模型：王留在棋盤上，非王棋子可在盤上或在手中，手中的棋子有歸屬方但沒有面向，盤上的棋子則同時有歸屬方與面向。

可達局面數仍是估計值。以動物將棋與五將棋作為上下界，大約落在 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 級，而不是筆電級。

資源：