Hanoï mystère, le casse-tête des tours à l’envers avec un soupçon d’inconnu

Topologie et raisonnement

Le jeu Hanoï mystère est largement inspiré du célèbre casse-tête des tours de Hanoï. Le raisonnement mis en œuvre est le même mais sa réalisation est plus ludique.

Principe du jeu

Le jeu se joue à deux. Chaque partie compte deux manches. L’un des deux joueurs est le “codeur” et met en place l’énigme, l’autre joueur, le “décodeur”, tente de la résoudre. Les rôles sont inversés à la manche suivante.

À l’insu du décodeur, le codeur dépose une pièce sur une planche composée de 3 ou 4 emplacements. Puis il dépose sur la planche un certain nombre de pots creux (sous la forme de cylindres creux sur le site) pouvant s’emboîter, de façon à cacher la pièce. Puis il appelle le décodeur. Celui-ci doit déplacer les pots un par un, avec une seule main, et les poser sur des places vides ou des pots plus petits, jusqu’à ce qu’il découvre complètement la pièce et qu’il puisse la saisir avec sa main – ce qui suppose qu’il ait déposé tous les pots sur les autres emplacements. Le nombre de coups est compté; celui qui fait le moins de coups gagne la partie. Pour éviter de brutaliser ces pots, un pot touché compte pour un coup même s’il n’est pas déplacé.

Pour chaque partie, le nombre d’emplacements utilisables -3 ou 4- ainsi que le nombre de pots, de 4 à 10, sont décidés par les deux joueurs, d’un commun accord.

Hanoï mystère avec 4 emplacements et 10 pots, mais on n’en voit que 4 au départ…

Intérêt

Dans le casse-tête d’origine, toute l’information est visible et donc connue par le décodeur. Ici, une partie de l’information est invisible au départ, puisque la pièce se trouve cachée sous un ou plusieurs pots, et que seuls les pots les plus gros sont visibles. Le rôle du codeur consiste donc à essayer de cacher le mieux possible la pièce; quand au décodeur, il doit affûter sa stratégie et mobiliser sa mémoire de travail, pour découvrir la pièce le plus rapidement possible. Le jeu est beaucoup plus intéressant – car plus facile – avec 4 emplacements. Les parties les plus sympathiques comptent 10 pots. En général, avec 4 emplacements on peut toujours trouver la solution en 40 coups au maximum.

En modulant le nombre d’emplacements et le nombre de pots, on peut adapter le jeu à tous les âges. On peut pratiquer ce jeu sans ordinateur, en utilisant des cubes qui s’emboîtent, en vente dans les magasins de jouets; il remporte toujours un franc succès auprès des petits et des grands.

Rôle du codeur

Le codeur doit essayer de créer les combinaisons les plus difficiles à percer. L’expérience montre qu’il vaut mieux cacher la pièce sous le plus petit pot, car on augmente le nombre de déplacements qu’il faut faire pour la découvrir. Mais, bien sûr, comme le décodeur s’attend à ce que la pièce soit cachée sous le plus petit pot, on peut, de temps en temps, poser un piège et la mettre sous un pot un peu plus grand…

La deuxième astuce consiste à mettre un peu plus de pots sur l’emplacement contenant la pièce, pour rendre l’accès à la pièce un peu plus difficile.

Sur le site l’ordinateur agira ainsi si vous le laissez coder.

Rôle du décodeur

C’est lui qui a le plus gros travail !

Non seulement il doit découvrir où se trouve la pièce, mais il doit mettre en place une stratégie pour la révéler et pour cela, il doit mémoriser la position des différents pots car, ne l’oublions pas, ils sont cachés par les plus gros. Pour l’aider, en plus de mémoriser la taille il peut se servir des couleurs; celles-ci sont choisies aléatoirement au démarrage du jeu, mais ensuite elles ne changent plus. Attention quand même, car si on choisit moins de 10 pots, ces derniers seront tirés aléatoirement parmi les dix possibles : donc les tailles et les couleurs peuvent changer d’une partie à l’autre, pour le même nombre de pots.

La stratégie du déplacement

C’est là qu’on retrouve le principe du casse-tête des tours de Hanoï. Il s’agit d’un raisonnement récursif qui mobilise la mémoire de travail et la mémoire procédurale. On peut cependant simplifier un peu les procédures en adoptant une règle assez simple, lorsqu’on doit déplacer un groupe de pots d’un emplacement à l’autre.

En général, quand on doit déplacer n pots, on se demande toujours: “où dois-je placer le premier pot de la série ?”

La réponse est assez simple. Prenons le cas d’une planche à trois positions, comme c’est le cas dans le casse-tête des tours.

Sur ces trois positions, on distingue :

  • la position de départ, sur laquelle se trouve mon tas à déplacer
  • la position d’arrivée, sur laquelle je souhaite déplacer le tas de pots de départ. Cet emplacement, bien sûr, est disponible pour cela; il est vide ou il contient des pots encore plus petits que ceux qu’il faut déplacer.
  • la position intermédiaire, qui va servir dans les déplacements, et qui elle aussi est disponible pour cela.

Si on n’a qu’un seul pot à déplacer, il suffit de le mettre sur la position d’arrivée. On a un seul déplacement.

Si on a deux pots, il faut mettre le premier sur la position intermédiaire, déplacer le second de la position de départ vers la position d’arrivée, puis déplacer celui de la position intermédiaire sur la position d’arrivée. Il y a 3 déplacements à faire. On commence donc par la position intermédiaire.

Déplacements de 2 pots: 3 mouvements.

Pour 3 pots, il y a 7 déplacements et il faut commencer par la position d’arrivée. Voici la vidéo qui montre les déplacements :

En poursuivant le raisonnement, on constate que pour un nombre impair de pots, il faut déplacer le premier sur la position d’arrivée. Lorsqu’il y a un nombre pair de pots, il faut commencer par la position intermédiaire.

Impair: arrivée
Pair: intermédiaire

En appliquant cette astuce on réduit considérablement le nombre de tâtonnements ! Mais, bien sûr, cela suppose que l’on sache combien il y a de pots, ce qui demande un considérable travail de mémorisation.

Lorsqu’il y a 4 positions on peut réduire le nombre de déplacements.

Le défi: ordinateur contre joueur

Dans le défi, le joueur s’oppose à l’ordinateur. C’est toujours le joueur qui choisit le nombre de pots et la taille de la planche de jeu, réglant ainsi le niveau de difficulté.

Une partie se déroule en deux manches asymétriques; pour qu’il y ait équilibre des chances, il faut jouer un nombre pair de parties.

Au tout début, on tire au sort pour savoir qui commence. Par la suite, celui qui termine la deuxième manche commence la première manche de la partie suivante.

L’ordinateur commence par créer une combinaison secrète à découvrir. C’est sa fonction “codeur” déjà présentée plus haut. Puis le premier joueur (humain ou machine) doit découvrir la pièce en un minimum de coups. Ensuite, la même combinaison est proposée au second joueur (machine ou humain), qui doit, lui aussi, trouver la pièce en essayant de faire mieux que le premier joueur.

On comprend pourquoi le jeu est asymétrique. En effet, le second joueur est avantagé puisqu’il connait déjà la position de la pièce (si le premier joueur a terminé) et il peut même avoir mémorisé la position des pots. Alors que le premier joueur doit tâtonner pour trouver la pièce, le second peut immédiatement appliquer la meilleure stratégie pour la découvrir. Il est donc largement avantagé.

Pour rétablir l’équilibre, il faut donc jouer 2 parties au moins.

Je tiens à préciser que l’ordinateur ne triche pas.  Au début de la partie, l’algorithme de résolution “voit” exactement ce que voit le joueur humain, et il “sait” exactement ce que le joueur sait : combien il y a d’emplacements, combien il y a de pots, quels sont les pots visibles. Ni plus, ni moins. En le voyant faire, on peut avoir l’impression qu’il se jette systématiquement sur la pièce, où qu’elle soit, comme s’il savait où elle est, mais c’est parce que l’algorithme est optimisé, pas parce qu’il triche ! Observez bien, on s’en rend mieux compte lorsqu’il y a 4 emplacements et beaucoup de pots. L’algorithme tâtonne lui aussi; il présente le cheminement de la première solution qu’il a trouvée et ce n’est pas forcément la meilleure.

Donc, si l’ordinateur commence, il est dans la même situation que le joueur. Ce dernier, s’il observe bien et mémorise à propos, peut donc gagner au second tour.

Par contre, si elle joue au second tour, la machine ne laisse rien passer puisqu’elle dispose de toute l’information qu’a laissée le joueur; et bien sûr, elle n’oublie rien.

Autrement dit, oui, la machine est redoutable dans ce jeu. Mais elle a un point faible : l’algorithme est borné ! Dans certains cas, pour que le temps de calcul reste raisonnable, j’ai du regrouper les déplacements en tas. En gros, cela signifie que l’algorithme va assimiler le déplacement de 2 pots à un seul coup, qui sera décomposé en 3 mouvements élémentaires au moment de l’exécution. Quelques fois, lorsqu’on travaille sur une planche à 4 positions, le programme ne va pas se rendre compte qu’il peut interrompre les déplacements élémentaires parce que le pot sous lequel se trouve la pièce est découvert et qu’il est possible de le dégager facilement sur un autre emplacement. Alors, il joue un coup en trop. C’est un avantage dont on peut tirer parti.

Démarrer l’activité.

 

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *