Nim

Nim est un jeu de stratégie mathématique dans lequel deux joueurs retirent à tour de rôle (ou « nimming ») des objets de tas ou de piles distincts. À chaque tour, un joueur doit retirer au moins un objet et peut retirer n'importe quel nombre d'objets à condition qu'ils proviennent tous du même tas ou de la même pile. Selon la version jouée, le but du jeu est soit d'éviter de prendre le dernier objet, soit de prendre le dernier objet.

Nim est fondamental pour le théorème de Sprague-Grundy , qui dit essentiellement que tout jeu impartial est équivalent à un jeu Nim avec une seule pile.

Des variantes du nim sont pratiquées depuis l'Antiquité. Le jeu serait originaire de Chine — il ressemble beaucoup au jeu chinois de jiǎn-shízi (捡石子), ou « ramasser des pierres » — mais l'origine est incertaine ; les premières références européennes au nim datent du début du XVIe siècle. Son nom actuel a été inventé par Charles L. Bouton de l' Université Harvard , qui a également développé la théorie complète du jeu en 1901, mais les origines du nom n'ont jamais été entièrement expliquées. L' Oxford English Dictionary fait dériver le nom du verbe allemand nimm , qui signifie « prendre ».

À l' Exposition universelle de New York de 1939, Westinghouse présenta une machine, le Nimatron , qui jouait au nim. Du 11 mai au 27 octobre 1940, seules quelques personnes réussirent à battre la machine au cours de cette période de six mois ; si elles y parvenaient, on leur présentait une pièce sur laquelle était écrit « Nim Champ ». C'était également l'un des premiers jeux électroniques informatisés. Ferranti construisit un ordinateur jouant au nim qui fut exposé au Festival of Britain en 1951. En 1952, Herbert Koppel, Eugene Grant et Howard Bailer, ingénieurs de la WL Maxson Corporation, développèrent une machine pesant 23 kilogrammes (50 lb) qui jouait au nim contre un adversaire humain et gagnait régulièrement. Une machine à jouer au nim a été décrite à partir de jouets en bois .

Le jeu de nim était le sujet de la chronique Mathematical Games de Martin Gardner de février 1958 dans Scientific American . Une version de nim est jouée – et a une importance symbolique – dans le film de la Nouvelle Vague française L'Année dernière à Marienbad (1961).

Nim est généralement joué comme un jeu de misère , dans lequel le joueur qui prend le dernier objet perd. Nim peut également être joué comme un jeu de « jeu normal » dans lequel le joueur qui prend le dernier objet gagne. Que ce soit dans le jeu normal ou dans un jeu de misère, lorsqu'il y a exactement un tas avec au moins deux objets, le joueur qui prend ensuite peut facilement gagner. Si cela supprime tous les objets ou tous les objets sauf un du tas qui en contient deux ou plus, alors aucun tas n'aura plus d'un objet, donc les joueurs sont obligés de retirer en alternance exactement un objet jusqu'à la fin du jeu. Si le joueur laisse un nombre pair de tas non nuls (comme le ferait le joueur dans le jeu normal), le joueur prend en dernier ; s'il laisse un nombre impair de tas (comme le ferait le joueur dans le jeu de misère), alors l'autre joueur prend en dernier.

Le jeu normal se joue entre deux joueurs et se joue avec trois tas d'un nombre quelconque d'objets. Les deux joueurs prennent à tour de rôle un nombre quelconque d'objets dans l'un des tas. Le but est d'être le dernier à prendre un objet. Dans le jeu de misère, le but est plutôt de s'assurer que l'adversaire soit obligé de prendre le dernier objet restant.

L'exemple suivant d'un jeu normal est joué entre les joueurs fictifs Bob et Alice , qui commencent avec des tas de trois, quatre et cinq objets.

La stratégie pratique pour gagner au jeu de nim consiste pour un joueur à placer l'autre dans l'une des positions suivantes, et à chaque tour successif, il devrait pouvoir faire l'une des plus petites positions. Seul le dernier coup change entre la misere et le jeu normal.

Pour les généralisations, n et m peuvent avoir n’importe quelle valeur > 0, et ils peuvent être identiques.

Le nim de jeu normal (ou plus précisément le système de nimbers ) est fondamental pour le théorème de Sprague-Grundy , qui dit essentiellement que dans le jeu normal, chaque jeu impartial est équivalent à un tas nim qui donne le même résultat lorsqu'il est joué en parallèle avec d'autres jeux impartiaux de jeu normal (voir somme disjonctive ).

Bien que tous les jeux normaux et impartiaux puissent se voir attribuer une valeur nim, ce n'est pas le cas selon la convention de misère. Seuls les jeux modérés peuvent être joués en utilisant la même stratégie que le nim de misère.

Nim est un cas particulier d'un jeu poset où le poset est constitué de chaînes disjointes (les tas).

Le graphe d'évolution du jeu de nim à trois tas est le même que les trois branches du graphe d'évolution de l' automate d'Ulam–Warburton .

Nim a été résolu mathématiquement pour n'importe quel nombre de tas et d'objets initiaux, et il existe un moyen facilement calculé pour déterminer quel joueur gagnera et quels coups gagnants sont ouverts à ce joueur.

La clé de la théorie du jeu est la somme numérique binaire des tailles de tas, c'est-à-dire la somme (en binaire), négligeant tous les reports d'un chiffre à l'autre. Cette opération est également connue sous le nom de « xor binaire » ou « addition vectorielle sur GF (2) » (addition binaire modulo 2). Dans la théorie des jeux combinatoires, on l'appelle généralement la nim-somme , comme on l'appellera ici. La nim-somme de x et y s'écrit x ⊕ y pour la distinguer de la somme ordinaire, x + y . Un exemple de calcul avec des tas de taille 3, 4 et 5 est le suivant :

Décimal binaire 011 2 3 10 Tas A 100 2 4 10 Tas B 101 2 5 10 Tas C --- 010 2 2 10 La somme nim des tas A, B et C, 3 ⊕ 4 ⊕ 5 = 2 

Une procédure équivalente, souvent plus facile à réaliser mentalement, consiste à exprimer les tailles de tas sous forme de sommes de puissances distinctes de 2, à annuler les paires de puissances égales, puis à ajouter ce qui reste :

3 = 0 + 2 + 1 = 2 1 Tas A 4 = 4 + 0 + 0 = 4 Tas B 5 = 4 + 0 + 1 = 4 1 Tas C -------------------------------------------------- ------------------- 2 = 2 Que reste-t-il après avoir annulé les 1 et les 4 

En jeu normal, la stratégie gagnante consiste à terminer chaque coup avec une somme nim de 0. C'est toujours possible si la somme nim n'est pas nulle avant le coup. Si la somme nim est nulle, alors le joueur suivant perdra si l'autre joueur ne fait pas d'erreur. Pour savoir quel coup faire, soit X la somme nim de toutes les tailles de tas. Trouvez un tas où la somme nim de X et de la taille du tas est inférieure à la taille du tas ; la stratégie gagnante consiste à jouer dans un tel tas, en réduisant ce tas à la somme nim de sa taille d'origine avec X. Dans l'exemple ci-dessus, en prenant la somme nim des tailles, on obtient X = 3 ⊕ 4 ⊕ 5 = 2 . Les sommes nim des tailles de tas A=3, B=4 et C=5 avec X=2 sont

A ⊕ X = 3 ⊕ 2 = 1 [Puisque (011) ⊕ (010) = 001 ]

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

Le seul tas qui est réduit est le tas A, donc le coup gagnant est de réduire la taille du tas A à 1 (en supprimant deux objets).

Dans un cas particulièrement simple, s'il ne reste que deux tas, la stratégie consiste à réduire le nombre d'objets dans le plus grand tas pour que les tas soient égaux. Après cela, quel que soit le mouvement effectué par l'adversaire, le joueur peut effectuer le même mouvement sur l'autre tas, garantissant ainsi qu'il prendra le dernier objet.

Dans le jeu de misère, la stratégie nim est différente uniquement lorsque le mouvement de jeu normal ne laisse que des tas de taille 1. Dans ce cas, le mouvement correct est de laisser un nombre impair de tas de taille 1 (dans le jeu normal, le mouvement correct serait de laisser un nombre pair de ces tas).

Ces stratégies pour le jeu normal et le jeu de misère sont les mêmes jusqu'à ce que le nombre de tas avec au moins deux objets soit exactement égal à un. À ce stade, le joueur suivant retire tous les objets (ou tous sauf un) du tas qui en contient deux ou plus, de sorte qu'aucun tas ne contienne plus d'un objet (en d'autres termes, tous les tas restants contiennent exactement un objet chacun), les joueurs sont donc obligés de retirer en alternance exactement un objet jusqu'à la fin du jeu. Dans le jeu normal, le joueur laisse un nombre pair de tas non nuls, donc le même joueur prend le dernier ; dans le jeu de misère, le joueur laisse un nombre impair de tas non nuls, donc l'autre joueur prend le dernier.

Dans un jeu de misère avec des tas de tailles trois, quatre et cinq, la stratégie serait appliquée comme ceci :

La solidité de la stratégie optimale décrite ci-dessus a été démontrée par C. Bouton.

Théorème . Dans une partie nim normale, le joueur qui fait le premier coup a une stratégie gagnante si et seulement si la somme nim des tailles des tas n'est pas nulle. Sinon, le deuxième joueur a une stratégie gagnante.

Preuve : Notez que la somme nim (⊕) obéit aux lois associatives et commutatives habituelles de l'addition (+) et satisfait également une propriété supplémentaire, x ⊕ x = 0.

Soient x ₁ , ..., x _n les tailles des tas avant un déplacement, et y ₁ , ..., y _n les tailles correspondantes après un déplacement. Soient s = x ₁ ⊕ ... ⊕ x _n et t = y ₁ ⊕ ... ⊕ y _n . Si le déplacement a été effectué dans le tas k , nous avons x _i = y _i pour tout i ≠ k , et x _k > y _k . Par les propriétés de ⊕ mentionnées ci-dessus, nous avons

Le théorème découle par récurrence sur la longueur du jeu de ces deux lemmes.

Lemme 1. Si s = 0, alors t ≠ 0 quel que soit le mouvement effectué.

Preuve : S'il n'y a pas de déplacement possible, alors le lemme est vide de sens (et le premier joueur perd la partie normale par définition). Sinon, tout déplacement dans le tas k produira t = x _k ⊕ y _k de (*). Ce nombre est différent de zéro, car x _k ≠ y _k .

Lemme 2. Si s ≠ 0, il est possible de faire un déplacement tel que t = 0.

Preuve : Soit d la position du bit non nul le plus à gauche (le plus significatif) dans la représentation binaire de s , et choisissons k tel que le d ième bit de x _k soit également non nul. (Un tel k doit exister, car sinon le d ième bit de s serait 0.) Alors, en posant y _k = s ⊕ x _k , nous affirmons que y _k < x _k : tous les bits à gauche de d sont les mêmes dans x _k et y _k , le bit d décroît de 1 à 0 (diminuant la valeur de 2 ^d ), et tout changement dans les bits restants sera au plus égal à 2 ^d −1. Le premier joueur peut ainsi faire un coup en prenant x _k − y _k objets du tas k , puis

t = s ⊕ x k ⊕ y k (par (*)) = s ⊕ x k ⊕ ( s ⊕ x k ) = 0. 

La modification pour le jeu de misère est démontrée en notant que la modification se produit d'abord dans une position qui ne possède qu'un seul tas de taille 2 ou plus. Notez que dans une telle position s ≠ 0, et donc cette situation doit se produire lorsque c'est le tour du joueur qui suit la stratégie gagnante. La stratégie de jeu normale est que le joueur réduise ce tas à la taille 0 ou 1, laissant un nombre pair de tas de taille 1, et la stratégie de misère est de faire l'inverse. À partir de ce moment, tous les coups sont forcés.

Dans un autre jeu connu sous le nom de nim (mais mieux appelé jeu de soustraction ), une limite supérieure est imposée au nombre d'objets qui peuvent être retirés en un tour. Au lieu de retirer un nombre arbitraire d'objets, un joueur ne peut en retirer qu'un ou deux ou... ou k à la fois. Ce jeu est généralement joué en pratique avec un seul tas.

L'analyse de Bouton s'applique facilement à la version générale à tas multiples de ce jeu. La seule différence est que, dans un premier temps, avant de calculer les nim-sommes, nous devons réduire les tailles des tas modulo k + 1. Si cela rend tous les tas de taille nulle (dans le jeu misère), le coup gagnant est de prendre k objets d'un des tas. En particulier, dans le jeu idéal à partir d'un seul tas de n objets, le deuxième joueur peut gagner si et seulement si

• 0 = n (mod k + 1) (en jeu normal), ou
• 1 = n (mod k + 1) (en jeu de misère).

Ceci résulte du calcul de la séquence nim de S (1, 2, ..., k ),

d'où découle la stratégie ci-dessus selon le théorème de Sprague-Grundy .

Le jeu « 21 » se joue comme un jeu de misère avec un nombre quelconque de joueurs qui prononcent à tour de rôle un nombre. Le premier joueur dit « 1 » et chaque joueur à son tour augmente le nombre de 1, 2 ou 3, mais ne peut pas dépasser 21 ; le joueur obligé de dire « 21 » perd. Cela peut être modélisé comme un jeu de soustraction avec un tas de 21 − n objets. La stratégie gagnante pour la version à deux joueurs de ce jeu est de toujours dire un multiple de 4 ; il est alors garanti que l'autre joueur devra finalement dire 21 ; donc dans la version standard, où le premier joueur ouvre avec « 1 », il commence par un coup perdant.

Le jeu 21 peut également être joué avec des numéros différents, par exemple « Ajoutez au plus 5 ; perdez sur 34 ».

Un exemple de jeu de 21 dans lequel le deuxième joueur suit la stratégie gagnante :

Une version similaire est le « jeu des 100 » : deux joueurs partent de 0 et ajoutent alternativement un nombre de 1 à 10 à la somme. Le joueur qui atteint 100 gagne. La stratégie gagnante consiste à atteindre un nombre dont les chiffres sont consécutifs (par exemple, 01, 12, 23, 34,...) et à contrôler le jeu en sautant par-dessus tous les nombres de cette séquence. Une fois qu'un joueur atteint 89, l'adversaire ne peut choisir que des nombres de 90 à 99, et la réponse suivante peut dans tous les cas être 100.

Dans une autre variante de nim, en plus de supprimer un nombre quelconque d'objets d'un seul tas, il est permis de supprimer le même nombre d'objets de chaque tas.

Une autre variante du nim est le « nim circulaire », dans lequel un nombre quelconque d'objets sont placés dans un cercle et deux joueurs retirent alternativement un, deux ou trois objets adjacents. Par exemple, en commençant avec un cercle de dix objets,

. . . . . . . . . . 

trois objets sont pris au premier coup

_ . . . . . . . _ _ 

puis trois autres

_ . _ _ _ . . . _ _ 

alors un

_ . _ _ _ . . _ _ _ 

mais alors trois objets ne peuvent pas être retirés en un seul mouvement.

Dans le jeu de Grundy , une autre variante du nim, un certain nombre d'objets sont placés dans un tas initial et deux joueurs divisent alternativement un tas en deux tas non vides de tailles différentes. Ainsi, six objets peuvent être divisés en piles de 5+1 ou 4+2, mais pas 3+3. Le jeu de Grundy peut être joué soit en mode misère, soit en mode jeu normal.

Le Greedy nim est une variante dans laquelle les joueurs sont limités à choisir des pierres uniquement dans la plus grande pile. C'est un jeu impartial fini . Le Greedy nim misère a les mêmes règles que le Greedy nim, mais le dernier joueur capable de faire un mouvement perd.

Soit m le plus grand nombre de pierres dans une pile et n le deuxième plus grand nombre de pierres dans une pile . Soit p _m le nombre de piles ayant m pierres et p _n le nombre de piles ayant n pierres. Il existe alors un théorème selon lequel les positions de jeu avec p _m pair sont des positions P. Ce théorème peut être démontré en considérant les positions où p _m est impair. Si p _m est supérieur à 1, toutes les pierres peuvent être retirées de cette pile pour réduire p _m de 1 et le nouveau p _m sera pair. Si p _m = 1 (c'est-à-dire que le plus grand tas est unique), il y a deux cas :

• Si p _n est impair, la taille du plus grand tas est réduite à n (donc maintenant le nouveau p _m est pair).
• Si p _n est pair, le plus grand tas est entièrement supprimé, laissant un nombre pair de plus grands tas.

Ainsi, il existe un déplacement vers un état où p _m est pair. Inversement, si p _m est pair, si un déplacement est possible ( p _m ≠ 0), alors il doit amener le jeu vers un état où p _m est impair. La position finale du jeu est paire ( p _m = 0). Par conséquent, chaque position du jeu avec p _m pair doit être une position P.

Une généralisation du nim multi-tas a été appelée « nim » ou « nim index- k » par EH Moore , qui l'a analysée en 1910. Dans le nim index- k , au lieu de supprimer des objets d'un seul tas, les joueurs peuvent supprimer des objets d'au moins un mais jusqu'à k tas différents. Le nombre d'éléments qui peuvent être supprimés de chaque tas peut être arbitraire ou limité à r éléments au maximum, comme dans le « jeu de soustraction » ci-dessus.

La stratégie gagnante est la suivante : comme dans un nim multi-tas ordinaire, on considère la représentation binaire des tailles de tas (ou tailles de tas modulo r + 1). Dans un nim ordinaire, on forme la somme XOR (ou somme modulo 2) de chaque chiffre binaire, et la stratégie gagnante est de rendre chaque somme XOR nulle. Dans la généralisation à un nim index- k , on forme la somme de chaque chiffre binaire modulo k + 1.

Là encore, la stratégie gagnante consiste à se déplacer de telle sorte que cette somme soit nulle pour chaque chiffre. En effet, la valeur ainsi calculée est nulle pour la position finale, et étant donnée une configuration de tas pour laquelle cette valeur est nulle, tout changement d'au plus k tas rendra la valeur non nulle. Inversement, étant donnée une configuration de valeur non nulle, on peut toujours prendre dans au plus k tas, soigneusement choisis, de telle sorte que la valeur devienne nulle.

La construction de nim est une variante de nim dans laquelle les deux joueurs construisent d'abord le jeu de nim. Étant donné n pierres et s piles vides, les joueurs, en alternance, placent exactement une pierre dans une pile de leur choix. Une fois que toutes les pierres sont placées, une partie de Nim commence, en commençant par le prochain joueur qui doit se déplacer. Ce jeu est noté BN(n,s) .

n -d nim se joue sur un plateau sur lequel n'importe quel nombre de pièces continues peuvent être retirées de n'importe quelle hyper-rangée. La position de départ est généralement le plateau complet, mais d'autres options sont autorisées.

Le plateau de départ est un graphique déconnecté et les joueurs se relaient pour supprimer les sommets adjacents.

Candy nim est une version du nim normal dans laquelle les joueurs tentent d'atteindre deux objectifs en même temps : prendre le dernier objet (dans ce cas, des bonbons) et prendre le nombre maximum de bonbons à la fin du jeu.