Jeux de Nim : encyclopédie mathématiques
Cet article est issu de l'encyclopédie libre Wikipedia.| 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 | ||||
|
|||||
| 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...
Sommaire |
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.
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).
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 :
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.
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.
Cet article est issu de l'encyclopédie libre Wikipedia.