L'algorithme évolutif surpasse les machines d'apprentissage en profondeur dans les jeux vidéo

Avec toute l'excitation suscitée par les réseaux de neurones et les techniques d'apprentissage en profondeur, il est facile d'imaginer que le monde de l'informatique se compose de rien d'autre. Les réseaux de neurones, après tout, ont commencé à surpasser les humains dans des tâches telles que la reconnaissance d'objets et de visages et dans des jeux tels que les échecs, Go et divers jeux vidéo d'arcade.

Ces réseaux sont basés sur le fonctionnement du cerveau humain. Rien ne pourrait avoir plus de potentiel que cela, n'est-ce pas ?

Pas assez. Un type d'informatique entièrement différent a le potentiel d'être beaucoup plus puissant que les réseaux de neurones et l'apprentissage en profondeur. Cette technique est basée sur le processus qui a créé le cerveau humain : l'évolution. En d'autres termes, une séquence de changements et de sélections itératifs qui a produit les machines les plus complexes et les plus performantes connues de l'humanité : l'œil, l'aile, le cerveau, etc. Le pouvoir de l'évolution est une merveille à voir.

C'est pourquoi les informaticiens ont longtemps tenté d'exploiter ses capacités. L'informatique dite évolutive a réalisé des exploits remarquables au cours des 30 années qui ont suivi sa première utilisation pour optimiser les lignes de production des usines de tracteurs.

Mais au cours des dernières années, ce domaine de l'informatique a dû jouer le second rôle par rapport aux machines d'apprentissage en profondeur et à leur énorme succès.

Aujourd'hui, les tables semblent prêtes à tourner grâce au travail de Dennis Wilson et de quelques collègues de l'Université de Toulouse en France. Ces gars-là ont montré comment l'informatique évolutive peut égaler les performances des machines d'apprentissage en profondeur au tâche emblématique qui les a rendus célèbres en 2013 : la capacité de surpasser les humains dans les jeux vidéo d'arcade tels que Pong, Breakout et Space Invaders. Les travaux suggèrent que l'informatique évolutive devrait être célébrée tout aussi largement que ses relations basées sur l'apprentissage en profondeur.

L'informatique évolutive fonctionne d'une manière totalement différente des réseaux de neurones. L'objectif est de créer un code informatique qui résout un problème spécifique en utilisant une approche quelque peu contre-intuitive.

La manière conventionnelle de créer du code consiste à l'écrire à partir des premiers principes avec un objectif spécifique en tête.

L'informatique évolutive utilise une approche différente. Cela commence avec du code généré entièrement au hasard. Et pas seulement une version de celui-ci, mais de nombreuses versions, parfois des centaines de milliers de morceaux de code assemblés au hasard.

Chacun de ces codes est testé pour voir s'il atteint l'objectif requis. Et bien sûr, tout le code est affreux car il est généré aléatoirement.

Mais juste par hasard, certains morceaux de code sont un peu meilleurs que d'autres. Ces pièces sont ensuite reproduites dans une nouvelle génération de code, qui comprend plus de copies des meilleurs codes.

Cependant, la génération suivante ne peut pas être une copie identique de la première. Au lieu de cela, il doit changer d'une manière ou d'une autre. Ces changements peuvent impliquer la permutation de deux termes dans le code, une sorte de mutation ponctuelle. Ou ils peuvent impliquer deux codes coupés en deux et les moitiés échangées, comme la recombinaison sexuelle.

Chacune des nouvelles générations est ensuite testée pour voir si cela fonctionne bien. Les meilleurs morceaux de code sont préférentiellement reproduits dans une autre génération, et ainsi de suite.

Ainsi, le code évolue. Au fil du temps, il s'améliore, et après de nombreuses générations, si les conditions sont réunies, il peut devenir meilleur que n'importe quel codeur humain ne peut concevoir.

Les informaticiens ont appliqué avec succès des approches évolutives à des problèmes allant de la conception de robots à la construction de pièces d'avion.

Mais il est tombé en disgrâce en raison de l'énorme intérêt pour l'apprentissage en profondeur. Une question importante est donc de savoir si cela peut égaler les performances des machines d'apprentissage en profondeur. Pour le savoir, Wilson et co ont utilisé l'approche pour développer un code qui pourrait contrôler les jeux informatiques d'arcade datant des années 1980 et 1990.

Ces jeux sont disponibles dans une base de données appelée Arcade Learning Environment, qui est de plus en plus utilisée pour tester le comportement d'apprentissage d'algorithmes de toutes sortes. La base de données se compose de 61 jeux Atari, tels que Pong, Space Invaders, Breakout et Kung Fu Master.

La tâche consiste à créer un algorithme capable de jouer à un jeu comme Pong en ne regardant que la sortie de l'écran, de la même manière que les humains jouent. L'algorithme doit donc analyser chaque position de jeu, puis décider comment se déplacer pour maximiser son score.

Les commandes de tous les jeux sont les mêmes. Ceux-ci correspondent aux huit directions dans lesquelles le contrôleur peut être déplacé (haut, bas, gauche et droite plus quatre directions diagonales), une pression sur un bouton, les mêmes huit mouvements combinés avec une pression sur un bouton, et ne rien faire du tout. Tous les jeux n'utilisent pas les 18 combinaisons possibles, et certains n'en utilisent que quatre.

Le code doit d'abord être créé. L'approche évolutive nécessite un vocabulaire de termes pouvant être concaténés pour former un code informatique. Les termes vont d'actions simples telles que ADD (x+y)/2 à des actions plus complexes, telles que renvoyer le vecteur x à 1 élément si x est un scalaire.

Le choix des termes qui composent ce vocabulaire est important, et Wilson et co utilisent un ensemble déjà défini pour la programmation génétique cartésienne (comme on appelle leur technique).

Le processus commence par la création aléatoire d'un code contenant 40 termes. C'est le génome du programme. Ce génome est ensuite testé pour voir dans quelle mesure il joue le jeu, à en juger par le score. En fonction de ses performances, le génome est ensuite reproduit avec des mutations et testé à nouveau, et ainsi de suite. Au total, l'équipe a ainsi testé 10 000 génomes.

Les résultats rendent la lecture intéressante. Au début, les génomes sont terribles pour jouer le jeu. Mais avec le temps, ils s'améliorent. Et après plusieurs générations, ils jouent bien, parfois mieux que les humains.

De nombreux génomes ont fini par jouer des stratégies de jeu entièrement nouvelles, souvent complexes. Mais ils en ont parfois trouvé de simples que les humains avaient négligés.

Par exemple, lors de la lecture de Kung Fu Master, l'algorithme évolutif a découvert que l'attaque la plus précieuse était un coup de poing accroupi. S'accroupir est plus sûr car il esquive la moitié des balles dirigées vers le joueur et attaque également tout ce qui se trouve à proximité. La stratégie de l'algorithme consistait à utiliser à plusieurs reprises cette manœuvre sans aucune autre action. Avec le recul, utiliser exclusivement le coup de poing accroupi a du sens.

Cela a surpris les acteurs humains impliqués dans l'étude. L'utilisation de cette stratégie à la main a permis d'obtenir un meilleur score que de jouer au jeu normalement, et l'auteur utilise désormais exclusivement des coups de poing accroupis lorsqu'il attaque dans ce jeu, disent Wilson et co.

Dans l'ensemble, le code évolué a bien joué à de nombreux jeux, surpassant même les humains dans des jeux tels que Kung Fu Master. De manière tout aussi significative, le code évolué est tout aussi bon que de nombreuses approches d'apprentissage en profondeur et les surpasse dans des jeux comme Asteroids, Defender et Kung Fu Master.

Il produit également un résultat plus rapidement. Bien que les programmes soient relativement petits, de nombreux contrôleurs sont compétitifs avec les méthodes de pointe pour l'ensemble de référence Atari et nécessitent moins de temps de formation, disent Wilson et co.

Le code évolué a un autre avantage. Parce qu'il est petit, il est facile de voir comment cela fonctionne. En revanche, un problème bien connu des techniques d'apprentissage en profondeur est qu'il est parfois impossible de savoir pourquoi elles ont pris des décisions particulières, ce qui peut avoir des ramifications pratiques et juridiques.

Dans l'ensemble, il s'agit d'un travail intéressant qui devrait suggérer aux informaticiens qui se concentrent exclusivement sur l'apprentissage en profondeur qu'il leur manque peut-être une astuce. L'approche évolutive est une alternative puissante qui peut être appliquée dans un large éventail de situations.

En effet, certains chercheurs ont commencé à l'utiliser pour faire évoluer de meilleures machines d'apprentissage en profondeur. Qu'est ce qui pourrait aller mal?

Réf : https://arxiv.org/abs/1806.05695 : Programmes simples évolutifs pour jouer à des jeux Atari

cacher