« Nim et la théorie des jeux impartiaux » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 11 : | Ligne 11 : | ||
Les jeux de Nim |
Les jeux de Nim |
||
Ce sont des jeux qui se jouent a deux adversaire (des variantes a 3 peuvent exister). Les deux adversaires jouent a tour de rôle et il n'y a pas de hasard. |
Ce sont des jeux qui se jouent a deux adversaire (des variantes a 3 peuvent exister). Les deux adversaires jouent a tour de rôle et il n'y a pas de hasard. |
||
Ces jeux se joue généralement avec des allumettes, des caillous, des os ect..... |
|||
Le joueur qui ne peut plus jouer perd la partie. A tout moment de la partie les deux joueurs connaissent toutes les informations du jeux (plateaux, nombre de pions restant). |
|||
Tous le jeux qui réunissent ces conditions sont appelés des jeux impartiaux. Tous jeux impartiaux possède une stratégie gagnante. |
|||
* Année 2016 -- 2017 |
* Année 2016 -- 2017 |
||
Version du 25 mai 2017 à 13:28
Les jeux de NIM
Histoire
Les jeux de NIM sont des jeux de stratégie pure, sans hasard. Ce sont des jeux très courants et semblent avoir été pratiqué aux XVIe siècle en France. Leur origines sont probablement plus anciennes. On retrouve notamment des traces en Chine sous le nom de FAN-TAN et en Afrique aussi. Le nom actuel à été donné par le mathématicien anglais Charles Léonard Bouton en 1901. C'est Bouton qui réussi a trouvé un algorithme pour gagner a tous les coups.
Les jeux de Nim Ce sont des jeux qui se jouent a deux adversaire (des variantes a 3 peuvent exister). Les deux adversaires jouent a tour de rôle et il n'y a pas de hasard. Ces jeux se joue généralement avec des allumettes, des caillous, des os ect..... Le joueur qui ne peut plus jouer perd la partie. A tout moment de la partie les deux joueurs connaissent toutes les informations du jeux (plateaux, nombre de pions restant). Tous le jeux qui réunissent ces conditions sont appelés des jeux impartiaux. Tous jeux impartiaux possède une stratégie gagnante.
- Année 2016 -- 2017
- Tuteur: Pierre Hyvernat
- Étudiant : Luca Chapelle
- Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
- Objectifs:
- comprendre la théorie du jeu de Nim (et la programmer)
- comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
- regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
- programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux
- Liens pour commencer