GéométrieNotion · Glossaire
jeu impartial
Un jeu impartial est un jeu combinatoire à deux joueurs qui jouent à tour de rôle, en information complète, où les coups possibles depuis une position ne dépendent pas du joueur, toute partie se termine après un nombre fini de coups et, en convention normale, celui qui ne peut plus jouer perd. Cette symétrie permet, grâce au théorème de Sprague-Grundy, de ramener chaque position à un tas de Nim équivalent et ainsi de déterminer des coups gagnants.
Sommaire
Ce que vous allez apprendre
- Reconnaître un jeu impartial à partir de ses coups et de son information disponible.
- Distinguer impartialité, équité, jeu partisan et convention misère.
- Calculer la nim-somme de tas de tailles 1, 2 et 4 et trouver un coup vers une valeur nulle.
- Situer le rôle du théorème de Sprague-Grundy et du nimbre.
En clair
Deux personnes font face aux mêmes tas de jetons. À chaque tour, chacune peut retirer des jetons selon exactement les mêmes règles. Rien n'est caché, et personne ne dispose d'un coup réservé.
Un tel affrontement est impartial : les possibilités dépendent seulement de la position, jamais de l'identité du joueur. En convention normale, celui qui se retrouve sans coup perd. Cette symétrie des choix ne garantit pas l'égalité des chances : la position peut favoriser la personne qui commence.
Définition
Un jeu impartial est un jeu combinatoire à deux joueurs qui jouent alternativement. Depuis une position donnée, l'ensemble des coups autorisés est identique pour les deux joueurs. L'état complet du jeu est connu de chacun. Dans le cadre fini considéré ici, toute partie s'achève après un nombre fini de coups. En convention normale, le joueur qui ne peut plus jouer perd.
La convention misère conserve les mêmes positions et les mêmes coups, mais inverse l'issue terminale : le joueur sans coup gagne. Cette modification suffit à changer l'analyse stratégique. Nim, le jeu de Grundy, le jeu de Wythoff, les jeux octaux, Sprouts, Cram, Chomp et Noktako fournissent des exemples classiques.
Pour une position finie en convention normale, le théorème de Sprague-Grundy associe un entier appelé nimbre, ou valeur de Grundy. Cette position est alors stratégiquement équivalente à un unique tas de Nim de cette taille. Pour une somme de sous-jeux indépendants, la valeur totale est le ou exclusif bit à bit, noté ⊕, de leurs nimbres. Une valeur totale nulle caractérise une position perdante si l'adversaire joue parfaitement.
Un exemple, pas à pas
Une partie de Nim comporte trois tas de 1, 2 et 4 jetons. À son tour, un joueur choisit un seul tas et y retire au moins un jeton. Le jeu suit la convention normale.
Données.
Tailles initiales : 1, 2 et 4.
Nimbre d'un tas de Nim : son nombre de jetons.
Opération de combinaison : le ou exclusif bit à bit, noté ⊕.
Tailles initiales : 1, 2 et 4.
Nimbre d'un tas de Nim : son nombre de jetons.
Opération de combinaison : le ou exclusif bit à bit, noté ⊕.
1. Écrivez les tailles en binaire : 1 vaut 001, 2 vaut 010 et 4 vaut 100.
2. Calculez la nim-somme initiale : . Elle n'est pas nulle, donc un coup gagnant existe.
3. Retirez un jeton du tas de 4. Les tailles deviennent 1, 2 et 3, et .
Résultat et contrôle. Le coup 4 vers 3 laisse une position de nim-somme nulle. En binaire, 001 ⊕ 010 ⊕ 011 vaut 000 : chaque colonne contient un nombre pair de chiffres 1. Ce contrôle refait le calcul sans supposer la conclusion.
En pratique
Pour reconnaître un jeu impartial, partez d'une position précise et comparez les coups disponibles selon la personne qui doit jouer. Si la liste reste identique et si tout l'état est visible, le cadre impartial est adapté. Si chaque camp déplace ses propres pièces, il faut plutôt une analyse de jeu partisan.
Pour analyser une somme de sous-jeux indépendants en convention normale, attribuez un nimbre à chacun, puis combinez ces valeurs par addition nim. Cherchez un coup qui rend la valeur totale nulle, comme le passage des tas 1, 2, 4 aux tas 1, 2, 3.
Avant d'appliquer ce diagnostic, vérifiez la règle de fin. Si l'absence de coup fait gagner, la partie est en convention misère et le critère ordinaire de Sprague-Grundy ne s'emploie pas tel quel.
À ne pas confondre
Jeu impartial et jeu partisan. Le test porte sur les coups disponibles depuis une même position. S'ils dépendent du joueur, le jeu est partisan : aux échecs, Blanc et Noir ne déplacent pas les mêmes pièces ; au go, chaque joueur ne pose que des pierres de sa couleur.
Impartialité et équité. « Impartial » décrit la symétrie des règles de déplacement, pas des chances identiques. Dans Nim avec des tas de 1, 2 et 4 jetons, le premier joueur dispose d'un coup gagnant malgré des coups autorisés identiques pour les deux personnes.
Limites et pièges
Convention misère. Le symptôme est une règle où ne plus pouvoir jouer fait gagner. Les positions et les coups restent impartiaux, mais l'issue terminale est inversée. Il faut employer l'analyse propre à la variante misère, et non transposer automatiquement le critère de nim-somme nulle.
Somme non indépendante. L'addition nim suppose que jouer dans une composante ne modifie pas les coups des autres. Si retirer un jeton d'un tas change aussi un autre tas, le découpage est invalide. Il faut calculer la valeur de Grundy de la position entière.
Finitude. L'énoncé utilisé ici suppose que toute partie se termine en un nombre fini de coups. Si un cycle ou une suite infinie est possible, la récursion qui attribue les valeurs de Grundy ne s'applique plus directement. Il faut d'abord traiter les répétitions ou adopter un cadre plus général.
Pour aller plus loin
La fiche jeu de Nim détaille le modèle de tas qui sert de référence aux nimbres et à l'addition nim.
Le théorème de Sprague-Grundy expose le résultat qui ramène toute position impartiale finie, en convention normale, à un tas de Nim.
L'article Conway, le joueur mathématicien replace ces idées dans un panorama plus large des jeux combinatoires.
L'article Une stratégie pour bouger la dame montre comment une position de jeu se transforme en problème de stratégie mathématique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres