Sokoban AI Solver: A* macro-push optimizado en JS

¿Qué es el Sokoban y por qué importa como benchmark de IA?

El Sokoban, juego de puzzle creado en Japón en la década de 1980, sigue siendo uno de los benchmarks más exigentes para evaluar algoritmos de búsqueda inteligente. El objetivo es simple: empujar cajas hasta marcaras todas en posiciones objetivo dentro de un almacén en cuadrícula. Pero bajo esa simplicidad se esconde un problema NP-hard que ha desafiado a investigadores en inteligencia artificial durante décadas.

Lo que acaba de compartirse en Hacker News no es otro solver cualquiera. Se trata de un port en JavaScript puro del solver óptimo en C++ escrito por Max Kornreich, disponible públicamente en su repositorio de GitHub. Lo interesante no es solo que resuelva puzzles, sino cómo lo hace: emplea técnicas avanzadas de optimización algorítmica que mantienen el rendimiento en tiempo real incluso en el navegador.

Para cualquier founder o ingeniero de software, este proyecto ilustra algo fundamental: la optimización de algoritmos de búsqueda es un skill directamente transferible a problemas reales de logística, planificación de rutas y scheduling — áreas donde las startups enfrentan costos exponenciales cuando sus soluciones escalan mal.

¿Cómo funciona el macro-push A* de este solver?

El núcleo del solver es una implementación de A* con macro-pushes, una variante sofisticada que cambia radicalmente la forma de explorar el espacio de estados:

Macro-push A*. En lugar de explorar cada paso individual del personaje (arriba, abajo, izquierda, derecha), cada arista de búsqueda representa un empuje completo de caja. El costo de cada arista se calcula como la distancia mínima que el keeper debe caminar hasta el punto de empuje más uno. Esto significa que el algoritmo salta directamente sobre los pasos de caminata y busca únicamente secuencias de empujes óptimas, reduciendo drásticamente el branching factor.

Estados compactos con bitmask. Las cajas se codifican en un entero de 32 bits sobre las celdas "vivas" alcanzables del tablero, y el keeper en un número adicional. Un estado completo ocupa aproximadamente 8 bytes en lugar de un objeto de ~1 KB. Esta compresión permite que millones de estados caben en decenas de megabytes de RAM.

Dial bucket queue + hash abierto. La frontera de búsqueda usa un bucket queue indexado por costo, mientras que el conjunto de estados visitados vive en un hash plano con typed arrays. Es allocation-free y cache-friendly, dos propiedades críticas para el rendimiento en entornos con recursos limitados como un browser tab.

Deadlock pruning. Un dead-square table estático basado en reverse-reachability desde los objetivos, combinado con una verificación de congelamiento (freeze check), descarta posiciones provablemente irresolubles antes de que el A* pierda tiempo explorándolas. Todo guiado por un lower bound de distancia de empuje consciente de las paredes que mantiene la admisibilidad del algoritmo.

Rendimiento comparado: ¿qué tan bueno es este solver?

Los resultados hablan por sí solos. Los tableros 1 al 14 se resuelven en milisegundos directamente en el navegador, devolviendo soluciones provadamente óptimas. El tablero 15 —el laberinto de 8 cajas— es la excepción que confirma la regla: su búsqueda óptima explora ~49 millones de estados y requiere más de 1 GB de memoria, por lo que se resolvió offline en ~5 segundos usando 24 núcleos y la solución se reproduce precomputada.

Para contextualizar este rendimiento, hay estudios comparativos recientes que midieron algoritmos en 99 niveles de Sokoban. Según datos de ZaMinVo/sokoban-algorithmic-solver, que evaluó cuatro enfoques diferentes:

Algoritmo	Niveles resueltos	Éxito promedio	Tiempo promedio
BFS estándar	94/99	94,9%	0,375 s
A* Normal	95/99	96,0%	0,462 s
A* con heurística Hungarian	95/99	96,0%	0,877 s

La diferencia clave del solver de Kornreich frente a estos benchmarks es que opera en el espacio de empujes (push-space), no en el espacio de movimientos individuales. Mientras que el BFS estándar genera un branching factor de aproximadamente 1,0 a 1,5 por movimiento, el macro-push A* reduce ese factor enormemente al tratar cada empuje como una unidad atómica. Eso explica por qué puede alcanzar optimalidad garantizada en tiempos que un BFS ingenuo no podría sostener.

Otro estudio de trihaingn/sokoban-solver compara BFS contra un enfoque híbrido heurístico, mostrando que mientras el BFS garantiza soluciones óptimas pero colapsa en niveles complejos, los métodos heurísticos son más rápidos pero sacrifican optimalidad. El macro-push A* intenta cerrar esa brecha.

¿Qué significa esto para tu startup?

Este tipo de optimización algorítmica tiene aplicaciones directas que van mucho más allá de resolver puzzles. Aquí hay tres lecciones concretas que puedes aplicar hoy:

1. Reducir el branching factor es la palanca más poderosa en búsqueda. Si estás construyendo un sistema de planificación, routing o scheduling, no explores todos los estados posibles. Agrupa acciones en operaciones significativas (como el macro-push agrupa caminatas en empujes) y busca en ese espacio abstracto. Cada reducción en branching factor se traduce en crecimiento exponencial de velocidad.

2. La representación de estados determina si tu solución escala. Mover de objetos JSON a estructuras compactas (bitmasks, typed arrays, flat hashes) puede reducir el consumo de memoria de kilobytes a bytes por estado. Para sistemas que procesan miles o millones de configuraciones, esta optimización no es opcional: es lo que separa una demo de un producto.

3. La detección temprana de imposibles vale más que la búsqueda exhaustiva. El deadlock pruning del solver elimina ramas muertas antes de expandirlas. En tu negocio, implementa validaciones rápidas que descarten opciones inviables antes de invertir recursos completos en analizarlas — ya sea en filtros de leads, validación de requisitos técnicos o screening de proveedores.

Acciones concretas para implementar

• Audita tus pipelines de decisión: identifica dónde estás explorando estados innecesarios y agrega filtros de viabilidad temprana que eliminen caminos muertos antes de profundizar.
• Revisa la representación de datos: si tu sistema maneja múltiples configuraciones o estados, evalúa si puedes comprimirlos en estructuras más densas (IDs numéricos, bitfields, enums) en lugar de objetos con propiedades.
• Considera espacios abstractos de búsqueda: en lugar de resolver cada sub-paso individualmente, agrupa acciones en bloques lógicos y busca en ese nivel superior. Es el principio detrás del macro-push A*.

Fuentes

• Sokoban AI Solver by Max Kornreich
• Sokoban Solver: A Comparative Study of Search Algorithms