TraAM 2016-2017 - Un jeu de nim publié le 13/09/2017  - mis à jour le 18/01/2019

Présentation du projet

Objectifs

À travers la pratique et l’analyse du jeu de Nim, étudier les interactions environnementales ou humaines avec un robot dans l’optique d’une programmation de ce jeu pour pouvoir jouer contre une machine.
Développer un regard critique concernant les issues de certaines actions et différencier hasard et stratégie.
Initier à "l’intelligence artificielle".

Niveau concerné

Fin de cycle 4.

Compétences mobilisées

Mathématiques	Technologie
Chercher :  S’engager dans une démarche scientifique, observer, questionner, manipuler, expérimenter (sur une feuille de papier, avec des objets, à l’aide de logiciels), émettre des hypothèses, chercher des exemples ou des contre-exemples, simplifier ou particulariser une situation, émettre une conjecture.  Tester, essayer plusieurs pistes de résolution.  Décomposer un problème en sous-problèmes.	CT1.1 Imaginer, synthétiser, formaliser et respecter une procédure, un protocole.
Modéliser :  Traduire en langage mathématique une situation réelle (par exemple, à l’aide d’équations, de fonctions, de configurations géométriques, d’outils statistiques).	CT1.2 Mesurer des grandeurs de manière directe ou indirecte.
Représenter :  Choisir et mettre en relation des cadres (numérique, algébrique, géométrique) adaptés pour traiter un problème ou pour étudier un objet mathématique.	CS 1.6 Analyser le fonctionnement et la structure d’un objet, identifier les entrées et sorties.
Raisonner :  Mener collectivement une investigation en sachant prendre en compte le point de vue d’autrui.  Démontrer : utiliser un raisonnement logique et des règles établies (propriétés, théorèmes, formules) pour parvenir à une conclusion.  Fonder et défendre ses jugements en s’appuyant sur des résultats établis et sur sa maîtrise de l’argumentation.	CT4.2 Appliquer les principes élémentaires de l’algorithmique et du codage à la résolution d’un problème simple.
Communiquer :  Faire le lien entre le langage naturel et le langage algébrique. Distinguer des spécificités du langage mathématique par rapport à la langue française.  Expliquer à l’oral ou à l’écrit (sa démarche, son raisonnement, un calcul, un protocole de construction géométrique, un algorithme), comprendre les explications d’un autre et argumenter dans l’échange.	CT5.4 Piloter un système connecté localement ou à distance.

Problématiques

Comment simuler un joueur de jeu de NIM à l’aide d’un ordinateur ou d’un robot afin de pouvoir jouer contre lui ?
Comment fonctionne un robot Thymio II ?
Comment fonctionne un capteur ?

Déroulement de la séquence

Les différentes étapes :

• Comment jouer au jeu de Nim choisi ? (Maths)
• Comment programmer avec scratch le jeu de Nim pour pouvoir jouer à deux sur un appareil numérique ? (Maths)
• Comment modifier le programme scratch pour pouvoir jouer contre un appareil numérique ? (Maths)
• Est-il possible de programmer un appareil numérique pour qu’il soit imbattable ? (Maths)
• Comment fonctionne Thymio II ? (Techno)
• Comment fonctionne un capteur ? (Techno)
• Comment adapter le programme scratch à Thymio II ? (Techno avec éventuellement Maths)

Il existe déjà des documents traitant des jeux de Nim : (au pluriel car il y a plusieurs règles possibles)
 un article très complet de la revue sesamath sur les jeux de Nim ;
 un document éduscol proposant une façon d’utiliser un jeu de Nim avec ses élèves ; (pdf de 301 Ko)
 l’académie de Créteil a déjà présenté des TraAM sur le sujet mais d’une autre manière. (pdf de 123 Ko)

Le déroulé proposé se distingue de par ses étapes, de la forte implication de la technologie, et de la production finale : un robot contre lequel on peut jouer au jeu de Nim.

Dans la suite, ce qui est présenté est ce qui a été expérimenté avec une classe de troisième de 23 élèves ou ce qui est considéré comme une amélioration suite à l’expérimentation.

---

Comment jouer au jeu de Nim choisi ? (Maths)

Où : En salle de classe classique.
Durée : environ 15 min (fin de cours par exemple)

Interroger les élèves pour savoir ceux qui connaissent déjà le jeu de Nim ("Comme dans Fort Boyard.").

Le jeu de Nim peut avoir plusieurs règles différentes.

La règle adoptée (imposée) :

• un certain nombre de barres verticales assez espacées, sont tracées les unes à côté des autres (entre 15 et 20),
• on place un objet d’un côté (règle, gomme, carnet de correspondance...),
• tour à tour, chaque joueur fait avancer l’objet de une à trois barres noires,
• celui qui fait franchir, la dernière barre à l’objet a gagné.
  Ou plus simplement : Le premier arrivé a gagné. On ne peut avancer que de 1, 2 ou 3 barres noires à chaque fois.

L’objectif est de s’approprier les règles dans un premier temps, donc rien n’est imposé : ni le nombre de barres, ni le joueur qui commence.

Une deuxième partie de cours peut être consacrée à cette appropriation des règles.

À la fin des temps de jeu, on peut faire remonter les remarques entendues éventuellement :

• "À chaque fois il s’arrange pour me laisser 4 barres !"
• "Il me reste quatre barres, j’ai perdu..."

Chercher à savoir s’il y en a qui ont des stratégies et rappeler la suite de la séquence : programmation avec scratch pour pouvoir jouer sur un appareil numérique.

---

Comment programmer avec scratch le jeu de Nim pour pouvoir jouer à deux sur un ordinateur ? (Maths)

Où : Dans une salle permettant d’avoir au moins un matériel numérique avec lequel on peut utiliser scratch pour deux ou trois élèves.
L’idéal est de s’arranger pour que la constitution de ces groupes soit la même que celle des groupes qui manipuleront Thymio II en technologie.

Durée : 1 à 2 cours.

Consigne : Comment programmer scratch pour pouvoir jouer à deux au jeu de Nim ?

Un exemple d’une production un peu trop minimale :

Les améliorations possibles :

• le programme indique qui du joueur 1 ou du joueur 2 doit jouer,
• le chat à une couleur différente en fonction du joueur,
• une animation lorsque l’un des joueurs gagne,
• mise en place d’un score,
• désignation du joueur qui commence aléatoire,
• nombre de barres total aléatoire,
• demande puis affichage du nom des joueurs,
• affichage du nombre restant de barres,
• déplacement du chat au clavier ou, après récupération de la réponse à une question et la vérification de la validité de la valeur donnée, ou en cliquant sur des lutins (pour une utilisation plus facile avec une tablette, un smartphone, un TNI...),
• un bouton d’aide pour rappeler les règles,
• un temps de jeu maximal par joueur,
• les barres sont des lutins qui disparaissent au fur et à mesure que le chat avance,
• les barres sont des clones pour éviter d’avoir autant de barres que de lutins,
• un lutin en forme de barre est "estampillé" sur l’écran autant de fois que de barres,
• ...

Fin de cette partie après avoir sélectionné le programme le plus approprié pour faire un tournoi.

Proposition d’organisation du tournoi

Où : Dans un lieu ayant les mêmes caractéristiques que précédemment avec en plus un vidéoprojecteur si possible.

Mise en place : numéroter les différents appareils numériques (qui peuvent être complété par des emplacements où les parties se joueront sur papier), ces différents matériels ne bougeront pas, ce sera les élèves qui changeront de place et d’adversaire après chaque manche.

Règle : le tournoi est individuel (mais pourquoi pas par équipe).
On effectue plusieurs manches.
Il faut deux ou trois parties gagnantes (suivant le nombre d’élèves) pour remporter une manche.
Le classement s’effectuera en fonction du nombre de manches gagnées.
Le nombre de barres est fixé (mais le faire diminuer au cours du tournoi) et c’est toujours le même qui commence lors d’une manche.

Pour gérer le tournoi, si vous ne connaissez pas de logiciel, utilisez Vega qui est gratuit pour une utilisation avec moins de 30 participants.

Pourquoi un logiciel pour gérer le tournoi ?

• une fois le tournoi créé et le nom des participants rentré, il indique qui joue contre qui, à quel emplacement et qui commence les parties,
• il fait jouer entre eux dès la deuxième manche les participants de niveau proche, ce qui limite les élèves qui arrêtent découragés,
• lors de la récupération des résultats des manches, son affichage permet de mettre en évidence que le nombre de barres au départ et la désignation du joueur qui commence, influe sur le résultat d’une partie,
• le système de comptage des points par défaut permet de classer les élèves correctement sans que tout le monde ait rencontré tout le monde ; entre 10 et 15 parties suffisent généralement.

La copie d’écran ci-dessus montre les résultats de la 6ème partie d’un tournoi. Les joueurs du haut du tableau sont ceux qui savent le mieux jouer normalement.
Pour cette manche le nombre de barres de départ était de 12 et le joueur qui commençait à chaque partie était le joueur de gauche. On voit que les joueurs de gauche de la partie supérieure du tableau ont tous perdu cette manche.

Voir une vidéo d’explication pour l’utilisation de ce logiciel :

Le tournoi a donc plusieurs finalités :

• mettre en valeur le travail du groupe qui a réalisé le programme le plus adapté,
• continuer de réfléchir sur la meilleure façon de jouer,
• mettre en évidence l’influence de certains paramètres : nombre de barres et qui commence.

Remarque :

• Ne pas hésiter à bien baisser le nombre de barres au cours des manches quitte à le remonter après si l’issue des parties est vraiment trop évidente.
• La stratégie gagnante n’est pas encore "institutionnalisée" à cette étape.

Distribution et ramassage des fichiers scratch :

• utilisation de l’ENT pour distribuer un fichier scratch vide puis ramasser le fichier complété,
• ou, utilisation d’un compte scratch enseignant avec l’utilisation d’un studio dédié,
• ou...

---

Comment modifier le programme scratch pour pouvoir jouer contre un appareil numérique ? (Maths)

Où : mêmes conditions que précédemment.

Durée : 1 à 2 cours

Coup de pouce : distribution d’un fichier scratch de départ aux groupes vraiment en difficulté.

Quelques stratégies attendues :
Quand c’est au tour de l’appareil numérique de jouer, il avance :

• toujours du même nombre de barres,
• en suivant un cycle : une barre, puis 2, puis encore 1, puis 2 et ainsi de suite par exemple,
• en fonction du nombre de barres choisi par l’adversaire au tour précédent :
  • le même nombre,
  • 4 moins le nombre de l’adversaire,
• aléatoirement,
• en prenant en compte le nombre de barres restantes :
  • un utilisant une liste préremplie où toutes les possibilités sont prévues (s’il reste 5 barres, on avance du nombre de barres correspondant au 5ème nombre de la liste),
  • en utilisant le reste de la division Euclidienne par 4 (le modulo).

Est-il possible de programmer un appareil numérique pour qu’il soit imbattable ? (Maths)

Où : même conditions que précédemment.

Durée : 1 cours

Consigne : Compléter le tableau suivant :

 

S’en suit un temps de rédaction en français sur la stratégie gagnante, puis la traduction en langage scratch avec le bloc "modulo" par exemple.

On répond à la question : Pour être imbattable, il faut qu’il reste un nombre de barres qui ne soit pas un multiple de 4 quand c’est à son tour de jouer. Il doit ensuite avancer pour que son adversaire se trouve dans cette situation.

Une fois les programmes finis, on peut les faire tester par les autres groupes et les affiner (voir la partie "intelligence artificielle" dans la partie "quelques remarques").

On peut aussi proposer un débat sur ce type de jeu (quelqu’un connaissant la stratégie gagnante sait d’avance s’il peut gagner à coups sûr et donc faire perdre son adversaire, où gagner suivant ses intentions).
Cela permet de montrer que savoir, dans certains cas, permet d’éviter de subir.

---

Partie technologie

Comment fonctionne Thymio II ?

Partie qui sera plus ou moins longue suivant le travail fait les années précédentes.
Elle peut commencer par une utilisation des différents comportements préprogrammés de Thymio II (vert, rouge, violet et jaune) pour lui faire faire un huit autour de deux obstacles comme des pots de colle par exemple (en évitant les deux modes bleus pour lesquels soit il faut taper dans les mains, soit il faut un circuit).

Puis continuer avec de la programmation visuel : l’interface VPL du logiciel ASEBA.

Les élèves peuvent avoir des missions à faire accomplir à Thymio II par exemple.

Une correction possible :

Un petit glossaire peut être constitué à partir de la correspondance entre les blocs utilisés et le texte correspondant du programme.

Comment fonctionne un capteur ?

On peut faire identifier les différents éléments de Thymio II et compléter le schéma de la chaine d’information :

On peut faire observer les valeurs renvoyées par les différents capteurs Thymio, associer chaque valeur à une grandeur physique et un capteur et pour les capteurs de proximité, demander de trouver un protocole pour associer les valeurs lues sur l’ordinateur aux distances Thymio II/obstacle.

On peut les faire s’interroger sur la nature des signaux émis : analogiques ou numériques ?

À partir des manipulations de Thymio II et d’autres exemples, on peut arriver à la modélisation et la simulation des objets et systèmes techniques suivante :

---

Comment adapter le programme scratch à Thymio II ?

Dans cette partie, il faut que les élèves fassent correspondre des actions virtuelles à des actions réelles :

• de quoi vont être faites les barres ?
• quels capteurs vont être utilisés ?
• comment traiter les informations ?

Pour des raisons pratiques, dans l’expérimentation, le choix a été fait d’utiliser une feuille au format A3 sur laquelle sont tracées des barres noires.
Ceci est possible car certains capteurs de Thymio II ne renvoient pas les mêmes valeurs suivant que la surface soit blanche ou noire. Le noir renvoyant moins de lumière, il s’apparente à un objet loin.

Le fait que les élèves qui ont participé à l’expérimentation, n’aient pas trop programmé les années précédentes, a orienté le choix de gestion de cette partie de l’EPI de la façon suivante :

• un fichier prêt leur a été fourni, qu’ils ont chargé dans Thymio et utilisé,
• des questions leurs ont été posées concernant ce programme,
• ils ont eu à en modifier certaines parties,
• ils ont eu un temps pour le personnaliser.

---

Quelques remarques

On peut demander aux élèves ce qu’il faut changer au programme si on change les règles : si c’est le premier arrivé qui perd, si on peut avancer de 1 à 4 barres au lieu de 3, de 2 à 4... ou de 1 à 2n barres si n est le nombre de barres choisi par l’autre joueur comme c’était le cas pour un atelier Maths en jean (voir le compte-rendu de cet atelier) (pdf de 129 Ko).

Concernant l’utilisation de Thymio II :

• penser à baisser complètement le son,
• le calibrer pour qu’il roule le plus droit possible,
• mettre son firmware à jour,
• acheter éventuellement des cartes microSD (voir les modèles préconisés sur le site de Thymio II) pour pouvoir l’utiliser avec un programme personnel sans ordinateur entre autres, (à ce sujet, sans carte microSD une fois le programme chargé dans le Thymio II, on peut toujours le débrancher de l’ordinateur mais il ne faut pas l’éteindre sinon, il faut le rebrancher pour charger une nouvelle fois le programme, à réfléchir si un élève choisit de présenter ce projet pour son oral ou si on veut l’utiliser pour une journée portes ouvertes par exemple).
• avoir une carte microSD permet aussi de stocker du son dessus et d’utiliser ces fichiers sons pour son programme (pour faire "parler Thymio II" par exemple).
• programmer Thymio II avec d’autres langages comme scratch est possible mais pour des questions de stabilité et de pérennité, le choix a été fait d’utiliser ASEBA studio pour thymio.
• Dans le programme donné permettant de jouer au jeu de Nim avec Thymio II, la valeur qui permet de faire la distinction entre le blanc et le noir est de "200". Attention cette valeur peut varier en fonction de plusieurs paramètres : l’imprimante que vous avez utilisé et la qualité d’impression que vous avez choisie pour imprimer les bandes noires et, la luminosité de la pièce (moins la pièce est éclairée par le soleil et mieux cela fonctionne). Il est conseillé de passer une première fois le Thymio II, en le tenant à la main, sur les bandes et d’observer les valeurs données par les variables "prox.ground.delta" dans Aseba Studio pour Thymio. Si besoin, remplacer les quatre "200" par une valeur correcte (comprise entre les valeurs lorsque les capteurs de Thymio II sont sur du blanc et celles lorsqu’ils sont sur du noir) à l’aide de la fonction "Remplacer" dans le menu "Édition". Sinon, le programme suivant fait intervenir une constante "limite_noir_blanc" que l’on peut régler en haut à droite dans Aseba Studio en double-cliquant sur la valeur, mais il est moins lisible pour des élèves je pense...
  jeu_de_nim_avec_constante-2-2 (Zip de 1.8 ko)

On parle d’initier à "l’intelligence artificielle" au début de l’article. Si on voulait faire un rapprochement avec le test de Turing, il faudrait qu’un humain qui joue avec Thymio II, n’arrive pas à savoir si c’est un robot programmé qui joue contre lui ou si c’est un robot piloté par un humain.
Ainsi, le nombre de barres total pourrait ne pas être connu par le robot et la première partie serait l’occasion pour lui de le déterminer. On pourrait aussi s’arranger pour qu’il perde de temps en temps, que les temps entre deux coups soient réalistes...
On pourrait parler aussi de ces robots qui "apprennent" tout seul et s’interroger sur : comment programmer Thymio pour qu’il fasse des parties en jouant au hasard au début, puis, que petit à petit, il réussisse à devenir un expert ?