在出货前用机器证明自动生成的全部400个关卡均可解的故事

在发布自动生成的谜题时，最可怕的是“混入了一个解不开的关卡”。

一旦评论里出现“○○关过不去”，开发者自己就无法判断这到底是生成器的 bug，还是玩家只是看漏了。要靠人工确认 400 个关卡并不现实。

所以，我决定让机器把所有关卡都解一遍。

这篇文章讲的是为此编写的求解器，以及重新设计了一次难度指标的经历。最后，我也会如实放上公开后结果如何的数字。

做了什么

是一款滑动拼图游戏。弹一下方块，它就会滑动，直到撞上某个东西为止。相同颜色接触就会消失。把盘面清空即可通关。

棋盘最大 8×8，关卡共 400 关。无广告、无追踪，可离线运行。使用 Godot 4.7.1 (mono) + C#，面向 Android 发布。

规则本身是旧有的形式。我动手改动的是关卡的制作方式和排列方式。

自动生成谜题的弱点

用编写生成器来替代手工制作，会出现 3 个问题。

会混入无解的关卡
“★3 = 最短步数”中的最短步数，只能靠设计者的感觉来判断
难度排序与体感不一致

1 是致命的。2 和 3 会在无人察觉的情况下降低品质。明明写着“★3 的条件是 5 步”，实际上 4 步就能解出的话，那个关卡要么永远拿不到 ★3，要么反过来过于宽松。

这些都是实际把盘面解一遍就能明白的问题。

所以让它们全部解了一遍

把流水线分成了 4 条命令。

gg-generate  →  gg-curate  →  gg-validate  →  gg-bundle
   生成           選別            検証           同梱

要点是 gg-validate 完全不信任 JSON 中写入的值。是否能解出、最短步数、解答示例、难度指标 ── 全部当场重新计算，并与文件内容进行核对。

/// <summary>スコア再計算との許容誤差。JSON には小数1桁で丸めて保存しているため。</summary>
private const double ScoreTolerance = 0.06;
private const double MetricTolerance = 0.006;

在验证器的注释里这样写道。

规则的解释交由 solver 一侧（Rules / BfsSolver / StateSpaceAnalyzer）负责。
验证器不得重新实现规则。

为了验证而另写一套独立实现，会引发“两套实现同时出错”的事故。相比之下，我判断让规则的实现只保留一份，只重新计算数值并进行比对更为安全。

求解器的实现

是广度优先搜索。逐层推进，到达目标（棋盘为空）时的深度即为最短步数。

把状态打包成 int

将 1 个方块装入 int。

bit  0- 5 : pos    (0..63)   盤面は最大 8x8 = 64 セル
bit  6- 9 : color  (1..15)
bit 10    : fixed
bit 11-18 : uid    (元 blocks 配列でのインデックス)

关键在于不要把 uid 用于判断状态的同一性。只要配置相同，无论经由哪条路径到达，都希望将其视为同一状态。另一方面，输出解答示例时，需要知道「移动的是第几个方块」。

因此，在取键时去掉 uid。

/// <summary>状態の同一性判定に使う部分（uid を除いたもの）。</summary>
public static int Key(int b) => b & KeyMask;   // bit 0-10

正準形

状态的键是将所有方块的 (位置, 色, fixed) 按升序排序后的结果。地形不变，因此不包含在状态中。

public StateKey(ReadOnlySpan<int> blocks)
{
    var cells = new int[blocks.Length];
    for (int i = 0; i < blocks.Length; i++) cells[i] = Blk.Key(blocks[i]);
    Array.Sort(cells);
    ...
}

由于进行了排序，仅仅是对调了同色方块的配置会被视为相同。如果不这样做，状态数会按阶乘膨胀。

也统计解的个数

顺便也统计了最短步数下有多少种解法。只要在推进层时累加到达次数即可。

if (nextCounts.TryGetValue(nk, out long c))
    nextCounts[nk] = SaturatingAdd(c, here);

如果因溢出变成负数，可能会误判为“无解”，所以采用了饱和加法。

这个值后面会起作用。例如免费51面是6×6、最短4步，但正确的步骤只有11种。这个数字直接成为“要通过多窄的路”的指标。

区分 Unsolvable 和 Unknown

这里是有意区分开的。

public enum SolveStatus
{
    Solved,
    /// <summary>全状態を探索したが解がなかった。このレベルは採用不可。</summary>
    Unsolvable,
    /// <summary>探索上限に達して打ち切った。**Unsolvable と混同しないこと。** このレベルは採用不可。</summary>
    Unknown,
}

达到搜索上限（200万节点）而中止的状态，不是“解不出”，而是“不知道是否能解出”。处理方式相同（不采用），但把含义不同的东西用同一个名字，之后必然会被误读。

结果，出货的只剩下了“能够证明可解的面”。“大概能解的面”一个都没有包含。

与客户端共享规则的实现

如果求解器和游戏本体在判定上不一致，验证就失去意义了。这就是“求解器说能解，但在应用里却消不掉”的事故。

我们让这在结构上不可能发生。Godot 侧的 .csproj 通过直接链接引入求解器的源码。

<Compile Include="..\tools\solver\Board.cs"   Link="Shared\Board.cs" />
<Compile Include="..\tools\solver\Blk.cs"     Link="Shared\Blk.cs" />
<Compile Include="..\tools\solver\Rules.cs"   Link="Shared\Rules.cs" />
<Compile Include="..\tools\solver\StateKey.cs"  Link="Shared\StateKey.cs" />
<Compile Include="..\tools\solver\BfsSolver.cs" Link="Shared\BfsSolver.cs" />

因为不是复制而是链接，所以不存在两份实现。 不可能产生偏差。

在此基础上，通过应用侧的连通性测试，在 Godot 运行时上实际回放全部400面的解答示例。

// 全400面の解答例を再生する。1面でも食い違えば共有が壊れている。
foreach (var mv in level.Solution!.Example) model.TryApplySolutionMove(mv);

构建时运行的测试目前共有59个。如果这里挂了，说明某处已经从根本上坏掉了。

重新设计难度指标这件事

这里花的时间最多。

最初的设计

难度分数用的是这样一个公式。

double raw =
      minMoves                 *  5.0
    + (1.0 - openingAccuracy)  * 20.0
    + deadEndRatio             * 30.0
    + branchingFactor          *  0.5
    + blockCount               *  0.8
    + (colorCount - 2)         *  3.0;

openingAccuracy ── 在所有合法首步中，能够维持最短通关路径的手的比例
deadEndRatio ── 进入死局的比例
branchingFactor ── 平均合法步数

最初我把这个 deadEndRatio 直接实现为「深度在 minMoves 以内可达的状态中，无法通关的状态所占的比例」。

返回了 0.95

在 6×6、8 个方块的棋盘上得到了 0.95。会被归类为 expert。但实际玩起来，并没有那么难。

原因很简单。状态数会随深度呈指数增长，因此比例只由最深层决定。

如果到深度4为止的状态数按 10 / 60 / 300 / 1500 递增，那么最深层在总数中所占的比例是压倒性的。而且越深的层死局越多。结果，这个指标测量的不是难度，而是分支数。

按深度分别测量并取平均

改变了测量对象。不是“有多少比例的状态是死局”，而是“从仍能获胜的状态下走出的一手，导致失去胜利的概率”。按深度分别算出这个值，再取平均。

bool Alive(int i) => dist[i] >= 0 && depth[i] + dist[i] <= maxDepth;

for (int v = 0; v < index.Count; v++)
{
    foreach (int u in reverse[v])
    {
        int d = depth[u];
        if (d >= minMoves) continue;   // 起点が深すぎる手は数えない
        if (!Alive(u)) continue;       // すでに詰んでいる状態からの手は数えない
        edgesFrom[d]++;
        if (!Alive(v)) blunders[d]++;
    }
}

按深度分别算出 blunders[d] / edgesFrom[d]，然后取平均。按深度加权消失了，变成了对应“不小心破坏步骤的概率”的数字。

到目标的距离，是在前向BFS过程中记录反向边，再从目标进行反向BFS求出的。

按深度限制搜索

初版会枚举所有可达状态，但在6×6、8个方块的情况下超过了500万个状态，因而失效了。

现在将深度限制为 minMoves + 2。不仅能抑制计算量，还成为了衡量“留下还差2手的余量，最短通关的希望却消失了”这一玩家实际感受到的难度的指标。结果上，这一限制反而完善了定义。

出现的数字

在400个关卡中，easy 和 expert 的结果如下。

	easy	expert
第一步正确的概率	45〜70%	17〜20%
死胡同的比例	23〜27%	46〜48%

在 expert 中，最初的 5 个首步里有 4 个是死局。

tier 的阈值并非推测，而是根据生成的 207 个盘面的分数分布反推出来的。实测中分数的出现范围是 31〜81，并未使用 0〜100 的整个区间。

public static string Tier(double score) => score switch
{
    < 43 => "tutorial",
    < 56 => "easy",
    < 67 => "normal",
    < 77 => "hard",
    _    => "expert",
};

题外话：无法用步数衡量难度

经过汇总，发现了一些情况。

关卡包	最短手数
無料100面	2〜6手
追加200面	4〜6手
高難易度100面	5〜6手

任何关卡包最长都是 6 步。 难的关卡并不是更长。难度不是来自长度，而是来自可选项的狭窄。

得益于这一特性，还带来一个副产品：关卡介绍视频只需 10 秒左右。

只在真机上出现的 bug

在桌面上全部都能通过，但在真机上首次出现了 4 个。

1. 一次点击会收到两次输入

由于 emulate_mouse_from_touch 默认启用，手指点击会同时产生触摸事件和合成鼠标事件。评分控件在两种事件下都会翻转，看起来像死掉了一样。我改成了只要看到一次触摸，之后便忽略鼠标事件。

2. 通关后棋盘卡住

因为我把“如果已通关就什么也不做”写在了处理松开通知之前，导致 _dragging 永久停留在 true 状态。

// 離した通知は、何があっても先に処理する
if (@event is InputEventScreenTouch { Pressed: false } or
              InputEventMouseButton { Pressed: false })
    _dragging = false;
if (_model is null || _model.IsCleared || Locked) return;

3. 日文全都变成豆腐块

在某台设备（Android 16）上，回退到系统字体没有生效，CJK 全都变成了□。于是我不再依赖设备字体，而是捆绑了根据 UI 中实际使用的字符串生成的子集（Noto 5 种字体，约 200KB）。我还加了一项测试：如果译文中出现子集之外的字符，就让构建失败。

4. 发送按钮沉到软键盘下面

如果把整个 UI 往上挪，标题就会跑到屏幕外，所以改成了把容器按键盘高度缩小的形式。VBox 被挤压，按钮正好位于键盘正上方。

另外 VirtualKeyboardGetHeight() 返回的是实际画面的像素。在 stretch mode = canvas_items 中需要转换为视口单位（与 GetDisplaySafeArea() 相同）。

并非 bug 的情况：Android 的导出模板要求 net9.0。编辑器的运行时是 net8.0，所以构建能通过，只有导出会失败。

实际发出去之后怎么样

这里我实话实说。

产品版的审核花了 13 天（明明封闭测试＋数据安全申报只用了 16 分钟就通过了）
上线两周内，新增安装 0 件
过去 28 天的商店展示次数 158 次（平均每天约 5.6 次）
月活跃设备 7

购买数为零。

有一阵子我一直以为「每天大概能进来 7 件」，但那其实是正式版轨道卡片上显示的累计安装数，并非新增获取。也就是说，我没有确认数字的含义，就把它拿来做了除法。

另一方面，只有一个数据还算不错。

商店页面的转化率 76.19%。 来到上架页面的人里，每 4 个就有 3 个安装。

也就是说，问题不在于内容或文案，而在于它根本没有被展示出来。我准备了 15 种语言的文案，但起作用的位置不对。这等于入口根本没人来，我却在打磨入口的招牌。

「只要做出来，总会有人发现」这句话，至少在我的应用上没有发生。

总结

自动生成的谜题，可以先让它们全部被解开之后再放出。 用机器验证 400 关，成本比想象中更现实
不要让验证器重新实现规则。 实现只保留一份，只重新计算数值并进行比对
只要求解器和客户端共享源码，就不可能再出现判定不一致的情况
把“解不出来”和“不知道”当作两回事来处理
要确认指标是否真的在测量你想测的东西。 我最初的 deadEndRatio 测的不是难度，而是分支数
而且，质量不能替代曝光

最后一行代价最高。不过制作过程倒是挺开心的。

做出来的东西就是这个。可以免费玩100关。

如果有想了解的求解器相关问题，我会在评论区回答。