微型将棋是一种 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 王、步 457,993 和棋 135,804 / 2,956 / 319,233 29 6.86
KPG 王、步、金 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 级别，而非笔记本级别。

资源：