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,...

Jeu de Wythoff (Jeu à 2 plateaux)

Description du jeu

Le jeu de Wythoff est une variante du jeu de Nim où l'on va rajouter un jeu d'allumettes.

Les règles sont également un peu complexifiés pour s'adapter à 2 jeux :

• On peut retirer le nombre d'allumettes qu'on veut dans 1 seul des jeux ;
• On peut retirer le nombre d'allumettes qu'on veut dans les 2 jeux.

À l'inverse du jeu d'avant, le but est de retirer la dernière allumette des jeux (Les deux jeux vides).

Pour simplifier la lecture, on va écrire ces valeurs comme des coordonnées de tableau.

Le nombre d'allumettes dans le 1er paquet sera x // Le nombre d'allumettes dans le 2e paquet sera y // On aura donc (x,y) le nombres d'allumettes dans chacun des paquets.

Exemple avec (8,5) :

1. Le joueur A enlève 4 à x. On se retrouve en (4,5).
2. Le joueur B enlève 1 à x et y. On se retrouve en (3,4).
3. Le joueur A enlève 3 à y. On se retrouve en (3,1).
4. Le joueur B enlève 1 à x. On se retrouve en (2,1).
5. Le joueur A enlève 1 à x et y. On se retrouve en (1,0).
6. Le joueur B gagne en retirant 1 à x. On se retrouve en (0,0).