Apprentissage par renforcement d’un agent jouant au jeu Breakthrough avec modèle neuronal et recherche en profondeur itérative.

Nicolas

Informations

• Publié par: Nicolas-
• Publié le: 12 juillet 2013
• Nombre de lectures: 31
• Langue: Français

Extrait

Apprentissage par renforcement d’un agent jouant au jeu Breakthrough avec modèle neuronal et recherche en profondeur itérative.   Nicolas Pinchaud COMP-424 9 avril 2009   Le problème consistait à développer un agent Nous optimisons l’exploitation des ressources jouant au jeu de Breakthrough. Nous allons temporelles et mémoire, à l’aide d’une présenter dans ce rapport, quelques points clefs recherche en profondeur itérative. Nous de sa réalisation. La problématique peut se effectuons des recherches MinMax avec résumer à un problème de recherche, où élagage alpha-beta, en augmentant l’ensemble des états sont les différentes itérativement la profondeur limite, cela tant configurations possibles du damier, les qu’il nous reste du temps. Nous prenons soin transitions entre les états se font en déplaçant de vérifier régulièrement la marge de temps un pion, les déplacements autorisés sont restante et nous nous attribuons une marge de définis par les règles du jeu, et les états sécurité, pour être sur de ne pas dépasser le terminaux correspondent aux situations où un seuil limite de 5 secondes. pion à atteint le bord adverse du damier. La ressource mémoire à été exploité en L’objectif est de trouver un chemin dans cet mémorisant à chaque itération l’arbre de espace d’états menant à un état terminal recherche, où chaque nœud contient les valeurs correspondant à une victoire, en prenant en des heuristiques, et la valeur du chemin depuis compte l’objectif opposé de l’adversaire. On la racine, cette information est ensuite va considérer l’ensemble des chemins exploitée par l’itération suivante. La possibles depuis un état courant, avec une disposition de l’arbre est optimisée lors de la longueur maximale limité par les ressources de recherche, pour l’itération suivante, en la machine. Si un de ces chemins mène à un disposant les meilleures branches de l’itération état terminal victorieux, nous le sélectionnons, i, à gauche de l’arbre, ainsi à l’itération i+1, sinon nous utilisons une heuristique pour ces branches seront explorées en premier. estimer la probabilité de chaque chemin de Lorsque la marge de temps restant passe en mener vers un état terminal favorable, et nous dessous d’un seuil de sécurité (200ms), la sélectionnons le meilleur. Nous allons voir les recherche s’arrête et renvoie la meilleure moyens utilisés pour optimiser cette recherche, solution obtenue jusqu’alors. Sur un ordinateur et voir comment l’on peut définir une cadencé à 1.8GHz, on atteint en général une heuristique efficace. profondeur de 7 coups en utilisant un PMC de   40 unités cachées pour l’heuristique, ce Pour calculer les coups à jouer, nous avions nombre augmente au fur et à mesure que le une limite en temps, et une limite en espace nombre de pièces sur le plateau diminue. mémoire. Nous proposons une approche qui exploite ces deux ressources, en utilisant une méthode de recherche en profondeur itérative. II Heuristique    L’heuristique est une combinaison linéaire de deux autres heuristiques, l’une définie par un L’heuristique est une combinaison linéaire de expert, l’autre par un perceptron multicouche deux autre heuristiques, l’une dite « rigide » (PMC). Etant donné que chaque adversaire codé par un expert, l’autre « souple » est un peut avoir un comportement de jeu différent, le PMC, dont les poids sont appris par PMC permet de moduler la stratégie en renforcement, avec une approche similaire à fonction de l’adversaire, en apprenant en [ Tesauro, 1992-1995 ]. Les paramètres de ce fonction de ses coups, grâce à la rétro PMC et de son apprentissage sont le nombre propagation du gradient. de neurones dans la couche cachée, les  « features » données en entrée, et les La première partie traite de la recherche en paramètres du TD-Learning. Dans un premier profondeur itérative, la seconde de  temps nous avons défini l’heuristique comme l’heuristique, et enfin nous concluons par un la sortie du PMC uniquement, mais il s’est résumé. avéré nécessaire de la compléter avec  l’heuristique rigide attribué par un expert, nous I Recherche en profondeur itérative allons voir pourquoi. Pour cela expliquons  d’abord comment nous avons déterminé les

paramètres du PMC, et voyons que la réalisation de ce problème a rendu compte de la nécessité d’ajouter l’autre heuristique.   L’apprentissage initial du PMC est fait en faisant jouer l’agent contre lui-même. Il est intéressant de voir que les résultats sont très dépendants du type d’entrées données au réseau. Pour des entrées RAW, le PMC ne parvient pas à déduire les règles fondamentales du jeu, et les issues de partie semblent dues au hasard, cela ce voit par une politique qui ne sélectionne pas les choix évidents, à gain immédiat maximal (victoire de la partie), on le voit aussi par le fait que les poids du PMC ne convergent pas. Nous supposons que c’est du au fait que la politique optimale représentée par une fonction non linéaire dans l’espace de représentation RAW est trop compliquée à apprendre, i.e. nécessite un nombre plus important de neurones dans la couche cachées. Mais augmenter le nombre de neurones, augmente d’autant la capacité du modèle et donc le nombre de minimas locaux, et par conséquent, avec une technique n’ayant pas d’apriori suffisant sur cette espace de solution, comme la descente de gradient qui ne se base que sur des informations locales (le gradient en un point), le risque de converger vers un minima de mauvaise qualité est important, d’où les mauvais résultats avec les entrées RAW. Par ailleurs, si l’espace de représentation est trop simple, le PMC ne va pas être performant non plus, car des informations utiles pourront être perdues, lors de la réduction. Il faut donc trouver un compromis. Un point de vue intéressant, pourrait être de voir une politique comme un vecteur, dont le nombre de composant correspond au nombre d’état différents, ce n’est pas un vecteur car ces composants ne sont pas des scalaires, mais d’autres vecteurs donnant pour chaque action, la probabilité qu’elle soit choisie, donc plutôt devrait t’on parler de tenseur ou de fonction multilinéaires, pour être exact. La politique ainsi vue comme un « vecteur généralisé », permettrait l’application de méthodes de type PCA, on considèrerait alors la projection de la politique dans un sous espace de plus faible dimension, tel que la perte d’information engendré soit minimale, ainsi la complexité de la politique dans cet espace est moins importante et peut permettre son apprentissage par un PMC. Toutefois ce n’est pas ainsi que nous procédons, mais l’idée est suffisamment intéressante pour être mentionné.  

La représentation réduite de la politique est définie par des features, qui sont donnés par un expert. Une feature ne représente qu’une partie de l’information concernant l’état du damier, comme par exemple le nombre de pion encore en jeu. Entrons dans un formalisme et appelons : S | A  la politique que nous voulons apprendre, où S  est l’ensemble des états, et A l’ensemble des vecteurs de probabilité sur les actions, les features sont des fonctions f i : S | Â . L’ensemble de ces features représente non pas un état, mais une classe d’états, partageant les mêmes propriétés définies par les features. Les features peuvent être vues comme une relation d’équivalence entre les états: sRs Û " i , f i ( s ) 1 f i ( s )   Et définissent un ensemble quotient : S / R 1 s , s 1 s Î S , s ' Rs ΥΥ   Ainsi on peut définir une nouvelle politique : S / R | A sur cet ensemble quotient à partir de la politique que nous voulons apprendre, comme étant la probabilité moyenne de chaque action sur une classe : ϑ : s | 1 ∑ ϑ ( s ) s s Î s   On voit que sera d’autant plus fidèle à si la variance au sein d’une classe est faible, il faut donc choisir judicieusement les features, pour minimiser cette variance. On pourrait les apprendre en faisant du clustering minimisant la variance intra classe, et maximisant celle inter-classes. Il serait possible de faire ce clustering sur un échantillon de réalisations de la politique, qui nous servirait de base d’apprentissage pour un nouveau PMC qui aurait pour objectif de généraliser la clusterisation sur l’ensemble complet des états, et donnerait en sortie leur classe correspondante, autrement dit le PMC serait une approximation de la projection canonique, sa sortie pourrait servir d’entrée à notre PMC d’origine, ce qui finalement reviendrait à définir un unique PMC avec trois couches cachées. Ce n’est pas comme ça que nous procédons, mais cela pourrait faire l’objet d’un futur travail.     Différentes features ont été testé, nous avons d’abord représenté le plateau du jeu en 32 valeurs, les 16 premières correspondants au nombre de pions du joueurs par ligne (8 valeurs), et par colonnes (8 autres valeurs), les

16 autres valeurs sont identiques mais correspondent aux pions de l’adversaire. Avec ce type de représentation, a émergé rapidement un comportement de type « agressif », le joueur ayant compris que le fait de réduire le nombre de pions de ses adversaires permettait d’optimiser ses gain, car favorisait la victoire, et réduisait le risque de défaite, car ce comportement évitait de se faire « avaler » par l’adversaire en l’avalant le premier. Cela entrainait une réduction rapide du nombre de pions sur le plateau. Nous avons aussi expérimenté une représentation « temporelle » en prenant en compte non seulement l’état courant du plateau, mais aussi l’état précédant, et deux features ont été ajoutées. La première valait 1 si le pion déplacé était mis en situation de péril par un pion adverse, la seconde valait aussi 1 si le pion déplacé « mangeait » un pion adverse, ils valaient tous les deux 0 sinon. Avec ce type de représentation, il était facile au PMC d’apprendre la simple heuristique qui consiste à donner des points si on mange un adversaire, ou à en enlever si on se met en péril. Cela amène à penser que beaucoup d’efforts sont mis en œuvre pour des résultats modestes, en effet il est simple de coder manuellement ce type d’heuristique, qui favorise les actions évidentes, comme manger, ou éviter de se faire manger. Par ailleurs, utiliser un PMC est couteux en temps de calcul, hors ici le temps est important. C’est donc pourquoi nous avons décidé de mixer deux types d’heuristiques. Les heuristiques « rigides », données par un expert, et restants fixes, et les heuristiques « souple » étant déterminées pas un modèle d’apprentissage, comme le PMC, elles ont la particularité de pouvoir évoluer et de s’adapter en fonction de la situation courante. Nous implémentons manuellement une heuristique « rigide », la plus générale possible, pour pouvoir être capable de faire face à un ensemble de stratégie adverse le plus large possible. En effet une heuristique qui engendre une stratégie très spécifique, comme « attaquer à droite » peut être très efficace contre d’autres stratégies spécifiques, par exemple « défendre à gauche », mais sera mauvaise en moyenne, car faible est la probabilité sans apriori, de se retrouver confronté à un adversaire abordant ce type de stratégie. L’heuristique codée « rigide » consiste à favoriser l’avancement des pions du joueur, et à défavoriser celui de l’adversaire, et donner un gain maximal en cas de victoire ou minimal en cas de perte. Cette heuristique est un socle

de base. Une comparaison intéressante avec le vivant peut être faite en voyant cette heuristique comme un mécanisme de reflexe instinctif, nécessaire a la vie d’un animal (ici en évitant la défaite de l’agent considérée comme sa mort), comme les battements du cœur. Heureusement nous n’avons pas à réfléchir à chaque instant et à ordonner consciemment le déclenchement de la pompe cardiaque. Ces ordres sont donnés automatiquement par des circuits nerveux simples et rapides, usant peu d’énergie, comme l’est notre heuristique « rigide » en utilisant peu de ressource machine. Remarquons que ces besoins vitaux sont constants, et qu’ils sollicitent une émission d’informations nerveuses régulière, depuis le cerveau vers le cœur, la nature a fait en sorte d’optimiser la consommation énergétique en développant des circuits nerveux simples pour ces taches répétitives. On peut extrapoler en imaginant des circuits de complexité graduellement croissante, et de plus en plus consommatrices d’énergie, utilisés pour des taches de moins en moins occurrentes, ces circuits doivent prendre en charge des classes d’événements de cardinalité plus grande et nécessitent un pouvoir de généralisation plus élevée, d’où leur complexité accrue. Ainsi pour l’individu moyen, la tache qui consiste par exemple à résoudre une équation différentielle, et qui possède une occurrence faible, va solliciter un circuit nerveux complexe, gourmand en énergie, on peut imaginer que pour le mathématicien, ce circuit aura été simplifié au fil du temps par des processus d’élagages ou d’aiguillage appropriés dans le cerveau, et nécessitera moins d’énergie. Notons que cela rappelle fortement l’algorithme de codage Huffman, qui consiste à attribuer aux mots fréquents, une écriture de petite taille. Ce n’est que lorsque les besoins vitaux de base sont satisfaits, que nous pouvons ajouter par-dessus une couche cognitive plus complexe, usant plus d’énergie, permettant de prendre en charge des évènements moins fréquents, c’est à cela que sert le PMC.   Les structures des arbres de recherche MinMax ne présentent pas une homogénéité suffisante pour pouvoir être généralisé par l’heuristique rigide. Les variantes stratégiques des différents adversaires rendent ces arbres hétérogènes, il est donc nécessaire d’adjoindre le modèle à pouvoir de généralisation plus élevé qu’est le PMC. Celui-ci va tenter de trouver des « patterns victorieux » ou des « patterns de défaite » dans les arbres. Il a l’avantage de

pouvoir permettre de les détecter « online »  1 , grâce a l’apprentissage par renforcement, il correspond à une heuristique « souple ». Par ailleurs le PMC va compléter l’heuristique « rigide », en étant dans un premier temps, pré- entrainé par renforcement en jouant contre lui- même, pour détecter d’autres patterns a occurrence élevée, que l’heuristique « rigide » ne prend pas en compte.   Les risques de faire du sur-apprentissage en faisant jouer l’agent contre lui-même est important. En effet, comme l’évolution d’une stratégie développée récursivement par auto- entrainement, se faisant en réponse à une précédente stratégie définie par l’état précédant du PMC, le résultat risque d’être très sensible à la stratégie initiale représentée par l’état initial aléatoire du PMC, et risque de converger vers un minima local représentant une classe particulière de stratégies, et de sur-apprendre cette classe. Pour éviter le sur-apprentissage, nous pouvons élargir l’espace des stratégies explorées en introduisant des mouvements aléatoires appliqués à l’agent durant son processus d’apprentissage. Ce caractère aléatoire est représenté par un paramètre de température, qui décroit au fil du temps, on espère que cela permet l’exploration d’un espace plus large autour de l’état initial, et qu’il y aura convergence stochastique vers une solution ayant une bonne capacité de généralisation. D’autre part, nous pourrions avoir une base de validation, caractérisée par un autre agent, sur lequel on testerait les performances de l’agent auto-apprenant, et on stopperait l’algorithme RL 2 , aussitôt que les performances sur l’agent de validation diminueraient, ce qui indiquerait le sur- apprentissage. Néanmoins, nous ne disposons pas ici d’agent tiers, nous avons donc utilisé un autre critère. Il consiste à sauvegarder des copies de l’agent durant son auto- apprentissage, à intervalle de temps régulier. On continue l’auto-apprentissage tant que la                                                   1 Notons que je n’ai pas activé la fonction d’apprentissage pour le tournois, car d’une part le nombre de jeux joués est faible et plusieurs instances du PMC sont créés en parallèles, cela limite donc l’efficacité de l’apprentissage, puisque la base d’apprentissage est divisé en nombre d’instances indépendantes. D’autre part après avoir consulté Mahdi, il semble que cela risquait de perturber le déroulement du programme gérant le tournoi, car l’apprentissage se fait par rétro propagation du gradient en fin de partie, et donc demande un temps supplémentaire, non prévu. 2 Reinforcement Learning

performance de l’agent est meilleure que celle des copies quand ils sont mis en confrontation. Par exemple l’agent 200HU-4000-FE32  qui a joué 4000 parties contre lui-même, obtient un taux de victoire de 0.93 contre l’agent 200HU-900-FE32, le même entrainé avec 900 parties. Cela signifie que l’agent 200HU-4000-FE32 a découvert des patterns utiles. Par ailleurs, l’agent 200HU- 11000-FE32 entrainé sur 11000 parties, obtient une performance de 0.30 contre 200HU-4000-FE32 , ce qui montre qu’il a sur-appris.   Nous avons notre heuristique « rigide » et « souple », nous obtenons notre heuristique globale par combinaison linéaire des deux heuristiques :   Heuristic (1 ) Heuristic _ PMC Heurisitic _ Rigid   Où est un apriori sur l’heuristique rigide, en pratique est élevé, de sorte que le comportement de l’agent est majoritairement gouverné par ses « instincts », mais lorsque l’heuristique souple détecte un pattern, il prendra une valeur extrême, proche de 1 si c’est un pattern « victorieux », proche de 0 sinon, cela influencera alors l’heuristique globale et par conséquent le comportement de l’agent.   III Résumé   Nous avons vu comment nous effectuons la recherche du coup à jouer en explorant d’une part l’arbre MinMax de façon itérative, d’autre part nous tentons de prédire la valeur de gain d’une branche à l’aide d’une heuristique. L’heuristique est une combinaison linéaire de deux autres : l’une est définie par un expert et identifie - les situations très générales et très fréquentes.   - la seconde est un PMC qui complète la première, en tentant d’identifier d’autres situations générales, grâce à un apprentissage par renforcement par auto- entrainement. On a vu comment éviter le sur-apprentissage en créant des copies de l’agent. D’autre part, on a vu aussi que le PMC pouvait s’adapter à la stratégie de l’adversaire courant en apprenant « online ».