Former un Agent pour maîtriser un jeu simple grâce à l’auto-apprentissage

Formation d'un agent pour maîtriser un jeu simple par auto-apprentissage

Simuler des jeux et prédire les résultats.

Introduction

N’est-il pas incroyable que tout ce dont vous avez besoin pour exceller dans un jeu d’information parfaite soit là pour tout le monde à voir dans les règles du jeu ?

Malheureusement, pour de simples mortels comme moi, lire les règles d’un nouveau jeu n’est qu’une infime partie du voyage pour apprendre à jouer à un jeu complexe. La plupart du temps est passé à jouer, idéalement contre un joueur de force comparable (ou un meilleur joueur assez patient pour nous aider à mettre en évidence nos faiblesses). Perdre souvent et espérer gagner parfois offre les punitions et les récompenses psychologiques qui nous poussent à jouer de manière incrémentielle mieux.

Peut-être que dans un avenir pas trop lointain, un modèle de langage lira les règles d’un jeu complexe comme les échecs et, dès le départ, jouera au plus haut niveau possible. En attendant, je propose un défi plus modeste : apprendre par auto-apprentissage.

Dans ce projet, nous allons entraîner un agent à apprendre à jouer à des jeux d’information parfaite à deux joueurs en observant les résultats de parties jouées par des versions antérieures d’eux-mêmes. L’agent estimera une valeur (le résultat attendu du jeu) pour n’importe quel état du jeu. En plus de cela, notre agent ne sera pas autorisé à maintenir une table de recherche de l’espace d’états, car cette approche ne serait pas gérable pour des jeux complexes.

• Le guide ultime pour entraîner BERT à partir de zéro Le Tokenizer
• Comment devenir un analyste sportif?
• Top 50 Outils d’écriture IA à essayer (septembre 2023)

Résoudre SumTo100

Le jeu

Le jeu que nous allons discuter est SumTo100. Le but du jeu est d’atteindre une somme de 100 en ajoutant des nombres entre 1 et 10. Voici les règles :

1. Initialiser la somme à 0.
2. Choisir un premier joueur. Les deux joueurs jouent à tour de rôle.
3. Tant que la somme < 100 :

• Le joueur choisit un nombre entre 1 et 10 inclusivement. Le nombre sélectionné est ajouté à la somme sans dépasser 100.
• Si la somme < 100, l’autre joueur joue (c’est-à-dire que nous revenons au point 3).

4. Le joueur qui a ajouté le dernier nombre (atteignant 100) gagne.

Commencer avec un jeu aussi simple présente de nombreux avantages :

• L’espace d’états n’a que 101 valeurs possibles.
• Les états peuvent être représentés sur une grille 1D. Cette particularité nous permettra de représenter la fonction de valeur d’état apprise par l’agent sous forme d’un graphique à barres 1D.
• La stratégie optimale est connue : atteindre une somme de 11n + 1, où n ∈ {0, 1, 2, …, 9}

Nous pouvons visualiser la valeur d’état de la stratégie optimale :

L’état du jeu est la somme après qu’un agent a terminé son tour. Une valeur de 1.0 signifie que l’agent est sûr de gagner (ou a gagné), tandis qu’une valeur de -1.0 signifie que l’agent est sûr de perdre (en supposant que l’adversaire joue de manière optimale). Une valeur intermédiaire représente le rendement estimé. Par exemple, une valeur d’état de 0.2 signifie un état légèrement positif, tandis qu’une valeur d’état de -0.8 représente une probable perte.

Si vous souhaitez plonger dans le code, le script qui effectue l’ensemble de la procédure de formation est learn_sumTo100.sh, dans ce référentiel. Sinon, suivez-moi car nous passerons en revue une description de haut niveau de la façon dont notre agent apprend par auto-apprentissage.

Génération des jeux joués par des joueurs aléatoires

Nous voulons que notre agent apprenne à partir des jeux joués par les versions précédentes de lui-même, mais lors de la première itération, puisque l’agent n’a encore rien appris, nous devrons simuler des jeux joués par des joueurs aléatoires. À chaque tour, les joueurs obtiendront la liste des mouvements légaux de l’autorité du jeu (la classe qui encode les règles du jeu), étant donné l’état actuel du jeu. Les joueurs aléatoires sélectionneront un mouvement au hasard dans cette liste.

La Figure 2 est un exemple d’un jeu joué par deux joueurs aléatoires:

Dans ce cas, le deuxième joueur a remporté le jeu en atteignant une somme de 100.

Nous implémenterons un agent qui a accès à un réseau neuronal qui prend en entrée un état de jeu (après que l’agent a joué) et produit la valeur de retour attendue de ce jeu. Pour un état donné (avant que l’agent ait joué), l’agent obtient la liste des actions légales et leurs états candidats correspondants (nous ne considérons que des jeux ayant des transitions déterministes).

La Figure 3 montre les interactions entre l’agent, l’adversaire (dont le mécanisme de sélection des mouvements est inconnu) et l’autorité du jeu:

Dans ce cadre, l’agent s’appuie sur son réseau neuronal de régression pour prédire la valeur de retour attendue des états de jeu. Plus le réseau neuronal peut prédire quel mouvement candidat produit le rendement le plus élevé, meilleur sera le jeu de l’agent.

Notre liste de matchs joués aléatoirement nous fournira les données pour notre première passe d’entraînement. Prenons l’exemple du jeu de la Figure 2, nous voulons punir les mouvements effectués par le joueur 1 car son comportement a conduit à une défaite. L’état résultant de la dernière action obtient une valeur de -1,0 car elle a permis à l’adversaire de gagner. Les autres états obtiennent des valeurs négatives réduites d’un facteur de γᵈ , où d est la distance par rapport au dernier état atteint par l’agent. γ (gamma) est le facteur de réduction, un nombre ∈ [0, 1], qui exprime l’incertitude dans l’évolution d’un jeu : nous ne voulons pas punir les décisions prises tôt aussi durement que les dernières décisions. La Figure 4 montre les valeurs d’état associées aux décisions prises par le joueur 1:

Les jeux aléatoires génèrent des états avec leur valeur de retour attendue. Par exemple, atteindre une somme de 97 a une valeur de retour attendue de -1,0, et une somme de 73 a une valeur de retour attendue de -γ³. La moitié des états adoptent le point de vue du joueur 1, et l’autre moitié adopte le point de vue du joueur 2 (bien que cela n’ait pas d’importance dans le cas du jeu SumTo100). Lorsqu’un jeu se termine par une victoire de l’agent, les états correspondants obtiennent des valeurs positives réduites de manière similaire.

Formation d’un agent pour prédire le retour des jeux

Nous avons tout ce dont nous avons besoin pour commencer notre formation : un réseau neuronal (nous utiliserons un perceptron à deux couches) et un ensemble de données de paires (état, retour attendu). Voyons comment la perte sur le retour attendu prédit évolue :

Il n’est pas surprenant que le réseau neuronal ne montre pas beaucoup de pouvoir prédictif sur le résultat des jeux joués par des joueurs aléatoires.

Le réseau neuronal a-t-il appris quelque chose ?

Heureusement, parce que les états peuvent être représentés sous la forme d’une grille unidimensionnelle de nombres entre 0 et 100, nous pouvons tracer les rendements prédits du réseau neuronal après le premier tour d’entraînement et les comparer aux valeurs d’état optimales de la Figure 1:

Il s’avère que, à travers le chaos des jeux aléatoires, le réseau neuronal a appris deux choses :

• Si vous pouvez atteindre une somme de 100, faites-le. C’est bon à savoir, étant donné que c’est l’objectif du jeu.
• Si vous atteignez une somme de 99, vous êtes sûr de perdre. En effet, dans cette situation, l’adversaire n’a qu’une seule action légale et cette action conduit à une perte pour l’agent.

Le réseau neuronal a essentiellement appris à terminer le jeu.

Pour apprendre à jouer un peu mieux, nous devons reconstruire l’ensemble de données en simulant des jeux joués entre des copies de l’agent avec leur réseau neuronal fraîchement entraîné. Pour éviter de générer des jeux identiques, les joueurs jouent un peu au hasard. Une approche qui fonctionne bien est de choisir des mouvements avec l’algorithme epsilon-greedy, en utilisant ε = 0,5 pour le premier mouvement de chaque joueur, puis ε = 0,1 pour le reste du jeu.

Répéter la boucle d’entraînement avec des joueurs de plus en plus forts

Étant donné que les deux joueurs savent maintenant qu’ils doivent atteindre 100, atteindre une somme entre 90 et 99 devrait être puni, car l’adversaire saisirait l’occasion de gagner le match. Ce phénomène est visible dans les valeurs d’état prédites après le deuxième tour d’entraînement :

Nous constatons l’émergence d’un motif. Le premier tour d’entraînement informe le réseau neuronal sur la dernière action ; le deuxième tour d’entraînement informe sur l’avant-dernière action, et ainsi de suite. Nous devons répéter le cycle de génération de jeux et d’entraînement sur la prédiction au moins autant de fois qu’il y a d’actions dans un jeu.

L’animation suivante montre l’évolution des valeurs d’état prédites après 25 tours d’entraînement :

L’enveloppe des rendements prédits décroît de manière exponentielle, à mesure que nous nous éloignons de la fin du jeu. Est-ce un problème ?

Deux facteurs contribuent à ce phénomène :

• γ amortit directement les rendements attendus cibles, à mesure que nous nous éloignons de la fin du jeu.
• L’algorithme epsilon-greedy injecte de l’aléatoire dans les comportements des joueurs, rendant les résultats plus difficiles à prévoir. Il y a une incitation à prédire une valeur proche de zéro pour se protéger contre les cas de pertes extrêmement élevées. Cependant, l’aléatoire est souhaitable car nous ne voulons pas que le réseau neuronal apprenne une seule ligne de jeu. Nous voulons que le réseau neuronal observe des erreurs et des mouvements inattendus, à la fois de l’agent et de l’adversaire.

En pratique, cela ne devrait pas poser de problème car dans toutes les situations, nous comparerons les valeurs parmi les mouvements légaux dans un état donné, qui partagent des échelles comparables, du moins pour le jeu SumTo100. L’échelle des valeurs n’a pas d’importance lorsque nous choisissons le mouvement vorace.

Conclusion

Nous nous sommes lancés le défi de créer un agent capable d’apprendre à maîtriser un jeu d’information parfaite impliquant deux joueurs, avec des transitions déterministes d’un état à l’autre, en fonction d’une action. Aucune stratégie ni tactique codée à la main n’était autorisée : tout devait être appris par auto-apprentissage.

Nous avons pu résoudre le jeu simple de SumTo100 en exécutant plusieurs tours d’affrontement de copies de l’agent les unes contre les autres, et en entraînant un réseau neuronal de régression à prédire le rendement attendu des parties générées.

Les connaissances acquises nous préparent bien pour l’échelon suivant de complexité du jeu, mais cela sera pour mon prochain post! 😊

Merci de votre temps.

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!