jeu de Nim

Trois piles de 3, 4 et 5 jetons sont posées sur une table. À son tour, chaque joueur choisit une seule pile et y retire autant de jetons qu'il veut. Celui qui prend le dernier gagne.

Le nombre total de jetons ne suffit pas à décider du bon coup : leur répartition compte. En écrivant 3, 4 et 5 en base 2, puis en comparant chaque colonne, on repère une position équilibrée. Le but est de laisser cet équilibre à l'adversaire après chacun de ses tours.

Le jeu de Nim, d'origine très ancienne et peut-être chinoise, appartient aux jeux combinatoires impartiaux : deux joueurs jouent à tour de rôle, connaissent toute la position, ne subissent aucun hasard et disposent des mêmes coups depuis une position donnée. Le nombre de positions est fini. Le nom « Nim » et la première analyse mathématique rigoureuse de la version classique sont dus à Charles Leonard Bouton, dans un article de 1901.

Dans la version à une rangée, un joueur retire au plus un nombre fixé de pions, noté p, avec p au moins égal à 2. Le dernier pion fait gagner. Les positions perdantes sont les multiples de p + 1 : depuis une telle quantité, le second joueur peut répondre pour que les deux prises successives totalisent p + 1. Dans la version à plusieurs rangées, un coup retire un nombre quelconque de pions dans une seule rangée, et prendre le dernier pion fait gagner. On écrit les effectifs en base 2 et l'on calcule leur ou-exclusif, nommé nim-sum. Une position non vide de nim-sum nul est perdante si l'adversaire joue parfaitement ; sinon, il existe un coup qui rend le nim-sum nul. Le nimber fournit le nombre associé à une position et le théorème de Sprague-Grundy étend cette analyse aux jeux impartiaux.

Les variantes changent les coups autorisés et donc le critère gagnant. Dans le jeu de Wythoff, on retire des jetons d'une pile ou le même nombre des deux piles ; les positions stratégiques font intervenir le nombre d'or et les suites de Beatty. Dans le Nim de Fibonacci, le premier joueur laisse au moins un pion, puis chaque prise vaut au plus le double de la précédente. Sa stratégie utilise le théorème de Zeckendorf : tout entier positif s'écrit de manière unique comme somme de nombres de Fibonacci non consécutifs. En convention misère, prendre le dernier pion fait perdre au lieu de faire gagner.

La position comporte trois piles de 3, 4 et 5 jetons. Un coup doit retirer au moins un jeton d'une seule pile, et le joueur qui prend le dernier jeton gagne.

1. Écrivons les tailles sur trois bits : 3 s'écrit 011, 4 s'écrit 100 et 5 s'écrit 101.
2. Appliquons le ou-exclusif colonne par colonne : un bit vaut 1 si le nombre de bits égaux à 1 est impair. Le nim-sum, noté par le symbole ⊕, vaut : $3\oplus 4\oplus 5=23\; \backslash oplus\; 4\; \backslash oplus\; 5\; =\; 2$. La position n'est donc pas équilibrée.

3. Réduisons la pile de 3 à 1 en retirant 2 jetons. Les nouvelles tailles sont 1, 4 et 5.
4. Contrôlons le résultat : $1\oplus 4\oplus 5=01\; \backslash oplus\; 4\; \backslash oplus\; 5\; =\; 0$. Le coup laisse donc à l'adversaire une position de nim-sum nul.

Le contrôle est refaisable sans formule : dans les écritures 001, 100 et 101, chaque colonne contient un nombre pair de chiffres 1. Quelle que soit la pile ensuite modifiée par l'adversaire, ce pairage est rompu ; un nouveau coup peut alors rétablir un nim-sum nul.

Avec une seule rangée et une prise limitée à p jetons, on regarde le reste de la division du nombre de jetons par p + 1. S'il n'est pas nul, on retire ce reste ; s'il est nul, aucun coup gagnant immédiat n'existe contre un jeu parfait.

Avec plusieurs piles et une prise libre dans une seule pile, le critère des multiples ne convient plus. On convertit chaque taille en base 2, on calcule le nim-sum, puis on cherche une réduction de pile qui l'annule.

Avant tout calcul, il faut lire la règle de victoire et les coups autorisés. Si le dernier coup fait perdre, ou si l'on peut toucher deux piles comme dans le jeu de Wythoff, la stratégie du Nim classique ne s'applique pas telle quelle.

Le nimber et le nim-sum ne désignent pas la même chose. Le nimber est le nombre associé à une position d'un jeu impartial ; le nim-sum est l'opération de ou-exclusif utilisée pour combiner ces nombres. Pour les piles de tailles 3, 4 et 5, les trois valeurs sont combinées par nim-sum et donnent 2 : ce résultat n'est pas le nimber d'une pile supplémentaire.

Convention misère. Si le joueur qui prend le dernier pion perd, le critère du nim-sum du jeu normal demande un traitement particulier en fin de partie. Le symptôme est l'arrivée à des piles ne contenant plus qu'un jeton : il faut alors raisonner sur la parité du nombre de piles restantes.

Une rangée bornée. Le critère des multiples de p + 1 suppose qu'une prise contient de 1 à p pions et que p est au moins égal à 2. Si la borne ou le droit de prendre le dernier pion change, il faut reconstruire les positions perdantes avec la règle réelle.

Somme ordinaire trompeuse. Dans la position 3, 4 et 5, le total usuel vaut 12, mais il ne donne pas le coup gagnant. Il faut utiliser le ou-exclusif binaire, qui vaut 2, puis réduire une seule pile pour obtenir un nim-sum nul.

Variante prise pour le jeu classique. Dans Wythoff, un même coup peut retirer autant de jetons aux deux piles ; dans le Nim de Fibonacci, la prise maximale dépend du coup précédent. Dès qu'un coup légal ne correspond plus à une réduction libre d'une seule pile, le critère classique ne doit pas être transplanté.

Le jeu de Nim sert de porte d'entrée à une théorie plus large : une position peut recevoir une valeur, puis être combinée à d'autres positions sans rejouer tout l'arbre des coups.

Le glossaire nimber précise le nombre associé à une position et son rôle dans la comparaison des jeux impartiaux.

Le théorème de Sprague-Grundy montre comment l'analyse de Nim s'étend aux positions finies des jeux impartiaux.

La théorie des jeux combinatoires replace Nim parmi les jeux à information complète, sans hasard et à coups alternés.