Shogi4：從 APK 還原規則，21 億個局面
簡述
- Shogi4 是一款 4×4 的打入式將棋，其規則已在公開網路上消失。我透過反編譯官方 Android 應用程式把規則還原出來。
- 我建立並驗證了一個求解器，並解出一個 21 億局面的封閉子遊戲：雙方各一枚王，加上其他每種棋子各一枚。
- 打入會把子力留在盤面上，所以完整遊戲是一張 4×10¹⁴ 格位的表：約 50 TB，以及 130 到 190 核心年，換算成雲端運算約 10,000 到 15,000 美元。
- 分散式設計已在封閉遊戲上測試過，但未實際執行。完整求解只會為一款幾乎沒人在玩的遊戲確認一個數字。
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 裡的工作。
完整求解的設計
求解器採推送式。每個局面保有一個尚未決定的子節點計數器。終端局面（王在下一著會被吃）先設為勝，然後值往回流動：只要某局面有一著能走進負的局面，立刻成為勝；而計數器歸零的局面，意即所有子節點現在都是勝，則成為負。值只會從已決定流向未決定，所以這項計算是一個單調不動點。
為了擴展到多台機器，排序空間被切分成多個分片，每個分片擁有自己格位的值與計數器。解出一個局面時，會用反向著法產生器生出它的所有前驅局面，並把每一個當成訊息送往擁有它的分片。這個路由就是洗牌，也是工作量的主體：每個局面約 7 則前驅訊息，在完整規模下相當於 15 到 30 PB。
每個分片擁有密集排序表的一段。訊息把計算搬到擁有該前驅局面的分片上。
工作者在屏障之後以超步推進。每個工作者排空當輪訊息，解出能解的部分，並發出下一輪訊息。由於不動點是單調的，最終的表既不取決於空間如何分片，也不取決於訊息抵達的順序。分片只改變排程，絕不改變答案，而正是這個性質讓這項計算可以安全地分散執行。
決定計算形貌的是儲存，而非運算。值陣列以分片形式存放在磁碟上，每個超步串流讀取後即丟棄，而不是常駐記憶體，而精確的左右折疊讓儲存與工作量都減半。
驗證
引擎會與一份獨立的 Python 移植版（由反編譯的應用程式而來）互相核對。索引與值分別驗證。
著法產生。perft（自初始局面起各搜尋深度的著法樹節點數）逐位吻合：
| 深度 | 局面數 |
|---|---|
| 1 | 8 |
| 2 | 64 |
| 3 | 626 |
| 4 | 6,304 |
| 5 | 68,723 |
| 6 | 769,014 |
另有一項在隨機對局（打入、升變、吃子、跳躍）上進行的 4,000 局面差異測試，兩個引擎之間的著法清單零不一致。
索引。密集排序是經過驗證的雙射：在每個小型遊戲索引上，先排序再反排序是恆等映射，而它列舉出的局面與直接列舉的結果相符。它在完整遊戲上的定義域恰為獨立排列計數的兩倍。該列舉器以動物將棋作為把關基準，在其上重現了田中發表的 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）形式的所有前驅邊清單，然後直接走訪那張反向圖。完整求解器負擔不起為每條邊儲存一列。它改為按需產生前驅局面：還原著法形狀、為每個前驅局面計算排序值，再把更新送往擁有該排序值的分片。這樣每條邊要花更多 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 秒 |
這就是工程上的取捨：密集排序花費格位與排序／反排序的 CPU，來避免儲存反向圖。在這一階層上，記憶體用量降為 1/8.8，單核心執行也快了 1.46 倍，因為省下了建立與保存反向圖的成本。
為什麼沒有執行
引擎、分散式設計、驗證與校準都已完成。要完成完整求解，缺的是租用的運算資源，而不是另一個想法。
這筆花費過不了門檻。技術是已知的，所以結果寫不成論文；遊戲冷門，所以對其值的需求也很少。自掏腰包只能買到一個數字：一款幾乎沒人在玩的遊戲的博弈論值。
這個專案的價值在於能力本身。規則已還原，求解器已建立並驗證，分散式路徑也在完整叢集執行之前用封閉遊戲核對過。解出這款遊戲只會確認一個值；它不會改變方法。
資源：
- Shogi4 檢視器：只允許合法著法的自由對局。
- Shogi4 規則：完整的還原規則集。
- brianhliou/shogi4：Rust 引擎、求解器與驗證測試架。
- 解出動物將棋：下一階層，已完整解出。