Les jeux combinatoires à la fête de la science

Approche kinesthésique du jeu de Nim
mardi 8 décembre 2015
par  Alain BUSSER , Florian TOBÉ

Deux catégories de jeux combinatoires ont été présentés à la fête de la science 2015 :

  1. les jeux de Nim joués directement sur le graphe du jeu ;
  2. les jeux de poursuite simples comme le jeu du lièvre et du chien et une variante décrite par Edouard Lucas à la fin du XIXe siècle.

Cet article est donc décomposé en deux parties, chacune d’entre elles consacrée à un de ces jeux.

Voici les jeux à télécharger, les pions n’étant pas encore fournis avec ; les versions html peuvent aussi être téléchargées en-dessous des pdf, mais on peut aussi s’en servir pour jouer en ligne.

jeu de la soustraction soustrais un carré chiens et tang
PDF - 388.3 ko
PDF - 395.2 ko
PDF - 1.7 Mo
HTML - 78.5 ko
jeu de la soustraction
cliquer-glisser le pion pour jouer
HTML - 72.9 ko
soustrais un carré
cliquer-glisser le pion pour jouer
HTML - 22.9 ko
chiens et tang
pour jouer un pion, le glisser sur l’écran

Jeux de Nim

L’article wikipedia sur les jeux de Nim montre un exemple de graphe du jeu, avec des couleurs différentes pour les positions gagnantes et les positions perdantes. La légende de ce graphe dit que « Le but du jeu est de déplacer un jeton d’un sommet à l’autre selon les arêtes indiquées ». Le principe est alors repris en dessinant un graphe et en laissant les joueurs glisser un pion [1] sur le graphe.

Note : Pour trouver la stratégie gagnante, il faut colorier ou numéroter les cases, ce qui n’a pas été fait ici ; mais la numérotation implicite est faite en remontant depuis la case d’arrivée, laquelle est numérotée 0.

Voilà comment on peut avancer de deux cases, en faisant glisser le pion le long d’une arête rouge :

ou de trois cases, en faisant glisser le pion le long d’une arête bleue :

La règle du jeu :

Et si on veut jouer en ligne, voici le jeu :

On constate que si on est à 1, 2 ou 3 cases de l’arrivée, on gagne (des flèches permettant de faire le parcours). Le coup joué ci-dessous est donc perdant puisqu’il finit à 3 (qui est gagnant pour l’adversaire, en jouant le bleu) :

Pourtant il était possible de gagner, en ne jouant pas le rouge (2 cases) mais le mauve (1 case) ; dans ce cas l’adversaire ne pouvait pas gagner mais ne pouvait pas faire autrement que mettre le pion dans une position gagnante.

D’ailleurs la mine réjouie de l’adversaire en dit long :

Rapidement les enfants comprennent que cette case située à 4 unités de l’arrivée est gagnante s’ils y mènent le pion. Au point que la partie s’arrête là et plus à l’arrivée. Il est plus rare que l’on comprenne que du coup la case située à 8 unités de l’arrivée est aussi gagnante puisqu’en y menant le pion, on peut au coup suivant atteindre la case gagnante située à 4 unités :

Personne ou presque n’est allé jusqu’à la constatation que la case 12 aussi est gagnante, pour les raisons exposées ci-dessus

Et depuis la case 14, on peut donc gagner en jouant le rouge pour aller vers la case 12 :

Ôtez un carré

Cette variante vient des jeux mathématiques du Monde (4 mars 1997) :

Deux joueurs disposent d’un tas d’alumettes. Chacun, à son tour de rôle, ôte un certain nombre, non nul, d’allumettes du tas, ce nombre ôté devant impérativement être un carré : 1, 4, 9, 16, 25 ...
Le joueur enlevant la dernière allumette a gagné.

Dans le graphe du jeu,

  • les arêtes mauves représentent la soustraction de 1 (qui est un carré) ;
  • les arêtes rouges représentent la soustraction de 4 ;
  • les arêtes bleues représentent la soustraction de 9 ;
  • et les arêtes vertes représentent la soustraction de 16.

Ici, le joueur joue mauve (-1) et gagne puisque 1 est un carré :

Si on est sur la case 2, on perd puisque le seul coup qu’on puisse jouer est 1 (mauve) ce qui mène à la position gagnante (pour l’adversaire) vue ci-dessus. Dans la vidéo ci-dessous, l’un des joueurs joue le rouge (-4) pour amener le pion à la case 2 et effectivement, l’autre joueur perd (et s’en vite compte d’ailleurs) :

Voici une partie complète basée sur cette fin (le perdant de tout-à-l’heure prend sa revanche) :

  • La première joue -1 ce qui fait passer de la case 20 à la case 19 ;
  • le second joue -4 (rouge) ce qui fait passer à la case 15 ;
  • la première joue -9 ce qui fait passer à la case 6, et on est dans la situation symétrique de celle de la partie précédente :
  • Le second joueur joue -4 ce qui l’amène à la case 2 ;
  • et les joueurs réalisent alors que le second a gagné, et s’arrêtent de jouer.

Ensuite, pour les raisons vues ci-dessus, la case 3 est gagnante puisque si on y est, en jouant 1 on arrive à la case 2 ce qui, on l’a vu, fait perdre l’adversaire. Ici, en jouant rouge, on arrive à cette case 3 qui fait gagner l’adversaire :

Par contre, comme 4 est un carré, la case 4 est perdante (en suivant l’arête rouge) :

Comme 20=16+4, si le premier joueur joue la flèche verte, il perd puisque cela le mène à la case 4 qui, on l’a vu, est perdante. Certaines parties de débutants sont donc très courtes ! Si le premier joueur joue rouge (-4), c’est pareil, le second gagne en jouant vert (-16).

Semaine des maths

La semaine des maths a été l’occasion de tester deux nouveaux jeux de type Nim :

PDF - 387 ko
Nim sur triangle
PDF - 384.7 ko
Nim sur rectangle

Mais aussi, une petite séance d’algorithmique débranchée, les joueurs ayant décidé de marquer (par pose d’une graine) les cases où ils n’ont pas intérêt à aller parce que celles-ci sont perdantes :

Le jeu « enlève un carré », ainsi marqué, a une stratégie gagnante assez esthétique :

En fait, la notion de case perdante est définie récursivement :

  • La case « arrivée » est gagnante ;
  • Toute case permettant d’aller à une case gagnante, est perdante ;
  • Toute case ne menant qu’à des cases perdantes, est gagnante.

Il est donc nécessaire non seulement d’empêcher d’aller à une case perdante en bloquant celle-ci par une graine, mais aussi de marquer d’une autre manière les cases gagnantes. Par exemple en plaçant d’un côté ou de l’autre, la graine, selon que la case est gagnante ou perdante :

Cette recherche « débranchée » de stratégie gagnante a été efficace avec le jeu sur graphe rectangulaire :

Et on a même vu du calcul parallèle (carrés et rectangle en même temps) :


Jeux de poursuite

Le jeu militaire est, d’après Edourd Lucas, un jeu à la mode à la fin du XIXe siècle, inventé par un militaire (d’où son nom) retraité, et basé sur un vocabulaire issu de l’armée. En fait il ne s’agit que d’une variante du jeu du lièvre et du chien, un jeu médiéval qui lui-même est une simplification des jeux de tigre qu’on trouve dans toute l’Asie, mais aussi une variante d’un jeu dit « de l’ours » que l’on jouait dans la Rome antique. Les jeux asiatiques, dont les plateaux sont de remarquables œuvres d’art, permettent de prendre des pions comme aux dames, ce qui les rapprocherait plus du fanorona. Par contre, le jeu de go est basé sur la même idée d’encercler un pion.

En 1887, dans la revue La Nature, Edouard Lucas analyse le jeu militaire, qu’il décrit comme inventé peu avant par un militaire retraité appelé Louis Dyen. Cette analyse du jeu est intéressante parce que Lucas dénombre les positions possibles du jeu et fait un arbre du jeu (« tableau général des parties » à la dernière page). Cet article vaut la peine qu’on le lise ne serait-ce que pour profiter du style ironique de Lucas. Le voici en pdf :

PDF - 431 ko

La règle du jeu est plutôt simple :

Pour jouer, on déplace un de ses pions vers une place verte disponible (qui ne soit pas déjà occupée), sans quitter le chemin (en marron). Le joueur qui a les chiens choisit à chaque tour, lequel des chiens ils veut bouger, mais les chiens n’ont pas le droit de reculer. Le but du jeu est, pour les chiens, de coincer le tang, et pour le tang, d’échapper aux chiens en passant derrière eux.

Comme le joueur qui joue en premier n’a qu’un choix possible, on peut faire commencer les chiens (« tours ») et prendre comme position de départ, celle où le pion a déjà avancé. Cela permet de rapidement s’exercer à ce jeu en ligne :

L’affirmation « les blancs gagnent toujours en une douzaine de coups, au maximum » signifie qu’il existe une stratégie gagnante pour les chiens (« blancs »). Pour autant, celle-ci n’est pas facile à trouver ni retenir et à la fête de la science, les parties gagnées et perdues étaient approximativement équiréparties.

Pour éviter de perturber les enfants avec des histoires de stratégie militaire, on a fait un peu « couleur locale » avec des chiens cherchant à bloquer dans son terrier, un tenrec ecaudatus (« tang », en créole ; en effet le chien n’attaque pas le tang mais ne fait que l’acculer dans son terrier). Le succès de ce jeu a été tel qu’il a fallu improviser un second jeu de pions :

Le but du jeu, pour les chiens, est de créer un mur bloquant le tang :

Pour le tang, évidemment, le but est d’échapper à ce mur en se glissant dans une faille de celui-ci. Mais la perception des diagonales n’est pas toujours parfaite ce qui amène certains enfants à « tricher » (le second coup ci-dessous est interdit puisqu’il n’y a pas de chemin en diagonale) :

Une stratégie qui apparaît vite chez les maîtres-chiens consiste à construire puis propager un mur, dès le début de la partie. Voici un début de partie typique :

Et voici une partie presque complète, qui se solde sans grosse surprise par une défaite du tang (à droite) :

Dans la situation suivante, où les chiens jouent, ils peuvent gagner mais à condition de bien s’y prendre :

Voici une partie où le tang gagne (erreur des chiens) :

Une autre où le tang peut s’échapper par le haut (puis la gauche, les chiens n’ayant pas le droit d’aller à gauche) :

Plusieurs enfants ont voulu essayer la version médiévale où le tang part de l’autre bout. Là, si ce sont les chiens qui commencent, ils gagnent plus difficilement (en essayant un coup interdit à la fin) :

Si c’est le tang qui commence ça donne ça :

Qui va gagner ?

Une technique classique quand on joue c’est de regarder non le plateau de jeu, mais le visage de l’adversaire, dans l’espoir d’y lire ses intentions :

Pour finir, quelques exercices (on peut se servir de la version en ligne ci-dessus comme support de raisonnement) :

  • Chaque joueur a joué trois coups depuis de début le partie ; lesquels ? Qui gagne ?

  • Le tang joue et gagne. Est-il possible que la position initiale des chiens ait été à gauche de la photo ?

  • Quels sont les coups qui ont été joués pour aboutir à cette position ?

Pour aller plus loin, voici un autre jeu de poursuite, sur un graphe plus équilibré ; on peut y jouer en ligne :

HTML - 22.5 ko
jeu de poursuite
glisser un pion pour le jouer

Bibliogaphie/Webographie


[1plus facile à déplacer qu’un jeton


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 24 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

164 aujourd'hui
292 hier
2063254 depuis le début
17 visiteurs actuellement connectés