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 棋盘上进行，每方五枚棋子，全部每回合走一格：
初始局面。棋子归属由朝向而非颜色表示。
| 棋子 | 走法 |
|---|---|
| 王（鹤 / 雉） | 向 8 个方向任一走一格（相当于王） |
| 鲤 | 向前走一格 |
| 狐 | 沿直线走一格 |
| 狸 | 沿斜线走一格 |
| 貘 | 向前或前斜方向走一格 |
有三条规则让 Shogi4 需要独立的引擎，而不是把动物将棋的引擎改一改就行：
- 打入。 被吃的棋子转归对方，并可从手中放回任意空格，因此子力总量守恒。唯一限制是不得打入对方底线。
- 升变。 走到最远一行的棋子必须升变：鲤、貘、狸升为银将的步法集合，狐升为金将。被吃的已升变棋子会还原为基础形态。
- 越友跳。 若合法走法方向上相邻的格子里有己方棋子，该棋子可越过它落到相隔两格处。只能越过一枚己方棋子，不能连跳，也不能越过敌方棋子。动物将棋中没有对应规则。
捕获对方的王即为胜。没有将军或将死的概念，走到可被吃的位置是合法的，也不存在王行到底取胜的规则。与动物将棋相比，多一枚棋子、更宽的棋盘、更广的升变集合、打入限制以及越友跳规则，足以要求一个全新的引擎。
为什么完整的 Shogi4 是一个分布式问题
强解通过逆向分析为每个局面赋一个值（胜、负或和棋），从终局局面（这里指王被吃掉）向后推算。若某着能到达一个负局面，则该局面为胜；若所有着法都到达胜局面，则为负；否则为和棋。
在国际象棋中，吃子只会减少子力，因此求解可分解为一系列越来越小的残局，可以自下而上逐层求解。打入规则破坏了这种结构。被吃的棋子会回到场上，子力固定不变，整个图是一个强连通的单一环，必须作为一个整体求解。这个整体很大：
| 数量 | 数值 |
|---|---|
| 全排列上界（精确值） | 205,148,532,253,680 |
| 从初始局面可达 | ~3×10¹³ |
| 稠密秩索引域 N | 410,297,064,507,360 |
求解器用稠密秩（局面到整数的双射）为局面编号，因此值表就是一个扁平数组，查表为 O(1)。索引必须覆盖每种合法摆放，所以决定规模的是 N（约 4×10¹⁴）而非可达局面数：每格两比特约需 100 TB，按精确的左右对称折叠后约 50 TB。这使完整求解成为一项分布式外存计算，而不是能放进内存的任务。
完整求解的设计
求解器采用推送式。每个局面保存一个未定子节点计数器。终局局面（下一着即可被吃掉王）作为胜局面播种，随后值向后传播：只要某局面有一着进入负局面，它立刻成为胜；某局面的计数器降到零，意味着它的所有子节点都已是胜，它就成为负。值只会从已定流向未定，因此整个计算是一个单调不动点。
为了扩展到多台机器，秩空间被划分为若干分片，每个分片拥有其槽位的值和计数器。解算一个局面时，通过逆着法生成其前驱局面，并把每个前驱作为消息发送给拥有它的分片。这种路由就是 shuffle，也是工作量的主体：每个局面约 7 条前驱消息，完整规模下为 15 到 30 PB。
每个分片拥有稠密秩表的一个切片。消息把计算搬到拥有该前驱的分片上。
工作节点以超步为单位，在屏障后推进。每个节点消耗当前一轮的消息，解算力所能及的部分，并发出下一轮消息。由于不动点是单调的，最终的值表既不依赖空间如何分片，也不依赖消息到达的顺序。分片只改变调度，绝不改变答案，正是这一性质使该计算可以安全地分布式化。
相比算力，存储对计算形态的决定作用更大。值数组分片存放在磁盘上，按超步流式读取并丢弃，而不是常驻内存；精确的左右折叠把存储和工作量都减半。
验证
引擎与一份独立实现的 Python 版反编译应用进行了对照检查。索引和值分别校验。
着法生成。 perft（从初始局面起各搜索深度上的着法树节点数）逐位一致：
| 深度 | 局面数 |
|---|---|
| 1 | 8 |
| 2 | 64 |
| 3 | 626 |
| 4 | 6,304 |
| 5 | 68,723 |
| 6 | 769,014 |
另有一项对随机对局（打入、升变、吃子、跳跃）的 4,000 局面差分测试，两个引擎之间的着法列表不匹配数为零。
索引。 稠密秩是经过验证的双射：在每个小型博弈索引上，先求秩再逆求秩都是恒等映射，且它枚举出的局面与直接枚举结果一致。它在完整博弈上的定义域恰好是独立排列计数的两倍。该枚举器还在动物将棋上做了对照，重现了 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）形式的全部前驱边列表，然后直接遍历这张反向图。完整求解器负担不起为每条边存一行。它改为按需生成前驱：撤销着法形态，为每个前驱求秩，并把更新发送给拥有该秩的分片。这样每条边的 CPU 开销更高，但这正是内存受限的捷径与真正的外存求解器之间的区别。
在做出上述估算之后，我在一个相关的 4×5 微型将棋台阶上实测了这一取舍：每方 K+P+G，869,287,068 个可达规范局面。基于可达局面 HashMap + 存储 CSR 的求解器峰值 RSS 约 60.5 GiB，核心求解耗时 12,385 秒。而一个针对 KPG 的稠密秩 + 逆着法求解器使用了 2,037,557,340 个秩槽位（是可达局面数的 2.34 倍），重现了完全相同的值计数，峰值 RSS 约 6.86 GiB，总求解时间 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 引擎、求解器与验证工具。
- 求解动物将棋：下一级台阶，已完整求解。