CayleyPy aplica redes neuronales a los cubos de Rubik donde se desconoce el número de Dios

El cubo de Rubik 3×3×3 tiene alrededor de 4,3×10^19 estados válidos, y desde 2010 se sabe que cualquiera de ellos se resuelve en 20 movimientos como máximo en la métrica HTM. Tomas Rokicki y sus colegas obtuvieron este resultado analizando por completo el espacio de estados. Para los cubos 4×4×4 y 5×5×5, los cubos grandes y el megaminx, el diámetro exacto del grafo de Cayley sigue siendo desconocido. El proyecto CayleyPy intenta abordar estos puzles desde otro ángulo: con búsqueda neuronal en lugar de fuerza bruta exhaustiva. Uno de los miembros del equipo ha publicado en Habr un análisis del pipeline y de los resultados de las competiciones.

El puzle como grafo

La formalización es sencilla. Los vértices del grafo de Cayley son los estados válidos del puzle y las aristas, los movimientos permitidos. Resolver el puzle en el mínimo número de movimientos equivale a un problema de camino más corto desde el vértice actual hasta el estado resuelto. El diámetro del grafo, es decir, el máximo de las distancias mínimas entre todos los pares de vértices, es precisamente el «número de Dios».

Para el 3×3×3 ese cálculo era factible, aunque exigió recursos computacionales considerables y el uso de simetrías para reducir el espacio. Al aumentar el tamaño del puzle, la situación cambia. El 4×4×4 tiene del orden de 7,4×10^45 estados, y el 5×5×5, cerca de 2,8×10^74. Recorrer el grafo completo es imposible. Quedan las heurísticas, las cotas superiores e inferiores y la búsqueda de soluciones subóptimas, que van reduciendo poco a poco la distancia respecto al óptimo desconocido.

Qué hace CayleyPy

CayleyPy es una biblioteca abierta en torno a la cual se ha montado una serie de competiciones en Kaggle. Su objetivo es encontrar caminos óptimos y subóptimos en grafos de Cayley con un número enorme de vértices. Los participantes envían soluciones, y la plataforma las valida y las clasifica según la longitud de los caminos encontrados. Para los investigadores supone una prueba gratuita de ideas sobre un benchmark común; para los organizadores, una forma de reunir muchos enfoques distintos sobre un mismo problema matemático.

Según el anuncio, en el artículo el autor analiza tres aspectos:

• la arquitectura del pipeline neuronal de CayleyPy;
• los resultados de los concursos ya finalizados;
• las condiciones de los concursos actuales para cubos grandes, en los que participa como miembro del equipo.

En el fragmento disponible no figuran cifras sobre la longitud de los caminos encontrados ni sobre las posiciones de los equipos, así que para valorar hasta qué punto el enfoque neuronal supera a la búsqueda clásica habrá que acudir al texto completo. El título del original afirma precisamente eso: que la red neuronal supera a los métodos clásicos. Qué métricas y qué algoritmos de referencia se usaron en la comparación no se desprende del anuncio.

Por qué el enfoque importa más allá de los cubos

El esquema general es bien conocido: la red neuronal aprende a estimar la distancia a la meta, y el algoritmo de búsqueda usa esa estimación para no explorar ramas innecesarias. Así funcionan también los trabajos anteriores que resolvían el cubo de Rubik mediante aprendizaje por refuerzo. El valor está en que el grafo de Cayley es un laboratorio matemático limpio: ofrece respuestas exactas para los casos pequeños, una complejidad escalable y una métrica de calidad inequívoca. Si un método funciona en el 3×3×3, se puede probar en el 4×4×4 y en puzles mayores, observando dónde falla.

Los grafos de Cayley describen grupos de permutaciones, de modo que la estimación de diámetros y la búsqueda de caminos cortos resultan de interés en combinatoria y teoría de grupos. Estructuras comparables aparecen en problemas de enrutamiento y en topologías de red, aunque es pronto para extraer conclusiones aplicadas a partir de una sola publicación.

Qué puede hacer un ingeniero en la práctica

Si trabaja con búsqueda y heurísticas, el repositorio abierto de CayleyPy en GitHub y los concursos de Kaggle ofrecen una plataforma lista para probar ideas propias en un problema cuya respuesta se mide en número de movimientos. Lo razonable es empezar por los puzles pequeños, donde el diámetro se conoce, y contrastar la estimación neuronal de la distancia con el valor exacto. Después se puede pasar a los cubos grandes, donde lo que se compite es la longitud de las soluciones encontradas.

Conviene tener presente una limitación: se trata de una reseña de un participante del proyecto, no de una investigación independiente. Cualquier afirmación de superioridad sobre la búsqueda clásica debe comprobarse en las tablas de resultados concretas y en los solucionadores con los que se comparó.