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번 넣기. 아래 두 줄을 시계 방향으로 읽었을 때 9·10·11·12 다음 15·14·13이 되도록 8수로 순서를 맞추고, 루프를 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. 전체 소스 코드와 사용한 모델’ 글에서 볼 수 있습니다.