2. 修正滑块拼图启发式

加入solve loop的原因

为了把解题规则应用到启发式上，我们引入了一个叫solve loop的东西。滑块拼图（以下简称TSP）原本并不是以对齐数字为目的的拼图。最开始带数字的盘面是练习盘，有点像教程；之后盘面上会出现图片，变成一个记住这张图片的图像记忆游戏。可是AI连第一个教程都很难通过。所以我们先教会了启发式解题过程。

1号和2号：只朝一个方向转

解题过程非常简单。假设要把1号移到第一个格子，就把空格放在1号后面。然后构建一个包含目标位置(1,1)坐标的环。只要一直朝一个方向转动这个环，1最终就会进入(1,1)坐标。接着用同样的方法对齐2，(1,2)也就对好了。

用solve loop放入1号。在1号后面放空格，构建一个到(1,1)为止的2×3环，只朝较短的方向转动，10步后1号进入(1,1)

3号和4号：排好顺序一起放入

接下来才是问题。现在必须同时对齐3号和4号。如果数字向右进入正确区域，就必须3在前、4在后；反过来如果向左进入，就必须4在前、3在后，再转动环，才能进入正确区域。

如果3和4的位置是反的，就先在两个数字之间放入空格并转动环。这样就能交换3和4的顺序。然后把环转到3、4的坐标处，就能对齐第一行的1、2、3、4。这样一来，5、6、7、8也能轻松解开。

交换3号和4号的顺序。如果4在前面，就在两者之间放入空格，把下方的环转11步让3到前面，然后把上方的环转10步，完成第一行1·2·3·4

9号到15号：一次性放入

之后的9～15号，必须一次性解到所有坐标上。所以9～12要按顺序排列，接下来要按15、14、13的倒序构建环，才能得出答案。

放入9～15号。用8步调整顺序，使下面两行按顺时针方向读起来是9·10·11·12，然后是15·14·13，再把环转10步一次性完成

修正的结果

之后，困难的工作交给编程AI，我们通过测试确认启发式是否正常运作。最初做的solve loop在500局中只解开了1局。第二天修正后的版本解开了全部4,000局，平均每局需要91步。同一时期用A*搜索做的教师，在搜索上限内解开了2,000局中的1,105局。

完整还原4×4拼图的比例。A*教师55%，solve loop第一版0.2%，修正后100%，DQN 0%

按阶段来看，同时放入3号和4号的区间平均22.5步，是最长的。因为要交换顺序再一起转进去，所以花的步数接近1号或2号的三倍。

solve loop各阶段的平均步数。1号8.9，2号7.7，3·4号22.5，5·6号13.4，7·8号16.8，9～15号20.6

在测试过程中我们发现，启发式对之后带图片的盘面也能很快解开。

接下来是AI训练

之后我们开始训练AI。一开始经常陷入无限循环的AI，随着训练的推进很快就能完成学习，但DQN没能解决这个问题。让模型模仿启发式解法的模仿学习，在重复40次的过程中，与启发式选择相同着法的比例从32%提高到了63%。重新运行训练好的模型的结果整理在第4篇中。

这一步的实际代码

这是放入1号的环。当空格和1号都位于环上时，先确定一次转动方向并锁定，然后只朝该方向一格一格地转动，直到1号进入(1,1)。

src/puzzle_planner.cppcpp · 28 行

    const bool use_snake = (target == 1) && tile1_snake_applicable(s);
    const bool snake_rotate_ready =
        use_snake && is_on_tile1_snake(s.blank_r, s.blank_c) && tile_position_on_snake(1, s);
    if (snake_rotate_ready && loop_ctx && loop_ctx->locked_dir) {
        if (!loop_ctx->locked_dir->has_value() || (loop_ctx->locked_target
                                                   && *loop_ctx->locked_target != target)) {
            lock_loop_dir_if_needed(loop_ctx,
                                    target,
                                    pick_best_snake_dir(s, target),
                                    "snake until tile1→A1");
        }
        const SnakeLoopDirection dir = loop_ctx->locked_dir->value();
        const auto chunk = snake_directed_one_step(s, target, dir);
        if (!chunk || chunk->empty()) {
            out.note = std::string("snake_") + snake_loop_direction_label(dir) + "_fail";
            return out;
        }
        const int a = (*chunk)[0];
        const TileCellMove mv = make_tile_move(s, static_cast<PuzzleAction>(a));
        if (!apply_action_on_tile1_snake(s, static_cast<PuzzleAction>(a), target)) {
            out.note = std::string("snake_") + snake_loop_direction_label(dir) + "_apply_fail";
            return out;
        }
        out.moves.push_back(mv);
        out.reached_goal = tile_at_goal(target, s);
        out.note = std::string("snake_") + snake_loop_direction_label(dir);
        return out;
    }

完整源代码和所用模型可以在“4. 完整源代码与使用的模型”一文中查看。