Intelligence artificielle et programmation Python publié le 12/04/2022  - mis à jour le 16/06/2022

Joueur aléatoire contre une IA

Historiquement, le jeu d’Hexapawn avait été créé par Martin Gardner pour simuler une intelligence artificielle en papier, composée de 24 boîtes d’allumettes contenant des perles de couleur.

IA papier de Martin Gardner avec les 24 boîtes d’allumettes.

Chaque boîte correspond à l’une des situations du plateau de jeu (ou son symétrique) et les couleurs aux différents coups que la machine peut réaliser dans cette situation.

Dans sa configuration initiale (celle que nous avons modélisée dans le tableur), lorsque c’est au tour de la machine de jouer, elle tire une perle au hasard dans la boîte correspondant à la situation et qui lui indique le coup qu’elle doit jouer. Cette perle est mise de côté et, à la fin de la partie, la règle est la suivante :

• si la machine a gagné, toutes les perles sont remises dans leurs boîtes ;
• si elle a perdu, la perle qui l’a fait perdre est éliminée et le coup associé ne peut plus être joué

En multipliant les parties, le retrait progressif des perles perdantes va permettre à la machine d’apprendre les bons coups en élaguant l’arbre de jeu pour ne conserver que les branches gagnantes.

Cette méthode d’apprentissage se base sur un système de punition : si l’IA perd, elle est punie (confiscation de perles) de façon à ce qu’elle ne reproduise plus l’erreur qu’elle a commise pour perdre. À force elle ne commet plus d’erreur.

Mais on peut aussi envisager de procéder par récompense. Lorsque que l’IA gagne, on rajoute une ou plusieurs perles de la couleur du coup gagnant dans la dernière boîte (on aurait aussi pu rajouter des perles dans les autres boîtes sélectionnées lors de la partie). Ainsi, l’IA a plus de chance de reproduire ce coup gagnant plus tard car la probabilité de tomber sur cette perle gagnante est augmentée.

Dans cette partie les élèves ont lu avec moi le code de la fonction sequence_alea_vs_ia, afin de saisir comment les récompenses et punitions étaient gérées d’un point de vue informatique.

Cette fonction prend en paramètre un nombre de parties et dispose de deux paramètres optionnels permettant la gestion de l’apprentissage : punition, réglée initialement à True et recompense, réglée initialement à False, afin d’être en accord avec le modèle original.

Ensuite, ils on fait des appels de cette fonction et de la fonction graphique pour mesurer l’effet de la méthode d’apprentissage sur la courbe des victoires :

• punition = False et recompense = False : on retrouve la partie aléatoire à deux joueurs, il n’y a pas d’apprentissage et les victoires des blancs se cumulent :
  

  Courbe d’apprentissage en l’absence de retour informatif

• punition = False et recompense = True. Sur un nombre limité de parties, l’apprentissage n’est pas flagrant. En revanche, dès que le nombre de parties devient important, on note l’évolution des victoires des noirs :

Sans punition et avec récompense, petit nombre de parties

Sans punition et avec récompense, grand nombre de parties

• punition = True et recompense = False. C’est la situation de la machine de Gardner. On note un certain nombre de défaites (une dizaine), avant de voir des victoires quasiment systématiques :
  

  Avec punition et sans récompense : conditions de la machine de Gardner

• punition = True et recompense = True. Le cumul des deux systèmes n’est pas forcément beaucoup plus efficace, peut-être la machine gagne-t-elle plus vite et les défaites disparaissent complètement plus tôt mais ce n’est pas probant avec les paramètres choisis (j’avais choisi de rajouter trois fois le mouvement gagnant dans la dernière "boîte").
  

  Avec punition et avec récompense : combinaison des deux feedbacks.

D’un point de vue du déroulement en classe, cette séquence s’est bien déroulée et les élèves ont bien apprécié de faire varier les différents paramètres de la fonction afin d’en retirer les conclusions attendues.

Prolongement : recherche d’une stratégie gagnante

Cette partie n’a pas été faite en classe. Elle consiste à utiliser une dernière fonction listant les parties gagnantes pour la machine et à se servir des résultats renvoyés pour rédiger une stratégie gagnante au jeu d’Hexapawn qui est résolu pour les noirs.

L’utilisation de cette fonction, avec les différents paramètres de feedbacks, permet alors de faire émerger une trentaine de parties types qui illustrent les meilleurs choix de l’IA en fonction du choix des blancs à chaque tour.

Une rédaction de la stratégie gagnante est alors possible. Cette partie a été donnée en devoir à la maison aux élèves afin de conclure l’expérimentation.

Version pdf du notebook professeur (PDF de 1 Mo)

Intégralité des fonctions Python construites pour la programmation de l’IA

 Page suivante : "Réussites, freins et limites"