Apprendre à jouer au jeu de Nim à un ordinateur avec scratch publié le 14/10/2022

Caractéristiques du scénario

Thématique

Programmer une machine pour qu’elle apprenne à jouer à un jeu. Ici, c’est le jeu de Nim.
Le jeu de Nim est cité dans les programmes d’enseignement dans le BOEN n° 31 du 30 juillet 2020 pour le thème E - Algorithmique et programmation page 136

Niveau concerné

Classe de Troisième

Problématique

L’apprentissage par la machine elle même à gagner à des jeux est très impressionnant et permet des prouesses comme celle d’être capable de battre les meilleurs joueurs humains au jeu de go. Ceci, grâce à une intelligence artificielle.
Méthode qui peut être réutilisée dans d’autres domaines.
Ce scénario, assez guidé, a pour objectif de faire vivre aux élèves les différentes étapes qui peuvent amener à une façon de programmer une machine pour qu’elle puisse apprendre à jouer à un jeu (un jeu beaucoup plus simple que les échecs ou le jeu de go) : le jeu de Nim.
On pourra garder en tête que :

Comment donc, rendre une machine "intelligente", lui faire apprendre, lui faire mémoriser.

Contenu

• Algorithmique et programmation. (séquences d’instructions, boucles, instructions conditionnelles, variables informatiques, liste, nombres aléatoires...)
• Écrire, mettre au point (tester, corriger) et exécuter un programme en réponse à un problème donné.
• Décompositions d’un problème en problèmes plus simples de difficulté croissante.
• Dans une moindre mesure : statistiques, arithmétique (les multiples), probabilités.

Nombre d’heures utilisées

• 1/2 h en salle classique
• 2h avec l’utilisation du logiciel scratch
• 1/2 h en salle classique

Pour un total d’environ 3 h en guidant suffisamment. Attention, on peut largement dépasser cette durée en laissant les élèves plus autonomes et en approfondissant l’étude du jeu de Nim.

Outils et ressources

• Le logiciel scratch.
• Le jeu de Nim : règle du jeu utilisée : On joue à deux. On part d’un nombre entier positif. Tour à tour les joueurs peuvent soustraire, 1 ou 2 ou 3 à ce nombre. Le joueur suivant fait la même chose avec le résultat et ainsi de suite. Le joueur qui gagne est celui qui atteint le premier zéro.

Exemple :

• On part de 8.
• Le joueur A décide de soustraire 2, le nouveau nombre est donc 8 - 2 = 6.
• Le joueur B décide de soustraire 3. le nouveau nombre est donc 6 - 3 = 3.
• Le joueur A soustrait 3 et gagne car 3 - 3 = 0.

Démarche de l’enseignant

L’idée est de faire arriver progressivement les élèves à un programme qui permet de faire apprendre à jouer au jeu de Nim à une machine afin de présenter une première approche de l’apprentissage machine aux élèves.
Au cours de ce scénario, on peut faire apparaitre des points communs et des différences entre le fonctionnement de notre cerveau et une machine.
Pour ce faire, les élèves, vont être amenés à utiliser différents programmes Scratch et les faire évoluer.

Déroulement du scénario

J’avais dit aux élèves en début d’année que l’on allait programmer un ordinateur pour lui faire apprendre à jouer à un jeu. En précisant que l’on allait partir d’un ordinateur qui "ne savait rien faire" (ou pas grand chose).
Étant donné les compétences demandées aux élèves au collège en terme de programmation, le jeu choisi est le jeu de Nim et dans sa forme exclusivement numérique (pas d’allumettes, de bâtons, de barres où autres objets physiques pour un traitement facile par un ordinateur et en limitant les distractions pour les élèves telle que le choix de belles allumettes, leur placement...). J’ai considéré que le choix du Tic Tac Toe aurait déjà rendu le traitement beaucoup plus difficile et hors de portée des élèves.

Un peu plus tard dans l’année, après avoir indiqué que c’était maintenant que l’on allait programmer un ordinateur pour qu’il apprenne à jouer au jeu de Nim (et à être fort), j’ai commencé par leur faire jouer eux-mêmes à ce jeu en leur demandant de garder en tête la façon dont ils font évoluer leur façon de jouer. (métacognition : comment j’apprends, domaine 2 du socle : les méthodes et outils pour apprendre)
J’ai organisé une sorte de tournoi sur la moitié d’un cours.
Les élèves ont noté leurs parties sur leur cahier.
Ils se mettaient par deux. Je leur donnais un nombre de départ, ils faisaient des parties en commençant chacun leur tour et ainsi de suite jusqu’à ce que trois minutes environ soient écoulées. On récupérait les résultats et on changeait ensuite les binômes.

Beaucoup d’élèves voient bien que s’ils laissent quatre à leur adversaire, ils ont gagné en testant les trois possibilités. Par contre, peu réussissent à en déduire que s’ils laissent huit, puis douze, puis seize puis... ils ont aussi gagné.
En bilan on a écouté où ils en étaient de leurs stratégies. Certains ont trouvé qu’il fallait laisser à leur adversaire un multiple de quatre pour gagner. Je leur ai dit que pour un ordinateur c’était déjà un raisonnement trop évolué et qu’il allait falloir trouver une autre façon de faire : la notion de multiple de quatre à apprendre à un ordinateur est très compliqué. Si on utilise le bloc "modulo" de scratch dans le programme, ce n’est pas l’ordinateur qui va apprendre à jouer puisqu’on lui donne la stratégie gagnante directement.

Première séance avec le logiciel scratch

J’ai fait le choix de leur donner un programme déjà fait mais avec des erreurs à corriger. (ce qui correspond à ce qui est demandé lors des épreuves du diplôme national du brevet)
Cela fait gagner du temps et permet d’avancer plus facilement car tout le monde a le même programme.
Les élèves sont par deux et jouent l’un contre l’autre.
Ils corrigent les quatre erreurs. Au bout d’un moment, ceux qui ont trouvé les erreurs passent "élève ressource" et vont aider leurs camarades à corriger leur programme.

Cette entrée en matière permet aux élèves de se remettre la règle du jeu en tête.
Le premier programme est donc un programme qui permet à un être humain de jouer contre un autre être humain.
Je leur demande de modifier le programme pour qu’un être humain puisse jouer contre l’ordinateur. (l’ordinateur sera le joueur 2)
Je les laisse regarder dans tous les blocs à disposition dans scratch.
J’évacue les propositions qui suppose que l’ordinateur est déjà "trop intelligent" et qui correspondent aux stratégies qu’ils ont trouvé.
Il faut bien garder en tête que l’ordinateur doit apprendre à apprendre à jouer.
Je leur dis d’utiliser le bloc vert "nombre aléatoire entre ... et ..." qui correspond à un ordinateur qui n’est pas "intelligent". C’est aussi comme cela que les élèves ont commencé à jouer. (on pourrait aussi choisir de dire que l’ordinateur soustrait toujours le même nombre au lieu qu’il joue au hasard)
Même principe, les élèves les plus avancés passent "élève ressource".
Ils testent ensuite leur programme et jouent ainsi contre l’ordinateur. Ils jouent contre un ordinateur qui ne sait pas encore vraiment jouer puisque ses coups sont basés sur le hasard : un ordinateur vraiment "débutant".
Pour la dernière étape de cette séance, ils modifient encore le programme pour que l’ordinateur joue contre lui-même. (comme ce qui est fait avec les ordinateurs qui ont appris à jouer au jeu de go par exemple)
Ils s’aperçoivent quand c’est fait que les parties sont quasiment instantanées.
Je demande aux plus avancés de choisir un nombre de départ et de voir si c’est plutôt le "joueur ordinateur 1" ou le "joueur ordinateur 2" qui gagne le plus souvent ou si les "chances de gagner" semblent être les mêmes. En entendant des conclusions un peu trop hâtives, je leur demande de faire jouer plus de parties. (certains, en ayant vu le "joueur ordinateur 1" gagner deux fois, en déduisent dans la foulée qu’il va tout le temps gagner...)
S’ensuit l’idée de créer des variables pour comptabiliser le nombre de parties gagnées par le "joueur ordinateur 1" ou par le "joueur ordinateur 2".
Je leur demande ensuite de faire qu’automatiquement, il se joue beaucoup de parties successives et d’observer le nombre de parties gagnées par l’un ou l’autre des joueurs.
Un bilan clôt la séance en rappelant les différentes étapes :

• un être humain joue contre un être humain ;
• un être humain joue contre un ordinateur débutant ;
• un ordinateur débutant joue contre un ordinateur débutant ;
• un ordinateur débutant joue un grand nombre de parties contre un ordinateur débutant.

Seconde séance avec le logiciel scratch

Elle commence par de la consolidation : reprise du premier programme donné, avec les mêmes étapes que la première séance mais en beaucoup plus vite avec toujours l’utilisation des "élèves ressource".
Dans un deuxième temps je reviens sur la stratégie que les élèves ont quand le nombre devient assez petit, à savoir ils testent les trois possibilités. Je mets à disposition un programme qui permet de faire cela. C’est un programme avec lequel on choisit un nombre de départ et qui va tester si on gagne plus de parties en enlevant 1, 2 ou 3.
Ils font des essais avec différents nombres de départ.
Les résultats ne sont pas forcément très probants. Pour un nombre de départ élevé, le choix du nombre à soustraire n’est pas toujours évident quand les "joueurs ordinateurs" jouent comme des débutants.
L’étape suivante est qu’ils stockent dans la mémoire de l’ordinateur le nombre à soustraire en fonction du nombre.
Je leur montre comment créer une liste et comment elle va être utilisée.
L’élément 1 de la liste indique combien il faut soustraire quand c’est le nombre 1 à leur tour de jouer.
L’élément 2 de la liste indique combien il faut soustraire quand c’est le nombre 2 à leur tour de jouer..
Et ainsi de suite....
Les élèves se rendent compte que la suite de nombres à soustraire obtenue est périodique. Je fais un point sur le fait que programmer un ordinateur pour qu’il détecte une régularité (ici une périodicité) est difficile.
Ils changent aussi le programme pour que le "joueur ordinateur" qui apprend utilise les informations stockées.
Ils complètent la liste progressivement en commençant par des parties où le nombre de départ est 1, puis 2, puis 3...

Cela leur montre en passant que, pour résoudre un problème, on peut d’abord le simplifier puis le rendre de plus en plus difficile jusqu’à résoudre le problème initial.

Dernière séance dans une salle classique

Lors de la séance précédente ce sont eux qui ont complété la mémoire (la liste) qui a permis à l’ordinateur de savoir jouer : puisque la façon de jouer est mémorisée, il a appris et donc maintenant, il sait jouer.
Je leur montre aussi que le fait que le joueur ordinateur 1 utilise au fur et à mesure la stratégie stockée dans la liste permet de compléter la liste de façon beaucoup plus efficace mais que si le joueur ordinateur 2 utilise lui aussi la stratégie trouvée alors c’est encore plus efficace.
Je leur montre un programme où la liste se complète automatiquement jusqu’au nombre de leur choix.
C’est le programme qui était l’objectif du scénario : un programme qui permet d’apprendre à apprendre à l’ordinateur à jouer au jeu de Nim.
Je leur montre aussi l’avantage des apprentissages d’un ordinateur par rapport à un être humain, c’est qu’il peut être copié et utilisé dans un autre programme contrairement aux êtres humains qui commencent leur apprentissage de zéro à leur naissance. Il n’existe pas encore de technique à ma connaissance pour récupérer un apprentissage acquis par un être humain et le donner à un autre être humain.
J’exporte donc cette liste dans un fichier que j’importe dans le programme où un être humain joue contre l’ordinateur en modifiant le programme pour que l’ordinateur utilise cette liste, cet apprentissage.
Je fais ensuite jouer la classe contre l’ordinateur.
Je termine en leur faisant écouter une émission de radio dans laquelle un enfant voudrait savoir grâce à quoi les smartphones sont si intelligents et où l’intervenant répond que ce sont surtout les personnes qui les programment qui sont très intelligentes.

La conclusion du scénario est qu’ils ont ainsi vu que l’on pouvait faire apprendre des choses à un ordinateur en gardant bien en tête que c’est un être humain à la base qui permet que cela soit possible.

Réussites, remarques, obstacles et limites

Pour ne pas prendre trop de séances, le scénario est tout de même très guidé, ce qui ne l’empêche pas d’être riche en enseignements.

Un des messages que je voulais faire passer aux élèves était, que dans la vie de tous les jours, on peut tomber sur des situations où on croit que l’on a affaire à une situation équitable comme quand on lance un dé équilibré alors qu’en fait, pas du tout. En effet, dans le cas du jeu de Nim, le joueur qui connait la stratégie gagnante sait avant de commencer la partie, s’il va gagner à coup sûr ou s’il peut gagner si l’autre ne connait pas la stratégie gagnante. Parfois, il est très difficile de reconnaitre ces situations. (Domaine 3 du socle : La formation de la personne et du citoyen) En tout cas, il me sera difficile de savoir si ce scénario a modifié leur façon d’aborder la vie de tous les jours.

Pour les plus rapides, on peut leur demander de modifier les programmes pour que les nombres soustraits soient bien donnés parmi 1, 2 ou 3 quand c’est à un humain de jouer. Il faut un "message d’erreur" sinon et que la question soit reposée.

Documents de référence

Les fichiers Scratch et leur utilisation.

Ces fichiers ont été mis à la disposition des élèves par l’intermédiaire d’un lien internet qui envoie sur les projets Scratch que j’ai mis sur mon compte enseignant. On peut tout à fait leur donner directement les fichiers.

 Jeu de Nim 01a h vs h
C’est le programme avec les erreurs à trouver. Il est à donner aux élèves. Il y a quatre erreurs. La correction s’obtient avec le lien suivant.
 Jeu de Nim 01b h vs h correction

On leur demande ensuite de modifier le programme précédent pour qu’un être humain puisse jouer contre la machine.
Voici une correction possible où la machine joue au hasard.
 Jeu de Nim 02 h vs m correction

Puis ils doivent encore modifier le programme pour que la machine joue contre elle-même.
Voici deux corrections. La deuxième est faite de telle manière que quand on exécute le programme, ce qui se passe soit plus compréhensible. Cela demande l’utilisation d’une variable supplémentaire...
 Jeu de Nim 03a m vs m correction
 Jeu de Nim 03b m vs m correction 2

Ils doivent encore modifier le programme pour que la machine joue beaucoup de parties contre elle-même et qu’elle compte combien de parties sont gagnées par le joueur machine 1 et par le joueur machine 2. L’objectif est qu’ils utilisent ce programme pour voir si on peut en déduire combien il faut soustraire en fonction du nombre qu’ils ont à leur tour de jeu.
Voici une correction possible. (cela demande un assez bon niveau de programmation et donc le fichier correction peut être donné aux plus fragiles pour qu’au moins ils l’utilisent)
 Jeu de Nim 04 m vs m plusieurs parties correction

Le fichier suivant est directement donné aux élèves pour qu’ils l’utilisent.
 Jeu de Nim 05a m vs m apprentissage aidé utilisation
Ils testent dans un premier temps en changeant le nombre de départ pour en déduire s’il vaut mieux soustraire 1, 2 ou 3 en fonction du nombre qu’ils ont à leur tour de jeu.
Pour ce faire, ils regardent les nombres de parties gagnées.
Puisque les résultats trouvés ne sont pas mémorisés dans un premier temps (à savoir, s’il vaut mieux soustraire 1, 2 ou 3) on leur demande de les mémoriser dans la liste à leur disposition.
L’élément 1 de la liste indiquant combien il faut soustraire quand c’est le nombre 1 à leur tour de jeu.
L’élément 2 de la liste indiquant combien il faut soustraire quand c’est le nombre 2 à leur tour de jeu.
...

Ils doivent se rendre compte que ce programme n’est pas très performant normalement pour obtenir la stratégie gagnante. Par exemple, si on prend un nombre de départ de 12, on ne sait pas à coup sûr quel nombre on doit soustraire...

Pour l’améliorer, on peut faire en sorte que la machine utilise les résultats qui ont été mémorisés pour en déduire les résultats avec des nombres plus grands.
Cela peut donner par exemple le programme suivant.
 Jeu de Nim 05b m vs m apprentissage aidé avec emploi direct utilisation
Je leur ai montré comment faire au vidéo-projecteur et ils l’ont refait ensuite.

Ce dernier programme est beaucoup plus efficace mais on peut faire encore mieux en faisant en sorte que le deuxième joueur utilise aussi la stratégie mémorisée :
 Jeu de Nim 05c m vs m apprentissage aidé avec emploi direct des deux utilisation
Certains élèves ont trouvé comment faire tout seuls puisque c’est le même bloc que précédemment qu’il faut placer dans les scripts correspondant au joueur 2.
C’est normalement la fin de la deuxième séance avec Scratch.

La dernière partie est faite en vidéo-projection en classe entière.
On montre un programme où la liste se complète automatiquement jusqu’au nombre de son choix.

 Jeu de Nim 05d m vs m apprentissage auto avec emploi direct des deux visualisations
On montre ensuite comment exporter la liste obtenue pour l’importer dans le programme suivant et ainsi faire jouer la classe contre une machine qui a appris à très bien jouer au jeu de Nim :
 Jeu de Nim 06 h vs m qui récupère l’apprentissage
On peut s’aider de la vidéo suivante (qui n’a pas de son) pour voir comment faire.

Vous trouverez ci-joint tous les fichiers Scratch compressés.