jeu impartial

COMBINATOIRE

Dans la théorie des jeux combinatoires , un jeu impartial est un jeu où deux joueurs jouent à tour de rôle, dans lequel
* toutes les informations concernant le jeu sont connues des deux joueurs à chaque instant
* les coups autorisés, ainsi que les gains obtenus, dépendent uniquement de la position, et pas du joueur dont c’est le tour
* il n’y a pas de partie nulle ou qui se prolonge indéfiniment, le joueur qui ne peut plus déplacer de pion a perdu (ceci dans la version normale, il y a aussi la version dite « misère » où celui qui ne peut plus jouer a gagné) .

Un jeu qui n’est pas impartial est appelé jeu partisan.

Parmi les jeux impartiaux, on peut citer le jeu de Nim , le jeu de Grundy, le jeu de Wythoff, les jeux octaux, le Sprouts, le jeu de Cram, Noktako, ou Chomp.
Remarquons que le jeu d’échecs n’est pas un jeu impartial 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.

D’après le théorème de Sprague-Grundy, chaque position d’un jeu impartial fini est équivalente à un jeu de Nim avec un seul paquet dont le nombre d’allumettes est un entier ; ce nombre est nommé le nimber de la position.