Jeu impartial
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
Dans la théorie des jeux combinatoires, un jeu impartial est un jeu tour par tour dans lequel les coups autorisés, ainsi que les gains obtenus, dépendent uniquement de la position, et pas du joueur dont c'est le tour. Un jeu qui n'est pas impartial est appelé jeu partisan.
Exemples[modifier | modifier le code]
Les jeux impartiaux incluent notamment le jeu de Nim, le jeu de Grundy, le jeu de Wythoff, les jeux octaux, le Sprouts, le jeu de Cram, Noktako, ou Chomp.
Les échecs ne sont pas impartiaux, car les coups disponibles à partir d'une position donnée sont différents pour le joueur blanc et le joueur noir (le joueur blanc ne peut pas déplacer les pièces noires, alors que le joueur noir le peut). De même, le jeu de go n'est pas impartial.
Propriété[modifier | modifier le code]
D'après le théorème de Sprague-Grundy tout jeu impartial est équivalent à un tas d'une certaine taille du jeu de Nim.
Article connexe[modifier | modifier le code]
Références[modifier | modifier le code]
- (en) John H. Berlekamp, Conway et Richard Guy, Winning Ways for your Mathematical Plays, Academic Press, (ISBN 0-12-091101-9 et 0-12-091102-7)
- (en) John H. Berlekamp, Conway et Richard Guy, Winning Ways for your Mathematical Plays, A K Peters, 2001-2004, 2e éd. (ISBN 978-1-56881-130-7, 1-56881-142-X et 1-56881-143-8)
