CayleyPy applique les réseaux de neurones aux Rubik's Cubes dont le nombre de Dieu est inconnu

Le Rubik's Cube 3×3×3 compte environ 4,3×10^19 états valides, et l'on sait depuis 2010 que chacun d'eux se résout en 20 mouvements au maximum dans la métrique HTM. Tomas Rokicki et ses collègues ont obtenu ce résultat en explorant intégralement l'espace des états. Pour les cubes 4×4×4 et 5×5×5, les cubes de grande taille et le mégaminx, le diamètre exact du graphe de Cayley reste à ce jour inconnu. Le projet CayleyPy aborde ces puzzles sous un autre angle : une recherche guidée par réseaux de neurones, plutôt qu'une exploration exhaustive. L'analyse du pipeline et des résultats des compétitions a été publiée sur Habr par l'un des membres de l'équipe.

Le puzzle comme graphe

La formalisation est simple. Les sommets du graphe de Cayley sont les états valides du puzzle, et les arêtes sont les mouvements autorisés. Résoudre le puzzle en un nombre minimal de mouvements revient alors à chercher le plus court chemin entre le sommet courant et l'état résolu. Le diamètre du graphe, c'est-à-dire le maximum des distances les plus courtes sur toutes les paires de sommets, est précisément le « nombre de Dieu ».

Pour le 3×3×3, ce calcul était réalisable, même s'il a exigé d'importantes ressources de calcul et le recours aux symétries pour réduire l'espace de recherche. La situation change à mesure que le puzzle grandit. Le 4×4×4 compte de l'ordre de 7,4×10^45 états, le 5×5×5 environ 2,8×10^74. Un parcours complet du graphe est ici impossible. Il reste les heuristiques, les bornes supérieures et inférieures, et la recherche de solutions sous-optimales, qui réduisent peu à peu l'écart avec l'optimum inconnu.

Ce que fait CayleyPy

CayleyPy est une bibliothèque open source autour de laquelle s'organise une série de compétitions sur Kaggle. Leur objectif : trouver des chemins optimaux et sous-optimaux dans des graphes de Cayley comptant un nombre immense de sommets. Les participants soumettent leurs solutions, la plateforme les vérifie et les classe selon la longueur des chemins trouvés. Pour les chercheurs, c'est un moyen gratuit de tester des idées sur un benchmark commun ; pour les organisateurs, une façon de rassembler de nombreuses approches différentes d'un même problème mathématique.

D'après l'annonce, l'auteur analyse dans son article trois points :

• l'architecture du pipeline neuronal de CayleyPy ;
• les résultats des concours déjà terminés ;
• les règles des concours en cours sur les grands cubes, auxquels il participe en tant que membre de l'équipe.

Le fragment accessible ne contient ni chiffres sur la longueur des chemins trouvés, ni classement des équipes. Pour savoir dans quelle mesure l'approche neuronale surpasse la recherche classique, il faudra donc se reporter au texte complet. Le titre de l'original affirme précisément cela : le réseau de neurones l'emporterait sur les méthodes classiques. L'annonce ne dit pas quelles métriques et quels algorithmes de référence servent à la comparaison.

Pourquoi l'approche compte au-delà des Rubik's Cubes

Le schéma général est bien connu : un réseau de neurones apprend à estimer la distance à l'objectif, et l'algorithme de recherche s'appuie sur cette estimation pour éviter d'explorer des branches inutiles. Les travaux antérieurs qui résolvent le Rubik's Cube par apprentissage par renforcement reposent sur le même principe. L'intérêt tient à ce que le graphe de Cayley constitue un laboratoire mathématique propre : il offre des réponses exactes pour les petits cas, une complexité qui monte en échelle et une métrique de qualité non ambiguë. Si une méthode fonctionne sur le 3×3×3, on peut la tester sur le 4×4×4 et au-delà, en observant à quel moment elle cède.

Les graphes de Cayley décrivent des groupes de permutations ; l'estimation des diamètres et la recherche de chemins courts intéressent donc la combinatoire et la théorie des groupes. Des structures comparables apparaissent dans des problèmes de routage et dans les topologies de réseaux, mais il est trop tôt pour tirer des conclusions appliquées de cette seule publication.

Que faire de tout cela quand on est ingénieur

Si vous travaillez sur la recherche et les heuristiques, le dépôt GitHub ouvert de CayleyPy et les concours Kaggle offrent un terrain prêt à l'emploi pour tester vos propres idées sur un problème dont la réponse se mesure en nombre de mouvements. Il est raisonnable de commencer par de petits puzzles dont le diamètre est connu, et de comparer l'estimation neuronale de la distance à la valeur exacte. Passez ensuite aux grands cubes, où la compétition porte sur la longueur des solutions trouvées.

Les lecteurs doivent garder une limite en tête : il s'agit d'un compte rendu d'un participant au projet, et non d'une étude indépendante. Toute affirmation de supériorité sur la recherche classique doit être vérifiée dans les tableaux de résultats concrets et en regardant avec quels solveurs la comparaison a été faite.