Comment apprend-on à une machine à jouer au Pong ?

Pour comprendre l'apprentissage par renforcement, imaginez un enfant qui apprend à marcher. L’enfant est autonome et en interaction avec son environnement. S'il réalise un bon mouvement, il reste debout et se satisfait d’avancer vers son objectif. A l’inverse, s'il réalise un mauvais mouvement, il tombe et se fait légèrement mal. Pour notre machine c’est pareil! Nous allons la placer dans un environnement (règles du jeu) et lui définir l’ensemble des actions possibles (mouvements). Quand la machine prend une décision, l’environnement lui renvoie une récompense positive ou négative. Ainsi à chaque étape, la machine apprend de son environnement.

Un vrai algorithme de Reinforcement Learning va s'intéresser à chacune des prises de décisions de la machine et essayer de choisir la meilleur action à prendre pour maximiser sa récompense actuelle et surtout future. A l’inverse, une méthode évolutive (algorithmes génétiques) va s’intéresser à l’état final du jeu. Elle va seulement regarder le score final de la machine et n’aura pas la précision de la qualité de ses actions tout au cours du jeu.

Ces méthodes évolutives sont certes limitées mais donnent déjà de bons résultats pour appréhender le concept d’apprentissage par renforcement. Plus de détails sur le Reinforcement Learning et ses différences avec les méthodes évolutives feront l’objet d’un autre article mais peuvent être trouvées ici.

Playground

Nous allons donc jouer à pong, le célèbre jeu inspiré du tennis de table. Par souci de simplicité, nous allons jouer à une version très basique : l'angle de rebond de la balle ne changera pas en fonction de l'impact avec la raquette. (cela ne change rien dans l'algorithme).

Définissons donc le terrain de jeu de notre agent :

• Environnement : le jeu Pong basique. Deux joueurs s'affrontent via leurs raquettes. La balle rebondit sur les bords de la table.
• Actions possibles : un joueur peut monter, descendre ou laisser en place sa raquette.
• Système de récompenses : si un joueur tape la balle il gagne 1 point. Le jeu s'arrête quand un des joueurs manque la balle.
• Etat de l’environnement : à chaque instant, chacun des joueurs voit où se trouve la balle (position relative à sa raquette) et connait la position de sa raquette

Le Pong est un jeu à 2 joueurs. Il s’agit donc à chaque partie de confronter deux agents virtuels. Le jeu s'arrête quand l’un des deux agents meurt.

L'algorithme

Un agent va être défini par un cerveau virtuel : un réseau de neurones. Un réseau de neurones est utilisé pour déterminer par apprentissage la relation qui donne le bon choix de mouvement à partir d’une observation de son environnement.

Pour notre exemple, l’agent observe son environnement avec 3 variables : les deux premières donnant la position relative de la balle par rapport à sa raquette et la dernière donnant la position de la raquette. A partir de ces données d’entrées, le réseau de neurones calcule (avec des fonctions et poids particuliers sur ses neurones) les données de sorties. On définit ensuite une action à prendre en fonction de ces dernières.

Le schéma suivant synthétise les données d'entrées et de sorties. La valeur la plus haute parmi les données de sorties donne l’action à prendre : monter, descendre ou rester.

Le sujet revient donc à la question suivante comment choisir le réseau de neurones ? Et comment le réseau apprend-il à choisir les bonnes actions à partir des données d’entrées ? C’est ici que l’algorithme génétique entre en jeu.

Les algorithmes génétiques répliquent les lois de la nature pour trouver les agents qui sont les plus forts face à leur environnement. Il sont ainsi basés sur deux concepts clés:

• Élitisme : l’idée derrière un algorithme génétique est de ne garder que les meilleurs agents - ceux dont le score est le plus élevé dans la partie du jeu - et de les mixer pour en créer des descendances. C’est le principe de la sélection naturelle : ceux qui survivent le mieux dans leur environnement se reproduisent et font perdurer leur code génétique aux générations suivantes.
• Mutation : lorsque des agents donnent naissance à un nouvel agent, celui-ci est en proie à une mutation génétique qui lui donnera peut-être une capacité encore plus puissante pour survivre dans son environnement. Sans ces mutations, l’évolution de l’espèce n’aura pas la capacité d’explorer et pourrait perdurer dans la mauvaise direction.

Le processus global d’apprentissage par renforcement est donc le suivant :

• On crée 50 cerveaux avec des branchements simples entre les neurones (modèle feed-forward à deux couches intermédiaires) et on met des poids aléatoires sur chacun des neurones
• On lance 50 parties de Pong avec ces réseaux. Les deux joueurs d’une même partie ont le “même cerveau”
• Une fois que toutes les parties sont terminées on récupère les cerveaux des dix meilleures parties (celles avec les meilleurs scores)
• On crée 50 enfants à partir de ces 10 cerveaux : les neurones sont mixés entre eux pour faire de nouveaux réseaux et certains neurones sont définis aléatoirement (mutations)
• On relance 50 parties et on réitère le processus

Résultats & Ouverture

Après une 50aine de générations, soit 2500 parties jouées, nos agents sont capables de faire de belles parties de Pong.

A venir : Un prochain article plongera plus en détail dans le code de cette expérimentation et vous permettra d'entraîner vous même votre propre IA au Pong pour ensuite la défier en réel !

Remarque: Pourquoi tant d’intérêt pour le Reinforcement Learning ? Réponse rapide : car c’est la manière la plus naturelle d'entraîner une intelligence artificielle. Une fois son environnement et son système de récompenses bien définis la machine est capable d’obtenir d’excellents résultats sans avoir aucune donnée d'entraînement historique à disposition. Un bel exemple est la main robot d’OpenAI qui apprends par elle même la dextérité.