简而言之

  • 微型将棋是一种 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 亿。第一次尝试还发现了一个具体的 bug：前驱偏移量存成了 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 的运行是一次有用的标定，但更重要的结果是重跑。它把方法从「保存每一条可达前驱边」改成了「给局面做稠密编号并按需生成前驱」。

那个求解器枚举可达局面，用一个 HashMap 把局面键映射到稠密 id，并存储一份压缩稀疏行格式的前驱边表。它容易验证，在内存装得下时也很快。一旦图达到数十亿条边，它本身就成了问题。

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 值一致。第一次稠密运行还暴露了一个较小的效率 bug：它为每个子局面都生成了两种镜像朝向，再做规范化，然后把一半丢掉。镜像感知的重跑去掉了 81.6 亿个重复前驱 id，把传播时间从 9,229 秒缩短到 4,961 秒。

最终的稠密运行才是有用的对照点：值相同，内存少到 1/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 周，这还没算上工程开销和验证重跑。内存数字只是那张扁平的值表，不是整个集群的占用。真实的运行还需要计数器、队列、检查点和 shuffle 空间。

这就是微型将棋比 Shogi4 更靠后的原因。它小到可以算出成本，但又大到随手跑一次云上运行会成为一种非常昂贵的发现架构 bug 的方式。

这些运行改变了什么

在 KPG 之前，微型将棋的计划基本上只是从 KP 和动物将棋做的规模外推论证。有了 KPG 之后，关键的不确定性收窄了：

  • 目前这套可达 HashMap + CSR 的求解器可以回答到 KPG 为止的标定问题，但它在 64 GB 上已经勉强，到此为止。
  • 稠密编号加按需前驱，是微型将棋正确的生产形态，而不只是 Shogi4 的一个细节。
  • 内存取舍是有实测的：在同样的 KPG 值上从 60.5 GiB 降到 6.86 GiB。
  • 镜像处理重要到值得实测。在第一次稠密运行中，生成对称的重复前驱几乎让传播时间翻倍。
  • 完整求解的预算应按排列编号域来算，而不是按可达局面的估算值。

剩下的工作说清楚不难，做起来仍然量大：对照一手资料或一个独立引擎确认规则、用精确计数取代可达局面的区间估算、为完整材料集构建分桶的稠密编号／反编号、实现完整微型将棋的撤销着法生成，并在为完整残局库付费之前跑一次规模较小的分布式预演。

眼下的结果是一份有实测标定的进展报告：KPG 已解决并通过校验，可扩展的方法已在同一份数据上验证过，而完整的微型将棋求解看起来是 PB 量级，而不是笔记本量级。

资源：