ArithmétiqueThéorème · Glossaire
théorème de Sprague-Grundy
Le théorème de Sprague-Grundy s'applique aux jeux impartiaux finis sans partie nulle, en convention normale : les deux joueurs ont les mêmes coups possibles, toute partie se termine et celui qui ne peut plus jouer perd. Il affirme que toute position d'un tel jeu est stratégiquement équivalente à un tas de Nim, dont la taille est son nimber, ou valeur de Grundy. Pour une somme de jeux indépendants, le XOR de leurs nimbers détermine si la position est gagnante et guide le choix d'un coup gagnant.
Sommaire
Ce que vous allez apprendre
- Déterminer une valeur de Grundy par minimum exclu.
- Combiner des sous-jeux indépendants avec le XOR.
- Vérifier un coup gagnant sur deux tas de 4 et 5 jetons.
- Reconnaître les cas où les hypothèses du théorème échouent.
En clair
Imaginez plusieurs tas de jetons. À chaque tour, les deux joueurs ont le droit de retirer un ou deux jetons d'un tas, et celui qui ne peut plus jouer perd. Le théorème remplace chaque position, même issue d'un jeu plus compliqué, par un unique tas fictif de Nim.
La taille de ce tas fictif est la valeur de Grundy. Pour combiner plusieurs jeux, on réunit leurs valeurs par le ou-exclusif, ou XOR. Un résultat nul signale une position perdante si l'adversaire joue parfaitement.
Définition
Le théorème de Sprague-Grundy concerne les positions des jeux combinatoires impartiaux, finis, sans partie nulle et joués selon la convention normale. « Impartial » signifie que, depuis une même position, les coups autorisés ne dépendent pas du joueur. La convention normale déclare perdant celui qui n'a aucun coup possible.
À chaque position P, on associe un entier naturel appelé valeur de Grundy, noté ici g(P). La valeur d'une position terminale est 0. Pour une autre position, g(P) est le plus petit entier naturel absent parmi les valeurs des positions accessibles en un coup. Cette opération est appelée mex, pour « minimum exclu » : . Le théorème affirme que P est stratégiquement équivalente à un tas de Nim contenant g(P) jetons.
Pour une somme de positions indépendantes P1, …, Pk, un coup ne modifie qu'une composante. La valeur totale est le XOR, noté ⊕, de leurs valeurs : . La somme est perdante sous jeu parfait exactement lorsque ce résultat vaut 0.
Le principe
Si une position appartient à un jeu impartial fini, sans partie nulle et en convention normale, alors elle est équivalente à un unique tas de Nim dont la taille est sa valeur de Grundy. Cette valeur est le minimum exclu des valeurs atteignables en un coup.
Si plusieurs positions indépendantes sont réunies, alors la valeur de leur somme est . La position totale est perdante sous jeu parfait si et seulement si ce XOR est nul ; sinon, au moins un coup mène à un XOR nul.
Quand l'utiliser
Le jeu doit être impartial : les options offertes par une position sont identiques pour les deux joueurs. Il doit aussi être fini, afin que les valeurs se calculent à partir des positions terminales. Enfin, la convention normale s'applique : ne plus pouvoir jouer fait perdre, et aucune partie n'est nulle. Ces conditions suffisent pour obtenir un nimber pour chaque position et combiner les composantes par XOR.
Dans une variante où prendre le dernier jeton fait perdre, la convention est dite misère. Le calcul ordinaire des valeurs de Grundy ne donne alors pas, à lui seul, le verdict annoncé par le théorème ; il faut employer l'analyse propre au jeu en convention misère. De même, un jeu où les coups dépendent du joueur relève des jeux partisans.
Un exemple, pas à pas
Deux tas indépendants contiennent 4 et 5 jetons. À chaque coup, un joueur retire 1 ou 2 jetons d'un seul tas. La position sans jeton est terminale et vaut donc g(0) = 0.
1. Depuis 1 jeton, seule la valeur 0 est accessible : g(1) = mex{0} = 1.
2. Depuis 2 jetons, les valeurs 1 et 0 sont accessibles : g(2) = mex{1, 0} = 2.
2. Depuis 2 jetons, les valeurs 1 et 0 sont accessibles : g(2) = mex{1, 0} = 2.
3. Depuis 3 jetons, on atteint les valeurs 2 et 1 : g(3) = mex{2, 1} = 0.
4. Le même calcul donne g(4) = 1 et g(5) = 2.
4. Le même calcul donne g(4) = 1 et g(5) = 2.
5. La valeur des deux tas est . La position est donc gagnante. Retirer 2 jetons du tas de 4 conduit aux tas 2 et 5, dont la valeur est .
Le contrôle est direct : après ce coup, tout retrait adverse rend le XOR non nul. Le premier joueur peut ensuite rétablir un XOR nul jusqu'à laisser son adversaire sans coup.
En pratique
Pour analyser un jeu de retrait, on part des positions sans coup, puis on remonte position par position avec le minimum exclu. Cette méthode est préférable à l'énumération de parties dès que plusieurs chemins rejoignent les mêmes positions.
Pour une somme de sous-jeux indépendants, on calcule chaque valeur séparément puis leur XOR. Un résultat non nul guide la recherche d'un coup vers 0 ; un résultat nul indique qu'aucun coup gagnant immédiat n'existe contre un jeu parfait.
Quand les coups possibles dépendent du joueur, ou quand le dernier coup fait perdre, on abandonne ce test standard. Une analyse partisane ou une méthode adaptée à la convention misère devient nécessaire.
À ne pas confondre
Valeur de Grundy et nombre de coups restants. La valeur de Grundy code les options stratégiques, pas la durée. Dans le jeu où l'on retire 1 ou 2 jetons, une pile de 3 jetons a la valeur 0 alors que des coups restent possibles.
Somme ordinaire et XOR. Le symbole ⊕ compare les écritures binaires bit par bit, sans retenue. Ainsi 1 ⊕ 2 vaut 3, mais 2 ⊕ 2 vaut 0, tandis que l'addition ordinaire donnerait 4.
Jeu impartial et jeu symétrique. Une apparence symétrique ne suffit pas. Le critère est local et testable : depuis toute position donnée, les deux joueurs doivent disposer exactement des mêmes coups.
Limites et pièges
Valeur nulle avec coups disponibles. Le seuil stratégique est g(P) = 0, non l'absence de coups. Une position terminale vaut 0, mais la pile de 3 jetons de l'exemple vaut aussi 0 et offre encore deux coups. Il faut calculer les options avant de conclure.
Cycles ou parties infinies. Si une position peut revenir à elle-même et permettre une suite infinie, la récursion par minimum exclu ne part plus nécessairement d'un cas terminal. Le théorème sous sa forme finie ne tranche pas ; il faut analyser les règles de répétition ou de partie nulle.
Convention misère. Si le dernier coup fait perdre, un XOR nul n'a plus toujours le sens standard. Le symptôme est visible dès un tas de 1 jeton : le joueur au trait perd en misère, alors qu'il gagne en convention normale.
Composantes dépendantes. La règle du XOR suppose qu'un coup agit sur une seule composante sans modifier les options des autres. Si retirer un jeton d'un tas change aussi les règles d'un autre tas, il faut traiter l'ensemble comme une seule position.
Pour aller plus loin
Jeu de Nim. Retrouver le jeu modèle dont les tas représentent les valeurs de Grundy et dont le XOR livre la stratégie gagnante.
Conway, le joueur mathématicien. Situer les jeux combinatoires dans une œuvre qui a largement prolongé leur étude mathématique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres