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) に入る
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行目の1、2、3、4がそろいます。そうすれば5、6、7、8も簡単に解けます。

3・4番の順番の入れ替え。4が前にあれば間に空きマスを入れ、下のループを11手回して3を前に出し、次に上のループを10手回して1行目の1・2・3・4を完成
3・4番の順番の入れ替え。4が前にあれば間に空きマスを入れ、下のループを11手回して3を前に出し、次に上のループを10手回して1行目の1・2・3・4を完成

9番から15番: 一度に入れる

その後の9〜15は、一度にすべての座標に入るように解く必要があります。そこで9〜12までは順番どおりに番号を並べ、その次は15、14、13の逆順でループを作らないと答えがそろいません。

9〜15番を入れる。下の2行を時計回りに読んだとき9・10・11・12の次に15・14・13となるよう8手で順番をそろえ、ループを10手回して一度に完成
9〜15番を入れる。下の2行を時計回りに読んだとき9・10・11・12の次に15・14・13となるよう8手で順番をそろえ、ループを10手回して一度に完成

直した結果

その後、難しい作業はコーディングAIに任せ、ヒューリスティックが正常に動くかをテストで確認しました。最初に作った solve loop は500局中1局しか解けませんでした。翌日に直したバージョンは4,000局をすべて解き、1局あたり平均91手かかりました。同じ時期に A* 探索で作った教師は、探索の上限内で2,000局中1,105局を解きました。

4×4 パズルを最後までそろえた割合。A* 教師 55%、solve loop 最初のバージョン 0.2%、修正後 100%、DQN 0%
4×4 パズルを最後までそろえた割合。A* 教師 55%、solve loop 最初のバージョン 0.2%、修正後 100%、DQN 0%

段階別に見ると、3番と4番を一緒に入れる区間が平均22.5手で最も長くかかりました。順番を入れ替えてから一緒に回し入れる必要があるため、1番や2番の3倍近くかかります。

solve loop の段階別の平均手数。1番 8.9、2番 7.7、3・4番 22.5、5・6番 13.4、7・8番 16.8、9〜15番 20.6
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) に入るまでその方向にだけ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. 全ソースコードと使用したモデル」の記事で見られます。