Sprague Grundy Theorem And Its Applications

Introduction

Nous allons aborder un thème qui rentre dans le domaine des jeux combinatoires.
Par jeux combinatoires, on parle d'un jeu qui comporte deux joueurs qui jouent alternance et dans lequel le hasard n'a pas sa place. On a donc aucune information cachée et le joueur qui ne peux plus continuer à jouer est un le perdant.
Pour cela, il faut connaître les principes du théorème de Sprague-Grundy, à l'origine même de la théorie des jeux combinatoires.

Théorème de Sprague-Grundy

Les positions N/P

Dans un jeu, on peut définir deux types de positions. Une position gagnante et une position perdante.
Plus précisément, la position P (previous player win) sera la position telle que le prochain joueur qui entreprendra un coup perdra, et la position N sera la position telle que le prochain joueur qui entreprendra un coup gagne (next player win).
Sur cette base on peut définir trois principes à respecter :

  • les positions finales sont toutes des positions P
  • S'il n'y a que des positions N, alors le prochain joueur gagne
  • S'il y a au moins une position P, alors le premier joueur peut gagner

Dans un jeu combinatoire, soit le premier joueur soit le second peut gagne si les joueurs ne commettent aucune erreur.

La somme de Nim

La somme de Nim est une opération qui s'effectue en relation avec l'expression d'un nombre sous sa forme binaire. Pour rappel le système binaire est l'expression d'un nombre selon la base 2

  • exemple : 7 est la somme de 22 + 21 + 20 est sera donc écrite sous la forme binaire suivante [1 1 1]2

La somme de Nim consiste donc à additionner des nombres exprimés sous leur forme binaire en respectant certaines règles d’opérations, à savoir :

  • [1] ⊕ [1] = 0
  • [1] ⊕ [0] = [0] ⊕ [1] = [1]

voici un exemple plus concret:

  • prenons 7 ⊕ 4 :

[1 1 1]2

[1 0 0]2

[0 1 1]2

Elle est essentielle pour définir une stratégie gagnante lorsque l’on est face à une somme de jeux combinatoires, tout du moins si on la combine avec les valeurs de Sprague-Grundy (voir ci-dessous)

Les valeurs de Sprague-Grundy

Pour définir les valeurs de Sprague-Grundy, on a besoin de définir la notion de MEX

  • MEX est une abréviation de Minimum excludent
  • Cette notion consiste à considérer le nombre naturel le plus petit qui n’est pas dans un ensemble de nombres définis
  • Prenons alors l’ensemble de nombres {0,1,3,7} ; la valeur Sprague-Grundy est alors le MEX de l’ensemble {0,1,3,7}
    • De ce fait, le nombre réel le plus petit qui n’est pas dans l’ensemble {0,1,3,7} est le nombre 2
  • La valeur Sprague-Grundy qui nous intéresse tout particulièrement est la valeur MEX=0
    • En effet, la valeur 0 correspond à la position P, qui définit donc une position gagnante

Adopter une stratégie gagnante

Pour adopter une stratégie gagnante, il faut donc s’arranger pour constamment se retrouver sur une position P, ou alors sur une position 0 si on considère les valeurs de Srague-Grundy.

  • Pour savoir quel mouvement d’un jeu nous permet d’arriver sur une case gagnante, il faut utiliser la somme de Nim :
    • Il faut alors modifier cette somme de Nim pour arriver à une situation finale [0 0 0]2

Pour mieux comprendre le principe ci-dessus, vous trouverez un exemple dans le chapitre suivant

Exemple avec le Jeu de Nim

Les règles du jeu
Prenons l'exemple de 2 rangées d'allumettes, avec 8 allumettes dans la première et 13 allumettes dans la deuxième

  • Ce jeu combinatoire comporte donc 2 joueurs
    • Chacun à leur tour, les joueurs peuvent enlever un nombre quelconque d'allumettes dans l'une des deux rangées
    • Le joueur qui ne peut plus retirer d'allumettes perd le jeu
flickr:10854366806

Figure d'un jeu de NIM avec des allumettes

Développer une stratégie gagnante

Pour développer une stratégie gagnante, il faut retranscrire le nombre d'allumettes de chacune des rangées dans un système binaire pour ensuite en faire la somme de Nim

  • dans ce cas nous aurons la somme de Nim suivante : NIM (8,11) = NIM (8) + NIM (11)
    • avec 8 = [1 0 0 0]2 et 11= [1 0 1 1]2
    • La somme de Nim correspondante sera donc [1 0 0 0]2 ⊕ [1 0 1 1]2 = [0 0 1 1]2
  • Pour qu'un joueur adopte la stratégie gagnante, il devra donc s'arranger pour enlever un nombre de bâtonnets de telle façon à ce que la somme de Nim soit [0 0 0 0]

Le jeu : Even if not All - All if Odd

Règle du jeu

  • Deux joueurs jouent alternativement; la position de départ comporte plusieurs piles de chips (ou allumettes, bâtonnets, …) qui sont disposées sur une table.
  • Chaque joueur choisit alternativement une pile et y enlève un certain nombre de chips.
  • Il faut cependant suivre deux règles :
    • (1) s'il reste un nombre paire de chips, on ne peut pas enlever toute la pile
    • (2) s'il reste un nombre impaire de chips, on peut enlever toute la pile, si on le veut.
  • Pour ce jeu, les valeurs de Sprague-Grundy sont définies selon les fonctions suivantes:
    • Nombre impaire de chips : g(2k-1) = k
    • Nombre pair de chips: g(2k) = k-1
  • La stratégie gagnante est la même que pour le jeu de NIM. Il faut toujours faire en sorte que l'on se trouve sur une position à valeur égale à 0. Pour cela, il faut modifier une des piles pour que la somme de NIM soit égal à 0. Il y a deux positions finales: lorsqu'il reste 0 ou 2 chips.

Exemple d'un déroulement de jeu

Prenons le cas d'un jeu avec une pile contenant 16 chips, une en contenant 13 et la dernière 18

  • A partir de là, on peut calculer la valeur de Sprague-Grundy pour chacune des piles avec les deux définitions données précédemment

Joueur 1: premier coup

  • Les valeurs de Sprague-Grundy :
    • Pour la pile de 16 Chips : g(16) = g(2*8) = 8-1 = 7
    • Pour la pile de 18 Chips : g(18) = g(2*9) = 9-1 = 8
    • Pour la pile de 13 Chips : g(13) = g(2*7-1) = 7
  • La somme de Nim des valeurs de Sprague-Grundy :
    • on a les valeurs 7, 8 et 7
    • la somme de Nim de ces valeurs donnent : [0 1 1 1]2 ⊕ [1 0 0 0]2 ⊕ [0 1 1 1]2 = [1 0 0 0]2
    • pour avoir une stratégie gagnante , il faut retirer un certain nombre de Chips pour que la somme de Nim soit nulle
      • on veut alors g(x)=0 pour la pile de 18 chips pour éliminer le [1 0 0 0]2 et on obtient alors x = 2 car g(2) = g(2*1) = 1-1 =0
      • il faut donc enlever 16 Chips à la pile de 18 Chips pour qu'il n'en reste que 2; on a alors dans ce cas la somme de Nim = 0

Joueur 2: premier coup
On se trouve déjà avec une somme de Nim étant égale à 0

  • De ce fait, le deuxième joueur, quelque soit son choix, ne peux que se retrouver dans une position où la somme de Nim sera différente de 0
  • Au hasard, il enlève 3 « chips » de la pile de 13.

Joueur 1: deuxième coup

  • Les valeurs de Sprague-Grundy :
    • Pour la pile de 16 Chips : g(16) = g(2*8) = 8-1 = 7
    • Pour la pile de 2 Chips : g(2) = g(2*1) = 1-1 = 0
    • Pour la pile de 10 Chips : g(10) = g(2*5-1)= 5-1 = 4
  • La somme de Nim des valeurs de Sprague-Grundy :
    • on a les valeurs 7, 0 et 4
    • la somme de Nim de ces valeurs donnent : [0 1 1 1]2 ⊕ [0 0 0 0]2 ⊕ [0 1 0 0]2 = [0 0 1 1]2
    • pour avoir une stratégie gagnante , il faut retirer un certain nombre de Chips pour que la somme de Nim soit nulle
      • on veut alors g(x)=4 pour la pile de 16 chips pour avoir [0 1 0 0]2 et on obtient alors x = 7 car g(7) = g(2*8) = 8-1 = 7
      • il faut donc enlever 9 Chips à la pile de 16 Chips pour qu'il n'en reste que 7; on a alors dans ce cas la somme de Nim = 0

Joueur 2: deuxième coup
Le deuxième joueur ne peut à nouveau pas se placer dans une position gagnante

  • Au hasard, il enlève 1 « chips » à la pile de 10

Joueur 1: troisième coup

  • Les valeurs de Sprague-Grundy :
    • Pour la pile de 7 Chips : g(7) = g(2*4-1) = 4
    • Pour la pile de 2 Chips : g(2) = g(2*1) = 1-1 = 0
    • Pour la pile de 9 Chips : g(9) = g(2*5-1)= 5
  • La somme de Nim des valeurs de Sprague-Grundy :
    • on a les valeurs 4, 0 et 5
    • la somme de Nim de ces valeurs donnent : [1 0 0]2 ⊕ [0 0 0]2 ⊕ [1 0 1]2 = [0 0 1]2
    • pour avoir une stratégie gagnante , il faut retirer un certain nombre de Chips pour que la somme de Nim soit nulle
      • on veut alors g(x)=4 pour la pile de 9 chips pour avoir [1 0 0] et on obtient alors x = 7 car g(7) = g(2*8) = 8-1 = 7
      • il faut donc enlever 2 Chips à la pile de 9 Chips pour qu'il n'en reste que 7; on a alors dans ce cas la somme de Nim = 0

Joueur 2: troisième coup
Au hasard, il enlève 1 « chips » à la pile de 2.

Joueur 1: quatrième coup

  • Les valeurs de Sprague-Grundy :
    • Pour la pile de 7 Chips : g(7) = g(2*4-1) = 4
    • Pour la pile de 1 Chips : g(1) = g(2*1-1) = 1
    • Pour la pile de 7 Chips : g(7) = g(2*4-1)= 4
  • La somme de Nim des valeurs de Sprague-Grundy :
    • on a les valeurs 4, 1 et 4
    • la somme de Nim de ces valeurs donnent : [1 0 0]2 ⊕ [0 0 1]2 ⊕ [1 0 0]2 = [0 0 1]2
    • pour avoir une stratégie gagnante , il faut retirer un certain nombre de Chips pour que la somme de Nim soit nulle
      • on veut alors g(x<1)=0 pour la pile de 1 chips pour avoir [0 0 0]2 et on obtient alors x = 0
      • il faut donc enlever la dernière Chips à la pile de 1 Chips pour qu'il n'en reste plus; on a alors dans ce cas la somme de Nim = 0

Joueur 2: quatrième coup
Au hasard, il enlève 4 « chips » à la 1ère de 7.

Joueur 1: cinquième coup

  • Les valeurs de Sprague-Grundy :
    • Pour la pile de 3 Chips : g(3) = g(2*2-1) = 2
    • Pour la pile de 7 Chips : g(7) = g(2*4-1)= 4
  • La somme de Nim des valeurs de Sprague-Grundy :
    • on a les valeurs 2,4
    • la somme de Nim de ces valeurs donnent : [0 1 0]2 ⊕ [1 0 0]2 = [1 1 0]2
    • pour avoir une stratégie gagnante , il faut retirer un certain nombre de Chips pour que la somme de Nim soit nulle
      • on veut alors g(x)=2 pour la pile de 4 chips pour avoir [0 1 0]2 et on obtient alors x = 3 car g(3) = g(2*2-1)= 2
      • il faut donc enlever 4 Chips à la pile de 7 Chips pour qu'il en reste 3; on a alors dans ce cas la somme de Nim = 0

Joueur 2: cinquième coup
Au hasard, il enlève la totalité des Chips d'une des piles de 3.

Joueur 1: sixième coup

Le joueur 1 se retrouve alors avec une seule pile, avec un nombre impair de Chips (3)

  • il peut donc enlever la totalité de la pile et évidemment se retrouver dans une position gagante

Joueur 2: sixième coup
Il ne peut plus jouer → il a perdu.

Exemple d'un jeu combinatoire d'une somme de deux jeux différents

Règle du jeu d'échec de Wythoff

  • Pour un jeu de Wythoff :
    • Deux joueurs jouent alternativement sur un échiquier de dimension 5x5, avec un seul pion
    • La position de départ du pion se trouve dans la case tout en haut à gauche de la grille
    • Chaque joueur peut alors bouger leur pion selon des règles de déplacement définies préalablement (à gauche ou vers le bas)
    • Le joueur qui amène le pion en bas à gauche de la grille à gagner puisque le joueur suivant ne plus opérer aucun déplacement
  • Dans le cas d'une somme de deux jeux de Wythoff, on définit les règles comme suit:
    • on se trouve alors avec deux pions qui sont soumis à des règles différentes, tout deux placés dans la case au sommet à droite :
    • prenons par exemple un pion violet avec comme déplacement autorisé : une case vers la droite, une case en bas ou une case en diagonal vers le bas et la gauche
    • prenons ensuite un pion orange avec comme déplacement autorisé : 1 ou 2 case(s) vers la droite, 1 ou 2 case(s) vers le bas ou 1 ou 2 cases en diagonal vers le bas et vers la gauche
flickr:10854454204

Déroulement du jeu

Chaque joueur joue tour à tour en déplaçant l'un des deux pions à choix en effectuant un mouvement qui suit la règle de déplacement de ce pion

  • la partie se termine lorsque les deux pions se retrouvent dans la case du bas à gauche

La stratégie gagnante repose toujours sur une somme de Nim égale à 0

  • il faut donc tout d'abord reporter les valeurs Sprague-Grundy dans chacune des case de l'échiquier
flickr:10854645743flickr:10854453484
= Valeurs pour les deux pions : Orange et Violet
  • à partir de là, chaque pion sera attribué au nombre de la case où il se trouve (qui correspond à la valeur Sprague-Grundy de la case)
    • Exemple: si un pion se trouve sur une case avec une valeur Sprague-Grundy égale à 2, alors son expression binaire sera [0 1 0]2
    • Attention: une même case n'a pas les mêmes valeurs Sprague-Grundy selon si l'on a le pion orange ou violet!!!
  • Pour évaluer la somme de Nim des deux jeux, il suffira d'additionner (selon la somme de Nim) les expressions binaires de chacune des deux cases où se trouve les pions
    • Exemple: prenons le cas où le premier pion se trouve sur une case dont la valeur de Sprague-Grundy est 2, et le second pion se trouve sur une case dont la valeur de Sprague-Grundy est 1
      • on aura alors la somme de Nim suivante : [0 1 0]2 ⊕ [0 0 1]2 = [0 1 1]2

La stratégie gagnante consiste alors à déplacer l'un des deux pions de telle sorte à ramener cette somme de Nim à 0

Exemples de déplacements pour arriver à une position gagante

Pour arriver à une position gagnante, il faut déplacer un des deux pions pour ramener la somme de Nim à zéro

  • Nous allons l'illustrer dans plusieurs cas concret d'une somme de deux jeux combinatoires
  • Pour les valeurs de Sprague-Grundy, il faut se référer à l'image précédente
flickr:10854454204

Somme de Nim

  • Pour le jeton violet : on se trouve dans une case où la valeur Sprague-Grundy est 0 : en nombre binaire [0 0 0]2
  • Pour le jeton orange : on se trouve dans une case où la valeur Sprague-Grundy est 2 : en nombre binaire [0 1 0]2
  • la somme de Nim sera alors : [0 0 0]2 ⊕ [0 1 0]2 = [0 1 0]2

Pour arriver à une position gagnante, on peut par exemple:

  • ramener le jeton violet dans une case où la valeur Sprague-Grundy est égale à 2
  • ou alors ramener le jeton orange sur une case où la valeur Sprague-Grundy est égale à 0

On voit qu'on a la possibilité d'effectuer différents mouvements, 4 au total, tout en restant dans une position gagnante

flickr:10854366176

Somme de Nim

  • Pour le jeton violet : on se trouve dans une case où la valeur Sprague-Grundy est 3 : en nombre binaire [0 1 1]2
  • Pour le jeton orange : on se trouve dans une case où la valeur Sprague-Grundy est 2 : en nombre binaire [0 1 0]2
  • la somme de Nim sera alors : [0 1 1]2 ⊕ [0 1 0]2 = [0 0 1]2

Pour arriver à une position gagnante, on a ici qu'une seule solution :

  • ramener le jeton violet dans une case où la valeur Sprague-Grundy est égale à 2
  • on aura alors une somme de Nim nulle
flickr:10854366056

Somme de Nim

  • Pour le jeton violet : on se trouve dans une case où la valeur Sprague-Grundy est 1 : en nombre binaire [0 0 1]2
  • Pour le jeton orange : on se trouve dans une case où la valeur Sprague-Grundy est 1 : en nombre binaire [0 0 1]2
  • la somme de Nim sera alors : [0 0 1]2 ⊕ [0 0 1]2 = [0 0 0]2

Dans ce cas, il est impossible d'arriver à une position gagnante ; en effet, quelque soit le mouvement que l'on effectuera, on retombera sur une somme de Nim différente de 0

Sources

Cour BSc_SI du SA 2013 de Mr. Leuenberger, Université de Fribourg, Faculté des Mathématiques.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License