Théorème de Sprague-Grundy

Dans la théorie des jeux combinatoires, le théorème de Sprague-Grundy indique comment définir la stratégie gagnante d'un jeu impartial fini sans partie nulle en version normale (c'est-à-dire où le joueur qui ne peut plus jouer est le perdant), lorsque ce jeu est lui-même somme de deux ou plusieurs jeux impartiaux.

Le théorème de Sprague-Grundy a été découvert indépendamment par Roland Sprague en 1935 et Patrick Grundy en 1939. Il généralise un résultat établi en 1901 par Charles Bouton, relatif au jeu de Nim classique ou jeu de Marienbad.

La généralisation de ce théorème aux jeux partisans a donné naissance à la théorie des jeux combinatoires.

Somme de deux jeux

On considère des jeux de Nim, jeux impartiaux constitués d'un nombre fini de positions et menant nécessairement au bout d'un nombre fini de coups à la fin de la partie, où le vainqueur est celui qui joue le dernier coup.

Si G et H sont deux tels jeux, on définit le jeu G + H somme des deux jeux de la façon suivante.

• Les positions de G + H sont les couples (x, y) où x est une position de G et y une position de H.
• La position initiale de G + H est constituée du couple (a, b) où a est la position initiale de G et b la position initiale de H.
• La position finale de G + H est constituée du couple (g, h) où g est la position finale de G et h la position finale de H.
• Les coups permis sont ceux qui font passer de la position (x, y) à la position (t, y), le passage de x à t étant permis dans la règle de G, ou bien ceux qui font passer de la position (x, y) à (x, u), le passage de y à u étant permis dans la règle de H.

Autrement dit, les deux jeux se jouent en parallèle, le joueur décidant de jouer à l'un ou à l'autre jeu, en respectant la règle des deux jeux.

À titre d'exemple, si G₁, G₂, G₃ et G₄ sont des jeux de Nim triviaux constitués chacun d'un tas d'allumettes où l'on peut prendre autant d'allumettes que l'on veut, la somme G₁ + G₂ + G₃ + G₄ constitue un jeu de Marienbad auquel le théorème de Sprague-Grundy apporte précisément la stratégie gagnante.

Nombre de Grundy

À chaque position d'un jeu de Nim, on affecte un nombre appelé nombre de Grundy ou nimber. Celui-ci est défini récursivement comme suit :

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

Par exemple, considérons le jeu de Nim trivial. Dans ce jeu, on dispose un unique tas d'allumettes. Le joueur à qui c'est le tour, doit prendre un nombre quelconque non nul d'allumettes. S'il n'y a plus d'allumettes, le joueur à qui c'est le tour perd. Pour le Nim trivial, le nombre de Grundy d'une position avec n allumettes est n.

On prouve que les positions dont les nombres de Grundy valent 0 sont des positions gagnantes qu'il convient d'atteindre, les autres étant des positions perdantes.

Le théorème de Sprague-Grundy

Le théorème de Sprague-Grundy énonce comment calculer le nombre de Grundy ou nimber d'une position mixte quelconque (x, y) d'une somme de deux jeux. On décompose les nombres de Grundy des positions x et y en binaire, et on fait la somme des deux nombres binaires sans tenir compte des retenues. Cette somme s'appelle Nim-somme ou somme digitale, notée $\oplus$. Le résultat obtenu est le nombre de Grundy de la position (x, y). Ce résultat se généralise à plusieurs jeux.

Démonstration

Afin d'alléger les notations, nous confondrons la position x d'un jeu de Nim avec son nombre de Grundy. Soit (x, y) une position mixte. Il s'agit de montrer :

• d'une part que, pour tout t < x et tout u < y, $x\oplus y\neq t\oplus y$ et $x\oplus y\neq x\oplus u$.
• d'autre part, que $x\oplus y$ est inférieur ou égal à tout entier n'apparaissant pas parmi les $t\oplus y$ ou $x\oplus u$, t < x, u < y.

Le premier point est facile. En effet, si $x\oplus y=t\oplus y$, alors $x\oplus y\oplus y=t\oplus y\oplus y$ et comme $y\oplus y=0$, on aurait $x=t$ ce qui n'est pas.

Le deuxième point est plus difficile. On montre la contraposée en prouvant que tout entier m strictement inférieur à $x\oplus y$ apparaît nécessairement parmi les $t\oplus y$ ou les $x\oplus u$. Nous illustrerons le principe de cette démonstration sur un exemple, en notant x et y en binaire, les chiffres de poids croissant étant notés comme d'habitude de droite à gauche. Soient :

$x=110\;011\;101\;111_{b}$

$y=111\;010\;110\;010_{b}$

$x\oplus y=001\;001\;011\;101_{b}$

$m=001\;000\;101\;111_{b}$

Pour que m soit strictement inférieur à $x\oplus y$, il faut et il suffit qu'un chiffre 1 de $x\oplus y$ soit transformé en 0, les chiffres à droite de celui-ci pouvant être quelconques. Dans le cas précédent, c'est le sixième chiffre à partir de la gauche qui a été transformé. Ce sixième chiffre, qui vaut donc 1 dans $x\oplus y$, provient nécessairement de la somme digitale d'un 1 et d'un 0, ici un 1 en sixième position dans x et un 0 en sixième position dans y. On peut alors obtenir m sous la forme $t\oplus y$ avec t < x. Il suffit pour former t de conserver les chiffres de x jusqu'au cinquième, de placer un 0 en sixième place, puis de transformer tous les chiffres qui suivent en faisant la somme digitale des chiffres de y et m de même rang :

$t=110\,010\,011\,101_{b}$

On a bien t < x et $m=t\oplus y$.

Exemple. Si les nombres de Grundy de x et y valent respectivement 11 et 7, alors :

• 11 = 1011_b
• 7 = 111_b

donc le nombre de Grundy de la position mixte (x, y) est $1011_{b}\oplus 111_{b}=1100_{b}=12$.

Ce théorème permet d'affirmer qu'une position d'un jeu de Nim quelconque G dont le nombre de Grundy est n est équivalente à celle d'un jeu de Nim à un seul tas G' doté de n allumettes, la substitution du jeu G' au jeu G dans une somme G + H conduisant à la même stratégie gagnante, celle consistant à atteindre les positions mixtes dont le nombre de Grundy est nul.

Voir aussi

• Fonction OU exclusif

Bibliographie

• (de) R. P. Sprague, « Über mathematische Kampfspiele », Tohoku Mathematical Journal, vol. 41,‎ 1935–36, p. 438–444
• (en) P. M. Grundy, « Mathematics and games », Eureka (en), vol. 2,‎ 1939, p. 6-8 (lire en ligne)

réimprimé en 1964, vol. 27, p. 9-11

• (en) Thomas S. Ferguson, Game Theory.