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

Stratégie de jeu

Ce jeu avantage également le premier joueur avec une stratégie gagnante.

Cette stratégie gagnante est un peu plus difficile à cerner aux premiers abords, mais rapidement applicable après avoir l'astuce :

On va commencer par colorier en vert la case (0,0) qui est l'objectif, puis colorier en noir les cases alignés verticalement, horizontalement et en diagonale.

Les cases avec la valeur de x ou y la plus petite seront en vert, puis on colorie également en noir les cases alignés verticalement, horizontalement et en diagonale.

On répète ce processus jusqu'à atteindre les bords du plateau sans cases libres.