Jeux de Nim

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. Expliquons en détail la version utilisée dans l'émission de Fort Boyard, un tel jeu constitue le duel des bâtonnets contre un maître des ténèbres (le tas comprend 20 allumettes). Ce jeu consiste à enlever 1, 2 ou 3 bâtonnets à chaque tour. Le vainqueur est celui qui peut jouer en dernier. Voici un exemple de partie : 20 -> 19 -> 16 -> 13 -> 12 -> 10 -> 8 -> 5 -> 4 -> 3 -> 0

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.

D'autres variantes existent :

• On peut imaginer une variante de la version de Fort Boyard 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.
• 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 tailles distinctes, jusqu'à ce qu'il ne reste que des tas à un ou deux objets.
• 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.

Aussi, le jeu de Nim trivial (ou jeu de Nim à un seul tas) est constitué d'un seul tas d'allumettes. Quand c'est son tour, chaque joueur prend le nombre d'allumettes qu'il veut. La stratégie gagnante pour le premier joueur consiste à prendre toutes les allumettes. Le jeu est trivial et a un intérêt théorique.

Les origines sont probablement très anciennes. Les premières traces sont signalées en Chine sous le nom de fan-tan, il est connu en Afrique sous le nom tiouk-tiouk[1]. Le nom actuel provient du mot allemand Nimm qui signifie « prends ! » mais il pourrait venir également du mot anglais WIN (« gagne !»), car en inversant graphiquement le mot WIN devient NIM[2]. Le nom actuel a été donné au jeu par le mathématicien anglais Charles Leonard Bouton en 1901 lorsqu'il a trouvé un algorithme permettant le gain.

A l'exposition universelle de New York en 1940, Westinghouse Electric Corporation présente une machine appelée Nimatron, qui joue au jeu de Nim[3]. Du 11 mai 1940 au 27 octobre 1940, seul un petit nombre de participants ont pu battre la machine ; ceux qui gagnèrent obtinrent une pièce de monnaie indiquant "Nim Champ"[4]^,[5]. En 1951, le Nimrod, reprenant le concept du Nimatron, est un ordinateur qui permet de jouer au jeu de Nim. Cependant, il a pour but initial de vanter la conception d'ordinateur par Ferranti et ses compétences en matière de programmation, plutôt que de divertir^{[réf. nécessaire]}.

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

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

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.

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=011₂, B=4=100₂ et C=5=101₂ d'origine et faisons la somme avec le X que nous avions trouvé (X=2=010₂):

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

En 1977, le manuel de la calculatrice programmable HP-25 proposait un jeu appelé Nimb. La partie démarrait avec 15 allumettes et chaque joueur pouvait en enlever 1, 2 ou 3 à son tour. Celui qui prenait la dernière avait perdu. Le programme, de 49 pas, jouait second et appliquait une stratégie gagnante qui n'autorisait aucune erreur chez son adversaire[6].