Jeux de Nim

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Nim.
Jeux de Nim
jeu de société
Ce jeu appartient au domaine public
Format divers
Joueur(s) 2
Âge à partir de 5 ans
Durée annoncée environ 10 minutes
habileté
physique

 Non
 réflexion
décision

 Oui
générateur
de hasard

 Non
info. compl.
et parfaite

 Oui

Les jeux de Nim sont des jeux très courants, de stratégie pure, à deux joueurs. Ces jeux, dont il existe d'innombrables variantes, se jouent avec des graines, des billes, des jetons, des allumettes ou tout autres objets facilement manipulables...

Histoire[modifier | modifier le code]

Les origines sont probablement très anciennes. Les premières traces sont signalées en Chine sous le nom de fan-tan et connus en Afrique sous le nom tiouk-tiouk[1]. Le nom actuel (tiré du mot allemand nimm qui signifie prends ! mais qui pourrait venir également de Win, gagne en anglais, qu'on peut lire lorsqu'on retourne le mot[2]) a été donné par le mathématicien anglais Charles Leonard Bouton en 1901 qui a trouvé un algorithme permettant le gain. En 1951, un ordinateur, le Nimrod, a été construit, dédié uniquement à sa résolution.

But du jeu[modifier | modifier le code]

Chaque jeu se joue à deux au tour par tour. Le hasard n'intervient pas. Il s'agit en général de déplacer ou de prendre des objets selon des règles qui indiquent comment passer d'une position du jeu à une autre, en empêchant la répétition cyclique des mêmes positions. Le nombre de positions est fini et la partie se termine nécessairement, le joueur ne pouvant plus jouer étant le perdant (ou selon certaines variantes, le gagnant).

Stratégie gagnante[modifier | modifier le code]

Exemple de jeu de Nim. Le but du jeu est de déplacer un jeton d'un sommet à l'autre selon les arêtes indiquées. Le gagnant est celui qui parvient au sommet bleu. Les positions gagnantes à atteindre sont en vert. Depuis un sommet vert, on est obligé d'aller à un sommet rouge perdant ; depuis un sommet rouge, on peut atteindre un sommet vert gagnant. Le joueur qui commence perd.

Les jeux de Nim sont des jeux de duel à somme nulle (deux joueurs, un vainqueur et un perdant, pas de partie nulle possible), équivalents à se déplacer d'un sommet à l'autre d'un graphe orienté sans circuit, les sommets du graphe représentant les diverses positions possibles du jeu, et les arêtes les transitions d'une position à une autre. On montre qu'il existe une stratégie optimale, les diverses positions du jeu se répartissant en deux sous-ensembles, les positions gagnantes et les positions perdantes.

Celles-ci sont définies récursivement comme suit, dans le cas où le joueur qui ne peut plus jouer a perdu :

  • Les positions finales (à partir desquelles on ne peut plus jouer) sont gagnantes, puisque le joueur qui en atteint une empêche son adversaire de jouer et gagne la partie.
  • Une position est perdante s'il existe un coup qui mène à une position gagnante. Si un joueur atteint une position perdante, son adversaire pourra donc parvenir à une position gagnante.
  • Une position non finale est gagnante si, quel que soit le coup que l'on joue, on arrive à une position perdante. Si un joueur parvient à une position gagnante, son adversaire devra aller à une position perdante.

En remontant des positions finales, on peut donc déterminer petit à petit le statut de chaque position. La stratégie optimale consiste alors à se déplacer d'une position gagnante à l'autre.

Nombres de Grundy des positions du jeu de Nim ci-dessus. Les positions gagnantes ont un nombre de Grundy nul.

La détermination des positions gagnantes dans le cas de graphe complexe utilise la notion de nombre de Grundy ou nimber. Celui-ci est défini de la façon suivante :

  • Le nombre de Grundy de la position finale vaut 0.
  • Le nombre de Grundy d'une position donnée est le plus petit entier positif ou nul n'apparaissant pas dans la liste des nombres de Grundy des positions qui suivent immédiatement la position donnée.

Les positions gagnantes sont celles dont le nombre de Grundy est nul. En effet, partant d'une telle position, quel que le soit le coup que l'on joue, on arrive à une position dont le nombre de Grundy est non nul (position perdante). Inversement, partant d'une position perdante, il existe au moins un coup que l'on peut jouer et qui conduit à une position dont le nombre de Grundy est nul (position gagnante).

Exemples[modifier | modifier le code]

De nombreux jeux de Nim se jouent avec un ou plusieurs tas d'objets (des allumettes par exemple), chaque joueur modifiant un ou plusieurs tas selon les règles adoptées.

  • Le jeu de Nim trivial ou (jeu de Nim à un seul tas) est constitué d'un seul tas d'allumettes, chaque joueur prenant le nombre d'allumettes qu'il veut. La stratégie gagnante consiste évidemment à prendre toutes les allumettes. Le nombre de Grundy d'une position est simplement le nombre d'allumettes de ce tas.
  • Une version moins triviale de ce jeu consiste à enlever 1, 2 ou 3 objets. Le vainqueur est celui qui peut jouer en dernier. Pour ce jeu, la stratégie est de laisser à chaque fois - si on le peut - un nombre d'objets multiple de 4 : ce sont les positions gagnantes. On constate alors que l'adversaire ne pourra pas en faire autant. Dans la variante de cette version où celui qui prend le dernier objet perd, la stratégie est de laisser un nombre d'objets congru à 1 modulo 4 (c’est-à-dire  : 1, 5, 9, 13...). En fait, on se ramène au cas précédent en considérant que le but du jeu est de prendre l'avant-dernier objet. Dans l'émission de Fort Boyard, un tel jeu constituait un duel contre un maître des jeux (le tas comprenait 20 allumettes).
  • Le jeu de Nim classique ou jeu de Marienbad a été rendu célèbre par un film d'Alain Resnais de 1961, L'année dernière à Marienbad. Il est constitué de plusieurs tas. Chaque joueur choisit le tas de son choix, et dans ce tas, prend le nombre d'allumettes de son choix.
  • Le jeu de Grundy se joue en séparant l'un des tas en deux tas de taille distincte, jusqu'à ce qu'il ne reste que des tas à un objet.
  • Le jeu de Wythoff se joue à deux tas. Chaque joueur réduit d'un même nombre d'objets les deux tas à la fois, ou bien réduit un seul tas du nombre d'objets qu'il veut.

Somme de jeux de Nim[modifier | modifier le code]

Article détaillé : théorème de Sprague-Grundy.

On appelle somme de jeux de Nim le jeu consistant à jouer à plusieurs jeux de Nim à la fois. À tour de rôle, chaque joueur choisit à quel jeu de Nim il veut jouer, et joue un coup de ce jeu. Le jeu somme se termine quand un joueur se trouve dans l'impossibilité de jouer à aucun des jeux de Nim individuels. Ainsi, le jeu de Nim classique ou jeu de Marienbad à n tas est la somme de n jeux de Nim triviaux.

Le théorème de Sprague-Grundy explique comment déterminer les positions gagnantes d'une somme de jeux de Nim, connaissant les positions gagnantes de chaque jeu de Nim individuel. Le nombre de Grundy d'une position quelconque du jeu somme s'obtient en effet en décomposant en binaire les nombres de Grundy des positions de chaque jeu individuel puis en appliquant la fonction OU exclusif aux chiffres de même rang de tous ces nombres. On obtient un nombre binaire dont la valeur est le nombre de Grundy de la position du jeu somme.

Ce phénomène est illustré dans le paragraphe suivant.

Jeu de Nim classique[modifier | modifier le code]

Article détaillé : jeu de Marienbad.

La version classique du jeu de Nim se joue avec plusieurs tas composés chacun de plusieurs jetons, ou pions, ou allumettes. Chaque joueur à son tour peut enlever autant de pions qu'il le souhaite, mais dans un seul tas à la fois. Le gagnant est celui qui retire le dernier pion (la version dite "misère" est celle où le joueur qui prend le dernier pion est le perdant. Elle se déduit aisément de celle-ci).

Ce jeu étant la somme de jeux de Nim triviaux à un seul tas, et le nombre de Grundy de chaque tas individuel étant le nombre de pions dans ce tas, on obtient le nombre de Grundy de la position en exprimant le nombre de pions de chaque pile en binaire et en faisant la somme OU exclusif ou XOR, (notée aussi ⊕) de ces nombres. Une position ayant une valeur de 0 est toujours gagnante pour celui qui y parvient, une position ayant une valeur autre que 0 est toujours perdante.

Prenons l'exemple d'une partie commençant avec trois piles A, B et C, la pile A contenant 3 pions, la pile B 4 pions et la pile C 5 pions. On a alors:

 

  0112    310    Pile A
  1002    410    Pile B
  1012    510    Pile C
  ---
  0102    210    Nim-somme X des piles A, B et C: 3 ⊕ 4 ⊕ 5 = 2

La stratégie gagnante consiste à laisser à son adversaire une position dont la Nim-somme X vaut 0. Cela est toujours possible dans le cas où l'on part d'une position où la Nim-somme est différente de 0, impossible lorsque l'on part d'une position dont la Nim-somme est 0. Ici il suffit de retirer par exemple deux pions du tas A (qui ne contient plus qu'un seul pion) pour arriver à:

 

  0012    110    Pile A
  1002    410    Pile B
  1012    510    Pile C
  ---
  0002    010    Nim-somme X des piles A, B et C: 1 ⊕ 4 ⊕ 5 = 0

Pour trouver de façon systématique le coup à jouer, il suffit de construire la somme XOR de chacune des piles avec le nombre X. Repartons par exemple de nos piles A=3=0112, B=4=1002 et C=5=1012 d'origine et faisons la somme avec le X que nous avions trouvé (X=2=0102):

A ⊕ X = 3 ⊕ 2 = 1 [Car (011) ⊕ (010) = 001 ]
B ⊕ X = 4 ⊕ 2 = 6
C ⊕ X = 5 ⊕ 2 = 7

La seule pile dont la quantité décroit est la pile A. Il faut donc réduire A à ce nombre, c'est-à-dire à 1 seul pion, donc retirer à A deux pions, ce qui est bien ce que nous avions fait.

Une des variantes les plus classiques consiste à limiter le nombre de pions que l'on peut prendre dans chaque pile à un maximum de k pions. La méthode précédente s'applique, à condition de prendre comme nombre de Grundy de chaque tas le nombre d'objets modulo k.

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Lisa Rougetet, Les multiples ancêtres du jeu de Nim, Pour la Science, octobre 2012, n°420, p.80-85
  2. J.-P. Delahaye, Stratégies magiques au pays de Nim, Pour la Science, mars 2009, n° 307, p 88-93