Nim et la théorie des jeux impartiaux - Historique des versions

L.chapelle le 25 mai 2017 à 16:02

2017-05-25T16:02:56Z

← Version précédente		Version du 25 mai 2017 à 16:02
Ligne 99 :		Ligne 99 :
	Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.<br>		Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.<br>

	'''Variantes'''<br>		*'''Variantes'''<br>
	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.		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 <br>		tas 1 : l ce qui nous donne 001 en binaire <br>
Ligne 117 :		Ligne 117 :

	----		----
	'''Programme'''<br>		*'''Programme'''<br>
	Voici mon programme qui a 3 mode de jeu:		Voici mon programme qui a 3 mode de jeu:
	-L'ordinateur joue au hasard.		-L'ordinateur joue au hasard.

L.chapelle le 25 mai 2017 à 16:02

2017-05-25T16:02:28Z

← Version précédente		Version du 25 mai 2017 à 16:02
Ligne 99 :		Ligne 99 :
	Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.<br>		Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.<br>

	'''Variantes'''		'''Variantes'''<br>
	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.		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 <br>		tas 1 : l ce qui nous donne 001 en binaire <br>
Ligne 117 :		Ligne 117 :

	----		----
	'''Programme'''		'''Programme'''<br>
	Voici mon programme qui a 3 mode de jeu:		Voici mon programme qui a 3 mode de jeu:
	-L'ordinateur joue au hasard.		-L'ordinateur joue au hasard.

L.chapelle le 25 mai 2017 à 16:01

2017-05-25T16:01:37Z

← Version précédente		Version du 25 mai 2017 à 16:01
Ligne 195 :		Ligne 195 :
	return tas		return tas
	On voit bien que la stratégie est très courte et la machine fait instantanément le calcule.		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 ~~cas~~ pour que la partie dure le plus longtemps possible(l'adversaire se trompe).		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).
	----		----

L.chapelle le 25 mai 2017 à 16:01

2017-05-25T16:01:04Z

← Version précédente		Version du 25 mai 2017 à 16:01
Ligne 32 :		Ligne 32 :
	Le jeu de NIM version classique aussi appelé jeu des allumettes.<br>		Le jeu de NIM version classique aussi appelé jeu des allumettes.<br>
	Le jeu est composé de plusieurs tas d'allumettes.<br>		Le jeu est composé de plusieurs tas d'allumettes.<br>
	Les ~~régles~~ du jeu sont :<br>		Les règles du jeu sont :<br>
	-On a le droit de retirer le nombre que le='on veut d'allumettes d'en un seul tas.<br>		-On a le droit de retirer le nombre que le='on veut d'allumettes d'en un seul tas.<br>
	-Le gagnant est celui qui retire la dernière allumettes.<br>		-Le gagnant est celui qui retire la dernière allumettes.<br>
Ligne 47 :		Ligne 47 :
	*'''La stratégie gagnante du jeu de NIM'''<br>		*'''La stratégie gagnante du jeu de NIM'''<br>
	C'est Charles Bouton qui trouve la stratégie gagnante en 1901.<br>		C'est Charles Bouton qui trouve la stratégie gagnante en 1901.<br>
	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.<br>		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.<br>
	Auparavant les mathématiciens ce penchais que sur des cas particulier (le plus connu 1,3,5 et 7 allumettes dans 4 tas)<br>		Auparavant les mathématiciens ce penchais que sur des cas particulier (le plus connu 1,3,5 et 7 allumettes dans 4 tas)<br>
	L'article de Bouton est considéré comme "fondateur" pour les jeux combinatoires.<br>		L'article de Bouton est considéré comme "fondateur" pour les jeux combinatoires.<br>
Ligne 194 :		Ligne 194 :
	break		break
	return tas		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 cas pour que la partie dure le plus longtemps possible(l'adversaire se trompe).
	----		----

L.chapelle le 25 mai 2017 à 15:58

2017-05-25T15:58:16Z

← Version précédente		Version du 25 mai 2017 à 15:58
Ligne 175 :		Ligne 175 :
	return res		return res

	def supprimer_ordi2(tas,max_allu):		def supprimer_ordi2(tas,max_allu):
	var=xor(tas,max_allu)		var=xor(tas,max_allu)
	if var == 0 or var > max_allu:		if var == 0 or var > max_allu:

L.chapelle le 25 mai 2017 à 15:57

2017-05-25T15:57:46Z

@@ Ligne 119 : / Ligne 119 : @@
 '''Programme'''
 Voici mon programme qui a 3 mode de jeu:
-  L'ordinateur joue au hasard.
+ -L'ordinateur joue au hasard.
-  L'ordinateur adopte la stratégie gagnante.
+ -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.
+ -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):
@@ Ligne 153 : / Ligne 153 : @@
             print("L'ordinateur a gagné")
     return
 ----

L.chapelle le 25 mai 2017 à 15:54

2017-05-25T15:54:56Z

← Version précédente		Version du 25 mai 2017 à 15:54
Ligne 128 :		Ligne 128 :
	tas.append(random.randint(1,nb_allu))		tas.append(random.randint(1,nb_allu))
	total = total_tas(tas)		total = total_tas(tas)

	while total > 0:		while total > 0:
	if choix == 3 or choix == 4:		if choix == 3 or choix == 4:
	affiche_xor(tas,max_allu)		affiche_xor(tas,max_allu)

	else:		else:
	for i in range(0,len(tas)):		for i in range(0,len(tas)):
	print("Le tas ",i + 1," contient",tas[i],"allumettes")		print("Le tas ",i + 1," contient",tas[i],"allumettes")

	print("C'est à vous de jouer")		print("C'est à vous de jouer")
	num_tas = sup_tas(nbdetas)		num_tas = sup_tas(nbdetas)
	sup = sup_allumettes(max_allu)		sup = sup_allumettes(max_allu)
		⚫	tas = supprimer_allumettes(tas,sup,num_tas)

⚫	tas = supprimer_allumettes(tas,sup,num_tas)


	total = total_tas(tas)		total = total_tas(tas)

	if total == 0:		if total == 0:
	print("Le joueur a gagné : bravo")		print("Le joueur a gagné : bravo")
	break		break
	for i in range(0,len(tas)):		for i in range(0,len(tas)):
	print("Le tas ",i+1," contient",tas[i],"allumettes")		print("Le tas ",i+1," contient",tas[i],"allumettes")

	print("L'ordinateur joue ......")		print("L'ordinateur joue ......")
	if choix == 2 or choix == 4 :		if choix == 2 or choix == 4 :
	tas = supprimer_ordi2(tas,max_allu)		tas = supprimer_ordi2(tas,max_allu)
	else:		else:
	tas = supprimer_ordi(tas,max_allu)		tas = supprimer_ordi(tas,max_allu)

	total = total_tas(tas)		total = total_tas(tas)
	if total == 0:		if total == 0:
	print("L'ordinateur a gagné")		print("L'ordinateur a gagné")
	return		return


	----		----

L.chapelle le 25 mai 2017 à 15:53

2017-05-25T15:53:03Z

@@ Ligne 115 : / Ligne 115 : @@
 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.<br>
 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.<br>
 ----

L.chapelle le 25 mai 2017 à 15:50

2017-05-25T15:50:32Z

@@ Ligne 99 : / Ligne 99 : @@
 Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.<br>
 ** [https://fr.wikipedia.org/wiki/Jeux_de_Nim jeu de Nim]
 ** [https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy théorème de Sprague Grundy]

L.chapelle le 25 mai 2017 à 14:44

2017-05-25T14:44:56Z

← Version précédente		Version du 25 mai 2017 à 14:44
Ligne 70 :		Ligne 70 :
	tas 2 : l l ce qui nous donne 010 en binaire <br>		tas 2 : l l ce qui nous donne 010 en binaire <br>
	tas 3 : 1 1 1 ce qui nous donne 011 en binaire <br>		tas 3 : 1 1 1 ce qui nous donne 011 en binaire <br>
	Le XOR de ces tas est en binaire : 101 <br>		Le XOR de ces tas est en binaire : 101 <br>
	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.<br>		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.<br>
	Donc sur notre exemple il le XOR est différent de 0 il est égale à 5 donc nous sommes sur une position gagnante.<br>		Donc sur notre exemple il le XOR est différent de 0 il est égale à 5 donc nous sommes sur une position gagnante.<br>
Ligne 86 :		Ligne 86 :
	le tas 1 ou il y a un 1 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))<br>		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))<br>
			Donc on ne peut que modifier le tas 1 : <br>
			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 : <br>
			tas 1 : l ce qui nous donne 001 en binaire <br>
			tas 2 : l l ce qui nous donne 010 en binaire <br>
			tas 3 : 1 1 1 ce qui nous donne 011 en binaire <br>
			Le XOR de ces tas est en binaire : 000 <br>

			Le XOR ces tas est bien égale a 0 donc on envoie une position perdante a l'adversaire.<br>

			Selon la stratégie l'adversaire ne peut que nous renvoyer une stratégie gagnante. Vérifions cela :<br>
			Pour nous renvoyer une position gagnante il faut que le xor soit différent de 0.<br>
			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.<br>
			Si le joueur applique cette stratégie il finira par enlevé la dernière allumettes et donc gagner.<br>