Avant

Le Nim est un jeu de stratégie mathématique pour deux joueurs. Le jeu commence avec plusieurs piles d’objets — traditionnellement des cailloux, des pièces de monnaie ou des allumettes. À tour de rôle, les joueurs retirent un nombre quelconque d’objets d’une même pile (au moins un, jusqu’à la pile entière). Dans la version standard (jeu normal), le joueur qui prend le dernier objet gagne. Dans la variante «misère», le joueur qui est contraint de prendre le dernier objet perd. Le Nim est l'un des jeux les plus fondamentaux de la théorie combinatoire des jeux.

Règles (jeu standard)

1. Le jeu commence avec plusieurs piles, chacune contenant un ou plusieurs objets. Une configuration de départ courante consiste en des piles de 3, 5 et 7 objets.
2. Les deux joueurs jouent à tour de rôle.
3. À chaque tour, un joueur doit retirer au moins un objet d’une seule et même pile. Il peut prendre autant d’objets qu’il le souhaite dans cette pile, jusqu’à la pile entière incluse.
4. Le joueur qui prend le dernier objet de la dernière pile restante gagne.

Règles (variante « Misère »)

Les règles sont les mêmes que ci-dessus, sauf que le joueur contraint de prendre le dernier objet perd.

Stratégies

• Nim-Sum (stratégie XOR) : La clé pour gagner au Nim réside dans la somme binaire (XOR) des tailles de toutes les piles. Si le XOR de toutes les piles est égal à 0, la position est perdante pour le joueur dont c’est le tour (en supposant un jeu parfait de la part de l’adversaire). Si le XOR est différent de zéro, le joueur actuel peut toujours effectuer un coup qui place l'adversaire dans une position où le XOR est égal à zéro.
• Comment calculer le Nim-Sum : Convertissez la taille de chaque pile en binaire, puis effectuez l'opération XOR entre elles. Par exemple : des piles de 3 (011), 5 (101), 7 (111) → XOR = 001 (différent de zéro, le joueur actuel peut gagner).
• Coup gagnant : pour gagner à partir d’une position XOR non nulle, trouvez une pile dont le XOR total devient égal à zéro en retirant certains objets. Il existe toujours au moins une telle pile.
• Stratégie « Misère » : Appliquez la même stratégie XOR que dans le Nim classique, à une exception près : lorsque tous les tas restants en contiennent un seul élément, prenez de manière à laisser un nombre impair de tas (ce qui oblige votre adversaire à prendre le dernier).
• Fin de partie à pile unique : s’il ne reste qu’une seule pile, prenez-la entièrement (jeu normal) ou toutes sauf une (stratégie « Misère »).
• Deux piles égales : s’il y a exactement deux piles de même taille, il s’agit d’une position perdante en jeu normal (XOR = 0). Imitez les coups de votre adversaire jusqu’à la fin de la partie.

Le Nim a des origines très anciennes, même s'il est difficile d'en retracer l'histoire exacte. Des jeux consistant à retirer des objets de piles sont pratiqués depuis des siècles dans de nombreuses cultures. Le nom « Nim » a été inventé par Charles L. Bouton, professeur de mathématiques à l’université de Harvard, qui a publié l’analyse mathématique complète du jeu en 1901 dans un article intitulé « Nim, A Game with a Complete Mathematical Theory ». L’origine du nom est incertaine : il pourrait provenir du mot allemand « nimm » (prendre) ou du mot anglais archaïque « nim » (voler).

La principale découverte de Bouton fut la stratégie gagnante basée sur l’opération XOR, qu’il démontra de manière rigoureuse. Ce fut l’un des premiers jeux à être entièrement résolu mathématiquement, et cela a jeté les bases du domaine de la théorie combinatoire des jeux. Son analyse a montré que l’ensemble du jeu pouvait être réduit à un simple calcul binaire, faisant du Nim l’une des intersections les plus élégantes entre les mathématiques et les jeux.

En 1939, Edward U. Condon, Willard A. Derr et Gerald L. Tawney, chez Westinghouse, construisirent le « Nimatron », une machine électromécanique capable de jouer au Nim. Elle fut exposée à l’Exposition universelle de New York de 1940, où elle remporta environ 90 % des 100 000 parties disputées contre elle, ce qui en fit l’une des toutes premières machines à jouer à des jeux. En 1951, l’ordinateur Nimrod fut conçu spécialement pour jouer au Nim et fut présenté au Festival of Britain, devenant ainsi l’un des tout premiers exemples d’ordinateurs numériques capables de jouer à des jeux.

La théorie mathématique du Nim, en particulier le théorème de Sprague-Grundy (élaboré par Roland Sprague en 1935 et Patrick Grundy en 1939), est devenue le fondement de la théorie combinatoire des jeux. Ce théorème démontre que tout jeu impartial (dans lequel les deux joueurs disposent des mêmes coups) est équivalent à une position de Nim. Cela signifie que la stratégie du Nim peut, en théorie, être appliquée à n’importe quel jeu impartial. Le Nim reste un sujet incontournable dans l’enseignement des mathématiques et de l’informatique et est fréquemment utilisé pour initier les élèves à la théorie des jeux et à l’arithmétique binaire.