Découvrir l'intelligence artificielle à partir d'un jeu publié le 31/03/2022  - mis à jour le 16/06/2022

TraAM 2021 - 2022

Sommaire des TraAms "Intelligence Artificielle"

Cet article présente la première partie de l’expérimentation qui est suivie d’une seconde partie de programmation (voir Intelligence artificielle et programmation Python)

L’apprentissage automatique

L’apprentissage automatique est un champ d’étude de l’intelligence artificielle qui se fonde sur des approches mathématiques et statistiques pour donner aux ordinateurs la capacité d’« apprendre » à partir de données qui lui sont fournies ou qu’elle génère elle-même.
La qualité de l’apprentissage et l’efficacité de la démarche algorithmique sous-jacentes sont donc fortement dépendantes de la sélection et du traitement des données transmises à la machine.

Une possibilité de guider la machine dans l’environnement des données est de mettre en place un système de punition/récompense qui lui permette d’identifier et sélectionner les choix pertinents qui lui permettront d’élaborer la stratégie optimale répondant au problème.

Ce paradigme appartient au domaine de l’apprentissage par renforcement qui consiste à améliorer un algorithme par l’expérience en se basant sur une démarche par essais-erreurs.

Le jeu Hexapawn

Hexapawn a été inventé en 1962 par Martin Gardner, un écrivain américain de vulgarisation scientifique. C’est une sorte de jeu d’échecs miniature sur un damier de 9 cases avec 3 pions par joueur (d’où le nom « Hexapawn » qui signifie « six pions »).
Les règles du jeu peuvent être consultées en cliquant sur l’image ci-dessous. Vous pouvez aussi consulter la notice de jeu proposée par le palais de la découverte dans un article dédié à cette expérience.

Règles du jeu Hexapawn

Règles du jeu Hexapawn

Le but poursuivi par Gardner était de construire un jeu déterministe dont le nombre de parties différentes est suffisamment petit pour être représentable par un nombre limité d’états de jeux.
Ainsi, dans sa configuration originale, le jeu consiste à opposer un humain à une "machine" composée de 24 boîtes d’allumettes contenant des perles de couleur.

IA papier de Martin Gardner

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

Étiquettes des 24 états de jeux pour construire l'IA en papier (PDF de 61.9 ko)

Étiquettes des 24 états de jeux pour construire l’IA en papier

Chaque boîte correspond à l’une des situations du plateau de jeu et les couleurs aux différents coups que la machine peut réaliser dans cette situation.
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.

Le jeu étant résolu, c’est-à-dire qu’il existe une stratégie gagnante pour les pions noirs gérés par la machine, l’algorithme converge vers cette stratégie gagnante au bout d’une dizaine de défaites de la machine.

 Page suivante : "Fiche synoptique" ; "Narration d’expérience"

Fiche synoptique

Thématique

Apprentissage automatique : découvrir l’apprentissage par renforcement

Niveau concerné

Seconde

Problématique

Popularisée par les matchs Deep Blue contre Kasparov à l’aube du 21ème siècle, la rivalité entre machine et être humain dans le domaine des jeux a toujours alimenté les fantasmes de notre inconscient collectif.
Depuis quelques années, les intelligences artificielles surpassent l’être humain lors de confrontations sur des jeux de stratégies comme les échecs ou le jeu de go et les récents progrès, utilisant en particulier les réseaux neuronaux et l’apprentissage profond, interrogent sur les modèles qui ont permis ces avancées remarquables.
Plus modestement, dans un contexte pédagogique de classe, il peut paraître pertinent de se poser la question suivante :

Comment une machine peut-elle apprendre à gagner contre un humain ?

Contenu

  • statistiques, probabilités
  • représentations graphiques : arbres, schémas
  • utilisation de la calculatrice et du tableur

Nombre d’heures utilisées

Environ 6 heures

Outils et ressources

 Page suivante : "Narration de l’expérimentation : approche statistique"

Narration de l’expérimentation

Présentation du jeu, approche statistique

La première séance (deux heures) avait pour but de découvrir le jeu et s’approprier les règles. Lancé à la veille des vacances de Noël, cette intermède ludique a été bien accueilli par les élèves.

Fiche de présentation du jeu, approche statistique (PDF de 93.5 ko)

Fiche de présentation du jeu, approche statistique

Toutefois, après les avoir laissé jouer pendant une vingtaine de minutes, je les ai interrogé sur l’équitabilité du jeu : est-ce un avantage pour les blancs de commencer ? Y a-t-il une stratégie gagnante pour une des couleurs ? Aucune de ces questions n’a trouvé de réponse et, faute de recul nécessaire sur le jeu, les élèves n’ont pas osé s’engager dans une quelconque forme d’argumentation.

Je leur ai alors proposé de jouer de manière aléatoire en enregistrant les parties et les victoires afin de constituer un échantillon statistique dont on pourrait déterminer la fréquence de victoire de chaque couleur, ce qui pourrait donner une tendance.

Par équipe de trois (deux joueurs et un secrétaire), ils ont donc réalisé une série de parties en choisissant les coups de manière aléatoire : dans la plupart des situations, les choix à faire se situaient parmi deux, trois ou quatre possibilités, qu’ils ordonnaient mentalement de la colonne de gauche vers celle de droite, le coup le plus à gauche étant numéroté 1. Ils utilisaient ensuite la fonction de tirage aléatoire de la calculatrice pour leur donner un numéro de coup.

Hexapawn : parties aléatoires

Hexapawn : parties aléatoires

Cette consigne, qui demandait rigueur et organisation, n’a été pleinement respectée que par une moitié d’équipes. Malgré ces quelques turpitudes, environ 80 parties ont pu être relevées et déposées dans un formulaire en ligne qui a permis de déterminer rapidement la fréquence de victoires de chaque couleur : la commande tableur NB.SI(), très utile en statistiques, a ainsi pu être introduite et présentée en classe entière.

La teneur du résultat (environ 62% de victoires pour les blancs et 38% de noirs) a quelque peu surpris les élèves qui s’attendaient à un ratio plus équilibré. Toutefois, certains ont avancé que l’échantillon n’était pas très gros et que la fréquence aurait pu être différente. La fluctuation d’échantillonnage a alors pu être évoquée, mise en débat et je me suis bien gardé d’apporter une réponse définitive.

 Page suivante : "Narration de l’expérimentation : approche probabiliste"

Arbre de jeu, approche probabiliste

Quelques semaines après cette introduction, lors d’une séance de deux heures, je suis revenu sur le jeu et j’ai sollicité leurs souvenirs pour reconstituer les règles du jeu. Abordant le problème de manière plus structurelle, je leur ai demandé au préalable combien de parties différentes il était possible de jouer. Les réponses ont été assez surprenantes : 3 , 6 (par rapport au nombre de pions), 5 (?), une infinité.

Nous avons ensuite construit ensemble les états de jeux des deux premiers tours : 3 possibilités pour les blancs au premier tour puis, pour chacune de ces possibilités, entre deux et quatre possibilités pour les noirs. Les élèves ont vite perçu la croissance "exponentielle" de l’arborescence : 3 états pour le premier tour, 10 états pour le deuxième, l’infinitude de l’arbre de jeu est dès lors apparue plus probable pour bon nombre d’élèves.

Je leur ai alors présenté la notion d’arbre de jeu qui permettait de dénombrer de manière rigoureuse le nombre de parties différentes, en insistant sur la représentation en arborescence, fondamentale en probabilités.

Arbre de jeu complet avant tronçonnage

Arbre de jeu complet avant tronçonnage

La classe s’est alors constituée en 10 groupes de trois à quatre élèves et chaque groupe a reçu un tronçon de l’arbre de jeu, les tronçons étant déterminés par les dix états de jeu dénombrés à l’issue du deuxième tour. Il était alors demandé à chaque groupe de relever le nombre de parties contenues dans son tronçon ainsi que les victoires de chaque couleur puis de venir l’écrire au tableau.

En quelques minutes, les valeurs demandées ont été écrites au tableau et les élèves ont spontanément remarqué la symétrie des effectifs selon un axe vertical. J’ai appuyé cette remarque en leur faisant aussi voir la symétrie des parties sur les états de jeux, avec un simple échange des colonnes A et C. La remarque sur la symétrie a été notée au tableau pour souligner l’importance de cette information dans la structure du jeu.

Dénombrement des parties

Dénombrement des parties

Collectivement, nous avons rapidement trouvé le nombre total de parties (134) ainsi que le nombre de victoires : 64/134 (48%) pour les blancs et 70/134 pour les noirs (52%), ce qui allait à l’encontre de la fréquence de l’échantillon statistique obtenu lors de la première séance. Comment expliquer une telle différence ? Aucun élève n’a osé proposé une explication et j’ai dû insister sur la notion de choix et commencer à mettre des "poids" sur les branches de l’arbre pour que les élèves suggèrent le mot "probabilités" comme mesure de la chance de réalisation d’une partie plutôt qu’une autre.
La détermination des probabilités d’un tour à l’autre n’a pas posé de problème mais la recherche de la probabilité d’une branche complète a donné lieu à des raisonnements erronés : le principe additif a été évoqué par une majorité d’entre eux et il a fallu faire le calcul de plusieurs branches pour montrer l’inexactitude du raisonnement.

Ayant déjà introduit la notion d’arbre de proportion pour les proportions échelonnées, j’ai invoqué leurs récents souvenirs du chapitre sur l’information chiffrée et leur ai proposé de considérer chaque branche comme une proportion échelonnée. Avec cette approche, le principe multiplicatif a été mis en évidence et a permis de valider les calculs des probabilités jusqu’au deuxième tour.

Afin de lever le dilemme sur l’équitabilité du jeu, je leur ai demandé de calculer la probabilité de chaque partie apparaissant dans leur tronçon et d’additionner les probabilités de chaque couleur.
Cette consigne demandait de la rigueur et sollicitait leur capacité à exploiter une représentation graphique en arbre afin de réaliser les produits des probabilités rencontrées le long de chaque branche, ces produits étant constitués de 3 à 7 facteurs. Par ailleurs, les groupes n’avaient pas la même charge de travail car le nombre de parties variait fortement d’un tronçon à l’autre (de 7 à 26 parties). Toutefois, les plus malins ont pu remarquer que certaines parties voisines avaient les mêmes probabilités, ce qui limitait les calculs.
Je passais dans les groupes afin de les aider dans leurs démarches de lecture et d’annotation de l’arbre et vérifier la validité des premiers calculs.
Comme pour le nombre de parties, les groupes les plus rapides ont marqué leurs résultats au tableau et j’ai complété les groupes manquants, en m’appuyant une nouvelle fois sur la symétrie des probabilités.

Calcul des probabilités de victoire de chaque couleur

Calcul des probabilités de victoire de chaque couleur

À la fin, la probabilité théorique de victoire de chaque couleur a pu être établie : 259/432 pour les blancs (≈ 60%) et 173/432 pour les noirs (≈ 40%). Nous avons pu constater la conformité de ce résultat avec les fréquences de l’échantillon.

Dès lors, la modélisation probabiliste nous a amené à la conclusion de l’avantage théorique des blancs, lors d’un jeu aléatoire, sans pour autant statuer sur la question initiale de l’existence d’une stratégie gagnante.

 Page suivante : "Fiche synoptique" ; "Narration d’expérience : vers l’apprentissage machine"

Vers l’apprentissage machine : jouer contre le tableur

Dans l’article initial de Martin Gardner, la mise en évidence de l’apprentissage par renforcement demandait la construction de l’IA de papier avec les boites de perles. Après avoir construit personnellement cette IA en papier et l’avoir testée, je ne l’ai pas présentée aux élèves car je ne voyais pas comment faire utiliser une seule IA par 33 élèves.

J’ai donc cherché à représenter cette IA sous forme d’un fichier informatique, en listant les 134 parties différentes dans une feuille de calcul de tableur.
Les élèves ayant déjà travaillé (avec moi) l’utilisation des filtres du tableur en SNT, l’idée de filtrer progressivement les parties est apparue comme un moyen de reproduire le fonctionnement de l’IA papier dont le principe de base repose sur la mémorisation de chaque partie et l’élimination des parties perdantes pour l’IA.

La troisième séance s’est donc déroulée en salle informatique la semaine suivant celles sur l’arbre de jeu. Ma présentation de la séance s’est focalisée sur le jeu entre un être humain et une machine. Les élèves, en demi-classe, se sont constitués en groupes, avec attribution d’un rôle à chaque membre :

  • un joueur "humain" qui fera jouer les blancs : celui-ci joue normalement et cherche à battre les noirs ;
  • un joueur "machine" qui fera jouer les noirs : celui-ci ne réfléchit pas et réalise des coups en fonction de ce que lui propose la machine : lorsque plusieurs coups sont proposés, il prend un mouvement au hasard parmi les lignes disponibles.
  • un secrétaire qui consignera les coups joués, les victoires et les défaites, ainsi que les numéros des parties éliminées.

Le déroulement du jeu était le suivant :

  • Le joueur humain (les blancs) commence ;
  • Le joueur machine filtre la colonne B avec le mouvement effectué par les blancs puis choisit au hasard un des mouvements proposés par le filtre de la colonne C ;
  • Le joueur humain rejoue et le joueur machine filtre la colonne D avec le mouvement effectué par les blancs et choisit au hasard un des mouvements proposés par le filtre de la colonne E.
  • Le jeu se poursuit ainsi jusqu’à la victoire de l’une des deux couleurs :
    • Si le joueur machine gagne, le secrétaire note la victoire des noirs mais la machine n’enregistre rien de particulier ;
    • Si le joueur machine perd, il sélectionne les lignes filtrées jusqu’au dernier mouvement noir et il les colorie en gris.
    • Il grise aussi les lignes filtrées par la partie symétrique
  • Le joueur machine réinitialise le filtre avant de recommencer une nouvelle partie.

Les élèves ont donc "joué" en suivant ce protocole et, au bout d’une dizaine de parties, selon le nombre de défaites de la machine qu’ils avaient obtenues, ils avaient grisé entre 10 et 20 lignes. Ils ont bien pris conscience que c’était une situation de défaite qui renvoyait une information significative à la machine tandis qu’une victoire ne modifiait pas l’état de la feuille de calcul. Les équipes qui avaient atteint 5 ou 6 défaites de la machine ont bien mesuré la difficulté pour le joueur humain de gagner de nouveau.

Hexapawn : humain contre machine

Hexapawn : humain contre machine

Une mise en commun des parties perdantes a permis de mettre en évidence des parties plus "impactantes" que d’autres pour l’élagage de l’arbre de jeu.
Je leur ai aussi fait remarquer que l’élagage était parfois grossier car il grisait des pans complets de l’arbre de jeu dans lesquels figuraient des parties menant à la victoire de la machine et qu’il laissait des parties menant à la victoire des blancs.
À force de questionnement, j’ai réussi à leur faire dire que, par le biais du marquage des parties perdantes, la machine apprenait de ses erreurs et qu’elle mémorisait les coups menant à une défaite afin de ne pas les reproduire.
C’est à ce moment là que les élèves ont commencé à évoquer la notion d’intelligence artificielle.
Les parties perdantes les plus fréquentes ont été retenues afin de griser un arbre de jeu de synthèse qui serait testé par les élèves lors de la séance suivante.

Fichier tableur de l'arbre de jeu élagué (OpenDocument Spreadsheet de 25.6 ko)

Fichier tableur de l’arbre de jeu élagué

Lors du cours de mathématiques qui a suivi cette séance, j’ai repris le cheminement fait depuis le mois de décembre et nous avons fait la synthèse de ce qui avait été vu. Afin de les convaincre de l’efficacité du processus, j’ai proposé à des élèves d’aller faire quelques parties contre la machine pendant le cours, celle-ci ayant été munie de l’arbre de synthèse construit auparavant.
Celui-ci comportait encore des parties gagnantes pour les humains mais la probabilité d’y parvenir était assez faible et sur la quinzaine de parties réalisées, seulement 4 ont abouti à une victoire des blancs.
La démonstration a paru convaincre les élèves et j’ai conclu l’expérimentation en nommant ce type d’apprentissage (par renforcement) et en abordant les domaines qui avaient recours à cette branche de l’intelligence artificielle.

La dernière partie de l’expérimentation consistera en la programmation sous Python de l’intelligence artificielle du jeu d’Hexapawn : (voir Intelligence artificielle et programmation Python).

 Page suivante : "Réussites, obstacles et limites"

Réussites, obstacles et limites

La série d’activités a été plutôt bien accueillie par les élèves qui se sont dans l’ensemble bien investis dans les tâches proposées. La principale difficulté a été de leur faire suivre les consignes et réaliser les manipulations car celles-ci exigeaient organisation et rigueur :

  • jouer au jeu de manière aléatoire et noter les coups réalisés ;
  • calculer les probabilités de chaque partie en suivant les probabilités le long des branches ;
  • élaguer l’arbre de jeu en grisant les parties perdantes ainsi que leurs symétriques

Ces tâches sollicitaient des compétences transversales liées à la démarche scientifique (s’approprier, réaliser, analyser) auxquelles se rajoutent des compétences plus spécifiques aux mathématiques (représenter, calculer, modéliser).
Elles ne s’inscrivaient pas dans un chapitre précis du programme mais ont permis de manipuler en situation concrète des éléments essentiels en information chiffrée, statistiques et probabilités :

  • fréquences, probabilités, lien entre le modèle et l’échantillon
  • structures arborescentes et principe multiplicatif
  • utilisation du tableur et de ses outils de filtre
  • initiation au dénombrement

Au fur et à mesure des activités, la représentation du jeu par les élèves a fortement varié : initialement, une majorité d’entre eux pensait que dans le cas d’une partie aléatoire, les blancs gagnaient plus souvent puisque c’étaient eux qui commençaient, ce qui a été confirmé par la fréquence de l’échantillon collectif.
Ensuite, les emmenant sur la considération du ratio brut des parties gagnantes pour chaque couleur (en faisant l’hypothèse erronée de l’équiprobabilité), leur conviction a paru ébranlée par la proportion favorable aux noirs.
Partant de cette contradiction, la pondération des parties s’est faite jour et le calcul collectif a redonné l’avantage aux blancs.
Dans la dernière phase, l’élagage de l’arbre de jeu a de nouveau perturbé les élèves dans leur représentation car les blancs gagnaient de moins en moins au fur et à mesure des parties. Il leur a donc fallu réajuster le modèle sous ces hypothèses.
Au-delà des considérations liées à l’intention initiale, cette série d’activités m’a donc semblé pertinente pour la formation des élèves au raisonnement scientifique.

Sur plusieurs pages
Document joint
un document Ressources de l'expérimentation (Zip de 8.1 Mo)

Cette archive contient l’intégralité des fichiers sources des documents (.tex, .py, .ipynb, .ods) utilisés pour la mise en œuvre de l’expérimentation

 Plan du site
 Contact
 Accessibilité
 Mentions légales
 Traitement des données