« Nim et la théorie des jeux impartiaux » : différence entre les versions
Aller à la navigation
Aller à la recherche
(Page créée avec « = Description du sujet = * Année 2016 -- 2017 * Tuteur: Pierre Hyvernat * Étudiant : Luca Chapelle * Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des pr... ») |
|||
| Ligne 1 : | Ligne 1 : | ||
Le jeu de NIM |
|||
---- |
|||
= Description du sujet = |
= Description du sujet = |
||
Version du 25 mai 2017 à 11:18
Le jeu de NIM
Description du sujet
- 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