La machine qui apprend à (bien) jouer toute seule
Par Eric Duchêne et Aline Parreau
Objectif
L’objectif est de présenter l’un des mécanisme d’intelligence artificielle appelé apprentissage par renforcement. En utilisant comme exemple le jeu des bâtonnets de Fort Boyard, nous illustrons comment une machine peut apprendre toute seule à bien jouer à ce jeu, en utilisant simplement le hasard. La machine que nous présentons est une machine «physique» en bois, manipulable par le public pour mieux en comprendre son fonctionnement. Sa transposition sur ordinateur ne pose pas de problème.
Historique
Cette machine est dérivée de la machine « Menace » créée par Donald Michie pour jouer au Morpion (chercheur britannique en Intelligence Artificelle). Lisa Rougetet, dans son article paru sur Images Des Maths, détaille l’histoire de cette machine considérée comme précurseur dans le domaine du machine learning.
Le jeu des bâtonnets
Rappelons tout d’abord les règles du jeu des bâtonnets : on considère une rangée de 8 bâtonnets. Deux joueurs, à tour de rôle, retirent un ou deux bâtonnets. Le joueur qui prend le dernier bâtonnet gagne la partie.
A quoi ressemble la machine ?
Il s’agit d’une boîte composée de 8 casiers. Chaque casier correspond à une position du jeu des batonnets : le casier 8 correspond à la position de départ avec 8 bâtonnets, le casier 7 à la position de jeu avec 7 batonnets etc…
Chaque casier contient des boules de couleur jaunes et rouges. Initialement, on initialise la machine avec autant de boules de chaque couleur (4 sur l'exemple ci-dessous).
Le contenu des casiers est caché pendant la partie.
Comment faire jouer la machine contre un humain ?
Il faut une personne qui joue pour la machine, et une autre qui joue le rôle de l’humain. On considère que la machine joue en premier, car dans la position de départ avec 8 batonnets, on sait qu’il existe une stratégie gagnante. Quand c’est à son tour de jouer, la machine regarde dans quelle position de jeu elle se trouve (en comptant le nombre de bâtonnets restant), sélectionne le casier correspondant, et tire au sort une boule dans le casier. Selon la couleur de la boule, elle retire 1 (si c’est jaune) ou 2 (si c’est rouge) bâtonnets. Toutes les boules tirées au sort par la machine sont posées sur le présentoir devant les casiers. Le joueur humain joue ensuite son coup, puis la machine recommence et ainsi de suite jusqu’à la fin de partie.
Fin de la partie
On regarde qui a gagné.
- Si c’est la machine : pour chaque boule tirée au sort par la machine, on la remet dans son casier et on rajoute 1 autre boule de la même couleur. Ainsi, à la partie suivante, ce coup aura une probabilité plus forte d’être joué. On dit qu'on le "renforce".
- Si c’est l’humain : chaque boule jouée est écartée, de sorte à diminuer la probabilité de rejouer ces coups à la prochaine partie. Ils sont donc pénalisés.
Apprentissage
On enchaine des parties. Lorsqu’un casier se vide, on le recharge comme au début.
La machine jouant vraiment au hasard au début, elle va perdre souvent. Plus le nombre de parties est grand, meilleur sera l’apprentissage de la machine.
Pour ce jeu, on sait que les positions perdantes sont les multiples de 3, et que depuis une position gagnante (non multiple de 3 donc), le coup gagnant consiste à se ramener à une position multiple de 3. Ainsi, la stratégie gagnante vers laquelle la machine devrait converger ressemble à ça :
Paramétrage de la machine
Il y a plusieurs facteurs qui rendent l’apprentissage de la machine plus ou moins rapide :
- Le niveau de l’humain qui joue
- Le nombres de boules dans les casiers au départ
- Le nombre de boules qu’on rajoute/enlève quand la machine gagne/perd
Il est intéressant de travailler sur les différences de convergence quand l’humain connait ou pas la stratégie gagnante.
Jeu contre elle-même
Une façon de faire converger la machine plus vite, et aussi d’expliquer comment les meilleurs programmes informatiques (type Alpha Go Zero) fonctionnent, est de faire jouer la machine contre elle-même. La machine joue donc tous les coups et aucune connaissance experte n’est requise. On utilise deux présentoirs, selon les boules tirées par la machine en tant que 1er ou 2eme joueur. A la fin de la partie, on renforce à la fois les casiers du gagnant et on pénalise les casiers du perdant.
La machine à la MMI
Cette machine est en accès libre dans l’exposition hasard présente à la MMI (Maison des Maths et de l’Informatique) pour la saison 2018-2019. Elle a été réalisée par Pierre Gallais.
Une application Java
Une application a été développée en parallèle et téléchargeable ici, afin de modifier les paramètres de la machine, les règles du jeu, et le nombre de bâtonnets au départ. Elle permet de constater la convergence et l’émergence d’une stratégie gagnante. Cela est très utile si on change les règles de jeu (càd si on modifie le nombre de batonnets que l’on a le droit de prendre). Contrairement au jeu de Fort Boyard, la stratégie gagnante n’est pas forcément connue en amont et elle va émerger en faisant rapidement simuler beaucoup de parties à la machine. La vidéo ci-dessous propose une démo de cette application pour un jeu avec 16 bâtonnets, et où les joueurs ont le droit d'enlever 1, 3 ou 4 bâtonnets à chaque tour. Après une centaine de parties, on voit que la machine ne perd presque plus et a fait émerger une stratégie gagnante. Les casiers avec peu de billes sont ceux qui sont souvent pénalisés et qui correspondent aux postions de jeu à partir desquelles il vaut mieux ne pas commencer. Les casiers avec beaucoup de billes d'une même couleur sont ceux qui ont été beaucoup renforcés ; ils correspondent donc souvent à des positions de jeu à partir desquelles on gagne - la nature du coup gagnant correspond à la couleur de la bille majoritaire dans le casier.
Utilisation avec le grand public
Cette machine est utilisée lors de salons grand public, où les personnes qui se succèdent renforcent l’apprentissage de la machine. On note les victoires et les défaites de la machine au fur et à mesure des participants. Un médiateur est là pour donner du sens à ce qui se passe.
Utilisation avec les scolaires
Plusieurs ateliers ont été proposés par des collègues pour proposer cette activité en classe avec des gobelets au lieu de la machine, et en changeant certains des paramètres évoqués plus haut. Un bilan et des explications très claires ont été rédigées ici par Marie Duflot Kremer et là par Florent Madelaine et Malika More.
De notre côté, nous avons élaboré un atelier d’1h30 avec P. Esclafit et H. Novet (étudiants du M1 didactique des maths à Lyon et Montpellier). En attendant l’article détaillé (à venir), les grandes lignes en sont les suivantes :
- Comme pour d’autres ateliers décrits sur la page de Marie et l'article de Florent et Malika, on utilise des gobelets transparents avec des petites billes pour représenter la machine. Les élèves sont en groupe et chaque groupe entraîne sa propre machine.
- Le jeu principal que nous regardons est une variante où les joueurs peuvent enlever 1, 3 ou 4 bâtonnets. Ainsi, la stratégie gagnante est beaucoup moins facile à trouver, et les élèves n’ont pas d’a priori sur l’état de la machine dans son état de convergence. L’enjeu de bien l’entraîner est beaucoup plus important.
- On organise un tournoi de machines entre les groupes une fois qu’ils les ont suffisamment entrainées.
- En plus des gobelets, l’utilisation de la grosse machine est très utile en support pour faire comprendre comment ça marche.
- Dans les explications, on utilise l’application Java pour simuler la convergence beaucoup plus rapidement et discuter avec les élèves du résultat obtenu.
