Une machine a compris le Rubik's Cube toute seule

Un autre bastion des compétences et de l'intelligence humaines est tombé sous l'assaut des machines. Un nouveau type de machine d'apprentissage en profondeur a appris à résoudre un Rubik's Cube sans aucune assistance humaine.

L'étape est importante car la nouvelle approche s'attaque à un problème important en informatique : comment résoudre des problèmes complexes lorsque l'aide est minime.

Tout d'abord un peu de contexte. Le Rubik's Cube est un puzzle en trois dimensions développé en 1974 par l'inventeur hongrois Erno Rubik, le but étant d'aligner tous les carrés d'une même couleur sur une même face du cube. Il est devenu un jouet à succès international et s'est vendu à plus de 350 millions d'unités.

Le puzzle a également suscité un intérêt considérable de la part des informaticiens et des mathématiciens. Une question qui les a intrigués est le plus petit nombre de coups nécessaires pour le résoudre à partir de n'importe quelle position . La réponse, prouvée en 2014, s'avère être 26.

Un autre défi courant consiste à concevoir des algorithmes capables de résoudre le cube à partir de n'importe quelle position. Rubik lui-même, moins d'un mois après avoir inventé le jouet, a proposé un algorithme qui pourrait le faire.

Mais les tentatives d'automatisation du processus se sont toutes appuyées sur des algorithmes fabriqués à la main par des humains.

Plus récemment, des informaticiens ont essayé de trouver des moyens pour que les machines résolvent elles-mêmes le problème. Une idée consiste à utiliser le même type d'approche qui a connu un tel succès avec des jeux comme les échecs et Go.

Dans ces scénarios, une machine d'apprentissage en profondeur reçoit les règles du jeu et joue ensuite contre elle-même. Surtout, il est récompensé à chaque étape en fonction de ses performances. Ce processus de récompense est extrêmement important car il aide la machine à distinguer le bon jeu du mauvais jeu. En d'autres termes, cela aide la machine à apprendre.

Mais cela ne fonctionne pas dans de nombreuses situations réelles, car les récompenses sont souvent rares ou difficiles à déterminer.

Par exemple, les tours aléatoires d'un Rubik's Cube ne peuvent pas être facilement récompensés, car il est difficile de juger si la nouvelle configuration est plus proche d'une solution. Et une séquence de tours aléatoires peut durer longtemps sans parvenir à une solution, de sorte que la récompense finale ne peut être offerte que rarement.

Aux échecs, en revanche, il y a un espace de recherche relativement grand mais chaque coup peut être évalué et récompensé en conséquence. Ce n'est tout simplement pas le cas pour le Rubik's Cube.

Entrez Stephen McAleer et ses collègues de l'Université de Californie à Irvine. Ces gars-là ont été les pionniers d'un nouveau type de technique d'apprentissage en profondeur, appelée itération autodidacte, qui peut apprendre à résoudre un Rubik's Cube sans aide humaine. L'astuce que McAleer et co ont maîtrisée est de trouver un moyen pour que la machine crée son propre système de récompenses.

Voici comment ça fonctionne. Étant donné un cube non résolu, la machine doit décider si un mouvement spécifique est une amélioration de la configuration existante. Pour ce faire, il doit être en mesure d'évaluer le déménagement.

L'itération autodidactique le fait en commençant par le cube fini et en travaillant en arrière pour trouver une configuration similaire au mouvement proposé. Ce processus n'est pas parfait, mais l'apprentissage en profondeur aide le système à déterminer quels mouvements sont généralement meilleurs que d'autres.

Après avoir été formé, le réseau utilise ensuite un arbre de recherche standard pour rechercher les mouvements suggérés pour chaque configuration.

Le résultat est un algorithme qui fonctionne remarquablement bien. Notre algorithme est capable de résoudre 100 % des cubes brouillés au hasard tout en atteignant une longueur de résolution médiane de 30 mouvements, soit moins ou égale aux solveurs qui utilisent la connaissance humaine du domaine, disons McAleer et co.

C'est intéressant car cela a des implications pour une variété d'autres tâches avec lesquelles l'apprentissage en profondeur a eu du mal, y compris des puzzles comme Sokoban, des jeux comme Montezuma's Revenge et des problèmes comme la factorisation des nombres premiers.

En effet, McAleer et co ont d'autres objectifs en vue : nous travaillons à l'extension de cette méthode pour trouver des solutions approchées à d'autres problèmes d'optimisation combinatoire tels que la prédiction de la structure tertiaire des protéines.

Il n'est pas clair si ces problèmes seront aussi sensibles à cette approche. Ils ne bénéficient généralement pas d'une preuve qu'ils peuvent être résolus en un petit nombre de coups, comme le fait le problème du Rubik's Cube. Cela a sans aucun doute joué en faveur de l'équipe ici.

McAleer et co soutiennent que leur approche est une forme de raisonnement sur les problèmes. Ils soulignent qu'une des définitions du raisonnement est : manipuler algébriquement des connaissances précédemment acquises afin de répondre à une nouvelle question.

Ils disent que c'est exactement ce que fait leur algorithme, appelé DeepCube. En revanche, les machines conventionnelles d'apprentissage en profondeur reconnaissent simplement certains modèles. DeepCube est capable de s'apprendre à raisonner afin de résoudre un environnement complexe avec un seul état de récompense en utilisant l'apprentissage par renforcement pur, disent-ils.

Peut-être. Le véritable 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 ça se passe.

Réf : arxiv.org/abs/1805.07470 : Résoudre le Rubik's Cube sans connaissance humaine

cacher