Il y a quelques semaines je termine un MOOC de Machine Learning en Python. Quand j’observe le bandeau final « Congratulations ! » qui apparait devant moi, je me dis que je ne peux pas en rester là. J’ai tout de suite eu envie d’appliquer mes connaissances fraîchement assimilées sur un cas ludique et simple, en l’occurrence le jeu du puissance 4 ! Cela me semblait un bon compromis entre le Morpion, jeu à combinatoire peu volumineuse où un algorithme frontal ferait l’affaire, et le jeu de Go sur lesquels les IA les plus performantes conçues aujourd’hui se cassent bien les dents. Le puissance 4 est un jeu où deux joueurs s’affrontent dans le but d’aligner 4 pions, horizontalement, verticalement ou en diagonale, dans une grille de 6 lignes et 7 colonnes. Dans cet article je présente deux méthodes de construction d’une IA capable d’affronter un humain lors d’une partie de puissance 4.

Pour clarifier nous appelons les deux joueurs qui se disputent la partie l’IA et l’Adversaire.

Première approche : l’algorithme MinMax

Cette méthode provient de la théorie des jeux et peut s’appliquer en théorie pour tous les jeux à deux joueurs à somme nulle, comme les échecs, le morpion, le puissance4, le jeu de Go… On retrouve celle-ci assez fréquemment en ce qui concerne l’état de l’art du sujet.

Cette méthode repose sur l’existence et la définition d’une fonction d’évaluation, qui pour tout état du jeu attribue un score, positif ou négatif, représentant quel joueur a l’avantage à ce stade du jeu. Lorsque la fonction renvoie un score positif [resp. négatif], c’est l’IA [resp. l’Adversaire] qui a l’avantage. Plus ce score est haut (positif ou négatif), plus l’avantage pour le joueur est considérable.

Le principe de l’algorithme MinMax (aussi appelé minimax) est, pour un état donné de la grille, de maximiser la valeur du jeu que l’on peut espérer avoir après « n » coups joués. Cela demande donc de prévoir les coups potentiels que peut jouer l’Adversaire. Pour cela on considère que celui-ci joue au mieux, i.e. qu’il sélectionne à chaque fois la colonne qui va maximiser en son sens la nouvelle valeur du jeu, i.e. qui va minimiser la fonction d’évaluation dans le sens de l’IA.

Pour cela l’algorithme effectue une recherche arborescente où la racine de l’arbre est l’état actuel du jeu et les feuilles sont tous les états possibles après « n » coups joués. On commence par évaluer le score de chacune des feuilles de l’arbre à l’aide de la fonction d’évaluation, puis on remonte ces scores au nœud parent en appliquant la règle suivante : si on se trouve sur un nœud « IA » [resp. « Adversaire »], la valeur du jeu de ce nœud sera le maximum [resp. minimum] de ses enfants. On procède ainsi en remontant jusqu’à la racine, ce qui permettra de déterminer la meilleure colonne à jouer. C’est cette alternance entre le choix du minimum et du maximum pendant la remontée de l’information qui donne son nom à l’algorithme.

Pour en savoir plus, contactez-nous
Nom
Prénom
Société
E-mail *
Téléphone
Votre message *

* Champs obligatoires

Le paramètre « n » est évidemment un facteur clé de la performance de l’algorithme. Plus celui-ci est grand, plus l’IA prévoira de coups d’avance, mais plus la combinatoire du problème augmentera de façon exponentielle. En pratique on dépasse rarement la valeur de n=7 car au-delà, l’IA prend trop de temps pour calculer son prochain coup et cela nuit au rythme du jeu.
Cette méthode a principalement deux avantages, elle ne demande aucun jeu de données ni aucun entrainement préalable pour pouvoir jouer. De plus les performances de l’IA sont plutôt bonnes pour un faible coup d’entrée. Le désavantage de cette méthode est que l’IA joue tout le temps de la même manière. Une fois que l’on a trouvé une manière de battre l’IA, on pourra reproduire cette victoire indéfiniment car elle n’apprendra jamais de ses erreurs (on peut alors introduire, afin que les parties soient moins monotone, une petite part d’aléatoire dans les décisions de l’IA). Le second désavantage de cette méthode est qu’elle nécessite l’existence d’une fonction d’évaluation du jeu. Il existe souvent plusieurs manières de définir celle-ci, et il est difficile d’estimer la qualité d’une telle fonction. Il arrive par exemple que la fonction d’évaluation estime qu’une configuration est neutre pour les deux joueurs alors que l’expérience montre manifestement qu’elle avantage l’un des deux.

Seconde approche : Q-learning

Le Q-learning fait partie du domaine de l’apprentissage par renforcement. A la différence de l’apprentissage supervisé, l’apprentissage par renforcement ne nécessite pas de jeu de données sur lequel s’entraîner en entrée. C’est l’algorithme lui-même qui va construire son jeu de données et apprendre de ses erreurs par la suite.

Le principe de cette méthode repose sur le calcul d’une table Q(s, a) qui pour un état « s » de la grille, donne le gain que le joueur peut espérer avoir lorsqu’il choisit l’action « a » . Ainsi lorsque c’est le tour de l’IA et que celle-ci se trouve dans l’état « s », elle se réfère à la table pour trouver l’action « a » (dans ce contexte, comprendre « la colonne ») qui maximise son espérance de gain Q(s, a).
Pour obtenir cette table, il faut dans un premier temps définir un système de pénalités / récompenses pour tous les états. Une solution simple est d’attribuer une récompense de 1 pour chaque état représentant une victoire de l’IA, une récompense de -1 pour chaque état représentant une victoire de l’Adversaire, et une récompense de 0 pour tous les autres états. A noter que d’autres distributions sont possibles.

Les éléments de la table Q(s, a) et les récompenses sont liés par une relation de récurrence, dite équation de Bellman. C’est en disputant des parties que cette table se construit petit à petit. Initialement, l’IA ne connait aucune stratégie, il est donc trivial de gagner contre elle. A chacune de ces défaites, les récompenses atteintes (-1 dans ce cas) vont se propager le long du chemin qui a été parcouru de l’état initial (grille vide) à l’état final (défaite de l’IA). Ainsi lorsque l’IA repassera par l’un de ces états, cela l’incitera à jouer différemment, car elle se souviendra que son action l’avait conduit à une défaite.

Pour jouer de manière optimale, l’IA doit toujours sélectionner l’action « a » qui maximise Q(s, a) lorsqu’elle se trouve dans l’état « s ». Mais comme initialement la table est très creuse, il est nécessaire de laisser l’IA explorer un peu librement son environnement. C’est pour cela que sur les premières parties nous laissons une grande part à l’exploration, et au fur et à mesure de l’entraînement l’IA explorera de moins en moins son environnement en laissant place à l’exploitation des résultats.

Deux paramètres jouent également un rôle majeur dans la construction de la table :

  • Le facteur d’actualisation permet de traduire le fait que les décisions futures ont moins d’importance. Autrement dit les premières décisions sont celles qui ont le plus de poids.
  • Le taux d’apprentissage : Lorsque l’on met à jour une valeur Q(s, a), il y a un compromis à faire entre son ancienne valeur et sa nouvelle. Il ne faut pas complètement oublier ce que l’IA a déjà appris, mais il faut également apprendre un peu de la partie qu’elle vient de jouer. C’est le rôle du taux d’apprentissage qui représente le poids dans cette moyenne.

Afin de « bien apprendre », il est essentiel que l’IA apprenne sur de « bonnes parties ». Si nous entraînons l’IA uniquement contre un adversaire qui joue systématiquement de manière aléatoire, celle-ci apprendrait trop de parties peu représentatives de la réalité, et notre IA se retrouverait bredouille face à un humain qui connait les règles du jeu. L’idéal serait que l’IA apprenne essentiellement sur des parties disputées contre des joueurs expérimentés, mais il peut être un peu fastidieux de réaliser autant de parties en guise d’entrainement. C’est pourquoi durant cette phase, on entraîne notre IA contre plusieurs adversaires :

  • Un adversaire virtuel qui joue selon la stratégie de l’algorithme MinMax en faisant varier la profondeur de recherche « n ».
  • Un adversaire virtuel qui joue de manière aléatoire (pour favoriser l’exploration des états).
  • Un adversaire réel : un humain expérimenté du puissance 4.
  • Elle-même : l’IA affronte un adversaire qui joue selon sa propre stratégie.

L’avantage de cette méthode est qu’elle ne nécessite aucun jeu de données pour s’entraîner. Le second avantage est qu’elle ne s’arrête jamais d’apprendre, chaque nouvelle partie disputée vient consolider la table de décisions pour aider l’IA dans ses décisions futures.

Le principal inconvénient est que cette méthode se prête mal aux problèmes à grande combinatoire. En l’occurrence pour le puissance 4, le nombre d’états possibles de la grille est gargantuesque. Et il est inconcevable de construire une table exhaustive qui donnerait la meilleure colonne à jouer pour chaque état de la grille, car une telle table ne tiendrait même pas sur un disque dur de 1TB. L’avantage du Puissance 4, c’est que certains états reviennent assez souvent lorsque deux joueurs s’affrontent (on préfère souvent commencer une partie en jouant au centre), et donc l’IA pourrait se contenter d’apprendre seulement à partir de ces parties, ce qui permettrait d’alléger le poids de la table.

Sur le principe cette méthode fonctionne très bien, mais dû à la combinatoire du problème, même si l’IA est bien entraînée sur des parties « corsées », il est possible de trouver un chemin « trivial » pour gagner tout simplement parce que l’IA ne s’est encore jamais retrouvée dans cette situation pendant l’entraînement. Ce qui rend discutable la performance de la méthode.

Une approche directement inspirée du Q-learning et qui pallierait au problème de la volumétrie de la table Q(s, a) est le Deep Q-learning. Le principe est relativement proche de celui du Q-learning si ce n’est qu’au lieu d’être calculée explicitement pour chaque état, la table Q(s, a) est ici approximée par un réseau de neurones. A partir d’un nouvel état donné celui-ci réalise une prédiction de la meilleure colonne à jouer basée sur ses premières observations.

Ma conclusion

Finalement j’ai découvert qu’un développeur n’a pas plus de facilité à entraîner une IA qu’un sélectionneur de Football en a pour entraîner l’Equipe de France. Je n’ose imaginer ce que peut représenter la construction d’une IA pour le jeu de Go quand je vois toutes les petites difficultés qu’on peut déjà rencontrer dans un cas simple (et pourtant pas tant que ça !) comme le jeu du Puissance 4. J’ai en tout cas trouvé l’expérience enrichissante et très intéressante. Je serais très curieux de publier mon IA en ligne pour qu’elle puisse apprendre de toutes les parties qu’elle disputerait avec les internautes chevronnés que vous êtes ! C’est décidé dès que je peux, je m’y remets !