Résolution automatique du Rubik's cube

philou22
Modifié (November 2023) dans Sciences des données
Bonjour
Je suis en train d’essayer de programmer une IA avec Tensorflow pour résoudre automatiquement un Rubik's cube sans utiliser les techniques classiques de résolution par étapes mais uniquement par apprentissage supervisé à partir de séquences de résolution inverse de séquences de mélange. Pour l’instant j’arrive à résoudre les cubes qui nécessitent peu de mouvements, entre 1 et 8 environ.
Quelqu’un s’est-il déjà penché sur le sujet ?

Réponses

  • Peux-tu expliquer l'intérêt de Tensorflow pour la résolution de ce problème?
  • Georges Abitbol
    Modifié (November 2023)
    J’avoue que je ne comprends pas trop. Quel est l’intérêt de tout cela ?
    Quel est le problème à résoudre ? Est-ce que tu veux résoudre le cube en un nombre minimal de mouvements ?
    Tu as lu ça ? https://towardsdatascience.com/learning-to-solve-a-rubiks-cube-from-scratch-using-reinforcement-learning-381c3bac5476
  • Je n’y connais rien. J’ai lu le fil comme une envie de se lancer empiriquement dans la programmation d’une IA qui apprend plus elle « joue ». 
    Sans chercher la performance, disons pour le plaisir. 
    Pardon si je me suis trompé. 
  • philou22
    Modifié (November 2023)
    Je veux résoudre le cube sans rien en connaître à part l’effet des rotations sur le cube. Pour développer un peu, je n’ai jamais joué à ce jeu car je supposais qu’une machine pouvait le résoudre mais en essayant de construire cette machine je me rend compte que c’est plus complexe que je l’imaginais. Merci pour le lien @Georges Abitbol
  • @philou22 Je conseille le film "Cube" qui a obtenu le prix du public au festival du film fantastique de Gerardmer, commune des Vosges connue pour son lac et ses jonquilles!
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • Avec le Rubik's cube, il y a des variantes de jeu qui sont intéressantes.
    On part d'un Rubik's cube bien rangé. On effectue k=3 mouvements aléatoires (en aveugle), et on essaie de reconstituer le cube, en k=3 mouvements seulement.
    Quand on est suffisamment doué et qu'on y arrive systématiquement, on passe à k=4, puis k=5 ... Certes, une machine peut le faire, mais c'est un exercice de visualisation dans l'espace qui devient vite très difficile.
    Et c'est beaucoup moins machinal que le jeu classique, où le joueur apprend des successions de mouvements symétriques qui donnent un résultat connu.
    Problème technique : si on échoue, il faut savoir reconstituer le cube d'une façon ou d'une autre.
    Dans le jeu classique, pour un joueur moyennement entraîné, à partir d'une situation où il y aurait un chemin optimal avec une quinzaine de mouvements, le joueur saura résoudre le Rubik's, mais avec $100$ ou $200$ mouvements.

    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • En compétition il y a une épreuve où il s'agit de résoudre un cube non pas en temps minimal mais avec le plus petit nombre de mouvements possible (on a environ 1 h et 4 ou 5 cubes à disposition). Si j'ai bien retenu les bonnes concurrentes arrivent typiquement à des scores de l'ordre de 22 à 25 quand le nombre minimal valable pour n'importe quelle position de départ est 20 (mot clé : "god's number").
  • Merci Math Coss, j'ai appris plein de choses aujourd'hui ! 
    Et c'est surprenant de voir que la 'superflip position' est une de celles qui demandent le plus de mouvements.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Fin de partie
    Modifié (November 2023)
    Une question que je me pose depuis longtemps.
    Existe-t-il des algorithmes qui permettent de remplacer une suite donnée de mouvements du cube par une suite plus courte de mouvements qui produisent le même effet sur le cube ?
  • Georges Abitbol
    Modifié (November 2023)
    Ben, à part la force brute, je n'en connais pas.
    Considérons le graphe dont les sommets sont les configurations du cube, et où deux positions sont reliées par une arête si on peut passer de l'une à l'autre en un mouvement élémentaire (rotation de face). Ce graphe est symétrique à cause de l'action transitive du groupe du Rubik's cube dessus. Le problème est de relier "assez vite" tout sommet à un sommet particulier, celui qui correspond au cube résolu.
    Ce graphe est $6$-régulier, ce qui veut dire que chaque sommet a six voisins. Selon Internet, ce graphe a $43 252 003 274 489 856 000$ sommets. Le nombre cité par Math Coss est le diamètre de ce graphe, i.e. la distance maximale entre deux sommets. C'est $20$.
    Imaginons que l'on "suspend" ce graphe par le sommet correspondant au cube résolu : les sommets tombent à une certaine profondeur, et se stratifient en "étages" : les positions du premier étage sont celles qu'on peut résoudre en un coup (il y en a six). Celles du deuxième étage sont celles qu'on peut résoudre en deux coups exactement (combien y en a-t-il ? exercice !). L'étage $n$ a au plus $6^n$ sommets. Que dire de l'étage moyen d'une position aléatoire ?
    Bref, tout ça pour dire que le problème de la résolution du Rubik's Cube revient à trouver des plus courts chemins dans un graphe énorme, très connecté, et où quasiment tout le monde est très, très loin à la même distance de la position du cube résolu.
  • lourrran
    Modifié (November 2023)
    Sauf cas très particulier, je pense qu'il y a peu de cas où un chemin 'partiel' peut être raccourci.
    Si les chemins $A$ et $B$ mènent au même point, ça veut dire que le chemin $A + B^{-1}$ est l'identité.
    On peut trouver des chemins 'identité' ; je crois me souvenir qu'il y avait une succession de mouvements qui permettait de 'retourner' 4 arêtes, donc cette succession de mouvement répétée correspond à l'identité. 
    On a donc un chemin de longueur 24 qui correspond à l'identité. Si on fait à un moment ou un autre n (n>12) mouvements de ce chemin, on peut les remplacer par les 24-n mouvements restants de ce chemin identité.
    Mais c'est totalement marginal. Une succession de p mouvements qui donne l'identité, avec p pas trop grand, et sans une arnaque du type "demi-tour", c'est rarissime.
    Je dis ça, je suis juste un type qui a joué à ce jeu il y a très longtemps, je n'ai jamais rien lu sur le sujet.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Dom
    Dom
    Modifié (November 2023)
    Existe-t-il une suite de mouvements qui assure résoudre le cube (pendant que on exécute la suite…) quel que soit son état initial ?
    Oui ! 
    A-t-on des travaux sur « Quelle est la plus courte ? » ?
  • hx1_210
    Modifié (November 2023)
    J’en profite pour savoir si quelqu’un connait une bonne ressource en ligne sur les mathématiques du Rubik s cube…
    [Ernő Rubik (1944-  } mérite bien sa majuscule. AD]
  • Georges Abitbol
    Modifié (November 2023)
    @Dom : Oui, cette suite a une longueur d'au moins $43252003274489856000$ :D
    @hx1_210 : La page wikipédia contient un certain nombre de choses https://fr.wikipedia.org/wiki/Groupe_du_Rubik%27s_Cube. Mais que cherches-tu exactement ? Le Rubik's cube, ce n'est rien d'autre que l'action simplement transitive d'un certain groupe fini sur un certain ensemble fini :p
  • Quelle magnifique casse-tête ! Je reviens sur le problème posé par @lourrran : on part d'un Rubik's cube bien rangé. On effectue $k$ mouvements aléatoires (en aveugle), et on essaie de reconstituer le cube, en $k$ mouvements seulement. Ma question est la suivante : existe-t-il un algorithme qui donne le nombre $k$ à partir du dérangement initial du cube ? J'imagine que pour $k=1$, $2$ ou $3$, voire $4$, la réponse est positive. Donc je précise ma question : à partir de quel entier $k$ "l'algorithme" échoue-t-il ?
  • Soc
    Soc
    Modifié (November 2023)
    @hx1_210: En voilà! Pour avoir l'audio, il faut aller à Bordeaux...
    The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
  • lourrran
    Modifié (November 2023)
    @Ludwig, je ne sais pas si je saisis bien ta question.
    Si on a fait $k$ mouvements pour mélanger le cube, alors forcément, il suffira de $k$ mouvements pour reconstituer le cube : les $k$ mouvements opposés, en ordre inverse.
    Eventuellement, en mélangeant en aveugle, on a fait un mouvement $M$ puis le mouvement $M^{-1}$ juste après, et dans ce cas, le chemin de retour comportera moins de $k$ étapes.

    @Dom
    Math Coss semble connaître le sujet mieux que nous tous, mais en attendant son retour, à partir du mot clé God Number, on trouve entre autre cette page (lien déjà donné hier)
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • D'accord @lourrran, mais admettons que c'est toi qui fait les $k$ mouvements et que tu donnes le cube à ton copain sans lui dire combien de mouvements tu as fait. Peut-il trouver ce nombre $k$ rien qu'en observant le cube ?
  • @philou22 ai-je bien compris, tu veux programmer la résolution du cube sans y avoir jamais joué ? C'est un objet qui se manipule.

  • @Sato En fait, je veux savoir si, comme je le supposais naïvement, un réseau de neurones relativement simple (en entrée, deux couches de convolution, une couche de normalisation, une couche dense de grande taille et une couche dense avant la sortie) peut devenir efficace pour sa résolution, sans utiliser directement un algorithme de résolution par étapes, mais juste en observant suffisamment de mouvements issus de séquences de résolution avec une certaine stratégie. Je génère actuellement des séquences de résolution avec l'algorithme en deux phases de https://github.com/hkociemba/RubiksCube-TwophaseSolver (il me semble que l'auteur est une référence mondiale en la matière). C'est assez long pour générer des séquences courtes mais très rapide pour simplement trouver une solution. Cela me pose donc une question de qualité des données d'entraînement que je génère : produire moins de données avec une meilleure qualité (résolution plus courte) ou produire plus de données avec une moins bonne qualité (résolution plus longue) ? Ce que je fais ressemble beaucoup au papier cité par @Georges Abitbol, mais mon but est aussi d'acquérir un peu d'expérience dans la programmation d'IA maintenant que c'est devenu très accessible.
  • @Ludwig : tu veux dire, autrement que par force brute ?

    @philou22 : As-tu essayé de faire résoudre un cube 2x2x2 à ton algorithme ?
  • lourrran
    Modifié (November 2023)
    Je pense que la question de Ludwig est : avec ses yeux, en comptant le nombre de rotations directes et indirectes etc etc, sans ordinateur, sans toucher le cube, un humain entrainé arrive-t-il à trouver le nombre exact de mouvements ?
    Déjà, il faut trouver un humain qui se soit entraîné à cet exercice particulier.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Sur cette dernière question, cela me paraît douteux.

  • J’arrive aux mêmes conclusions que l’étude référencée plus haut. Les réseaux de neurones actuels sont peu performants pour résoudre le Rubik’s cube. Au delà de 8 mouvements de mélange initiaux, ils sont largement dépassés. Même avec toutes les techniques classiques contemporaines et des quantités de données d’entraînement très importantes. Concernant l’algorithme en deux étapes également référencé plus haut il est très efficace bien qu’assez peu efficient et nécessite la construction de tables de plusieurs dizaines de Mo. En somme, mon intuition selon laquelle une machine pouvait relativement facilement résoudre ce problème était fausse. Pour ceux que cela pourrait effrayer, et il y en a, puisque j’en connais, l’intelligence artificielle ne rendra pas caduque les algorithmes de chiffrement comme pourrait le faire l’ordinateur quantique. Il s’agit là encore d’une intuition et l’expérience montre qu’elle n’est pas toujours juste !
  • Un autre livre, en anglais, est celui de David Joyner (Adventures in group theory).
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
Connectez-vous ou Inscrivez-vous pour répondre.