Théorème de Sprague-Grundy

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 (pt) en 1935 et Patrick Grundy (it) 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[1].

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[modifier | modifier le code]

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 G1, G2, G3 et G4 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 G1 + G2 + G3 + G4 constitue un jeu de Marienbad auquel le théorème de Sprague-Grundy apporte précisément la stratégie gagnante.

Nombre de Grundy[modifier | modifier le code]

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

Dans le jeu de Nim trivial, le nombre de Grundy d'un unique tas de n allumettes n'est autre que n lui-même.

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[modifier | modifier le code]

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.

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

  • 11 = 1011b
  • 7 = 111b

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[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. Charles L.Bouton, Nim, a game with a complete mathematical theory, Annals of Mathematics,2nd Ser., Vol.3, n°1/4, (1901-1902),pp.35-39