Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Jeu de nim

Posté par
Yenyen
11-02-16 à 14:48

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

Posté par
Glapion Moderateur
re : Jeu de nim 11-02-16 à 17:28

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).

Posté par
mathafou Moderateur
re : Jeu de nim 11-02-16 à 20:13

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...

Posté par
mathafou Moderateur
re : Jeu de nim 12-02-16 à 00:55

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  0


en 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
IIIII


se code en binaire

1        1
2       10
4      100
5      101
somme  010


cette 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
 IIIII


et 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        IIII


et 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    IIII


qui 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)

Posté par
Yenyen
re : Jeu de nim 12-02-16 à 20:52

Merci de votre j'ai résolu le sujet haut la main grâce à des ou exclusif (xor) !

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !