DeepCubeA : L'IA résout le Rubik's Cube instantanément sans connaissance préalable du domaine

La nouvelle approche d'apprentissage par renforcement profond nommée DeepCubeA peut résoudre le Rubik's Cube en quelques secondes. Le modèle d'apprentissage profond peut être appliqué à divers autres domaines, y compris la robotique et les sciences naturelles.

L'intelligence artificielle (IA) a déjà prouvé son succès aux échecs et au Go, mais des puzzles plus difficiles comme le Rubik's Cube n'ont pas été résolus via l'intelligence machine. C'est un puzzle combinatoire classique qui pose des défis uniques et intrigants pour l'apprentissage automatique.

Bien que des techniques d'apprentissage automatique aient été utilisées précédemment pour résoudre le Rubik's Cube, elles ont échoué à résoudre le puzzle de manière efficace et fiable. De plus, ces techniques ont dû compter sur des connaissances spécifiques au domaine.

Maintenant, des chercheurs de l'Université de Californie, Irvine, ont construit une approche d'apprentissage par renforcement profond nommée DeepCubeA qui peut résoudre un puzzle incroyablement complexe sans aucune connaissance spécifique au domaine. Il peut résoudre un Rubik's Cube en quelques secondes sans coaching humain en jeu.

Au fur et à mesure que les dimensions augmentent, la complexité du puzzle combinatoire sous-jacent augmente dramatiquement. Trouver une solution optimale au puzzle 15, par exemple, prend une fraction de seconde sur un ordinateur conventionnel, alors que trouver une solution optimale au puzzle 24 pourrait prendre des jours sur la même machine.

Dans cette étude, les chercheurs ont essayé de développer un modèle d'apprentissage automatique qui peut apprendre à résoudre une variété de puzzles sans compter sur des connaissances humaines spécifiques au domaine. Ils ont combiné trois approches de pointe pour développer DeepCubeA :

1. Apprentissage profond
2. Renforcement classique (itération de valeur approchée)
3. Méthodes de recherche de chemin (recherche A* pondérée)

Il consiste en un algorithme d'apprentissage par renforcement profond qui utilise une fonction de politique et de valeur combinée avec la recherche d'arbre Monte Carlo pour résoudre le Rubik's Cube.

Les chercheurs ont utilisé le framework d'apprentissage profond TensorFlow pour entraîner le réseau — il a été entraîné sur environ 10 milliards de simulations du puzzle mélangé et résolu. Tout le processus a été réalisé pendant environ 1 000 000 d'itérations, ce qui a pris 36 heures.

Référence : Nature | DOI:10.1038/s42256-019-0070-z | UCI | Démo en ligne

Une fois entraîné, DeepCubeA a été capable d'atteindre 100 % de précision lors de chaque configuration de test, trouvant le chemin le plus court vers l'état final 60,3 % du temps.

DeepCubeA utilise une fonction heuristique qui ne surestime jamais le coût d'un chemin le plus court. La recherche A* pondérée a certaines bornes sur combien la longueur de la solution peut varier par rapport à la longueur d'une solution optimale.

Applications au-delà des puzzles combinatoires

L'équipe de recherche a également entraîné DeepCubeA sur d'autres puzzles, y compris le puzzle 24, Lights Out, et Sokoban. Il a été capable de trouver le chemin le plus court dans la majorité des cas vérifiables.

L'objectif ultime d'études [comme celle-ci] est de développer les modèles d'apprentissage profond de prochaine génération qui peuvent être appliqués dans des domaines au-delà des puzzles combinatoires, allant de la robotique aux sciences naturelles.

Nous interagissons déjà avec l'IA au quotidien via les moteurs de recherche et des applications comme Alexa et Siri. Cependant, ces systèmes ne sont pas vraiment intelligents : ils peuvent être facilement manipulés ou trompés.

Nous avons besoin de construire une IA plus robuste, plus intelligente et capable de comprendre, raisonner et planifier. L'étude est un petit pas vers cet objectif massif.