Stratégies magiques au pays de Nim

Dans le domaine des jeux les plus simples où deux joueurs s’affrontent, la théorie des jeux combinatoires, qui progresse avec régularité, est la plus abordable et la plus généreuse en jolis résultats mathématiques. Les amateurs de jeux tireront avantage de cette théorie à la fois puissante, élégante et amusante. Elle sert de socle aux développements plus subtils menés aujourd’hui pour maîtriser la programmation de jeux complexes, dont les jeux de tableaux comme les Dames, les Échecs et le Go. Un jeu à deux joueurs entre dans la catégorie des jeux combinatoires s’il vérifie les conditions suivantes :

1. Les deux joueurs jouent à tour de rôle.
2. Toutes les informations concernant le jeu — configurations, possibilités de mouvements des joueurs – sont connues à chaque instant des deux joueurs (l’information est complète).
3. Aucun hasard n’intervient dans le jeu (pas de lancer de dé, ni de distribution aléatoire de cartes, etc.).
4. Dans la version normale du jeu, le joueur qui n’a plus aucune possibilité de mouvement perd la partie. Lorsque la convention inverse est adoptée (dans la
   version « misère » ou « qui perd gagne » du jeu), celui qui fait le dernier mouvement perd.

Deux types de jeux combinatoires sont particulièrement bien compris et disposent de théories détaillées et puissantes : les jeux de Nim, entièrement résolus en 1901 par le mathématicien américain Charles Bouton, et les jeux impartiaux où le théorème de Sprague-Grundy, qui en donne une compréhension générale, est devenu d’usage courant pour écrire des programmes informatiques. Nous allons présenter ce noyau fondamental de la théorie à l’aide d’exemples simples qui vous permettront de briller en société en gagnant d’une manière qui semblera magique à vos adversaires.

Les jeux de Nim

  
Machine Nimrod spécialisée dans le Nim, construite par la Société Ferranti et présentée en 1951 à Londres.

Sous diverses formes, ces jeux semblent avoir été pratiqués en Europe dès le XVI^e siècle et même avant, en Chine. Bouton les baptisa du nom de Nim sans que nous sachions si Nim provient de l’allemand Nimm qui signifie prendre, du verbe de l’ancien anglais Nim qui avait le même sens, ou si c’est une astuce graphique puisqu’en retournant NIM, on obtient le mot anglais WIN qui signifie gagner. Ce jeu tient une place importante dans l’intrigue du film d’Alain Resnais L’année dernière à Marienbad avec Delphine Seyrig, film qui obtint le Lion d’or de la Mostra de Venise en 1961. On peut voir les extraits du film où les personnages « jouent » la version misère en anglais.

Les règles sont les suivantes : p lignes d’allumettes (ou de pions) sont disposées devant les joueurs et comportent respectivement N₁ allumettes, N₂ allumettes, …, N_p allumettes.
Les joueurs jouent à tour de rôle et chacun des deux joueurs prend autant d’allumettes qu’il veut dans une ligne (mais au moins une). Celui qui prend la dernière allumette a gagné. Dans la version « misère », celui qui prend la dernière allumette a perdu.

Chaque joueur joue à tour de rôle en prenant autant d’allumettes qu’il le veut dans une ligne ; le joueur qui prend la dernière allumette gagne.
Dans la partie figurée en haut, le joueur B gagne, alors que le joueur A avait une position gagnante initiale. Cette position gagnante est indiquée par une somme de Nim non nulle des nombres d’allumettes des lignes (exprimés en numération binaire). D’une position gagnante, un joueur peut toujours amener son adversaire dans une position perdante à somme de Nim nulle. Les numéros des positions gagnantes sont en rouge, ceux des positions perdantes en bleu.
La partie figurée en bas est correctement jouée par A.

L’analyse de ce jeu par Bouton l’a conduit à énoncer un théorème inattendu. Celui-ci indique que le joueur qui doit jouer dispose d’une stratégie gagnante de jeu si les entiers (N₁, N₂, …, N_p) qui décrivent la position du jeu ont une somme non nulle, pour une addition particulière nommée la Nim-addition. Cette Nim-addition, que l’on retrouvera dans le théorème de Sprague-Grundy et dans toute la théorie des jeux combinatoires, est simple dès que les entiers N₁, N₂, …, N_p sont écrits en base de numération binaire. Expliquons cette addition bizarre à partir d’un exemple :
N₁ = 11, N₂ = 9, N₃ = 7.
Écrire un nombre en binaire revient à décomposer ce nombre en une somme de
puissances de 2 : 1, 2, 4, 8, 16, 32, …. Puisque 11 = 8 2 1, l’écriture binaire de 11 est 1011, ce qui signifie 1 fois 8, 0 fois 4, 1 fois 2, 1 fois 1. De même 9 = 8 1 = 1001 et 7 = 4 2 1 = 111.

La Nim-addition consiste à disposer les chiffres binaires comme on le fait quand on pose une addition habituelle, puis à additionner en colonnes, sans tenir compte des retenues. Le nombre binaire obtenu retraduit en entier est le résultat :

Notons bien que nous travaillons en base 2 : 1 1 = 10, 1 1 1 = 11 et, puisque nous ne tenons pas compte des retenues, 1 1 = 0, 1 1 1 = 1. Le fait de négliger les retenues a pour conséquence que le chiffre résultat de la somme d’une colonne vaut 0 quand il y a un nombre pair de 1 dans la colonne, et vaut 1 quand il y a un nombre impair de 1 dans la colonne. Pratiquer la Nim-addition est simple dès lors que l’on sait décomposer en binaire et que l’on sait repérer les nombres pairs et impairs. La Nim-addition de la configuration (11, 9, 7) est 5. D’après le théorème de Bouton, c’est une configuration gagnante. Si c’est à vous de jouer, vous disposez d’une stratégie de jeu gagnante qui consiste à placer votre adversaire en position perdante (c’est-à-dire ayant une Nim-addition nulle). Ici, il faut prendre 5 allumettes dans le troisième paquet, c’est-à-dire placer l’adversaire en position (11, 9, 2), dont la Nim-addition est 0 :

Facile à dire ! Mais en pratique, comment faire avec des lignes d’allumettes ? Ce n’est pas très compliqué et, avec un petit entraînement, on peut opérer de tête les calculs nécessaires. Voici la méthode. Pensez les nombres en les séparant en paquets ayant chacun un nombre d’allumettes qui est une puissance de 2. Comme nous venons de l’expliquer, cela revient à les écrire en numération binaire. Faites ce travail de tête ou déplacez légèrement les allumettes pour matérialiser ces décompositions. Partant de la disposition :

vous obtenez — discrètement — la disposition :

Il est facile maintenant de voir si oui ou non il y a un nombre pair de paquets dans chaque colonne. Si c’est le cas, vous ne gagnerez pas face à un adversaire averti, car vous êtes en situation perdante. Sinon, il existe une façon de jouer qui conduit à une configuration dont chaque colonne contient un nombre pair de paquets. Ici, on voit immédiatement qu’il faut enlever le paquet I I I I de la dernière ligne, ainsi que le paquet I, c’est-à-dire 5 allumettes au paquet qui en contient 7. C’est d’ailleurs la seule façon de jouer qui, ici, conduise à une configuration nulle. Exercez-vous avec (13, 10, 3, 1).

Reste une double question. Pourquoi le théorème de Bouton est-il vrai, c’est-à-dire :
(a) Pourquoi, en opérant comme on vient de l’indiquer à partir d’une situation dont la Nim-addition est non nulle, on finit par gagner ?
(b) Pourquoi, si vous vous trouvez dans une position nulle, vous perdrez face à un adversaire qui connaît et applique la règle de la Nim-addition ?

L’idée de la démonstration se fonde sur les deux faits suivants. D’une part, à partir d’une situation nulle, quoi que vous jouiez, vous créez une situation non nulle ; d’autre part, à partir d’une situation non nulle, il existe toujours au moins une façon de jouer qui mène à une situation nulle. Il en résulte qu’une fois tombé dans une situation nulle, un joueur n’en sort jamais si son adversaire fait ce qu’il faut, et cela jusqu’à ce qu’il se trouve dans la situation nulle de la fin de partie (il n’y a plus aucune allumette) qui signifie qu’il a perdu !

Toutes sortes de variantes du jeu de Nim classique ont été envisagées et résolues. La première est la variante « misère » : on y convient que le joueur qui prend la dernière allumette perd. La solution est la suivante : vous jouez comme dans le jeu normal en appliquant la règle de Bouton, sauf si votre coup conduit à une situation où il ne reste que des paquets d’une seule allumette, auquel cas vous jouez de façon à laisser un nombre impair de paquets d’une allumette (au lieu d’en laisser un nombre pair, ce que le théorème de Bouton vous soufflerait). Bien sûr, dès lors, vous êtes certain de gagner. Cette solution est un peu étonnante puisqu’elle signifie que partant par exemple de (11, 9, 7), le joueur qui commence est certain de gagner, que ce soit la règle normale qui détermine le gagnant ou que ce soit la règle misère. Il jouera exactement les mêmes coups, sauf par exemple quand arrivé à (1, 1, 3) qui l’aurait conduit à jouer (1, 1), il choisira de jouer (1, 1, 1) pour le jeu misère.

La variante de Moore

Une généralisation du jeu de Nim, notée Nim_k, étudiée et résolue par le mathématicien Eliakim Moore (1862-1932), consiste à autoriser les joueurs à prendre non pas des allumettes dans un paquet unique, mais dans plusieurs paquets, pourvu qu’ils n’en prennent pas dans plus de k paquets (k fixé) et pourvu qu’ils en prennent au moins une. Le jeu de Nim est Nim₁ ; dans une partie de Nim₂, chaque joueur prend à chaque coup autant d’allumettes qu’il veut dans un ou deux paquets (et en prend au moins une), etc. La solution de Moore généralise celle de Bouton. On procède de la même manière (décomposition en binaire de chaque nombre définissant une configuration du jeu), sauf qu’au lieu d’effectuer une somme sans retenue en base 2 sur les colonnes, on l’effectue en base k 1.

Si le résultat est nul, c’est que la situation est perdante, sinon elle est gagnante et la stratégie de jeu consiste à créer une situation nulle pour son adversaire et à l’y maintenir de coup en coup. Par exemple pour k = 2, en partant de la position de notre exemple :

Pour que le nombre de 1 de chaque colonne soit un multiple de 3 (k 1 = 3),
on choisit d’agir sur les deux premiers paquets. On est conduit à la position (7, 7, 7).

L’adversaire créera en jouant une configuration non nulle à partir de laquelle vous le mettrez dans une position nulle, etc.

Paquets infinis d’allumettes !

Les jeux finis sont certes amusants, mais le propre des mathématiques est de considérer l’infini avec le plus grand sérieux et donc… d’inventer des jeux qui l’utilisent ! Le jeu de Nim (normal) se pratique en partant d’une série de paquets d’allumettes comportant chacun un nombre fini d’allumettes. Et si on acceptait des paquets infinis ? Georg Cantor a introduit une catégorie de nombres infinis, les ordinaux, qui vont faire l’affaire et qui garantiront que toute partie se termine par un gagnant ou un perdant. Rappelons que pour construire les ordinaux, on convient qu’au-delà de tous les entiers 0, 1, 2, …, n, … on trouve un nombre plus grand que tous les autres, noté ω (oméga) et dénommé « le premier ordinal transfini ». On convient aussi qu’il y un ordinal juste au-dessus de lui, ω 1, et un autre juste au-dessus encore ω 2, puis ω 3, ω 4, etc. Au-delà de tous ces nombres transfinis, il y a 2ω (divers types de notations sont possibles, nous choisissons celle-ci qui est naturelle). Il y a aussi 2ω 1, 2ω 2, 2ω 3,…, 3ω, 3ω 1, 3ω 2,…, 4ω,… et juste après tous ces nω, il y a ω². Nous nous contenterons de ces ordinaux, mais tout ce qui suit se généralise aux ordinaux au-delà de ω² (et il y en a beaucoup !).

Une situation du jeu de Nim infini est une série de paquets d’allumettes ayant chacun un nombre d’allumettes représenté par un ordinal jusqu’à ω². Par exemple : (ω 5, ω², 2ω 1, 9ω, 7)

Jouer consiste à prendre des allumettes dans un paquet, c’est-à-dire à remplacer l’ordinal désignant le paquet d’allumettes par un ordinal plus petit. Par exemple, on pourra à partir de la configuration décrite ci-dessus, prendre des allumettes dans le deuxième paquet (le plus gros) et y laisser 5ω 1 allumettes, ce qui donnera la configuration : (ω 5, 5ω 1, 2ω 1, 9ω, 7).

Un tel jeu est-il assuré de se terminer ? Cela ne semble pas évident puisqu’il y a une infinité d’allumettes dans certains paquets. Pourtant, on peut montrer que toute partie a nécessairement une durée finie. Il est impossible de dire que la durée d’une partie est inférieure à n étapes (n étant un entier fixé), mais aucune partie ne peut se prolonger indéfiniment.

Comment gagner au Nim infini ?

En jouant quelques parties, vous découvrirez qu’avec ces paquets infinis, il y a aussi des configurations qui assurent de gagner, et d’autres qui ne permettent pas de battre un adversaire malin. Il est clair par exemple que (ω, 12) est une situation gagnante : il faut jouer (12, 12). De même, pour tout entier n, (ω, n) est gagnante. En revanche, (ω, ω) est perdante car, quoi que vous fassiez, votre adversaire pourra répliquer en vous plaçant dans une configuration (n, n) qui est perdante (elle a une Nim-addition nulle). De proche en proche, on remarque ainsi que (ω, ω, ω) est gagnante, (ω, ω, ω, ω) est perdante, etc. Comment faire dans le cas général ? Voici la règle qui généralise le théorème de Bouton. Énonçons-la d’abord sans prendre en compte ω². La configuration (a₁ω b₁, a₂ω b₂,…, a_kω b_k) est perdante si la Nim-addition des a_i est nulle ainsi que la Nim-addition des b_i. S’il y a en plus des ω₂, la configuration est perdante si leur nombre est pair. Dans tous les autres cas, la configuration est gagnante et bien sûr la stratégie gagnante consiste à mettre l’adversaire dans une situation perdante et à l’y maintenir de coup en coup.

Jeux impartiaux

Venons-en au théorème magique de Sprague-Grundy (découvert indépendamment par R. Sprague en 1935 et par P. Grundy en 1939). Il concerne la catégorie de jeux combinatoires nommée jeux impartiaux. Ces jeux sont semblables au jeu de Nim normal :

1. Les coups permis à un joueur ne dépendent que de la configuration.
2. Le but est de placer l’adversaire dans une position où il ne peut plus jouer.
3. Les règles du jeu sont telles qu’il n’y a pas de partie nulle ou qui se prolonge indéfiniment.

Un exemple de jeu impartial fini est le jeu du déplacement d’un pion sur un graphe sans cycle : il va nous guider pour expliquer le théorème. Un pion est placé sur le nœud d’un graphe donné qui ne doit pas comporter de cycle (on ne doit pas y trouver de suite d’arcs formant une boucle). Chaque joueur déplace, à son tour, le pion en suivant un arc du graphe. Le joueur qui ne peut plus déplacer le pion a perdu.

Voici maintenant le théorème de Sprague-Grundy qui comporte trois volets :

1. Chaque position d’un jeu impartial fini est équivalente à un jeu de Nim avec un seul paquet dont le nombre d’allumettes est un entier ; ce nombre est nommé le nimber de la position.
2. Le calcul du nimber d’une position se fait par la règle du mex (minimum de la valeur exclue) : les positions finales ont pour
   nimber 0 ; le nimber d’une position permettant d’atteindre les positions de nimber n₁, n₂, …, n_k est le plus petit entier qui n’est pas dans la liste n₁, n₂, …, n_k.
3. Lorsque l’on joue simultanément à plusieurs jeux impartiaux (jeu 1, jeu 2, …, jeu m), le nimber de la position définie comme la combinaison de la position P₁ du jeu 1, P₂ du jeu 2, …, P_m du jeu m, est la Nim-addition des nimbers des positions P₁, P₂, …, P_m.

Le théorème magique

Cela semble un peu difficile à avaler, mais en pratique c’est très simple. Reprenons l’exemple du pion sur un graphe (auquel tout jeu impartial fini peut d’ailleurs se ramener si on veut). Il nous montrera l’immense intérêt pratique de ce théorème. Pour savoir comment jouer quand un pion est placé sur le graphe, la méthode consiste à calculer le nimber de chaque nœud du graphe. Grâce à la règle du mex, c’est l’affaire de quelques secondes pour chaque nœud du graphe. Pour jouer et gagner, la méthode est de tenter de placer votre adversaire dans une position dont le nimber est 0, et dès que c’est fait, maintenez-le toujours dans des positions de nimber 0. Si vous êtes dans une position dont le nimber est non nul, c’est possible, sinon c’est impossible et vous devez espérer que votre adversaire n’a pas connaissance du théorème de Sprague-Grundy. Comme dans le jeu de Nim, une fois dans une position de nimber 0, quoi que fasse votre adversaire, vous pourrez toujours le remettre dans une position de nimber 0.

La troisième partie du théorème concerne les jeux simultanés (on dit aussi les « sommes de jeux »). Au lieu de placer un pion sur le graphe, placez-en plusieurs. La règle est que chaque joueur déplace un pion qu’il choisit librement (toujours en suivant un arc du graphe bien sûr). Le joueur qui ne peut plus déplacer aucun pion a perdu.

Le théorème de Sprague-Grundy formule une méthode magique pour gagner. À chaque ensemble de pions sur le graphe correspond un nimber. Pour le connaître, il suffit de faire la Nim-addition des nimbers des nœuds où sont placés les pions. Si le résultat est non nul, vous êtes certain de gagner, la stratégie consistant à déplacer un pion de telle façon que la Nim-addition des cases qu’occuperont les pions après votre déplacement soit toujours nulle. D’une manière tout à fait générale, le théorème de Sprague-Grundy fournit le moyen de calculer les nimbers de tout jeu impartial (par la règle du mex) et un moyen très rapide et efficace de calculer les nimbers associés à des positions d’un jeu simultané.

L’intérêt des jeux simultanés est qu’un jeu peut parfois se décomposer en une somme de jeux simultanés plus simples. C’est le cas de la fin des parties au jeu de Go quand plusieurs actions se déroulent indépendamment sur le goban. C’est le cas aussi du Jeu des Pousses (voir la rubrique « Logique et calcul » de la revue Pour la Science de septembre 2008) où des sous-jeux indépendants apparaissent, dont la méthode des nimbers permet la résolution rapide. Comme la règle du mex est facile à programmer, une méthode efficace de programmation des jeux impartiaux doit se fonder sur le calcul du nimber en utilisant la règle du mex et, à chaque fois que possible, la troisième partie du théorème de Sprague-Grundy (c’est la méthode utilisée par Julien Lemoine et Simon Viennot qui leur a permis de battre tous les records au Jeu des Pousses).

Ce que nous venons d’expliquer pour les jeux impartiaux finis s’adapte aux jeux impartiaux infinis à condition de généraliser la notion de nimber et d’accepter que n’importe quel ordinal — et non plus n’importe quel entier — soit un nimber. L’opération mex, qu’on étend immédiatement aux ordinaux, donne alors la méthode pour attribuer un nimber (fini ou infini) à chaque position d’un jeu impartial infini. L’opération d’addition que nous avons définie (partiellement) pour les ordinaux donne de son côté la méthode pour traiter les jeux impartiaux infinis simultanés.

On recommande aux enfants de ne pas jouer avec des allumettes. Pour les mathématiciens, le conseil inverse s’impose.

Une première version de ce document est parue dans la rubrique « Logique et calcul » de la revue Pour la Science, n°377, en mars 2009.