Solvable Sokoban Without a Solver via Diffusion

En el mundo de la informática, existe una clase de problemas tan complejos que verificar una solución puede ser fácil, pero encontrar una requiere navegar por un laberinto de posibilidades tan vasto que tardaría más que la edad del universo en resolverse mediante la fuerza bruta. Estos no son meramente acertijos difíciles; son problemas donde el camino hacia la respuesta no es solo largo, sino exponencialmente largo, lo que significa que cada paso que das puede abrir un universo de nuevas posibilidades mientras cierra otros simultáneamente. Uno de los ejemplos más famosos de esto es un juego llamado Sokoban, que se juega en una cuadrícula donde un único personaje debe empujar cajas hacia cuadros de objetivo específicos. El detalle es que el personaje solo puede empujar, nunca tirar, y una vez que una caja queda encajonada en una esquina, a menudo queda atrapada para siempre. Debido a que la posición de una sola caja puede alterar completamente la accesibilidad de todo el tablero, el juego no puede descomponerse en tareas pequeñas e independientes. Resolverlo requiere un plan holístico que contemple cada interacción antes de realizar un solo movimiento. Durante décadas, la capacidad de generar nuevos rompecabezas válidos de este tipo ha sido un desafío, porque crear un laberinto resoluble es tan difícil como resolver uno, y verificar si un laberinto funciona suele requerir una computadora potente para simular cada movimiento posible.

Un estudio reciente ha encontrado una forma sorprendente de generar estos complejos rompecabezas sin haber enseñado nunca a la computadora cómo resolverlos. Los investigadores entrenaron un tipo de modelo de inteligencia artificial para rellenar las piezas faltantes de una cuadrícula de Sokoban, de forma muy similar a como un humano completa un crucigrama adivinando las palabras faltantes basándose en las letras circundantes. El modelo fue mostrado miles de rompecabezas reales y se le pidió que aprendiera los patrones de paredes, suelos y cajas, pero nunca se le dijo qué rompecabezas eran resolubles, ni se le dieron recompensas por crear un juego funcional. Simplemente aprendió a predecir qué baldosa debería ir en un lugar oculto basándose en las baldosas ya visibles. El resultado fue asombroso: cuando el modelo generaba nuevos rompecabezas desde cero, el 77.4 por ciento de ellos eran resolubles. Este es un resultado notable porque el modelo nunca fue entrenado explícitamente para asegurar la resolubilidad; solo fue entrenado para rellenar los huecos. Los investigadores descubrieron que la capacidad de crear un rompecabezas resoluble no era una habilidad separada que el modelo aprendió, sino un subproducto natural de aprender los patrones locales del juego.

El éxito de este enfoque reside en cómo el modelo piensa sobre la cuadrícula. Los programas informáticos tradicionales que generan secuencias, como los que escriben texto, trabajan en un orden fijo, decidiendo la primera palabra, luego la segunda, luego la tercera. Este enfoque lineal tiene dificultades con Sokoban porque una decisión tomada al principio de la cuadrícula puede restringir lo que es posible al final, creando un conflicto que el programa no puede corregir más tarde. El modelo utilizado en este estudio, sin embargo, no sigue un orden fijo. Comienza con una cuadrícula completamente vacía donde cada celda está oculta y las revela una por una en una secuencia aleatoria. En cada paso, observa todo el tablero tal como está en ese momento —paredes aquí, cajas allá y espacios vacíos en otros lugares— y decide qué pertenece al siguiente espacio oculto. Esto le permite colocar una pared en una esquina y un objetivo en la esquina opuesta, y luego idear el pasillo que los conecta, ajustando su comprensión de todo el tablero con cada nueva pieza que revela. Esta flexibilidad refleja la forma en que un jugador humano debe pensar sobre el juego, donde la dificultad proviene de las interacciones no locales entre partes distantes del tablero.

Para probar qué tan bien funcionó este método, los investigadores generaron 50,000 nuevos rompecabezas y verificaron cada uno con un solucionador estándar. Descubrieron que casi tres cuartas partes de los rompecabezas eran resolubles de inmediato. Aún más revelador fue lo que sucedió con los rompecabezas que fallaron. En el 94.5 por ciento de los casos no resolubles, el rompecabezas podía arreglarse simplemente eliminando una sola pared interior. Esto sugiere que el modelo no estaba adivinando al azar; estaba creando estructuras que eran casi totalmente correctas, con solo errores menores y superficiales que impedían una solución. Los investigadores también verificaron para asegurarse de que el modelo no estuviera simplemente memorizando los rompecabezas que había visto durante el entrenamiento. Compararon los nuevos rompecabezas con el conjunto de datos original y encontraron que los rompecabezas generados eran tan diferentes de los datos de entrenamiento como lo son los rompecabezas reales no vistos. El modelo había aprendido la estructura subyacente del juego, no solo una lista de ejemplos específicos.

El estudio también exploró cómo cambiaba el comportamiento del modelo cuando los investigadores ajustaban su confianza. Al hacer que el modelo fuera más decisivo en sus elecciones, pudieron aumentar la tasa de resolubilidad a casi el 99 por ciento, aunque esto tuvo el costo de crear rompecabezas con un poco más de paredes de lo habitual. El ajuste predeterminado, sin embargo, producía rompecas de forma que coincidían perfectamente con la densidad de paredes encontrada en el conjunto de entrenamiento original. Este equilibrio entre estructura y aleatoriedad es clave. El modelo aprendió que, para que un rompecabezas sea válido, las paredes y las cajas deben encajar de una manera muy específica, y al aprender a rellenar los huecos correctamente, aprendió inadvertidamente las reglas de la resolubilidad. Los investigadores señalaron que el rendimiento del modelo en la propiedad global de la resolubilidad siguió mejorando mucho después de que su capacidad para predecir baldosas individuales hubiera dejado de mejorar. Esto indica que los dos objetivos son distintos: un modelo puede ser bueno rellenando una sola baldosa sin ser bueno creando un rompecabezas completo, pero en este caso, dominar los detalles locales fue suficiente para desbloquear la solución global.

Las implicaciones de este hallazgo se extienden más allá de solo crear mejores rompecabezas. Demuestra que las propiedades globales complejas pueden emerger de objetivos de entrenamiento locales simples. El modelo nunca recibió la instrucción de que un rompecabezas deba ser resoluble, pero aun así aprendió a crearlos. Esto sugiere que la estructura de los datos en sí misma contiene la lógica de la solución, y que un modelo capaz de comprender las relaciones entre todas las partes de un sistema puede heredar la capacidad de resolverlo. Los investigadores confirmaron que el modelo no estaba utilizando un solucionador oculto para guiar su generación. Cada paso del proceso fue impulsado por las propias predicciones del modelo basadas en las partes visibles de la cuadrícula. El hecho de que el modelo pudiera generar un laberinto resoluble sin haber visto nunca la ruta de la solución es un testimonio del poder de aprender los patrones de un sistema profundamente para reproducir sus propiedades más difíciles.

Al final, el trabajo muestra que la barrera entre generar un problema y resolverlo no es tan alta como se pensaba. Al entrenar a un modelo para simplemente completar un patrón, los investigadores desbloquearon la capacidad de crear desafíos válidos y complejos. El modelo no necesitaba ser un gran maestro del juego para crear un juego que valiera la pena jugar; solo necesitaba entender las reglas de las baldosas. Este enfoque ofrece una nueva forma de pensar sobre la inteligencia artificial, sugiriendo que si enseñamos a un sistema a comprender las relaciones locales dentro de un mundo complejo, este puede aprender naturalmente a navegar los desafíos globales de ese mundo sin haber sido enseñado explícitamente cómo hacerlo. Los rompecabezas generados no eran perfectos, pero estaban lo suficientemente cerca como para que un pequeño ajuste pudiera hacerlos funcionar, demostrando que el modelo había captado la esencia del juego.