2. Corregir la heurística del puzzle deslizante

Por qué añadí el solve loop

Para aplicar las reglas de resolución a la heurística, introduje algo llamado solve loop. El puzzle deslizante (en adelante, TSP) no es originalmente un puzzle cuyo objetivo sea ordenar números. El primer tablero con números es un tablero de práctica, como un tutorial; a partir de ahí aparecen imágenes en el tablero, y se convierte en un juego de memoria visual en el que hay que recordar la imagen. Sin embargo, a la IA le cuesta incluso superar el primer tutorial. Por eso primero le enseñé el proceso de resolución a la heurística.

Fichas 1 y 2: girar en un solo sentido

El proceso de resolución es muy sencillo. Supongamos que queremos llevar el 1 a la primera casilla. Se pone la casilla vacía justo detrás del 1. Luego se forma un bucle que incluya la coordenada de destino (1,1). Si se gira el bucle en un solo sentido, al final el 1 entra en la coordenada (1,1). Después se coloca el 2 del mismo modo y queda colocada la (1,2).

Fichas 3 y 4: ordenarlas y meterlas juntas

Lo siguiente es el problema. Ahora hay que colocar el 3 y el 4 a la vez. Si los números entran en la zona de destino hacia la derecha, el 3 tiene que ir delante y el 4 detrás; si entran hacia la izquierda, el 4 tiene que ir delante y el 3 detrás, y entonces se gira el bucle para que entren en la zona de destino.

Si el 3 y el 4 están en orden inverso, primero se mete la casilla vacía entre los dos números y se gira el bucle. Así se puede intercambiar el orden del 3 y el 4. Después se gira el bucle hasta las coordenadas del 3 y el 4, y queda completa la primera fila 1, 2, 3, 4. Hecho esto, el 5, 6, 7 y 8 también se resuelven con facilidad.

Fichas 9 a 15: meterlas de una vez

A partir de ahí, del 9 al 15 hay que resolverlos de forma que entren todos en sus coordenadas de una sola vez. Por eso, del 9 al 12 se colocan en orden y después hay que formar el bucle con el 15, el 14 y el 13 en orden inverso para llegar a la solución.

Resultado de la corrección

Después dejé el trabajo difícil a una IA de programación y comprobé con pruebas que la heurística funcionaba bien. El primer solve loop solo resolvió 1 de 500 tableros. La versión corregida al día siguiente resolvió los 4.000 tableros, con una media de 91 movimientos por tablero. En la misma época, un profesor construido con búsqueda A* resolvió 1.105 de 2.000 tableros dentro de su límite de búsqueda.

Por etapas, la de meter juntos el 3 y el 4 fue la más larga, con una media de 22,5 movimientos. Como hay que intercambiar el orden y meterlas girando juntas, se tarda casi el triple que con la ficha 1 o la ficha 2.

Con las pruebas descubrí que la heurística también resuelve rápidamente los tableros posteriores con imágenes.

Lo siguiente: entrenar la IA

Después empecé a entrenar la IA. La IA, que al principio caía a menudo en bucles infinitos, podía completar el aprendizaje rápidamente a medida que avanzaba el entrenamiento, pero DQN no pudo resolver este problema. Con el aprendizaje por imitación, que la hacía copiar las soluciones de la heurística, la proporción de movimientos iguales a los de la heurística subió del 32% al 63% a lo largo de 40 iteraciones. Los resultados de volver a ejecutar los modelos entrenados están resumidos en la entrada 4.

El código real de este paso

Este es el bucle que coloca la ficha 1. Cuando la casilla vacía y la ficha 1 están sobre el bucle, se decide una vez el sentido de giro y se bloquea, y se gira el bucle casilla a casilla solo en ese sentido hasta que el 1 entra en (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;
    }

El código fuente completo y los modelos utilizados están en la entrada "4. El código fuente completo y los modelos utilizados".