Nous suivre Industrie Techno

DeepCubeA, l'algorithme champion de Rubik’s Cube

DeepCubeA, l'algorithme champion de Rubik’s Cube

L'algorithme DeepCubeA résout 100% des configurations en trouvant le chemin le plus court dans 60% des cas.

© Fernando Latorre / Pixabay

Publiés le 15 juillet dans la revue Nature Machine Intelligence, les travaux d’une équipe de l’Université de Californie à Irvine détaillent une méthode basée sur de l’apprentissage profond par renforcement pour résoudre un Rubik’s Cube en un temps record.

Pour résoudre un Rubik’s Cube en un minimum de temps, une équipe de l’Université de Californie à Irvine a mis au point une méthode baptisée DeepCubeA qui se base sur de l’apprentissage profond par renforcement (« deep reinforcement learning »). Leurs travaux sont détaillés dans un article paru le 15 juillet dans la revue Nature Machine Intelligence. Si l’apprentissage par renforcement s’est déjà illustré avec AlphaZero, le programme qui joue au go ou aux échecs, c’est une première pour le Rubik’s Cube : « A ma connaissance, cela n’a jamais été fait », déclare Pierre Baldi, l’un des auteurs de l’article.

L’apprentissage par renforcement consiste, pour un algorithme d’intelligence artificielle, à apprendre à partir d’expériences en recevant des récompenses lorsque les décisions prises sont optimisées.

Une immensité d'états possibles pour un seul « gagnant »

Comparé aux échecs et au go, le Rubik’s Cube présente des différences notables qui complexifient sa résolution avec un tel algorithme. Tout d’abord, échecs et go se jouent à deux alors que le Rubik’s Cube est un jeu solitaire. Mais celui-ci offre également un grand nombre de configurations possibles (4,3 x 10^19) pour une seule gagnante : les six faces de la même couleur. Ce n’est pas le cas pour le go et les échecs : « Si vous mettez des pierres noires et blanches au hasard sur un plateau de go, le jeux se terminera à un moment donné, remarque Pierre Baldi. Mais si vous effectuez des mouvements aléatoires sur votre Rubik’s Cube, vous n’arriverez jamais à le finir. »

« DeepCubeA part donc d’un Rubik’s Cube résolu et travaille à l’envers en apprenant comment résoudre des cubes mélangés une fois, deux fois, et ainsi de suite », poursuit M. Baldi. Pour cela, il combine de l’apprentissage profond avec de l’apprentissage par renforcement classique, et une méthode de recherche de chemin appelée algorithme de recherche A* pondérée.

Limiter les mouvements n’est pas plus rapide

Les auteurs indiquent que leur approche pourrait trouver des applications dans des domaines variés où le nombre de situations possibles est grand par rapport à un nombre très restreint de solutions. Notamment dans la recherche de chemins ou la robotique. « Imaginez un robot qui doit nettoyer votre cuisine, précise Pierre Baldi. Le nombre d’états « cuisine sale » dans lesquels elle peut être est immense, mais il n’y a qu’un état à atteindre : la cuisine propre. Si le robot déplace des plats sales au hasard, la cuisine ne sera jamais nettoyée. Cette situation se rapproche du Rubik’s Cube où vous devez partir de l’état final pour arriver progressivement à l’état actuel. »

Si DeepCubeA a été capable de résoudre 100% des configurations testées, comme l’indiquent les chercheurs dans leur article, le chemin le plus court n’est pas toujours le plus judicieux. « Ce qui est assez paradoxal, indique M. Baldi, c’est que si vous cherchez à faire le moins de mouvements possibles, l’algorithme met plus de temps à trouver la solution. » Il lui faut une vingtaine de secondes pour y parvenir, et il y arrive dans 60% des cas. « Mais en étant moins exigeant et en autorisant l’algorithme à faire plus de mouvements, il peut résoudre n’importe quel cube en une seconde avec 20 à 30 mouvements », poursuit M. Baldi.

Une approche similaire à celle des champions du monde humains de Rubik’s Cube qui ne cherchent pas à faire le moins de mouvements possible pour être les plus rapides. « Ils prennent en compte d’autres facteurs comme des contraintes ergonomiques au niveau des poignets, indique M. Baldi. Ils résolvent un cube en environ 6 secondes et une cinquantaine de mouvements. »

Bienvenue !

Vous êtes désormais inscrits. Vous recevrez prochainement notre newsletter hebdomadaire Industrie & Technologies

Nous vous recommandons

Bertin Nahum veut conquérir le monde avec ses robots chirurgicaux

Bertin Nahum veut conquérir le monde avec ses robots chirurgicaux

Portrait du PDG de Quantum Surgical, Bertin Nahum, qui prépare l’arrivée sur le marché de son prochain robot[…]

« En Europe, la difficulté n’est pas tant la création d’entreprises que leur croissance », selon Chahab Nastar, chef de l’innovation d’EIT Digital

Interview

« En Europe, la difficulté n’est pas tant la création d’entreprises que leur croissance », selon Chahab Nastar, chef de l’innovation d’EIT Digital

La maintenance à distance d’Oculavis récompensée à l’EIT Digital Challenge 2019

La maintenance à distance d’Oculavis récompensée à l’EIT Digital Challenge 2019

Pour bien commencer la semaine : L’étage supérieur d’Ariane 6 a son usine 4.0

Pour bien commencer la semaine : L’étage supérieur d’Ariane 6 a son usine 4.0

Plus d'articles