Quand une machine apprend à jouer au jeu de Nim
Les
documents disponibles sur cette page ainsi que le contenu de la page
sont mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International 
Notions abordées :
Cette activité a pour but de présenter l'intelligence artificielle, plus particulièrement une forme simple d'apprentissage, et de montrer qu'en effectuant des actions élémentaires notre machine peut réussir à trouver la stratégie gagnante à un jeu.
Public :
Cette activité a été testée sur des enfants à partir de la fin de l'écolée élémentaire (CM1, 9 ans). Elle peut très bien convenir à des publics plus agés (secondaire ou adultes) sans faire "bébé".
Matériel :
- 8 allumettes ou autres petits objets (stylos,...)
- autant de gobelets/récipients que d'allumettes
- des petits jetons sur lesquels on peut écrire (en bois, en carton...), 3 par verre
Pour préparer l'activité on va numéroter les verres avec les nombres de 1 à 8 (en l'écrivant au marqueur), et faire trois jetons par verre, numérotés 1, 2 et 3. Puis comme ça n'a pas de sens de piocher plus d'allumettes qu'il n'y en a sur la table, on ne laisse que le jeton 1 dans le verre 1, et que les jetons 1 et 2 dans le verre 2.
Principe :
Les explications du jeu de Nim sont données plus en détails sur la page de l'activité "sans IA". S'y référer en cas de question. Le principe du jeu est de faire s'affronter deux joueurs qui prendront chacun leur tour une, deux ou trois allumettes. Celui ou celle qui prend la (ou les) dernière allumette a gagné.
Pour la version du jeu de Nim avec apprentissage, l'idée est de casser les idées préconçues sur un ordinateur doué d'intelligence. On verra qu'avec un algorithme simple et sans connaissance particulière sur la straétégie gagnante, on obtient une solution surprenante, où la machine devient infaillible à ce jeu.
Je propose de suivre le déroulé suivant :
- Mettre en place la matériel (jetons dans les gobelets, allumettes sur la table)
- Commencer une partie en laissant l'humain jouer en
premier. La machine quand c'est son tour va :
- compter le nombre d'allumettes et prendre le gobelet correspondant
- piocher au hasard un jeton dans le gobelet, le poser sur la table juste devant ce gobelet, et piocher le nombre d'allumettes indiqué par le jeton (1, 2 ou 3 donc)
- en fin de partie (quand il n'y a plus d'allumettes) soit la machine a gagné, et dans ce cas elle remet chaque jeton dans le gobelet où elle l'a pioché, soit elle a perdu et dans ce cas elle remet tous les jetons piochés sauf le dernier, qui était clairement un mauvais choix (puisqu'il a permis à l'humain de gagner directement) et qu'elle met de côté.
- On continue à faire des parties, et à un moment il peut arriver qu'un gobelet soit vide (parce que par exemple avec 4 allumettes il n'y a pas de bon choix). Dans ce cas on retourne le gobelet à l'envers, et à partir de ce moment là, si l'adversaire nous laisse avec un nombre d'allumettes pour lequel le gobelet est vide, la machine abandonne la partie, décide qu'elle a perdu (car elle sait qu'elle va perdre) et applique son algorithme de partie perdue (remettre tous les jetons piochés dans leur gobelet sauf le dernier).
- La machine va être assez mauvaise au début, mais au fil des parties elle va s'améliorer et finir par suivre une stratégie qui la fera gagner à tous les coups. Et tout ça en suivant un algorithme très simple.
Extensions :
La plupart des extensions ci-dessous est décrite plus en détails dans le document décrivant l'activité qui est disponible dans la section Liens ci-dessous.- On peut s'amuser à faire jouer deux machines l'une contre l'autre. Ainsi à chaque partie l'une des deux va perdre et apprendre quelque chose. On peut décider de toujours faire commencer la même machine, ou les faire alterner. Attention, au bout d'un certain nombre de parties l'une des deux machines va avoir une stratégie gagnante (celle qui commence ou celle qui joue en deuxième selon votre nombre d'allumettes) et l'autre va abandonner la partie systématiquement.
- Vous pouvez faire varier le nombre d'allumettes et donc de gobelets.
- Voir dans le document d'explications pour une version différente où l'on ne supprime pas les mauvais choix mais on augmente les chances de faire les bons choix en rajoutant des jetons en cas de victoire (il faut alors plein de jetons).
- On peut proposer un match humain machine avant de commencer, et dire qu'on fait 25 parties et si l'humain en gagne plus de la moitié on lui offre un cadeau. En fait il n'y a pas de risque, avec 8 allumettes la machine va perdre au plus 12 fois (et enlever 12 jetons) : le jeton 1 dans le verre 2, les jetons 1 et 2 dans le verre 3, les 3 jetons du verre 4, et deux jetons dans les verres 5, 6 et 7 (on n'enlève rien dans le verre 8 car comme l'humain commence il n'y a jamais 8 jetons quand c'est le tour de la machine).
Liens :
- Une vidéo de l'activité filmée en situation lors du concours Jeux Fabrique en 2019 est accessible ici (de 1:00 à 21:30).
- Ma page de l'activité sur le jeu de Nim (sans la partie IA) est par ici.
- Le document pdf décrivant l'activité plus en détails est par là.
- Éric Duchêne et Aline Parreau ont également documenté leur version de l'activité, qui est maintenant réalisée sur une machine en bois. L'apprentissage est légèrement différent, et on y voit aussi des variantes de règles inédites en suivant ce lien.
- Florent Madelaine et Malika More ont coécrit un article dans Tangente Education accessible gratuitement sur une version légèrement différente de cette activité.
- Dans le même genre une activité d'apprentissage autour du jeu d'Hexapawn est disponible sur cette page
- Vous pouvez trouver sur le site Computer Science for Fun le descriptif d'une activité basée sur le jeu Hexapawn ci-dessus.
Photos :