Ressource

Les cartes qui apprennent à jouer au jeu de Nim

Cette activité est basée sur le document diffusé par Marie Duflot-Krémer sur son site de médiation scientifique, ainsi que sur une discussion passionnante avec Chloé Mercier et Thierry Viéville. Il est diffusé sous licence CC-BY-SA (diffusable et modifiable en citant l’auteur et en gardant cette licence).

Axel Palaude (2021)

Le contexte

L’intelligence artificielle (IA) est partout aujourd’hui. Cependant, l’image qu’on en a est assez farfelue. Elle permettrait de créer des ordinateurs super intelligents capables de surpasser les humains, voire de dominer le monde ! Il y a de quoi être à la fois fasciné et effrayé.

La réalité est toute autre : les robots entièrement autonomes, les cerveaux artificiels, ce n’est pas pour demain. En réalité, l’IA est quelque chose de bien moins fantaisiste, mais tout aussi remarquable. Alors essayons de dépasser les clichés et découvrir un des mécanismes d’IA.

Voici une définition de l’intelligence artificielle, donnée par Marvin Minsky : “Artificial intelligence is the science of making machines do things that would require intelligence if done by men”, qui pourrait se traduire par “L’intelligence artificielle est la science qui fait faire aux machines des choses qui demanderaient de l’intelligence si ces choses étaient faites par les humains.”

Avec cette définition, nous avons découvert le pot-aux-roses. L’intelligence artificielle ne fait pas appel aux mêmes mécanismes que ceux dédiés à l’intelligence au sens humain du terme. Dans les faits, on observe que c’est par des calculs longs et coûteux réalisés par des machines, et des idées et algorithmes trouvés par des humains que les choses se passent “comme si” la machine était intelligente.

Pour illustrer cela, l’activité proposée dans ce document va permettre de fabriquer une machine faite de cartes de jeu qui, de manière totalement mécanique, va réussir à trouver la stratégie pour gagner à tous les coups d’un jeu à deux joueurs qui s’appelle le jeu de Nim.

Préparation du matériel

Pour réaliser l’activité, nous aurons besoin d’un simple jeu de 32 cartes, triés par couleur.
Les carreaux seront utilisés pour jouer au jeu de Nim, tandis que les trois autres couleurs seront utilisées pour décider des actions de la machine.

Il faut donc :

• étaler les carreaux pour que chaque carte corresponde à un élément du jeu de Nim. J’aime les étaler dans l’ordre décroissant As-roi-…-7 pour que le but du jeu de Nim soit de s’emparer de l’As, mais cela n’est pas nécessaire.
• Devant chaque carreau, faire un paquet de 3 cartes mélangées contenant 1 pique, 1 trèfle et 1 coeur, à l’exception des tas correspondants aux deux derniers carreaux : l’avant-dernier tas ne doit pas contenir de trèfle et le dernier tas ne doit contenir ni trèfle ni coeur. Ces paquets sont les “actions possibles” de la machine pour une situation donnée (détaillée plus loin) Encore une fois, j’aime bien que les cartes de chaque tas aient la même valeur que la valeur du carreau associé, mais ce n’est pas nécessaire.
  • Mettre les carreaux et les piles correspondantes en quinconce peut être utile pour bien identifier dans quelle pile piocher lorsque la machine joue, voir la section suivante pour plus de détails sur la façon dont la machine joue.

La figure 1 montre une disposition possible des cartes lors de la préparation de l’activité, et la figure 2 montre l’activité une fois prête à être lancée.

Figure 1 :
Disposition de base des cartes

Figure 2 :
État de l’activité au début

Jouons avec la machine

La machine va apprendre à jouer à une version simple du jeu de Nim.

Le jeu de Nim

Les 8 carreaux sont étalés et deux joueurs s’affrontent. Chaque joueur à son tour prend une, deux ou trois cartes carreau, et le vainqueur est celui qui prend la dernière carte (dans le cas où les cartes sont ordonnées, le vainqueur est celui qui réussit à récupérer l’as de carreau).

Dans notre activité, l’humain va jouer contre la machine. L’humain joue toujours en premier, et la machine joue en deuxième.
Lorsque l’humain joue, il se saisit simplement de une, deux ou trois cartes et c’est alors au tour de la machine.

Fonctionnement de la machine

Lorsque la machine “joue” (c’est-à-dire qu’une personne joue le rôle de la machine, en se contentant de manipuler les cartes selon le mécanisme ci-dessous), elle va retourner la première carte du paquet (contenant les piques, cœurs et trèfles) correspondant à la prochaine carte à saisir.

Il y a alors trois possibilités :

• Si la carte piochée est un pique, la machine prend une carte;
• Si la carte piochée est un cœur, la machine prend deux cartes;
• Si la carte piochée est un trèfle, la machine prend trois cartes.

Notons que c’est pour cette raison que nous avons retiré le trèfle de l’avant-dernier paquet ainsi que le trèfle et le coeur du dernier paquet, qui correspondent à des actions impossibles (prendre deux cartes quand il n’en reste qu’une par exemple).

Les figures suivantes montrent le déroulement d’une partie.

 

Figure 3 :
L’humain a pris une carte, la machine retourne une carte de la pile associée à la dernière carte

Figure 4 :
La machine a retourné un cœur : prise de 2 cartes

 

Figure 5 :
L’humain prend 1 carte

Figure 6 :
La machine retourne un Trèfle de la pile associée à la dernière carte

 

Figure 7 :
La machine a retourné un trèfle : prise de 3 cartes

Figure 8 :
L’humain prend 1 carte et gagne

S’il n’y a plus de carte dans le paquet correspondant, alors la machine abandonne la partie.
Une fois que la machine a pris les cartes, c’est au tour de l’humain, et on continue à jouer jusqu’à ce qu’il y ait un vainqueur.

Le mécanisme d’apprentissage

Si l’humain gagne la partie, c’est que la machine a fait au moins une erreur, et elle va donc apprendre de cette erreur. Dans le cas d’une défaite, la machine sait qu’au moins le dernier coup joué était mauvais. Afin de ne plus jouer ce mauvais coup, la machine va retirer la carte correspondant au dernier coup joué du tas correspondant et mettre la carte de côté. Les autres cartes (qui étaient peut-être de bons choix, on ne sait pas encore) sont mélangées à leur pile respective.

L’exemple donné précédemment s’est soldé par une victoire de l’humain : la dernière carte (le valet de trèfle) est retirée du jeu (voir Figure 9).

Figure 9 :
Défaite de la machine, Abandon du valet de trèfle

Si la machine a gagné, c’est que les actions effectuées ont mené à la victoire. Dans ce cas, toutes les cartes révélées sont mélangées à leur pile respective. Si le temps pour faire l’activité semble un peu court mais qu’on souhaite débarrasser la machine de tous les mauvais coups plus rapidement, il est possible, plutôt que de mélanger les piles à chaque fois, de mettre en dessous de la pile les cartes révélées, afin de s’assurer de tomber sur un mauvais coup à retirer par la suite.

Piles vides et abandon de la partie par la machine

Quand la machine est laissée avec 4 cartes, il n’y a pas de bon coup à jouer. Qu’elle en prenne une, deux, ou trois, l’humain va gagner directement. Avec notre méthode d’apprentissage, la pile correspondant à cette situation va finir par être vidée. Une pile vide signifie alors que, dans cette situation, la machine ne peut plus gagner. Dans ce cas, la machine abandonne la partie et considère que le dernier coup joué a mené à la défaite (par exemple prendre une carte quand il y en avait 7). Une illustration est proposée ci-dessous.

 

Figure 10 :
La pile de choix est vide, la machine abandonne

Figure 11 :
La machine abandonne donc le 8 de pique

Au final, après un nombre fini de défaites, soit la machine va abandonner dès le départ, soit elle va se mettre à gagner systématiquement. Dans notre cas par exemple, la machine va perdre au maximum 12 fois et dispose d’une stratégie gagnante qu’elle va construire par échecs successifs.

 

Figure 12 :
État final de l’activité

Figure 13 :
État final de l’activité, piles visibles

Extensions

En fonction du temps disponible et de ses objectifs, on peut creuser une ou plusieurs pistes suivantes.

Réfléchir à la méthode d’apprentissage

Pour réfléchir à la méthode d’apprentissage, on peut se permettre de mettre en place l’activité au fur et à mesure pour moins la guider. Au début, seuls les carreaux sont mis en place. La machine ne sait pas jouer, il faut donc qu’elle choisisse combien de cartes prendre. Une stratégie simple peut alors consister à choisir un coup au hasard. On peut ainsi mettre en place un premier tas de 3 cartes (pique, trèfle et cœur) qu’on utilise alors pour tous les coups de la machine.

La deuxième étape consiste à observer que la stratégie va sans doute dépendre du nombre de cartes restantes. En effet, s’il y a une seule carte sur la table, en prendre une est un coup gagnant, mais s’il y a deux cartes sur la table, en prendre une est une mauvaise idée. Cela nous amène à sortir d’autres piles de trois cartes afin d’en avoir une par carreau.
On commence ensuite à jouer une partie, et quand la machine perd (ce qui arrive rapidement puisqu’elle joue au hasard) on pose la question de comment éviter que cela ne se reproduise, et arrive la conclusion qu’il faut enlever des cartes dans les piles. Attention cependant : on n’enlève pas tous les jetons de la partie, juste le dernier. Peut-être qu’on avait bien joué au début et qu’on s’est juste trompé sur la fin.

Réfléchir à l’apprentissage humain

On pourra dresser un parallèle entre cette activité et l’apprentissage humain. Une bonne façon d’apprendre peut correspondre au fait d’entreprendre quelque chose d’un peu difficile, de s’y tromper, puis d’adapter nos actions pour réduire ou éliminer ces erreurs, ceci sans s’attaquer à quelque chose de trop difficile qui décourage et pour lequel quoi que nous faisions on est toujours en échec. C’est un peu comme la machine construite ici qui supprime ses erreurs au fil du temps. De la même manière, ne plus se tromper peut indiquer une utilisation de ses acquis (comme la machine qui a trouvé une stratégie infaillible) et l’absence d’un nouvel apprentissage.

Ainsi, les modèles d’apprentissage machine nous permettent de comprendre un peu mieux comment fonctionne notre cerveau.

Variations du nombre de cartes et du premier joueur

Il est tout à fait possible de changer le nombre de cartes du jeu de Nim. Par exemple, avec un jeu de 54 cartes, on peut rajouter jusqu’à 5 cartes supplémentaires avec le même genre de configuration.

De plus, on peut également essayer de changer l’ordre des joueurs. Dans le cas du jeu à 8 cartes, si la machine commence elle finira par vider la pile de la première carte (car le deuxième joueur a une stratégie gagnante) et finira donc par abandonner dès le départ.

Machine contre machine

On peut également faire jouer deux machines l’une contre l’autre (avec par exemple un deuxième jeu de 32 cartes) en faisant commencer les machines chacune leur tour. Peu importe quelle machine commence car dans la stratégie, ce qui compte c’est le nombre de cartes qui restent sur la table, pas ce qui a été joué avant. A chaque partie une des machines va perdre et donc apprendre de son erreur en enlevant une carte. Au bout d’un moment, quand elles auront bien affiné leur stratégie, les actions effectuées par les machines seront toujours les mêmes.

Récompenser les victoires plutôt que sanctionner les défaites

Au lieu d’enlever des cartes quand la machine perd, on peut choisir d’en ajouter quand elle gagne. Cela correspond à la version présentée par Malika More et Florent Madelaine citée en introduction. Pour cela il faut bien plus qu’un seul jeu de cartes. On joue une partie, si on perd on remet chaque carte dans sa pile d’origine, et si on gagne on remet dans chaque pile la carte piochée, plus une autre de même couleur. Cela permet de donner plus de chances de jouer les coups qui nous ont déjà permis de gagner, et d’augmenter nos chances de gagner à chaque coup.
Par exemple dans la pile correspondant à trois cartes restantes, il y a au début 3 cartes, une de chaque couleur, mais après quelques parties le nombre de cartes de couleur correspondant à la valeur 3 va augmenter dans la pile, et nos chances de gagner quand il y a 3 cartes aussi. Par contre, si l’adversaire sait repérer le dernier coup gagnant, la pile correspondant à 4 cartes restantes ne sera jamais alimentée de nouvelles cartes, laissant systématiquement une chance égale à chaque coup d’être joué.
La différence entre cette version et celle développée dans les sections précédentes est, que dans notre cas, si une telle stratégie existe, on trouve forcément la stratégie gagnante et la machine va finir par devenir infaillible. Si au contraire il n’y a pas de stratégie gagnante, la machine va finir par abandonner dès le départ. Dans l’autre cas (la version qui fait l’objet de cette extension) au fil des parties on joue de mieux en mieux, mais on peut perdre de temps en temps, et la machine va jouer toutes les parties sans abandonner (et donc pouvoir avec un peu de chance gagner si son adversaire se trompe).

C’est de l’informatique ?

Cette activité s’intéresse à un champ de l’informatique qu’on appelle l’apprentissage machine. Il s’agit d’une version très simplifiée d’un type d’apprentissage machine : l’apprentissage par renforcement. Elle illustre bien que la machine peut apprendre une stratégie que l’humain ne connaissait pas au départ sans disposer de l’intelligence nécessaire à l’humain pour la découvrir. Finalement, bien qu’une stratégie précise se construise au fur et à mesure, la machine n’a réalisé que des étapes élémentaires. L’intelligence artificielle aujourd’hui correspond à des algorithmes qui “appliquent sans comprendre” des règles données au départ pour leur permettre de résoudre des tâches spécifiques, comme c’est le cas ici avec l’objectif de trouver la meilleure stratégie possible pour gagner au jeu de Nim.

Une activité à faire partout !

Mon objectif via cette activité est de permettre de réduire grandement le matériel nécessaire à sa réalisation. Un jeu de cartes tient dans une simple poche, mais peut permettre de faire de nombreuses activités, comme celle présentée ici. En réduisant le matériel nécessaire, on s’autorise à y avoir facilement accès pour pouvoir faire ce genre d’activité instructive à tout moment !

Aussi, nous avons choisi le jeu de 32 cartes grâce à sa facilité d’accès, mais l’activité peut être recréée avec autre chose, par exemple d’autres types de cartes. Il suffit de respecter les conditions suivantes :

• 8 éléments permettant de représenter l’action prendre 1 objet;
• 7 éléments permettant de représenter l’action prendre 2 objets;
• 6 éléments permettant de représenter l’action prendre 3 objets;
• 8 objets (allumettes, cartes etc.) permettant de jouer au jeu de Nim.

Par exemple, dans le cas d’autres jeux de cartes, il faut identifier 3 types de cartes pour les 3 actions, et les cartes restantes retournées peuvent être utilisées pour jouer au jeu de Nim. La figure 14  montre une configuration de l’activité réalisée avec les cartes d’un autre type de jeu de cartes.

 

Figure 14 :
L’activité préparée avec un autre jeu de cartes. les cartes nommées marais font prendre une carte, les cartes nommées plaine font prendre 2 cartes et les autres font prendre 3 cartes. Les cartes retournées servent au jeu de Nim.

PDF view