Algorithme du Jeu de Nim

Un grand classique qui se transcris bien en algorithme :

Règle du jeu de Nim
Activité-algorithmique-Jeu-de-Nim-1

II/ Eléments de réponse pour l’algorithme de Nim

Vous avez joué et rejoué et joué encore au Jeu de Nim et vous avez constaté que tout semblait très clair lorsqu’il ne reste plus que 4 allumettes :

  • Si l’autre prends 1, 2 ou 3 allumettes (il n’a pas d’autre choix), c’est terminé pour lui, il ne reste plus qu’à conclure et gagner.
  • Si c’est à moi de jouer…je suis mort

Reste à l’amener vers cette situation…

Quelques indices pour trouver l’algorithme toujours gagnant (lorsque l’autre commence…)

Nous avons 16 allumettes au départ, l’idée est de faire en sorte que l’autre se trouve toujours face à un nombre multiple de 4…jusqu’à son dernier coup ce qui nous mène à gagner sans que l’adversaire puisse s’y opposer.

C’est facile lorsque l’autre commence : si l’autre prend n allumettes (n entre 1 et 3) alors on prends (4-n) allumettes soit le « complément à quatre ». Ainsi, à chaque coup, on ajuste le nombre d’allumettes restantes à un multiple de 4…et à la fin on gagne.

Voici donc l’algorithme pour gagner à tous les coups…si l’autre commence.

Et que faire si l’autre nous demande de commencer ?

Dans le cas où l’on doit commencer, tout ira bien si l’autre ne connaît pas l’astuce. Il suffit de se débrouiller pour placer l’adversaire dans la même situation que précédemment c’est à dire face à 4*n allumettes (12,8 ou 4 ici). Vous avez trois tours pour y parvenir.

Si vous y arrivez…c’est gagné, sinon…c’est perdu.

Voici l’algorithme complet (que vous commenciez ou non)