Former un agent à maîtriser le Tic-Tac-Toe grâce au jeu autonome | de Sébastien Gilbert | septembre 2023

Étonnamment, un agent logiciel ne se lasse jamais du jeu.

Ah ! école primaire! C’est à cette époque que nous avons acquis des compétences précieuses, telles que l’alphabétisation, l’arithmétique et le jeu optimal du morpion.

Jouer un tic-tac-toe avec son ami sans se faire prendre par le professeur est tout un art. Vous devez passer discrètement la feuille de jeu sous le bureau tout en donnant l'impression d'être attentif au sujet. Le plaisir était probablement plus lié à l'opération d'infiltration qu'au jeu lui-même.

Nous ne pouvons pas enseigner à un agent logiciel l’art d’éviter de se faire prendre en classe, mais pouvons-nous former un agent à maîtriser le jeu ?

Dans mon article précédent, nous avons étudié un agent apprenant le jeu SommeÀ100 grâce au jeu personnel. C'était un jeu simple qui nous permettait d'afficher la valeur de l'état, ce qui nous a aidé à construire une intuition sur la façon dont l'agent apprend le jeu. Avec le tic-tac-toe, nous abordons un espace d’états beaucoup plus vaste.

Vous pouvez trouver le code Python dans ce référentiel. Le script qui effectue la formation est apprendre_tictactoe.sh:

#!/bin/bash
déclarer -i NUMBER_OF_GAMES=30000
déclarer -i NUMBER_OF_EPOCHS=5
exporter PYTHONPATH='./'
prétraitement python/generate_positions_expectations.py \
--outputDirectory=./learn_tictactoe/output_tictactoe_generate_positions_expectations_level0 \
--game=tictactoe\
--numberOfGames=$NUMBER_OF_GAMES \
--gamma=0,95 \
--randomSeed=1 \
--agentArchitecture=Aucun \
--agentFilepath=Aucun \
--opponentArchitecture=Aucun \
--opponentFilepath=Aucun \
--epsilons="[1.0]" \
--température=0
dataset_filepath="./learn_tictactoe/output_tictactoe_generate_positions_expectations_level0/dataset.csv"
python train/train_agent.py \
$dataset_filepath \
--outputDirectory="./learn_tictactoe/output_tictactoe_train_agent_level1" \
--game=tictactoe\
--randomSeed=0 \
--validationRatio=0,2 \
--batchSize=64 \
--architecture=SaintAndré_1024 \
--dropoutRatio=0,5 \
--learningTaux=0,0001 \
--weightDecay=0,00001 \
--numberOfEpochs=$NUMBER_OF_EPOCHS \
--startingNeuralNetworkFilepath=Aucun
pour le niveau en {1..16}
faire
dataset_filepath="./learn_tictactoe/output_tictactoe_generate_positions_expectations_level${level}/dataset.csv"
prétraitement python/generate_positions_expectations.py \
--outputDirectory="./learn_tictactoe/output_tictactoe_generate_positions_expectations_level${level}" \
--game=tictactoe\
--numberOfGames=$NUMBER_OF_GAMES \
--gamma=0,95 \
--randomSeed=0 \
--agentArchitecture=SaintAndré_1024 \
--agentFilepath="./learn_tictactoe/output_tictactoe_train_agent_level${level}/SaintAndre_1024.pth" \
--opponentArchitecture=SaintAndré_1024 \
--opponentFilepath="./learn_tictactoe/output_tictactoe_train_agent_level${level}/SaintAndre_1024.pth" \
--epsilons="[0.5, 0.5, 0.1]" \
--température=0 
déclarer -i next_level=$((level + 1))
python train/train_agent.py \
"./learn_tictactoe/output_tictactoe_generate_positions_expectations_level${level}/dataset.csv" \
--outputDirectory="./learn_tictactoe/output_tictactoe_train_agent_level${next_level}" \
--game=tictactoe\
--randomSeed=0 \
--validationRatio=0,2 \
--batchSize=64 \
--architecture=SaintAndré_1024 \
--dropoutRatio=0,5 \
--learningTaux=0,0001 \
--weightDecay=0,00001 \
--numberOfEpochs=$NUMBER_OF_EPOCHS \
--startingNeuralNetworkFilepath="./learn_tictactoe/output_tictactoe_train_agent_level${level}/SaintAndre_1024.pth"
fait

Le script parcourt les appels à deux programmes :

L'apprentissage du jeu par l'agent se déroule à travers un cycle de génération de matchs et d'entraînement pour prédire le résultat du match à partir de l'état du jeu :

Le cycle commence par la simulation de matchs entre joueurs aléatoires, c'est-à-dire des joueurs qui choisissent au hasard dans la liste des actions en justice dans un état de jeu donné.

Pourquoi générons-nous des matchs joués de manière aléatoire ?

Ce projet concerne l'apprentissage par le jeu personnel, nous ne pouvons donc donner à l'agent aucune information a priori sur comment jouer. Dans le premier cycle, puisque l’agent n’a aucune idée des bons ou des mauvais coups, les matchs doivent être générés par jeu aléatoire.

La figure 2 montre un exemple de match entre joueurs aléatoires :

Quelle leçon peut-on tirer en observant ce match ? Du point de vue du joueur « X », nous pouvons supposer qu'il s'agit d'un exemple de jeu médiocre puisqu'il s'est soldé par une défaite. Nous ne savons pas quel(s) mouvement(s) est(sont) responsable(s) de la défaite, nous supposerons donc que toutes les décisions faites par le joueur « X » étaient mauvaises. Si certaines décisions étaient bonnes, on mise sur les statistiques (d’autres simulations pourraient passer par un état similaire) pour rectifier leur valeur d’état prédite.

La dernière action du joueur « X » reçoit une valeur de -1. Les autres actions reçoivent une valeur négative actualisée qui décroît géométriquement d'un facteur γ (gamma) ∈ [0, 1] à mesure que nous reculons vers le premier mouvement.

Les États des matchs qui ont abouti à une victoire reçoivent des valeurs réduites positives similaires. Les États tirés des tirages reçoivent une valeur de zéro. L'agent prend le point de vue du premier et du deuxième joueur.

Le jeu s'exprime sous forme de tenseurs

Nous avons besoin d'une représentation tensorielle de l'état du jeu. Nous utiliserons un tenseur [2x3x3] où la première dimension représente les canaux (0 pour 'X' et 1 pour 'O'), et les deux autres dimensions sont les lignes et les colonnes. L'occupation d'un carré (ligne, colonne) est codée comme 1 dans l'entrée (canal, ligne, colonne).

Les couples de (tenseur d'état, valeur cible) obtenus par la génération de correspondances constituent l'ensemble de données sur lequel le réseau de neurones s'entraînera à chaque tour. L'ensemble de données est construit au début du cycle, en tirant parti de l'apprentissage effectué lors des cycles précédents. Alors que le premier tour génère un jeu purement aléatoire, les suivants génèrent des matchs progressivement plus réalistes.

Injecter du hasard dans le jeu

Le premier tour de génération de matchs oppose des joueurs aléatoires. Les tours suivants opposent l’agent à lui-même (d’où le « self-play »). L'agent est équipé d'un réseau neuronal de régression formé pour prédire le résultat du match, ce qui lui permet de choisir l'action en justice qui génère la valeur attendue la plus élevée. Pour promouvoir la diversité, l'agent choisit des actions basées sur un algorithme epsilon-gourmand : avec une probabilité (1-ε), la meilleure action est choisie ; sinon, une action aléatoire est choisie.

La figure 5 montre l'évolution des pertes de validation sur cinq époques pour un maximum de 17 cycles d'entraînement :

Nous pouvons voir que les premiers cycles de formation montrent une diminution rapide de la perte de validation, puis il semble y avoir un plateau autour d'une perte d'erreur quadratique moyenne de 0,2. Cette tendance montre que le réseau neuronal de régression de l'agent est plus apte à prédire l'issue d'un match joué contre lui-même, à partir d'un état de jeu donné. Puisque les actions des deux joueurs ne sont pas déterministes, il existe une limite à la prévisibilité de l’issue du match. Cela explique pourquoi la perte de validation cesse de s'améliorer après quelques tours.

Amélioration de tour en tour

Avec le jeu SommeÀ100, nous pourrions représenter l'état sur une grille 1D. Cependant, avec le tic-tac-toe, on ne peut pas afficher directement l'évolution des valeurs d'état. Une chose que nous pouvons faire pour mesurer l’amélioration est de comparer l’agent à sa version précédente et d’observer la différence entre les victoires et les pertes.

En utilisant ε = 0,5 pour la première action des deux joueurs et ε = 0,1 pour le reste du match, en effectuant 1000 matchs par comparaison, voici ce que nous obtenons :

Le nombre de victoires a dépassé le nombre de défaites (montrant une amélioration) jusqu'à 10 tours d'entraînement. Après cela, l'agent ne s'est pas amélioré d'un tour à l'autre.

Il est temps de voir comment notre agent joue au tic-tac-toe !

Une caractéristique utile d'un réseau neuronal de régression est la possibilité d'afficher l'évaluation de l'agent pour chaque mouvement légal. Jouons à un jeu contre l'agent, montrant comment il juge ses options.

Lecture manuelle

L'agent démarre en jouant « X » :

C'est comme ça qu'on se fait brutalement écraser par une machine à tic-tac-toe sans âme !

Dès que j'ai mis le « O » dans le carré (1, 0), le rendement attendu est passé de 0,142 à 0,419, et mon sort a été scellé.

Voyons comment cela se passe lorsque l'agent joue en second :

Il n'est pas tombé dans le piège et le match s'est soldé par un match nul.

Matchs contre un joueur aléatoire

Si nous simuler un grand nombre de matchs contre un joueur aléatoire, voici ce que l'on obtient :

Sur 1000 matchs (l'agent a joué le premier dans la moitié des matchs), l'agent a gagné 950 matchs, n'a perdu personne et il y a eu 50 matchs nuls. Ce n’est pas une preuve que notre agent joue de manière optimale, mais il a certainement atteint un niveau de jeu correct.

En guise de suivi à Former un agent à maîtriser un jeu simple grâce au jeu autonome là où le jeu était facile à cracker et où l'espace d'état était petit, nous avons utilisé la même technique pour maîtriser le tic-tac-toe. Bien qu'il s'agisse encore d'un problème de jouet, l'espace d'état du tic-tac-toe est suffisamment grand pour que le réseau neuronal de régression de l'agent soit nécessaire pour trouver des modèles dans les tenseurs d'état. Ces modèles permettent la généralisation de tenseurs d’état invisibles.

Le code est disponible dans ce dépôt. Essayez-le et dites-moi ce que vous en pensez !