Calcul des valeurs de Grundy pour des jeux octaux

Étudiant : Mathieu BRUNOT

Tuteur : Valenti Gledel

Jeu de Impartiaux

Description

Un jeu impartial est un jeu à 2 joueurs où les joueurs jouent à tour de rôle et leurs mouvements possibles ne dépendent pas du joueur qui joue, il n'y a donc pas de hasard ni d'égalité dans une partie.

Le perdant étant celui qui ne peut plus jouer, aussi appelé version normale.

En voici des exemples:

• Jeu de Cram
  Les joueurs mettent des dominos sur une grille. Le joueur qui met le dernier domino gagne.
  
• Jeu de Nim
  Il se joue avec un ou plusieurs tas d'objets exemple des allumettes.
  Chacun des joueurs joue à tour de rôle en choisissant un tas et en retirant autant d’allumettes que souhaité dans le tas, pour que son adversaire n’ait plus la possibilité de jouer, c’est ainsi que le jeu prend fin.
  
• Jeu des bâtonnets Fort Boyard
  Ce jeu consiste à n’avoir que le droit de retirer de 1 à 3 bâtonnets à chaque tour. Hormis la différence est que le joueur perdant est celui qui prend le dernier bâtonnet. Cette condition de victoire est appelé version misère.
  

Stratégie Gagnante

En effet, l’ensemble des jeux impartiaux sont résolubles à l’aide d’outils théorique afin de connaitre l'action à faire pour être le joueur en position gagnante.

Prenons le jeu de Fort Boyard mais cette fois-ci en version normale. Dans celui-ci la stratégie gagnante est de laisser un tas à l'adversaire qui serait un multiple de quatre.

• Pour le trouver il suffit de regarder les positions perdantes dans chaque cas:
  1. Si le nombre de bâtonnets est n=1, le joueur courant gagne car il peut enlever le dernier jeton et laisser l'adversaire avec un tas vide.
  2. Si n=2, le joueur courant gagne car il peut retirer les derniers bâtonnets.
  3. Si n=3, le joueur courant gagne car il peut retirer les derniers bâtonnets.
  4. Si n=4, le joueur courant perd car il va forcément laisser son adversaire dans une position gagnante.
  5. Plus généralement, toute position où $n\equiv 1,2,ou3{\pmod {4}}$est une position gagnante, et toute position où $n\equiv 0{\pmod {4}}$ est une position perdante.

Ainsi on pourrait se demander la stratégie gagnant d'autres jeux tel que le jeu de Nim ou le jeu de Cram

Valeurs de Grundy

Théorème de Sprague-Grundy

Le théorème de Sprague-Grundy nous permet de trouver la stratégie gagnante d’un jeu impartial fini en version normale (le perdant est le joueur ne pouvant plus jouer).

La valeur de Grundy ou d’un tas se calcule récursivement par ses règles :

- Un tas vide a pour valeur de Grundy 0.
- Le nombre Grundy d’une position non nulle est le plus petit entier positif ou nul qui n’est pas dans la liste des valeurs de Grundy des positions que l’on peut atteindre à partir de notre position.

Une position perdante d’un jeu celle qui donne une valeur de Grundy de 0.

Calcul des valeurs pour le jeu de Nim

Cas à 1 tas

La valeur de Grundy du jeu de Nim classique d’un tas de taille n (un entier) est celle du nombre de bâtonnets dans ce tas.

On l’explique car toutes les tailles de tas strictement inférieures à n sont atteignables à partir de celui-ci. Alors le minimum exclu(mex) des valeurs atteignables est n.

On appelle ce nombre précis dans le cas du jeu de Nim, un nimber.

Donc par exemple dans un tas de taille 9 du jeu Nim, on aurait une valeur de Grundy de 9, ceci est simple à comprendre.

Cas à plusieurs tas

Dans le cas de plusieurs tas, la valeur de Grundy de tous les jeux est le XOR de toutes les valeurs de Grundy de chaque tas.

Par exemple :

Voici un jeu de Nim composé de trois tas de bâtonnets: Exemple_jeu_de_nim.png