CayleyPy supera a los algoritmos clásicos en la resolución de cubos de Rubik grandes

El proyecto CayleyPy impulsa una serie de concursos en la plataforma Kaggle dedicados a encontrar soluciones óptimas para rompecabezas mecánicos cuyo número de Dios es desconocido. En lugar de algoritmos clásicos como IDA* y la búsqueda bidireccional en anchura (BFS), que dependen de tablas precalculadas (Pattern Databases), CayleyPy aplica una heurística neuronal entrenable. En el cubo de Rubik clásico 3×3×3, con un diámetro de grafo de 20 movimientos (métrica HTM, Tomas Rokicki, 2010), el sistema alcanzó un 98,4% de soluciones óptimas, superando a DeepCubeA (60,3%) y EfficientCube (69,6%).

Arquitectura: tres pasos de las caminatas aleatorias a la búsqueda

El método consta de tres etapas. La primera es la generación de muestras: se parte de un cubo resuelto, se mezcla de forma aleatoria y se guarda, para cada estado, un par «configuración-distancia al origen». La segunda es el entrenamiento: la red neuronal aprende a predecir la distancia a partir del estado, convirtiéndose así en una heurística de búsqueda. La tercera es el Beam Search: el algoritmo mantiene W de las posiciones más prometedoras (habitualmente W=5 o W=40), evalúa a sus vecinos y selecciona las W mejores. El proceso se repite hasta resolver el cubo o alcanzar el límite de búsqueda.

Una conclusión importante de los experimentos: aumentar el tamaño de la muestra de entrenamiento deja de mejorar rápidamente la calidad de la heurística, mientras que ampliar el ancho del haz reduce de forma constante la longitud de la solución.

Del cubo 4×4 al megaminx: avances en diámetros desconocidos

En el cubo 4×4×4, el espacio contiene 7,4×10⁴⁵ estados (26 órdenes de magnitud más que el 3×3). El número de Dios es desconocido; se conocen los límites: entre 32 y 53 movimientos en la métrica BTM, con una hipótesis de 48 movimientos. CayleyPy alcanzó un promedio de 46,51 movimientos en la clasificación final, superando a Tomas Rokicki.

En el megaminx (dodecaedro), el espacio de estados es de aproximadamente 1,01×10⁶⁸. La configuración Superflip (todas las aristas invertidas, con las esquinas y centros en su lugar) se consideraba una candidata potencial a ser la más alejada del estado resuelto. Tomas Rokicki resolvió Superflip en 55 movimientos bajo la métrica FTM en mayo de 2023. Herbert Kociemba estableció en 2016 el límite inferior del diámetro del megaminx: 48 movimientos en FTM.

Vladislav Kuznetsov, usando CayleyPy, resolvió Superflip en 47 movimientos bajo FTM en mayo de 2026. De la desigualdad 47<48 se desprende directamente que Superflip no es el antípoda del grafo de Cayley del megaminx, por lo que no puede ser una configuración que alcance el diámetro. Tomas Rokicki calificó el resultado como «el primer avance importante y significativo en la aplicación de la inteligencia artificial a la teoría de los rompecabezas mecánicos» (SpeedSolving.com).

Concursos actuales: escala de las tareas y recursos disponibles

En Kaggle se celebran concursos para tres cubos con número de Dios desconocido:

• Cubo 5×5×5 (2,83×10⁷⁴ estados), con un premio de 10.000 rublos por soluciones de menos de 90 movimientos; • Cubo 6×6×6 (1,57×10¹¹⁶ estados); • Cubo 7×7×7 (1,95×10¹⁶⁰ estados).

El principal problema del aprendizaje por refuerzo clásico en este contexto es la señal dispersa: el agente solo recibe información útil al alcanzar el estado objetivo, dejando cientos de pasos intermedios sin retroalimentación. CayleyPy resuelve esto mediante una señal continua: la red neuronal evalúa cada estado intermedio con un número, lo que permite al algoritmo avanzar siguiendo un gradiente en lugar de deambular a ciegas.

Los participantes tienen acceso a GPU NVIDIA Tesla T4/P100 y TPU v3-8/v5e-8 en la plataforma Kaggle, al código fuente abierto del proyecto (480 estrellas en GitHub) y a problemas sin resolver durante cuatro décadas. Es posible unirse a través de Alexander Chervov en Telegram.