Partie 2
L'intelligence artificielle
Jeu de Nim
Qu'est ce que le jeu de Nim ?
Le jeu de Nim est un jeu très courant, de stratégie pure, à deux joueurs. Ce jeu, dont il existe d'innombrables variantes, se joue avec des graines, des billes, des jetons, des allumettes ou n'importe quels autres objets facilement manipulables...
Le jeu de Nim va être le support de cette activité et de la suivante.
Ce jeu présente un intérêt particulier dans le cadre d'une initiation à l'algorithmique, et donc à l'intelligence artificielle : ces règles sont simples ; il n'y a aucune part de hasard ; le nombre de coups possibles est limité ; la stratégie gagnante est simple sans être trop évidente.
Ci-dessous, nous vous présentons le jeu dans sa version classique. Cette lecture vous permettra de comprendre plus facilement l'activité de la page suivante.
Cependant, nous vous invitons à procéder à l'inverse en classe, en réservant l'activité ci-dessous pour un deuxième temps de recherche avec les élèves.
Règles du jeu :
Deux joueurs ramassent tour à tour 1, 2 ou 3 objets sur une table. Celui qui ramasse le(s) dernier(s) a gagné.
Matériel :
16 bouchons ou jetons, ou graines, ou billes, ou allumettes…
Tâche finale pour l’élève :
Concevoir et écrire un algorithme qui permet d’atteindre la stratégie gagnante.
Quels sont les concepts travaillés ?
À travers ce jeu, de nombreux concepts sont travaillés (instruction simple, programmation conditionnelle « si…alors », la notion de boucle, de synchronisation, de variable) mais ce qui nous intéresse dans le cadre de la thématique de l'intelligence artificielle est de faire comprendre aux élèves ce qu'est le concept d'algorithme. Pour gagner à ce jeu de Nim, il faut découvrir qu'il existe un algorithme qui permet de l'emporter à chaque fois.
Mise en activité des élèves :
Lors de la première séance consacrée à la découverte de ce jeu, l'enseignant joue contre un ou plusieurs élèves qui ne connaissent pas l'algorithme permettant de gagner chaque partie jouée. Lors de la passation de la consigne, l'enseignant doit donner le moins d'informations possible : "Nous allons jouer au jeu de Nim. Je vais jouer contre un élève. À son tour, chaque joueur a la possibilité de prendre 1, 2 ou 3 objets sur la table. Celui qui ramasse le dernier ou les derniers a gagné. Je vais laisser mon adversaire commencer".
Vous pouvez jouer 2 ou 3 parties ainsi. Au bout d'un moment, les élèves observateurs, voyant que l'enseignant gagne à chaque fois, commencent à se dire qu'il y a un "truc". Vous pouvez leur indiquer qu'en effet il y a un truc, que l'on appelle un algorithme et qui permet d'être sûr de gagner à chaque fois, lorsqu'on le connait et qu'on le suit. Et cela va être à eux de le découvrir.
Repartissez-les ensuite par groupes de 3 ou 4 pour qu'ils cherchent et découvrent l'algorithme gagnant. Demandez-leur d'élaborer une trace écrite pour que cet algorithme soit communicable. Une mise en commun permettra d'expliciter les réponses des élèves.
Dans cette vidéo, la règle fixe le nombre d'objets au départ à 20, mais nous allons voir que l'algorithme qui permet de gagner est le même qu'avec 16.
Lors de la mise en commun, les groupes d'élèves exposent le résultat de leur recherche. Voici, ci-dessous, un exemple de formalisation de l'algorithme gagnant pour cette variante du jeu de Nim.
Ce qu'il faut comprendre dans cet algorithme
Le nombre d'objets, au départ, est important. 16 est un multiple de 4. Pour bien visualiser pourquoi l'adversaire n'a aucune chance de gagner, il est possible d'organiser les 16 objets en 4 paquets de 4. Chaque tour de jeu ne va finalement concerner qu'un seul paquet de 4 objets. Lorsque mon adversaire prend 1, 2 ou 3 objets, je prends le complément à 4. Ainsi, je suis certain de prendre le dernier objet de chaque paquet de 4, donc de gagner la partie.
Cet algorithme peut donc permettre de gagner, à condition que le nombre d'objets au départ soit un multiple de 4 et que l'adversaire accepte de commencer la partie.
Si les élèves ont du mal à trouver l'algorithme seuls, il est possible d'orienter leurs recherches en limitant le nombre d'objets au départ à 8, par exemple, ou en séparant les paquets de 4 objets sur la table.
Autres variantes du jeu
Ce n'est pas nécessaire dans notre projet, mais, si vous souhaitez aller plus loin avec cette activité, vous pouvez faire évoluer le jeu de Nim en faisant varier :
les règles du jeu (la personne qui ramasse le dernier objet a perdu) ;
le nombre d'objets au départ.
Il faudra alors certainement adapter l'algorithme pour être sûr de gagner : par exemple, il pourra être nécessaire de ne pas laisser jouer l'adversaire en premier.
Le logigramme ci-dessous (qui n'est pas à donner aux élèves) vous permettra de retrouver l'algorithme gagnant, quelles que soient les règles choisies.