Une illustration de DeepCube. Le processus de formation et de résolution est divisé en ADI et MCTS. D'abord, nous entraînons itérativement un DNN en estimant la vraie valeur des états d'entrée en utilisant la recherche en largeur d'abord. Puis, utiliser le DNN pour guider l'exploration, nous résolvons des cubes en utilisant Monte Carlo Tree Search. Crédit :arXiv : 1805.07470 [cs.AI]
Libérer des moyens pour qu'une machine résolve le Rubik's Cube ? De nombreuses équipes peuvent se lever et dire été là, c'est fait. Nous avons vu beaucoup de gros titres, trop, sur la façon dont ils ont pointé pour établir des records de temps. Alors, quel est le problème avec la dernière histoire de cube de résolution de machines ?
David Grossman dans Mécanique populaire a remarqué que les scientifiques californiens ont amené les choses à la troisième dimension avec un algorithme qui peut comprendre comment résoudre un Rubik's Cube.
Une équipe de l'Université de Californie à Irvine est à l'origine d'une approche qui a particulièrement retenu l'attention. "Solving the Rubik's Cube Without Human Knowledge" est le titre de leur article, qui décrit leur exploration, et le papier est sur arXiv.
Stephen McAleer, Forêt Agostinelli, Alexander Shmakov et Pierre Baldi en sont les auteurs.
« Nous présentons l'itération autodidacte :un nouvel algorithme d'apprentissage par renforcement qui est capable d'apprendre par lui-même à résoudre le Rubik's Cube sans aucune assistance humaine. »
Paul Lilly dans HotHardware :Les machines utilisent généralement une méthode d'auto-apprentissage basée sur un système de récompenses. Les chercheurs nourrissent la machine des règles du jeu, puis il utilise un processus de récompenses pour déterminer si un coup était bon ou mauvais,
Cependant, comme l'écrivent les auteurs, "pour de nombreux environnements d'optimisation combinatoire, les récompenses sont rares et la fin des épisodes n'est pas garantie."
Ils ont suivi le chemin de l'itération autodidacte. Ils ont dit, "Afin de résoudre le Rubik's Cube en utilisant l'apprentissage par renforcement, l'algorithme apprendra une politique. La politique détermine quel mouvement prendre dans un état donné."
Examen de la technologie du MIT défini comment cela fonctionne. « Étant donné un cube non résolu, la machine doit décider si un mouvement spécifique est une amélioration par rapport à la configuration existante. Pour faire ça, il doit être capable d'évaluer le mouvement. L'itération autodidacte le fait en commençant par le cube fini et en travaillant en arrière pour trouver une configuration similaire au mouvement proposé."
Les auteurs ont écrit que "DeepCube a découvert une quantité notable de connaissances Rubik's Cube au cours de son processus de formation, y compris la connaissance de la façon d'utiliser des groupes de permutation complexes et des stratégies similaires aux meilleurs « speed-cubers » humains. »
Leur machine d'entraînement était un serveur Intel Xeon E5-2620 à 32 cœurs avec trois GPU NVIDIA Titan XP. Ils ont appelé leur solveur DeepCube.
Évaluation de Lilly :ce n'est pas une solution parfaite au problème, mais est impeccable en termes de précision.
L'équipe a déclaré dans le résumé de l'article que "Notre algorithme est capable de résoudre 100% des cubes brouillés de manière aléatoire tout en atteignant une longueur de résolution médiane de 30 mouvements, inférieure ou égale aux solveurs qui utilisent la connaissance du domaine humain".
Pourquoi c'est important :c'est une histoire de résolution de cubes et plus encore. L'équipe a mentionné des objectifs supplémentaires.
"En plus de continuer à travailler avec le Rubik's Cube, nous travaillons à étendre cette méthode pour trouver des solutions approximatives à d'autres problèmes d'optimisation combinatoire tels que la prédiction de la structure tertiaire des protéines. De nombreux problèmes d'optimisation combinatoire peuvent être considérés comme des problèmes de prise de décision séquentielle, auquel cas nous pouvons utiliser l'apprentissage par renforcement."
Examen de la technologie du MIT a déclaré que la nouvelle approche s'attaquait à "un problème important en informatique :comment résoudre des problèmes complexes lorsque l'aide est minime".
Idéalement, dit Lilly, « cela pourrait conduire à trouver des remèdes aux maladies, si la méthode est capable de fonctionner aussi bien sur de telles choses qu'elle le fait avec la résolution d'un Rubik's Cube."
Examen de la technologie du MIT :"Le vrai test, bien sûr, sera de savoir comment cette approche fait face à des problèmes plus complexes tels que le repliement des protéines. Nous allons regarder pour voir comment cela se passe."
© 2018 Tech Xplore
