2. Corrigindo a heurística do quebra-cabeça deslizante

Por que colocamos o solve loop

Para aplicar as regras de resolução à heurística, introduzimos algo chamado solve loop. O quebra-cabeça deslizante (daqui em diante, TSP) originalmente não é um quebra-cabeça de alinhar números. O primeiro tabuleiro com números é um tabuleiro de treino, como um tutorial; depois disso, aparecem imagens no tabuleiro, e ele vira um jogo de memória visual em que você precisa lembrar a imagem. Mas a IA tem dificuldade até para passar do primeiro tutorial. Por isso, primeiro ensinamos o processo de resolução à heurística.

Peças 1 e 2: girar só para um lado

O processo de resolução é muito simples. Digamos que queremos levar o 1 para a primeira casa. Coloque a casa vazia logo atrás do 1. Depois, monte um loop que inclua a coordenada de destino (1,1). Se você girar o loop só para um lado, o 1 acaba entrando em (1,1). Em seguida, posicione o 2 da mesma forma, e (1,2) fica certo.

Peças 3 e 4: acertar a ordem e colocar juntas

A próxima parte é o problema. Agora o 3 e o 4 precisam ser posicionados ao mesmo tempo. Se os números entram na zona de destino indo para a direita, o 3 tem que estar na frente e o 4 atrás; se entram indo para a esquerda, o 4 tem que estar na frente e o 3 atrás, e então o loop é girado para levá-los à zona de destino.

Se o 3 e o 4 estiverem na ordem invertida, primeiro coloque a casa vazia entre os dois números e gire o loop. Assim dá para trocar a ordem do 3 e do 4. Depois, gire o loop até as coordenadas do 3 e do 4, e a primeira linha 1, 2, 3, 4 fica completa. Feito isso, 5, 6, 7 e 8 também ficam fáceis.

Peças 9 a 15: colocar todas de uma vez

Depois disso, as peças de 9 a 15 precisam ser resolvidas de modo que todas entrem nas suas coordenadas de uma só vez. Por isso, de 9 a 12 os números são dispostos em ordem e, em seguida, o loop precisa ser montado com 15, 14 e 13 em ordem inversa para chegar à resposta.

Resultado da correção

Depois disso, deixei o trabalho difícil com uma IA de programação e confirmei com testes que a heurística funcionava corretamente. O primeiro solve loop resolveu só 1 de 500 tabuleiros. A versão corrigida no dia seguinte resolveu todos os 4.000 tabuleiros, levando em média 91 jogadas por tabuleiro. Na mesma época, um professor feito com busca A* resolveu 1.105 de 2.000 tabuleiros dentro do limite de busca.

Por etapa, colocar o 3 e o 4 juntos foi a mais longa, com 22,5 jogadas em média. Como é preciso trocar a ordem e girar os dois juntos para dentro, leva quase três vezes mais que a peça 1 ou a peça 2.

Com os testes, descobrimos que a heurística também resolve rapidamente os tabuleiros seguintes, que têm imagens.

Em seguida, o treinamento da IA

Depois, começamos a treinar a IA. A IA, que no início caía com frequência em loops infinitos, conseguia completar o aprendizado rapidamente à medida que o treinamento avançava, mas a DQN não conseguiu resolver esse problema. Com o aprendizado por imitação, que fazia o modelo copiar as soluções da heurística, a proporção de jogadas iguais às da heurística subiu de 32% para 63% ao longo de 40 iterações. Os resultados de rodar de novo os modelos treinados estão resumidos no post 4.

O código real desta etapa

Este é o loop que posiciona a peça 1. Quando a casa vazia e a peça 1 estão as duas no loop, a direção de giro é decidida uma vez e travada, e o loop é girado uma casa por vez só nessa direção até o 1 entrar em (1,1).

    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;
    }

O código-fonte completo e os modelos usados estão no post "4. O código-fonte completo e os modelos usados".