Inscription / Connexion Nouveau Sujet
Jeu de nim
Bonjour,
Je cherche à gagner à tout les coups au jeu de nim en commençant en deuxième, sachant que celui qui prends en dernier une allumette a perdu. Et que l'on peut prendre autant d'allumettes que l'on veut sur un tas.
Le plateau:
|
| | |
| | | | |
| | | | | | |
Sachant qu'il y a 16 allumettes à la base j'ai tenté que le resultat d'un modulo 4 soit toujours 1 mais je n'aboutis pas.
Merci par avance de votre aide
Bonsoir, oui moi je connaissais la recette qui consiste à traduire en binaire chaque ligne :
au début ça donne donc 1 ; 11;111;1111 puis à additionner (en base 10) donc ici ça donne 1234. Si c'est pair c'est perdant (donc notamment on voit que celui qui commence perd).
(ça revient à prendre des modulo d'ailleurs mais quand j'étais petit, je ne connaissais pas les modulos et j'avais trouvé cette recette là)
Donc un algorithme est simple à faire, il teste toutes les allumettes et dès qu'il tombe sur une qui donne une somme paire, il la prend. S'il en trouve aucune (c'est qu'il est en train de perdre), il en prend une dans la ligne qui en a le plus (pour compliquer les choix de l'adversaire).
Bonjour,
c'est effectivement assez archi-connu
l'intéressant est de généraliser à un nombre quelconque d'allumettes
il y a deux variantes
le jeu normal et le "qui perd gagne" selon que celui qui prend la dernière à perdu ou gagné
il est intéressant de constater que le fonctionnement des deux variantes est exactement le même tant qu'il ne reste pas que des tas de une seule allumette !!!
(et donc la configuration de départ "traditionnelle" est perdante pour les deux variantes !)
si le dernier qui prend perd, alors il faut laisser un nombre impair de tas de une seule allumette et donc on viole la règle générale disant qu'on laisse un jeu "équilibré" (somme digitale = 0)
un petit calcul sur les ou exclusifs en binaire détermine directement d'ailleurs le coup à effectuer (quel tas et combien) sans "essayer" des allumettes
il y a des variantes plus intéressantes :
on peut aussi prendre dans deux tas mais alors autant d'allumette dans chacun des deux tas
(on prend autant d'allumettes que l'on veut dans un seul tas ou le même nombre dans deux tas)
un Javascript pour jouer à cette variante sur mon site : 
la configuration de départ aléatoire est toujours perdante pour l'ordinateur
mais à la moindre erreur, il gagne !
comme c'est en JavaScript, on peut fouiller le source pour décortiquer l'algorithme...
comme il semble que le jeu ordinaire ne soit pas franchement connu ici ...
en fait on est amené à étudier la théorie des nombres de Grundy d'un jeu, l'arbre des positions et le résultat combinant plusieurs jeux (ici il y a combinaisons de 4 jeux = 4 tas) par l'usage de la "somme Nim" (du nom du jeu)
que l'on appelle aussi "somme digitale"
sans entrer dans les détails de la définition des nombres de Grundy d'un jeu, le principe est d'affecter à chaque noeud de l'arbre des positions un nombre
qui vaut 0 si la position est perdante et autre chose sinon
de sorte que :
d'une position gagnante on puisse toujours aboutir (en jouant judicieusement) à une position perdante pour l'adversaire (donc valant 0)
et d'une position perdante (valant 0) on soit obligé quel que soit le coup qu'on fait de donner à l'adversaire une position gagnante (valant autre chose que 0)
toute la difficulté est dans le cas général de tracer l'arbre des positions du jeu et d'affecter à chaque noeud le "nombre de Grundy" qui va bien.
pour le jeu de Nim à un tas, le nombre de Grundy est ... le nombre d'allumettes
jouons au jeu "normal" (celui qui prend la dernière à gagné, donc pas le jeu usuel, mais "normal" d'un point de vue mathématique)
s'il y a 0 allumettes c'est une position clairement déja perdue puisque le joueur précédent avait tout pris
et quelque soit le nombre d'allumette 
0 de ce tas, c'est une position gagnante : on prend tout et on a gagné
ce jeu à un seul tas est donc trivialement sans intérêt.
mais simple
maintenant concernant la combinaison de plusieurs jeux en un seul
alors la règle est que le nombre de Grundy du jeu composé est la "somme nim" des nombres de Grundy de chaque jeu élémentaire
donc ici le nombre de Grundy de la position est la "somme nim" des nombres d'allumettes de chaque tas.
reste à savoir comment on calcule cette somme nim qui a une table d'addition particulièrement tordue au premier coup d'oeil :
0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 0 3 2 5 4 7 6
2 2 3 0 1 6 7 4 5
3 3 2 1 0 7 6 5 4
4 4 5 6 7 0 1 2 3
5 5 4 7 6 1 0 3 2
6 6 7 4 5 2 3 0 1
7 7 6 5 4 3 2 1 0en fait c'est très simple si on écrit ça en binaire !
la somme nim est alors l'addition bit à bit sans retenue ("somme digitale")
ainsi la position
I
II
IIII
IIIIIse code en binaire
1 1
2 10
4 100
5 101
somme 010cette somme étant non nulle c'est une position gagnante
et pour l'amener à 0 (et donc donner une position perdante à l'adversaire) il suffit de supprimer cette valeur 2 quelque part
dans un tas qui contient ce "2"
c'est à dire de prendre tout le deuxième tas
I
---
IIII
IIIIIet la "somme nim" de 1 + 4 + 5 = 0
on notera aussi que "mentalement" on ne s'amuse pas franchement à calculer en binaire (pff) mais on groupe par la pensée par tas de puissances de 2 (ce qui revient au même)
la position initiale de cet exemple est ainsi "vue" comme :
I
II
IIII
I IIIIet on jouera pour "équilibrer les tas de 2n"
il est clair que pour équilibrer ce jeu il faut vider le tas de 2 allumettes
on peut ainsi considérer cette stratégie comme une simple "stratégie de paires" puisque il y a ainsi appariement des sous tas
la position initiale du jeu standard est ainsi à voir comme
I
I II
I IIII
I II IIIIqui est équilibrée (donc perdante) : quel que soit le coup joué, l'équilibre est rompu.
maintenant pour programmer ça, la somme nim est tout simplement ... le ou exclusif bit à bit
(existe dans tous les langages de vraie programmation, en C et langages dérivés du C, y compris JavaScript et donc Algobox, c'est ^
7^4 donne 7 ou exclusif 4 = 3
pour savoir dans quel tas il y a ces sous tas que l'on veut éliminer, on peut faire un et logique bit à bit (&) etc
comme je le disais précédemment, dans le jeu de nim "usuel" (qui est la variante à qui perd gagne du jeu "mathématique" : celui qui prend la dernière allumette perd) on poursuit cette stratégie tant qu'elle ne conduit pas à ne laisser que des tas de 1
et dans ce cas, on modifie au besoin pour laisser un nombre impair de tas de 1 (alors que le jeu normal consisterait à laisser un nombre pair de tas de 1 pour avoir la somme nim = 0)
avec tout ça vous avez tout ce qu'il faut pour programmer ce jeu sur machine...
(ce qui est un exercice classique de programmation)
Annuler
connectez vous