Nim et la théorie des jeux impartiaux
- Année 2016 -- 2017
- Tuteur: Pierre Hyvernat
- Étudiant : Luca Chapelle
- Les jeux de NIM
Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
- Histoire
Les jeux de NIM sont des jeux de stratégie pure, sans hasard.
Ce sont des jeux très courants et semblent avoir été pratiqué aux XVIe siècle en France.
Leur origines sont probablement plus anciennes.
On retrouve notamment des traces en Chine sous le nom de FAN-TAN et en Afrique aussi.
Le nom actuel à été donné par le mathématicien américain Charles Léonard Bouton en 1901.
C'est Bouton qui réussi a trouvé un algorithme pour gagner a tous les coups.
- Les jeux de Nim
Ce sont des jeux qui se jouent a deux adversaire (des variantes a 3 peuvent exister). Les deux adversaires jouent a tour de rôle et il n'y a pas de hasard.
Ces jeux se joue généralement avec des allumettes, des caillous, des os ect.....
Le joueur qui ne peut plus jouer perd la partie. A tout moment de la partie les deux joueurs connaissent toutes les informations du jeux (plateaux, nombre de pions restant).
Tous le jeux qui réunissent ces conditions sont appelés des jeux impartiaux. Et tous jeux impartiaux possède une stratégie gagnante.
- Le Jeu de NIM
Les jeux de NIM sont entièrement résolu en 1901. Charles Bouton,mathématicien américain se penche d'abord sur le jeu de NIM original.
Le jeu de NIM version classique aussi appelé jeu des allumettes.
Le jeu est composé de plusieurs tas d'allumettes.
Les règles du jeu sont :
-On a le droit de retirer le nombre que le='on veut d'allumettes d'en un seul tas.
-Le gagnant est celui qui retire la dernière allumettes.
Il existe beaucoup de variantes de ce jeu.
Le jeu de NIM est un jeu impartiale donc il possède une stratégie gagnante.
Une stratégie gagnante c'est quoi :
-C'est une stratégie qui permet de gagner quoique joue l'adversaire, si on ne se trompe pas.
Il y a deux positions au cours du jeu. Une position perdante et une gagnante.
Quant c'est à nous de jouer soit on est sur une position perdante est quant on joue on est obligé de renvoyer une position gagnante a l'adversaire.
Soit on est sur une position gagnante et si on connait la stratégie on envoie une position perdante a l'adversaire.
On est sur de gagner car l'adversaire est obliger de nous envoyer une position gagnante.
- La stratégie gagnante du jeu de NIM
C'est Charles Bouton qui trouve la stratégie gagnante en 1901.
Dans son article il se penche sur le jeu de NIM en générale : Peut importe le nombre de tas et d'allumettes par tas il faut que la stratégie marche.
Auparavant les mathématiciens ce penchais que sur des cas particulier (le plus connu 1,3,5 et 7 allumettes dans 4 tas)
L'article de Bouton est considéré comme "fondateur" pour les jeux combinatoires.
Nous allons voir cette stratégie sur un exemple :
Le premier tas contient 4 allumettes, le deuxième tas en contient 2 et le troisième 3.
Ce qui nous donne cela :
tas 1 : l l l l
tas 2 : l l
tas 3 : 1 1 1
Pour savoir si on est dans une position gagnante ou perdante il suffit de faire une addition sans retenus en binaire (dans la base 2). Cette opération s’appelle le XOR.
1 XOR 0 = 1
1 XOR 1 = 0
Reprenons l'exemple ci-dessus :
tas 1 : l l l l ce qui nous donne 100 en binaire
tas 2 : l l ce qui nous donne 010 en binaire
tas 3 : 1 1 1 ce qui nous donne 011 en binaire
Donc il faut faire le XOR entre ces 3 tas (ou l’addition sans retenue en base 2 c est la même chose (en binaire 1+1 =0)).
tas 1 : l l l l ce qui nous donne 100 en binaire
tas 2 : l l ce qui nous donne 010 en binaire
tas 3 : 1 1 1 ce qui nous donne 011 en binaire
Le XOR de ces tas est en binaire : 101
Selon la stratégie gagnante si le XOR de tous les tas est égale a 0 alors nous sommes dans une postions perdantes alors que si il est différents de 0 on est en position gagnante.
Donc sur notre exemple il le XOR est différent de 0 il est égale à 5 donc nous sommes sur une position gagnante.
Donc si l'on veut gagner il suffit de suivre la stratégie qui nous dit d'envoyer une position perdante a l'adversaire.
Pour se faire il suffit d'envoyer une configuration ou le XOR de tous les tas est égale a 0
Donc suivant les règles du jeu il faut modifier qu'un seul tas.
Le quelle allons nous modifier :
Pour que le XOR soit égale a 0 il faut changer le premier 1 en 0 et le troisième 1 en 0(101 --> 000)
Donc pour cela dans un seul tas nous allons changer le premier chiffre en 1 si il est égale a 0 ou en 0 si il est égale a 1.
Par exemple sur le deuxième tas 010 --> 110. Si on refais le XOR on voit que le premier 1 s'est transformé en 0.( xor = 001)
Donc il maintenant il faut choisir sur le quelle des trois tas on va modifier.
Dans l'exemple on a deux cas différents :
le tas 2 et 3 ou il y a un 0 en premier le tas 1 ou il y a un 1 en premier
Si on choisi de modifier le tas 2 ou 3 on rajouterais des allumettes et c'est interdits dans ce jeu (tas 2 010(2) -->110(5))
Donc on ne peut que modifier le tas 1 :
Vu qu'on ne peut modifier qu'un seul tas le 3eme chiffre qui est 0 devient 1 (car le xor est 101). Ce qui nous donne :
tas 1 : l ce qui nous donne 001 en binaire
tas 2 : l l ce qui nous donne 010 en binaire
tas 3 : 1 1 1 ce qui nous donne 011 en binaire
Le XOR de ces tas est en binaire : 000
Le XOR ces tas est bien égale a 0 donc on envoie une position perdante a l'adversaire.
Selon la stratégie l'adversaire ne peut que nous renvoyer une stratégie gagnante. Vérifions cela :
Pour nous renvoyer une position gagnante il faut que le xor soit différent de 0.
On voit bien que cela est impossible car si il enlève au moins une allumettes dans n’importe quel tas le xor sera différent de 0.Donc il,nous renvoie une position gagnante a chaque fois.
Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.
- Variantes
Il existe plusieurs variantes du jeu de NIM. La plus connue est celle ou le joueur qui enlève la dernière allumettes perd. La stratégie est la même (ce qui est rare pour ce genre de jeu) jusqu’à la fin quant il reste un seul tas ou il y a plusieurs allumettes.
tas 1 : l ce qui nous donne 001 en binaire
tas 2 : l ce qui nous donne 001 en binaire
tas 3 : 1 ce qui nous donne 001 en binaire
tas 4 : l ce qui nous donne 001 en binaire
tas 5 : l ce qui nous donne 001 en binaire
tas 6 : 1 1 1 ce qui nous donne 011 en binaire
Si les règles sont les classiques il suffirait d'enlever une allumettes 2 allumettes dans le tas 6.
Alors que si le perdant est celui qui prends les allumettes il suffit de prendre les 3 allumettes dans le tas 6 pour qu'il reste un nombre impaire de tas de 1 allumettes (si il y a déjà un nombre impair de tas laissé une allumettes au lieu de tout prendre).
Une autre variantes très inintéressantes est la variantes de Moore qui consiste a prendre plusieurs allumettes dans plusieurs tas avec un nombre limité de tas ( ex on a le droit de prendre autant d'allumettes que l'on veut dans 3 tas différent).
On appellera ce nombre de tas max t.
Donc si t = 3 la stratégie consiste a faire l'addition sans retenue en base t+1 donc en base 4 (3+3 = 0) de tous les tas et si le résultat est égale a 0 on est en position perdante et si il est différent de 0 on est en position gagnante.
Dans la version classique du jeu on a le droit a retiré dans un seul tas donc t = 1 donc l'addition sans retenue est en base 2 et l'addition sans retenue en base 2 s'appelle le XOR.
- Programme
Voici mon programme qui a 3 mode de jeu:
-L'ordinateur joue au hasard. -L'ordinateur adopte la stratégie gagnante. -On affiche pour le joueur a chaque coup le nombre d'allumettes qui faut retirer dans un tas pour gagner.
Programme principale
def main(choix,nbdetas,max_allu,nb_allu):
tas =[]
for i in range (0,nbdetas):
tas.append(random.randint(1,nb_allu))
total = total_tas(tas)
while total > 0:
if choix == 3 or choix == 4:
affiche_xor(tas,max_allu)
else:
for i in range(0,len(tas)):
print("Le tas ",i + 1," contient",tas[i],"allumettes")
print("C'est à vous de jouer")
num_tas = sup_tas(nbdetas)
sup = sup_allumettes(max_allu)
tas = supprimer_allumettes(tas,sup,num_tas)
total = total_tas(tas)
if total == 0:
print("Le joueur a gagné : bravo")
break
for i in range(0,len(tas)):
print("Le tas ",i+1," contient",tas[i],"allumettes")
print("L'ordinateur joue ......")
if choix == 2 or choix == 4 :
tas = supprimer_ordi2(tas,max_allu)
else:
tas = supprimer_ordi(tas,max_allu)
total = total_tas(tas)
if total == 0:
print("L'ordinateur a gagné")
return
Fonction ou l'ordinateur enlève des allumettes au hasard
def supprimer_ordi(tas,max_allu):
i = 0
sup=random.randint(1,max_allu)
num_tas = random.randint(0,len(tas)-1)
while i == 0:
if tas[num_tas] <= 0:
num_tas = random.randint(0,len(tas)-1)
else:
i = 1
tas[num_tas] = tas[num_tas] - sup
if tas[num_tas] < 0:
tas[num_tas] = 0
return tas
Fonction ou l'ordinateur adopte la stratégie gagnante
def xor(tas,max_allu):
res = 0
for i in range(0,len(tas)):
res = res^(tas[i])
return res
def supprimer_ordi2(tas,max_allu):
var=xor(tas,max_allu)
if var == 0 or var > max_allu:
i = 0
sup = 1
num_tas = random.randint(0,len(tas)-1)
while i == 0:
if tas[num_tas] <= 0:
num_tas = random.randint(0,len(tas)-1)
else:
i = 1
tas[num_tas] = tas[num_tas] - sup
if tas[num_tas] < 0:
tas[num_tas] = 0
for i in range(0,len(tas)):
if tas[i] ^ (var) < tas[i]:
tas[i] = tas[i]^(var)
break
return tas
On voit bien que la stratégie est très courte et la machine fait instantanément le calcule. Si l'ordinateur a une position perdante (xor=0) je l'ai fait enlever 1 allumettes dans n'importe quelle tas pour que la partie dure le plus longtemps possible(l'adversaire se trompe).
Sources