Formation

Tranche de formation toi-même ! (chapitre 2 : le jeu de nim)

Télécharger le slide

Après cette introduction, je fais plonger les participants directement dans le bain, en les mettant à contribution. C´est toute la philosophie et l´intérêt des [activités débranchées] alors autant en profiter ! Je propose donc de jouer au jeu de Nim. Vous trouverez sur pixees une vidéo qui explique comment animer un atelier avec le jeu de nim. Cela dit, je voudrais décrire ici la façon dont je l´anime et les explications qui me paraissent convenir pour cette formation.

• Il parait que c´est proche d´un jeu de « Fort Boyard » alors autant le dire tout de suite. Mais il parait aussi que la règle du jeu est légèrement différente dans notre atelier.
• J´explique la règle en insistant sur sa simplicité. Deux joueurs s´affrontent en prenant des jetons tour à tour. Chaque joueur prend de 1 à 3 jetons. Celui qui emporte les derniers jetons a gagné.
• Je demande à un participant de m´affronter ;  je me débrouille pour qu´il commence. Chacun son truc pour faire commencer l´autre (mais il est préférable que ce soit discret puisque ça fait partie de la stratégie gagnante). Mon truc c´est de redire la règle et d´ajouter « c´est bon ? alors si tu as compris je t´en prie, joue… ». D´autres diront « je suis bon prince, je te laisse commencer ».
• Une fois que mon adversaire a commencé à jouer j´explique que je suis vraiment pas sympa, parce que j´ai oublié de dire que je suis strictement imbattable (et tout le monde se marre, y compris, parfois, mon adversaire mais pas toujours 😉 ). Mais la bonne nouvelle, c´est que toi aussi, après cet atelier, tu seras imbattable !
• On enchaîne les tours et, en appliquant la stratégie gagnante, viens obligatoirement un moment où il reste 4 jetons et c´est à mon adversaire de jouer. Là, je fais stopper la partie et je dis « tiens ! C’est intéressant ! Est-ce que tu as une chance de gagner ? ». On analyse les deux coups à venir et bien sûr que non… Mon adversaire n´a aucune chance à ce stade. J´explique alors que je n’ai pas été sympa en ne prévenant pas à l´avance que j´étais imbattable et on ne va pas jusqu´au bout.
• Ensuite je demande aux participants de jouer entre eux. Il y a deux scénarios :

* scénario 1 : ils ont trouvé la stratégie.

* scénario 2 : ils encore besoin d’y réfléchir. Dans ce cas, je place les pions en ligne et par 4 colonnes et je refais une partie avec mon adversaire initial (histoire de lui donner sa revanche). Je demande à enlever les pions en « serpent » pour garder la structure « lignes/colonne ». En général, à ce stade, les participants se doutent de l´importance d´être le premier. Donc je commence. D´une manière ou d´une autre, il faut faire comprendre à l´adversaire et au groupe (si ce n´est pas déjà le cas) qu´il doit vider une ligne à chaque fois, pour arriver dans la configuration imbattable où il reste 4 jetons et c´est à moi de jouer (donc je vais perdre).

Maintenant tout le monde a compris comment gagner au jeu de Nim. Il reste donc à transformer cette stratégie gagnante en algorithme. A ce stade, j´explique que je suis un robot capable de jouer à ce jeu (capable de compter les pions et de les déplacer). Je demande donc comment il faut me programmer pour gagner à tous les coups. Pour mettre les participants en situation de programmeur qui vont débugger, j´explique que  je vais jouer toute la nuit pour eux. A chaque fois que je gagne une partie, je rapporte un Euro. A chaque fois que je perds une partie, je coûte un Euro.

Alors quel est le programme ? Souvent, on passe par l´étape « si l´adversaire en prend 1 j´en prends 3, si il en prend 2 j´en prends 2, etc. ». Personnellement, je coupe court en disant « ok, on va dire que je prends le complément à 4 ». Mais d´autres se servent de ça pour faire un topo sur le complément à 4 ou les instructions conditionnelles. Je me souviens d´une intervention en fête de la science où Antoine Rousseau avait profité de ce passage pour sortir le feutre et le tableau blanc et expliquer ça en direct aux élèves. Le programme de base, qu´on peut obtenir en discutant avec eux est le suivant :

1. L´adversaire commence.
2. Je prends le complément à 4.
3. Tant qu´il reste des jetons sur la table, on recommence depuis le début.

Il y a toujours un bug à trouver dans leur programme. En voici trois, du plus évident, au plus tordu (parfois, ils trouvent tous seuls les deux premiers, alors je leur dis que je les déteste et donc je sors le troisième bug parce qu´ils m´ont énervé à être trop forts 😛 ).

Bug 1. Ne pas penser à faire commencer l´autre. Ça peut arriver… Alors on peut expliquer qu´en faisant les comptes on va voir que c´est plutôt « nul » (pas de gain, pas de coût, c´est à peu près équilibré). On va donc regarder ce qui s´est passé dans l´historique des parties et voir que j´ai perdu à chaque fois que j´ai commencé. Il faut alors débugger. C´est bon ? Ça marche maintenant ? Je suis sûr d´être riche ? Et nooooon… il y a le bug n° 2.

Bug 2. Ne pas vérifier que le nombre de jetons sur la table est bien un multiple de 4. D´ailleurs j´en profite pour faire une parenthèse qui concerne les élèves (et donc je quitte pour quelques lignes le monde des participants, adultes, à cette formation). Selon l´âge, c´est peut-être une bonne façon d´expliquer la notion de « multiple ». Si c´est nécessaire, je demande aux élèves « Est-ce que notre stratégie marche avec une ligne de 4 jetons ?  » (oui). « Est-ce que notre stratégie marche avec deux lignes de 4 jetons ?  » (oui). « Est-ce que notre stratégie marche avec n´importe quel nombre de lignes de 4 jetons ?  » (oui). « Est-ce que notre stratégie marche avec autre chose que n´importe quel nombre de lignes de 4 jetons ?  » (non).

Revenons à la formation. Donc le nouveau programme c´est :

1. Vérifier que le nombre de jetons sur la table est un multiple de 4.
2. L´adversaire commence.
3. Je prends le complément à 4.
4. Tant qu´il reste des jetons sur la table, on recommence depuis le début.

C´est bon ? Ça marche maintenant ? Je suis sûr d´être riche ? Et nooooon… il y a le bug n° 3.

Bug 3. L´adversaire peut tricher ! Oui, c´est tordu, et ça fait râler tout le monde. Mais tricher, en informatique, c’est voler des numéros de carte bleue ou s’introduire sur un site sécurisé, par exemple. Et puis ils sont énervants aussi ces participants à trouver les bugs tous seuls ! Donc je sors celui-là s’ils ont trouvé les deux premiers tout de suite ou selon le temps disponible. Et encore… il m´est arrivé qu´un groupe trouve les 3 seuls et très rapidement. Ceux-là je les ai détestés 😀 ! (et ils ont kiffé quand je leur ai avoué 😛 ). Nous voilà avec une entrée en matière sur la notion d´algorithmes. Ces algorithmes qui, une fois traduits dans un langage compréhensible pour la machine, permettront à cette dernière d´exécuter des opérations et même des tâches complexes. C´était également l´occasion de parler de ces fameux bugs et de discuter de leurs causes possibles (des erreurs de conceptions, ou bien de traduction pour la machine).

PDF view