Aujourd'hui, l'une des branches phare du développement de l'Intelligence Artificielle est celle de l'apprentissage par renforcement. Cette technique est capable d'apprendre à un programme n'ayant aucune connaissance préalable à évoluer dans un environnement, à en comprendre les règles, à y prendre des décisions et s'adapter en fonction de récompenses/punitions liées à cet environnement.
Ces dernières années, de nombreux exploits ont été réalisés grâce à cette méthode. C'est notamment dans le domaine des jeux que nous en avons entendue parler. Ainsi, c'est grâce à l'apprentissage par renforcement que DeepMind a battu Lee Sedol au jeu de Go en 2016 avec son programme AlphaGo. Depuis, d'autres exploits ont eu lieu sur d'autres jeux tels que Starcraft, Dota, Atari, et bien d'autres...
Par curiosité personnelle, j'ai souhaité découvrir un peu mieux ce monde de l'apprentissage par renforcement. Ainsi, j'ai travaillé sur un premier projet dont le but était de développer une variante du jeu Santorini (un jeu de plateau) et d'y entrainer un agent. Le code associé à ce projet est open-source et disponible sur ce dépôt github.
Comme énoncé précédemment, l'apprentissage par renforcement utilise les récompenses et les punitions que son environement lui donne pour évoluer. Son but étant de prendre des décisions qui vont maximiser les récompenses et minimiser les punitions obtenues. Pour ce faire, l'agent doit parcourir l'ensemble des différentes situations et mémoriser les récompenses ou les punitions pour chacune des décisions qu'il peut prendre. De cette manière, il peut s'arranger pour réaliser la meilleure d'entres elles dans chacune des situations qu'il rencontre, et ainsi créer sa politique optimale.
Le fait est que dans certains environnement, le nombre de situations différentes est tellement élevé qu'il est techniquement impossible de toutes les parcourir et donc, de connaître pour chacune d'entre elle la meilleure décision à prendre - c'est entre autre le cas du jeu de Go où l'on dénombre pas moins de 10^172 différentes situations (c'est à dire un 1 avec 172 zéro derrière) pour une grille 19x19.
Pour créer sa politique optimale, l'agent doit alors utiliser une fonction capable de généraliser les situations et de deviner, pour chacune des situations possibles (y compris celles qu'il n'a encore jamais rencontrées), la récompense ou la punition qu'il obtiendra pour chacune des décisions qu'il peut prendre. Souvent, nous utilisons alors un réseau de neurones artificiels dont la tâche sera de modéliser cette fonction, et que nous entraineront en le faisant explorer le plus de situations possibles dans son environnement.
Santorini sur plateau
Santorini est un jeu de plateau tour par tour et multijoueur dont le but est d'être le premier joueur à atteindre le 3ème étage.
A tour de rôle, chaque joueur a deux actions à effectuer : un déplacement d'une case, puis la construction d'un étage sur une case adjaçante à sa position. Un joueur ne peut se déplacer ou construire sur une case occupée par un autre joueur, ou de hauteur 4 (ayant un dôme). Si un joueur ne peut pas effectuer l'une de ces deux actions, il perd la partie.
Kothrak-v1 est une version 1 joueur de Santorini et sert de Proof Of Concept pour le développement d'une version 2 joueurs que vous pouvez voir ici : Kothrak-v2.
Cette version 1 joueur est donc minimaliste : le joueur gagne lorsqu'il atteint le troisième étage. Il ne peut pas construire au delà du 3ème niveau et ainsi ne peut jamais sceller une case jusqu'à la fin de la partie. De plus, à la différence du vrai Santorini, le jeu se déroule sur une grille hexagonale au lieu d'un classique quadrillage.
L'ensemble de cette première version a été entièrement développée en Python et utilise PyQt5 pour son interface graphique.
Interface d'entrainement
La tâche que l'agent doit réaliser (construire et atteindre le 3ème étage) semble être assez simple dans sa version 1 joueur. Au bout de 80 parties seulement, l'agent est déjà en mesure d'atteindre le 3ème étage et a trouvé la politique permettant d'y arriver avec le moins de coups possibles (alterner déplacement et construction entre deux cases).
La vidéo ci-dessous nous montre la configuration de l'agent ainsi que son entrainement en vitesse réelle (attention, c'est rapide !).
Entrainement d'un agent
Deux systèmes de représentation du jeu ont été implémentés pour ce projet : l'un dit relatif, l'autre dit absolu.
Nous pouvons observer que ces deux systèmes d'état permettent à une IA un joueur de converger, mais nous pouvons constater quelques différences : le système d'état absolu converge en trouvant un endroit spécifique dans la map (un couple de deux cellules) où il arrive à atteindre le troisième niveau, et essaie alors systématiquement de rejoindre cet endroit pour gagner la partie. Alors que le système d'état relatif est en mesure de trouver la victoire sur plusieurs couples de cellules différents, mais conservera la même relation adjaçante (le couple de cellule qu'il utilisera sera toujours agencer pareil : deux cellules en diagonales, ou deux cellules horizontales par exemple).
J'ai travaillé sur une seconde version de ce projet, dont vous pouvez trouver l'article ici : Kothrak-v2. Pour cette seconde version, nous nous intéressons toujours à entrainer des agents sur le jeu Santorini, mais cette fois-ci dans un mode 2 joueurs et sur une autre interface graphique, en 3D.