Valeurs de Sprague-Grundy pour le jeu de Wythoff

Étudiant : Nolann SANMARTI

Tuteur : Stéphane TAVENAS

Jeu de Nim (Jeu simple à 1 plateau)

Description du jeu

Le jeu de Nim est un jeu à deux joueurs qui se joue en tour par tour.

Des allumettes sont disposées sur une table, en ligne, et chaque joueur retire entre 1 et 3 allumettes de cette ligne.

La personne qui retire la dernière allumette est perdante.

• Exemple avec 12 allumettes :
  1. Le joueur A retire 2 allumettes. Il en reste 10.
  2. Le joueur B retire 3 allumettes. Il en reste 7.
  3. Le joueur A retire 1 allumette. Il en reste 6.
  4. Le joueur B retire 2 allumettes. Il en reste 4.
  5. Le joueur A retire 3 allumettes. Il en reste 1.
  6. Le joueur B perd car il est forcé de prendre la dernière allumette.

Stratégie de jeu

Ce jeu est un jeu avantageant le premier joueur par le fait qu'une stratégie gagnante est présente. En effet, on sait que chaque joueur ne peut enlever qu'entre 1 et 3 allumettes, donc en ayant 5 allumettes sur le plateau :

1. Si le joueur A enlève 1 allumette, on aura alors 4 allumettes sur le plateau et le joueur B enlèvera 3 allumettes ;
2. Si le joueur A enlève 2 allumettes, on aura alors 3 allumettes sur le plateau et le joueur B enlèvera 2 allumettes ;
3. Si le joueur A enlève 3 allumettes, on aura alors 2 allumettes sur le plateau et le joueur B enlèvera 1 allumette.

On remarque que cette stratégie peut être appliquée pour passer de 9 à 5, de 13 à 9, et ainsi de suite.

En gardant cet écart de 4, on aura une suite de positions perdantes permettant ainsi en se positionnant dessus de faire perdre l'adversaire.

Suite : 1,5,9,13,17,...