Jeux de Nim

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
modifier

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...

[modifier] Histoire

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. 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^[1]) 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.

[modifier] But du jeu

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).

[modifier] Stratégie gagnante

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 cycle, 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.

La détermination des positions gagnantes dans le cas de graphe complexe utilise la notion de nombre de Grundy ou nimber.

[modifier] Exemple

Une version basique de ce jeu utilise un seul tas d'objets. Chaque joueur à tour de rôle enlève 1, 2 ou 3 objets. Le vainqueur est celui qui peut jouer en dernier. Pour cet exemple, 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.

[modifier] Variantes

• 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. Cependant, le théorème de Sprague-Grundy permet parfois de déterminer les positions gagnantes de jeux de Nim complexes en les ramenant à des jeux de Nim à un seul tas.
• Une illustration de ce phénomène se produit avec le jeu de Marienbad, rendu célèbre par un film d'Alain Resnais de 1961, L'année dernière à Marienbad.
• Dans l'émission de Fort Boyard, une variante à un seul tas constituait un duel contre un maître des jeux (le tas comprenait 20 allumettes).
• Le jeu de Grundy, où le seul coup autorisé consiste à séparer l'un des tas en deux tas de taille distincte.
• Le jeu de Wythoff, qui se joue à deux tas, et où il est possible de réduire d'un même nombre deux tas à la fois.

[modifier] Voir aussi

• Théorème de Sprague-Grundy

[modifier] Notes et références