CayleyPy bat les algorithmes classiques dans la résolution des grands Rubik's Cubes

Le projet CayleyPy fait progresser une série de compétitions sur la plateforme Kaggle, consacrées à la recherche de solutions optimales pour des casse-têtes mécaniques dont le nombre de Dieu reste inconnu. Plutôt que de recourir aux algorithmes classiques comme IDA* ou la recherche bidirectionnelle en largeur (BFS), qui s'appuient sur des tables précalculées (Pattern Databases), CayleyPy emploie une heuristique neuronale entraînable. Sur le Rubik's Cube classique 3×3×3, dont le diamètre du graphe est de 20 mouvements (métrique HTM, Thomas Rokicki, 2010), le système atteint 98,4% de solutions optimales — un résultat supérieur à DeepCubeA (60,3%) et EfficientCube (69,6%).

Architecture : trois étapes, des marches aléatoires à la recherche

La méthode se déroule en trois temps. D'abord, la génération de l'échantillon : on part du cube résolu, on le mélange aléatoirement, et on conserve pour chaque état la paire « configuration-distance au point de départ ». Ensuite, l'entraînement : le réseau de neurones apprend à prédire la distance à partir de l'état observé, devenant ainsi une heuristique de recherche. Enfin, le Beam Search : l'algorithme conserve les W positions les plus prometteuses (généralement W=5 ou W=40), évalue leurs voisins, puis ne retient que le top W. Le processus se répète jusqu'à la résolution ou jusqu'à atteindre la limite de recherche.

Un constat important ressort des expériences : augmenter la taille de l'échantillon d'entraînement cesse rapidement d'améliorer la qualité de l'heuristique, alors qu'élargir la largeur du faisceau réduit constamment la longueur des solutions.

Du cube 4×4 au

Megaminx : des avancées sur des diamètres inconnus

Sur le cube 4×4×4, l'espace d'états compte 7,4×10⁴⁵ configurations (26 ordres de grandeur de plus que le 3×3). Le nombre de Dieu reste inconnu ; on connaît seulement des bornes : de 32 à 53 mouvements en métrique BTM, avec une hypothèse à 48 mouvements. CayleyPy atteint une moyenne de 46,51 mouvements sur le classement final, devançant Thomas Rokicki.

Sur le Megaminx (dodécaèdre), l'espace d'états avoisine 1,01×10⁶⁸. La configuration Superflip (toutes les arêtes retournées, coins et centres en place) était considérée comme potentiellement la plus éloignée de l'état résolu. En mai 2023, Thomas Rokicki avait résolu Superflip en 55 mouvements en métrique FTM. En 2016, Herbert Kociemba avait établi une borne inférieure du diamètre du Megaminx : 48 mouvements en FTM.

Vladislav Kuznetsov, à l'aide de CayleyPy, a résolu Superflip en 47 mouvements en FTM en mai 2026. De l'inégalité 47<48 découle directement que Superflip n'est pas l'antipode du graphe de Cayley du Megaminx, et ne peut donc pas être une configuration atteignant le diamètre. Thomas Rokicki a qualifié ce résultat de « première avancée majeure et significative dans l'application de l'intelligence artificielle à la théorie des casse-têtes mécaniques » (SpeedSolving.com).

Compétitions en cours : ampleur des défis et ressources disponibles

Trois compétitions sont en cours sur Kaggle, portant sur des cubes dont le nombre de Dieu est inconnu :

• Cube 5×5×5 (2,83×10⁷⁴ états) avec un prix de 10 000 roubles pour les solutions de moins de 90 mouvements ;
• Cube 6×6×6 (1,57×10¹¹⁶ états) ;
• Cube 7×7×7 (1,95×10¹⁶⁰ états).

Le principal problème de l'apprentissage par renforcement classique ici est le signal épars : l'agent ne reçoit une information utile qu'en atteignant l'état cible, tandis que des centaines d'étapes intermédiaires restent sans retour. CayleyPy résout ce problème grâce à un signal continu : le réseau de neurones attribue un score à chaque état intermédiaire, ce qui permet à l'algorithme de suivre un gradient plutôt que d'errer à l'aveugle.

Les participants disposent de GPU NVIDIA Tesla T4/P100 et de TPU v3-8/v5e-8 sur la plateforme Kaggle, du code source ouvert du projet (480 étoiles sur GitHub), et de problèmes non résolus depuis quatre décennies. Il est possible de rejoindre le projet via Alexander Chervov sur Telegram.