théorème de Sprague-Grundy

nombre de Grundy

COMBINATOIRE

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).
Le théorème de Sprague-Grundy généralise un résultat (établi en 1901 par Charles Bouton), relatif au jeu de Nim classique ou jeu de Marienbad.
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.

Le théorème de Sprague-Grundy a été découvert indépendamment par Roland Sprague en 1935 et Patrick Grundy en 1939.