Image : meisjedevos @pixabay
Tu as sûrement déjà mis tes neurones à l’épreuve avec le casse-tête le plus célèbre de la planète : le cube Rubik. Peut-être y as-tu passé des heures sans même parvenir à le résoudre. Pour les champions du monde de la discipline, le record est passé sous la barre des 4 secondes en 2018: Yusheng Du, un jeune Chinois, a réussi l’exploit en 3,47 secondes !
Mais tout comme pour le jeu de Go ou les échecs, le plus grand adversaire de ces champions, c’est l’intelligence artificielle (IA), dont le meilleur temps à ce jour est de 1,2 seconde ! Mais comment réussir cette prouesse alors qu’il existe 4,3×1019 façons de mélanger les faces du casse-tête et une seule solution ?
En 2010, une équipe de programmeurs informatiques a déterminé qu’aucune de ces combinaisons ne nécessitait plus de 25 mouvements pour être résolue. Cela étant dit, aucun humain n’est capable de regarder un cube et d’évaluer exactement le nombre minimum de mouvements possibles pour résoudre ce casse-tête. La méthode des champions de cube Rubik se base en partie sur des mouvements réflexes.
Elle implique de mémoriser des séquences de mouvements, des algorithmes, qui sont mis en œuvre pour résoudre le cube, section par section. Ainsi, les professionnels de cube Rubik s’entraînent à mémoriser et à pratiquer des centaines d’algorithmes. Chacune de ces séquences correspond à un motif particulier du cube. Une fois ce motif reconnu, ils réalisent l’algorithme correspondant et se rapprochent de cette manière de la résolution complète. En moyenne, la résolution d’un cube par ces champions nécessite 50 à 60 mouvements. Mais, par chance il arrive qu’un cube se retrouve « mélangé » dans une configuration qui va permettre de diminuer le nombre minimum de coups !
L’intelligence artificielle DeepCubeA a pulvérisé le record des champions humains justement parce qu’elle utilise un nombre de coups très proche du nombre minimum nécessaire pour résoudre le casse-tête. Ce qui est particulier avec le cube Rubik, c’est qu’il existe une seule solution pour résoudre le problème, contrairement aux échecs ou au jeu de Go. Alors pour entraîner la machine, les programmeurs sont partis de la solution et ont appris à la machine comment résoudre un cube mélangé une fois, deux fois, et ainsi de suite. Cette méthode d’apprentissage est intéressante en robotique par exemple, pour des problèmes possédant de nombreuses configurations, mais très peu de solutions.