AlgèbreNotion · Glossaire
nimber
Un nimber résume une position de jeu impartial par une valeur : zéro signale une position perdante pour le joueur au trait, tandis qu'une valeur non nulle signale une position gagnante. Ce résumé s'applique en convention normale, lorsque les deux joueurs disposent des mêmes coups et que le jeu ne peut pas se prolonger indéfiniment. Les sections suivantes expliquent comment le calculer avec le mex, pourquoi le théorème de Sprague-Grundy le relie au jeu de Nim et comment combiner plusieurs positions.
Sommaire
Ce que vous allez apprendre
- Relier une position impartiale à sa valeur de Grundy et au nimber correspondant.
- Calculer la nim-somme de deux tas de 2 et 3 jetons.
- Reconnaître les hypothèses qui rendent le critère nul ou non nul valable.
En clair
Imaginez deux tas de jetons. À chaque tour, les deux joueurs suivent les mêmes règles et retirent des jetons à tour de rôle. Le nimber résume tout l'avenir d'une position par une valeur : zéro signale que le joueur dont c'est le tour ne peut pas forcer la victoire, tandis qu'une valeur non nulle signale qu'il le peut.
Ce résumé permet aussi de combiner plusieurs jeux. Pour des nimbers finis, l'addition se fait chiffre par chiffre en binaire, sans retenue : c'est la nim-somme.
Définition
Un nimber est la valeur canonique d'une position dans un jeu impartial joué selon la convention normale : les coups disponibles ne dépendent pas du joueur, et celui qui ne peut plus jouer perd. Pour une position dont le graphe de jeu est fini et acyclique, sa valeur de Grundy est un entier naturel. Plus généralement, une position impartiale sans suite infinie de coups reçoit une valeur ordinale. Le nimber correspondant est noté avec une étoile, par exemple *2.
Pour une position P, notons O(P) l'ensemble des positions accessibles en un coup. Sa valeur de Grundy g(P) est le plus petit entier naturel absent des valeurs de ses options ; cette opération s'appelle le mex, pour « minimum exclu ».
Une position terminale n'a aucune option, donc sa valeur est 0. Le théorème de Sprague-Grundy affirme alors que P est équivalente, pour l'addition disjonctive des jeux, à un tas de Nim de g(P) jetons.
Pour les positions de jeux impartiaux normaux sans suite infinie de coups, la somme de positions correspond à l'addition des nimbers. Pour les valeurs finies, cette addition est le ou exclusif bit à bit, aussi appelé nim-somme, et non l'addition ordinaire. Une multiplication spécifique complète ces opérations et donne aux nimbers une structure de corps ; elle ne se calcule pas, en général, comme la multiplication usuelle des entiers.
Un exemple, pas à pas
Deux joueurs pratiquent le jeu de Nim en convention normale. Une position comporte deux tas, A et B.
Données : le tas A contient 2 jetons ; le tas B en contient 3 ; un coup retire au moins un jeton d'un seul tas ; le joueur privé de coup perd.
Données : le tas A contient 2 jetons ; le tas B en contient 3 ; un coup retire au moins un jeton d'un seul tas ; le joueur privé de coup perd.
1. Dans le jeu de Nim, un tas de n jetons a pour nimber *n. Les deux tas ont donc les valeurs *2 et *3.
2. On additionne 2 et 3 par ou exclusif binaire :
La position a le nimber *1, qui est non nul : le joueur au trait possède un coup gagnant.
3. Il retire un jeton du tas B. Les tailles deviennent 2 et 2. La représentation par jetons permet de suivre ce passage vers deux tas égaux.
4. On contrôle la nouvelle nim-somme :
Le résultat exact est le nimber *0.
Le contrôle se refait sans calcul binaire : après tout retrait adverse dans un tas, le premier joueur retire autant dans l'autre. Il rétablit deux tas égaux, puis prend le dernier jeton.
En pratique
Pour analyser une position dont le graphe de jeu est fini et acyclique dans un jeu impartial, on part des positions terminales, puis on remonte le graphe des coups. À chaque position, on calcule le mex des valeurs déjà obtenues. Par exemple, si les options d'une position ont pour valeurs 0, 1 et 3, le plus petit entier absent est 2 : la position a donc pour valeur de Grundy 2. Une analyse directe des variantes reste préférable si les joueurs n'ont pas les mêmes coups.
Pour additionner un nombre fini de sous-jeux impartiaux normaux, indépendants et sans suite infinie de coups, on remplace chacun par son nimber et on effectue leur nim-somme. Une valeur totale nulle caractérise alors une position perdante avec jeu parfait ; une valeur non nulle indique qu'un coup vers zéro existe.
Pour chercher ce coup dans une position de Nim, on teste une réduction d'un seul tas et on recalcule la nim-somme. Si la règle impose de prendre le dernier coup pour perdre, il faut employer une analyse du jeu misère, car le critère ordinaire ne s'applique plus tel quel.
À ne pas confondre
Nimber et entier ordinaire. Les valeurs finies portent les mêmes nombres, mais leurs opérations diffèrent. Ainsi, la nim-somme de 2 et 3 vaut 1, alors que leur somme entière vaut 5.
Nimber et valeur de Grundy. La valeur de Grundy g(P) est l'étiquette ordinale calculée par mex pour une position P ; le nimber *g(P) est le jeu canonique auquel cette position est équivalente. Dans un jeu fini, parler du « nombre de Grundy 2 » ou du « nimber *2 » encode la même valeur, mais pas le même objet conceptuel.
Limites et pièges
Jeu partisan. Si les coups autorisés dépendent du joueur, le symptôme est que les deux camps n'ont pas le même ensemble d'options depuis une position. Le théorème de Sprague-Grundy ne suffit plus ; il faut conserver la valeur complète du jeu combinatoire.
Convention misère. Si le dernier joueur à jouer perd, une position sans coup devient gagnante pour le joueur au trait au lieu d'être perdante. Il faut appliquer les règles propres au jeu misère, et non conclure directement à partir d'une nim-somme nulle.
Cycles ou parties infinies. La récurrence par mex suppose que les options ont déjà une valeur, ce qui est garanti pour un graphe fini sans cycle. Si un coup peut ramener à une position antérieure ou si une partie peut se prolonger indéfiniment, le calcul ordinaire des nimbers peut échouer ; une théorie adaptée aux jeux avec boucles est alors nécessaire.
Opérations usuelles. Une étiquette comme *2 ne transforme pas l'addition ou la multiplication en calcul entier. Pour les nimbers finis, l'addition est le ou exclusif binaire ; la multiplication suit sa propre définition récursive.
Pour aller plus loin
jeu de Nim — Pour voir le modèle concret auquel chaque position impartiale est ramenée et pratiquer la nim-somme sur des tas.
théorème de Sprague-Grundy — Pour approfondir l'équivalence entre une position impartiale et un tas de Nim de même valeur.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres