« Jeux d'allumettes/Jeux de Nim » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

Intégrés

Version du 23 juin 2019 à 17:32

**Jeux de Nim**
Leçon : Jeux d'allumettes

Chapitre n^o 4
Chap. préc. :	Jeu de Marienbad
Chap. suiv. :	Sommaire

En raison de limitations techniques, la typographie souhaitable du titre, « Jeux d'allumettes : Jeux de Nim
Jeux d'allumettes/Jeux de Nim », n'a pu être restituée correctement ci-dessus.

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.

Le jeu de Nim classique est le jeu de Marienbad.

Le jeu

Dans les jeux de Nim, on a 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

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).

Exemple de jeu de Nim: Le but du jeu est de déplacer une allumette d'un sommet à l'autre selon les arêtes indiquées. Le gagnant est celui qui parvient au sommet bleu. Les positions gagnantes à atteindre sont en vert. Depuis un sommet vert, on est obligé d'aller à un sommet rouge perdant ; depuis un sommet rouge, on peut atteindre un sommet vert gagnant. Le joueur qui commence perd.

Le jeu de Nim classique ou jeu de Marienbad

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

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

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

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.

Nombres de Grundy des positions du jeu de Nim ci-dessus. Les positions gagnantes ont un nombre de Grundy nul.

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

<\references>

Un contributeur vous informe que cette page, ou cette section de page, n’est pas finie.

Son état actuel est provisoire et doit être pris avec prudence.
Une version améliorée est en préparation et devrait être disponible prochainement.

Pour en suivre l’avancement ou y participer, veuillez consulter la page de discussion.

Jeux d'allumettes

Jeu de Marienbad

Sommaire

↑ en math, on dit: congru à 1 modulo 4.
↑ jeux équivalents à se déplacer d'un sommet à l'autre d'un graphe orienté sans circuit

[1] th, on dit: congru à 1 modulo 4.

[2] ux équivalents à se déplacer d'un sommet à l'autre d'un graphe orienté sans circuit

[1]

[2]

@@ Ligne 9 : / Ligne 9 : @@
 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.
@@ Ligne 18 : / Ligne 19 : @@
 Dans les jeux de Nim, on a 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 ==
+* 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... <ref>en math, on dit: congru à 1 modulo 4.</ref>. 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).
+[[Fichier:JeuNim.svg|droite|vignette|Exemple de jeu de Nim: Le but du jeu est de déplacer une allumette d'un sommet à l'autre selon les arêtes indiquées. Le gagnant est celui qui parvient au sommet bleu. Les positions gagnantes à atteindre sont en vert. Depuis un sommet vert, on est obligé d'aller à un sommet rouge perdant ; depuis un sommet rouge, on peut atteindre un sommet vert gagnant. Le joueur qui commence perd.]]
+== Le jeu de Nim classique ou [[Jeux_d'allumettes/Jeu_de_Marienbad|jeu de Marienbad]] ==
+* Le jeu de Nim classique ou [[Jeux_d'allumettes/Jeu_de_Marienbad|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 ==
+* 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 ==
+* 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 ==
+Les jeux de Nim sont des '''jeux de duel à somme nulle''' (deux joueurs, un vainqueur et un perdant, pas de partie nulle possible) <ref>jeux équivalents à se déplacer d'un sommet à l'autre d'un graphe orienté sans circuit</ref>, 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.
+[[Image:JeuNimber.svg|vignette|Nombres de Grundy des positions du jeu de Nim ci-dessus. Les positions gagnantes ont un nombre de Grundy nul.]]
+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 ==
+<\references>
 {{pas fini}}