Jeux d'allumettes/Jeux de Nim
Les jeux de Nim sont des jeux très courants où s'affrontent deux joueurs. Dans ces jeux, on déplace des objets chacun son tour. Ces objets peuvent être des billes, des jetons ou des allumettes par exemple...
Chaque joueur modifie un ou plusieurs tas selon les règles adoptées.
Ce sont des jeux de stratégie pure. Le hasard n'intervient pas.
Les jeux de Nim classiques sont le jeu de Marienbad ou le jeu des bâtons.
Le jeu[modifier | modifier le wikicode]
Dans les jeux de Nim, on a un ou plusieurs tas d'allumettes. Le nombre de tas et le nombre d'allumettes par tas peut varier à volonté. À tour de rôle, chaque joueur doit prendre autant d'allumettes qu’il le veut dans un seul tas. Celui qui prend la dernière allumette a gagné (variante: Celui qui prend la dernière allumette a perdu).
jeu de Nim où on enlève 1, 2 ou 3 objets[modifier | modifier le wikicode]
- Une version moins triviale de ce jeu consiste à enlever 1, 2 ou 3 objets. Le vainqueur est celui qui va jouer en dernier. Pour ce jeu, la stratégie est de laisser à chaque fois - si on le peut - un nombre d'objets multiple de 4 : ce sont les positions gagnantes. On constate alors que l'adversaire ne pourra pas en faire autant. Dans la variante de cette version où celui qui prend le dernier objet perd, la stratégie est de laisser un nombre d'objets 1, 5, 9, 13[1].... En fait, on se ramène au cas précédent en considérant que le but du jeu est de prendre l'avant-dernier objet. Dans l'émission télévisée de Fort Boyard, un tel jeu constitue le duel des bâtonnets contre un maître du temps (le tas comprend 20 allumettes).
Le jeu de Nim classique ou jeu de Marienbad[modifier | modifier le wikicode]
- Le jeu de Nim classique ou jeu de Marienbad a été rendu célèbre par un film d'Alain Resnais L'année dernière à Marienbad (1961). Il est constitué de plusieurs tas. Chaque joueur choisit le tas de son choix, et dans ce tas, prend le nombre d'allumettes de son choix.
Le jeu de Grundy[modifier | modifier le wikicode]
- Le jeu de Grundy se joue en séparant l'un des tas en deux tas de tailles distinctes, jusqu'à ce qu'il ne reste que des tas à un ou deux objets.
* Le jeu de Wythoff[modifier | modifier le wikicode]
- Le jeu de Wythoff se joue à deux tas. Chaque joueur réduit d'un même nombre d'objets les deux tas à la fois, ou bien réduit un seul tas du nombre d'objets qu'il veut.
Stratégie gagnante[modifier | modifier le wikicode]
Les jeux de Nim sont des jeux de duel à somme nulle (deux joueurs, un vainqueur et un perdant, pas de partie nulle possible)[2], les sommets du graphe représentant les diverses positions possibles du jeu, et les arêtes les transitions d'une position à une autre. On montre qu'il existe une stratégie optimale, les diverses positions du jeu se répartissant en deux sous-ensembles, les positions gagnantes et les positions perdantes.
Celles-ci sont définies récursivement comme suit, dans le cas où le joueur qui ne peut plus jouer a perdu :
- Les positions finales (à partir desquelles on ne peut plus jouer) sont gagnantes, puisque le joueur qui en atteint une va empêcher son adversaire de jouer et gagne la partie.
- Une position est perdante s'il existe un coup qui mène à une position gagnante. Si un joueur atteint une position perdante, son adversaire pourra donc parvenir à une position gagnante.
- Une position non finale est gagnante si, quel que soit le coup que l'on joue, on arrive à une position perdante. Si un joueur parvient à une position gagnante, son adversaire devra aller à une position perdante.
En remontant des positions finales, on peut donc déterminer petit à petit le statut de chaque position. La stratégie optimale consiste alors à se déplacer d'une position gagnante à l'autre.
La détermination des positions gagnantes dans le cas de graphe complexe utilise la notion de nombre de Grundy ou nimber.
Celui-ci est défini de la façon suivante :
- 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.
Les positions gagnantes sont celles dont le nombre de Grundy est nul. En effet, partant d'une telle position, quel que soit le coup que l'on joue, on arrive à une position dont le nombre de Grundy est non nul (position perdante).
Inversement, partant d'une position perdante, il existe au moins un coup que l'on peut jouer et qui conduit à une position dont le nombre de Grundy est nul (position gagnante).
Par exemple, un jeu de Nim trivial où on aurait un seul tas d'allumettes et où chaque joueur prendrait le nombre d'allumettes qu'il veut, alors la stratégie gagnante consisterait évidemment à prendre toutes les allumettes et le nombre de Grundy de la position de départ est simplement le nombre d'allumettes de ce tas.
Notes[modifier | modifier le wikicode]
- voir : www.pedagogie.ac-nice.fr/mathematiques (GROUPE DE RÉFLEXION SUR L’ENSEIGNEMENT DES MATHÉMATIQUES AU COLLÈGE).
