Shogi4：從 APK 復原規則，21 億個局面
Shogi4 是 Oca Studios 推出的公共領域 4×4 打入型將棋，其規則已從公開網路上消失。我從官方 Android 套件中復原了規則，接著依照復原後的規則打造了一套強解求解引擎。
這不是一份完整解答。它是一套經過驗證的求解器、一個 21 億局面的封閉子遊戲，以及一套分片式外部記憶體設計，該設計已在封閉遊戲上測試過，但從未以完整規模執行。這條界線才是有趣之處：Shogi4 是動物將棋之上的第一階，在這裡打入會把一次遊戲求解變成一個分散式系統問題。
可以直接在下方試玩規則。這個檢視器會強制合法著法，包括打入、升變與友方跳躍，但不會顯示理論結果。
本文其餘部分把完整遊戲的求解器設計（已測試但未以完整規模執行）與最大的封閉子遊戲（確實已求解）分開說明。
規則
沒有任何二手來源以引擎級的精確度記載 Shogi4 的規則。列印遊玩用的 PDF 從未被存檔，出版商的伺服器也已停擺。我從官方 Android 套件中復原了規則：那是一個 Python/Kivy 應用程式，其遊戲程式碼以 .mp3 形式發佈，實際上是位元碼的 gzip 壓縮封裝檔。反編譯後，其中的 get_possible_squares 與 can_take_square 函式就是權威規則集。完整的復原規則放在 Mistboard；本文的摘要已足以理解這次求解。
遊戲在 4×4 棋盤上進行，每方五枚棋子，全部每回合走一格：
起始局面。棋子歸屬由朝向決定，而非顏色。
| 棋子 | 走法 |
|---|---|
| 王（鶴／雉） | 八個方向任一方向走一格（即王） |
| 鯉魚 | 向前走一格 |
| 狐狸 | 沿直線走一格 |
| 狸 | 沿斜線走一格 |
| 貘 | 向前或向前斜方走一格 |
有三條規則讓 Shogi4 需要自己的引擎，而不是把動物將棋的引擎改指向它：
- 打入。 被吃的棋子會換邊，並可從手中放回任何空格，因此子力總量守恆。唯一的限制是不得打入對方的底線。
- 升變。 抵達最遠一列的棋子必須升變：鯉魚、貘與狸升為銀將的步法組，狐狸升為金將。被吃的已升變棋子會回復為原本的棋子。
- 友方跳躍。 若合法走法方向上相鄰的格子有己方棋子，該棋子可以跳過它，落在兩格之外。只能跳一枚己方棋子，不能連跳，也不能跳過敵方棋子。動物將棋沒有對應的規則。
吃掉對方的王即獲勝。沒有將軍或將死的概念，走到可被吃掉的位置是合法的，也沒有王行軍獲勝的規則。與動物將棋相比，多出的一枚棋子、更寬的棋盤、更廣的升變組合、打入限制與友方跳躍規則，已足以要求一套新的引擎。
為何完整的 Shogi4 是個分散式問題
強解會透過逆向分析為每個局面指定一個值（勝、負或和棋），從已結束的局面往回推算，這裡指的是王被吃掉的局面。若某個著法能走到負局面，該局面為勝；若所有著法都走到勝局面，該局面為負；其餘為和棋。
在西洋棋中，吃子只會減少子力，因此求解可分解成一連串越來越小的殘局，由下往上逐層解決。打入破壞了這個結構。被吃的棋子會回來，子力固定不變，整張圖成為單一的強連通環，必須當成一個整體來求解。這個整體很大：
| 數量 | 數值 |
|---|---|
| 所有排列的上界（精確值） | 205,148,532,253,680 |
| 從起始局面可達 | ~3×10¹³ |
| 稠密排序索引定義域 N | 410,297,064,507,360 |
求解器以稠密排序（一種局面到整數的雙射）為局面編索引，因此值表是一個平坦陣列，查找為 O(1)。索引必須涵蓋每一種合法排列，所以決定大小的是 N（約 4×10¹⁴），而不是可達局面數：每個格位兩位元約為 100 TB，套用精確的左右對稱折疊後約 50 TB。這使完整求解成為一項分散式的外部記憶體運算，而不是能放進 RAM 的工作。
完整求解的設計
求解器採推送式。每個局面保有一個計數器，記錄尚未判定的子節點數。終端局面（王在下一著就會被吃掉）先播種為勝，之後值往回流動：只要有一個著法能走進負局面，該局面立刻成為勝；而計數器歸零的局面，代表所有子節點都已是勝，則成為負。值只會從已判定流向未判定，因此整個運算是一個單調不動點。
為了擴展到多台機器，排序空間被切分成分片，各自擁有其格位的值與計數器。判定一個局面時，會以反向著法生成它的前驅局面，並把每個前驅作為訊息送往擁有它的分片。這個路由就是 shuffle，也是工作量的主體：每個局面約產生 7 則前驅訊息，在完整規模下為 15 到 30 PB。
每個分片擁有稠密排序表的一段。訊息把運算搬到擁有該前驅局面的分片上。
工作者在屏障後以超級步推進。每個工作者處理完當輪訊息、判定能判定的部分，再發出下一輪訊息。由於不動點是單調的，最終的值表不取決於空間如何分片，也不取決於訊息抵達的順序。分片只改變排程，絕不改變答案，而正是這個性質讓運算能安全地分散執行。
決定運算形狀的是儲存，而不是計算。值陣列以分片形式存在磁碟上，每個超級步串流讀取後即丟棄，而不是常駐記憶體，而精確的左右折疊讓儲存與工作量都減半。
驗證
引擎會與一份由反編譯應用程式獨立改寫的 Python 版本互相比對。索引與值分別驗證。
著法生成。 perft（從起始局面在各深度的著法樹節點數）逐位相符：
| 深度 | 局面數 |
|---|---|
| 1 | 8 |
| 2 | 64 |
| 3 | 626 |
| 4 | 6,304 |
| 5 | 68,723 |
| 6 | 769,014 |
另有一項在隨機對局上進行的 4,000 局面差異測試（涵蓋打入、升變、吃子、跳躍），兩套引擎之間的著法列表沒有任何不符。
索引。 稠密排序是已驗證的雙射：在每個小型遊戲索引上，先 rank 再 unrank 都是恆等映射，而它列舉出的局面也與直接列舉相符。它在完整遊戲上的定義域正好是獨立計算的排列數的兩倍。該列舉器以動物將棋作為對照，能重現 Tanaka 發表的 1,567,925,964 個局面數，以及完整的手中棋子分類統計。
值。 三套求解器（Python 兩種演算法、Rust 一種）在每個封閉子遊戲上的結果一致。局部一致性審查沒有發現任何違例：每個勝局面都有一個著法走向負，每個負局面的所有著法都走向勝，而和棋局面兩者皆無。左右鏡像完全成立，零不符，前驅生成器也與真正的反向邊相符。
這些已完整求解的小型封閉遊戲，是 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% |
雙王的結果沒有任何負局面，這是一項合理性檢查：場上只有王時，行棋方總能避免自己的王被強迫吃掉。
在筆電上降低完整求解設計的風險
在租用叢集之前，我先在一台筆電上測試這套分散式設計，並以記憶體內求解器作為標準答案。
- 匯合性。 分片求解器在 1、4、16 與 64 個分片下都重現了單機的結果。傳播最多執行 54 個超級步，也就是最長強制變化的深度。單調不動點的論證表示分片數不可能有影響；測試也印證了這一點。
- 查核。 一次一致性掃描就能為整張表背書，成本低於求解本身。在 {2 王 + 鯉魚 + 狐狸} 上求解耗時 5.5 秒、審查 3.0 秒，因此查核是求解的 55%，而我刻意破壞的每一個值都被抓到（每個會呈現為 1 到 5 個局部違例）。
- 復原。 崩潰後重播能逐位元組重現每個超級步。建置它時抓到一個真正的錯誤：前驅局面是從一個雜湊集合收集的，因此重播順序與原本不同。把輸出排序後，求解器變成確定性的，而這正是冪等復原所需要的。
最大規模的封閉求解
設計驗證完成後，我求解了一個更大的封閉遊戲：雙王加上每種棋子各一枚（鯉魚、狐狸、狸、貘），共 2,100,849,024 個局面。它是一個縮減版遊戲，而不是完整 Shogi4 的一個切片，因為打入使子力守恆，真實遊戲永遠不會走到各一枚的配置。它是我能用來在規模上驗證核心的最大封閉遊戲。
| 執行環境 | Hetzner Cloud CCX43（16 顆專用 vCPU、64 GB） |
| 作業系統 | Ubuntu 26.04 |
| 模式 | 單執行緒、完全在記憶體中 |
| 記憶體峰值 | 約 15 GB（工作佇列壓縮為 32 位元排序值） |
| 實際耗時 | 5.3 小時 |
| 成本 | 約 2 美元 |
這是單機、記憶體內的求解，不是分散式路徑的一次執行。約 15 GB 可以放進一台筆電；我在租用的機器上執行，只是為了讓自己的機器在這五小時內保持空閒。結果以行棋方為準：
| 結果 | 局面數 | 占比 |
|---|---|---|
| 勝 | 1,662,776,212 | 79.15% |
| 負 | 339,566,116 | 16.16% |
| 和棋 | 98,506,696 | 4.69% |
這些計數之和正好等於局面總數，並通過審查。
這次執行也校準了每條邊的成本與工作集大小的關係：
| 局面數 | 每條邊奈秒數 |
|---|---|
| 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 核心年的計算量：約一百萬核心小時，換算成雲端費用約為 10,000 到 15,000 美元。
這個數字經過兩次修正。原始的局面數一開始差了一個數量級。接著佔用空間被誤以可達局面數（約 3×10¹³）來估算，而非排列定義域（約 4×10¹⁴，大約大 13 倍），後者才是稠密排序索引必須涵蓋的範圍。
那個索引是彆扭但必要的部分。小型求解器可以列舉可達局面，並保留一個從局面鍵到表格格位的 HashMap。在這種規模下，建立那張映射本身就已經太大。可擴展的版本為每一種排列給出一個數學位址：rank(position) -> integer。這會在不合法或不可達的排列上浪費格位，但也把殘局庫變成可以分片、串流、設檢查點與審查的平坦陣列。
同樣的取捨也出現在往回推算的步驟。小型的記憶體內求解器可以儲存一份壓縮稀疏列（CSR）形式的所有前驅邊清單，再直接走訪那張反向圖。完整求解器負擔不起為每條邊儲存一列。它改為按需生成前驅：還原著法形狀、為每個前驅計算 rank，再把更新送往擁有該 rank 的分片。這在每條邊上花更多 CPU，但這正是受記憶體限制的捷徑與外部記憶體求解器之間的差別。
在這份估算之後，我在相關的 4×5 微型將棋的一階上實測了這個取捨：每方 K+P+G，共 869,287,068 個可達的標準局面。採用可達局面 HashMap 加上儲存式 CSR 的求解器，核心求解需要約 60.5 GiB 的峰值 RSS 與 12,385 秒。而專為 KPG 設計的稠密排序加反向著法求解器使用了 2,037,557,340 個排序格位，是可達局面數的 2.34 倍，並以約 6.86 GiB 峰值 RSS 與 8,464 秒的總求解時間重現了相同的值計數。
| 方法 | 索引 | 前驅局面 | 記憶體峰值 | 單核心時間 |
|---|---|---|---|---|
| 可達局面 + CSR | 8.69 億個可達鍵 | 儲存式反向圖 | 約 60.5 GiB | 核心求解 12,385 秒 |
| 稠密排序 + 反向著法 | 20.4 億個排序格位 | 按需生成 | 約 6.86 GiB | 總求解 8,464 秒 |
這就是工程上的取捨：稠密排序花費格位與 rank/unrank 的 CPU，來避免儲存反向圖。在這一階上，記憶體降為 1/8.8，單核心執行也快了 1.46 倍，因為它不必建立與保留反向圖。
為何留著不執行
引擎、分散式設計、查核與校準都已完成。要完成整個求解，缺的是租用的運算資源，而不是另一個想法。
這筆花費過不了門檻。技術本身已為人所知，所以結果寫不成論文；遊戲本身冷門，所以對其結果的需求也很少。自掏腰包只能買到一個數字：一個幾乎沒人玩的遊戲的賽局理論值。
這個專案的價值在於能力本身。規則已復原，求解器已建置並驗證，分散式路徑也在完整叢集執行之前先以封閉遊戲檢驗過。求解這個遊戲只會確認一個數值；它不會改變方法。
資源：
- Shogi4 檢視器：只允許合法著法的自由對局。
- Shogi4 規則：完整的復原規則集。
- brianhliou/shogi4：Rust 引擎、求解器與驗證工具。
- 求解動物將棋：更低的那一階，已完整求解。