Tour de Hanoï et espace problème : Newell et Simon expliqués (psycho)
La tour de Hanoï est un casse-tête qui consiste à déplacer une pile de disques de taille décroissante d'un piquet à un autre, en ne bougeant qu'un disque à la fois et sans jamais poser un grand disque sur un plus petit. Avec trois disques, la solution optimale demande 7 déplacements. Newell et Simon en ont fait un modèle pour étudier la résolution de problèmes comme une recherche dans un espace d'états.
Ce problème est au programme de psychologie cognitive de L3, avec les heuristiques et les problèmes isomorphes. Voici la solution, puis les concepts qu'elle permet d'illustrer.
La solution en 7 coups
On note A le piquet de départ, C le piquet d'arrivée et B le piquet intermédiaire, avec les disques 1, le plus petit, 2 et 3, le plus grand. La solution optimale est la suivante.
1 de A vers C ; 2 de A vers B ; 1 de C vers B.
3 de A vers C : le grand disque est en place.
1 de B vers A ; 2 de B vers C ; 1 de A vers C.
La logique est récursive : pour déplacer trois disques, on déplace les deux du dessus vers le piquet intermédiaire, puis le grand disque, puis de nouveau les deux petits. Le nombre minimal de coups pour n disques vaut 2 puissance n moins 1 : 7 pour trois disques, 15 pour quatre, 31 pour cinq.
L'espace problème de Newell et Simon
Dans « Human problem solving » (1972), Newell et Simon décrivent tout problème comme un espace d'états : un état initial, un état but, des opérateurs qui permettent de passer d'un état à un autre et des contraintes qui limitent ces opérateurs. Résoudre un problème, c'est chercher un chemin dans cet espace. Pour la tour de Hanoï à trois disques, l'espace compte 27 états possibles, ce qui permet de suivre précisément les détours des participants.
Les fiches de psychologie cognitive de L3 avec des cas pratiques corrigés : Fiches et cas pratiques OFFERTS
Algorithmes et heuristiques
Un algorithme garantit la solution, par exemple en explorant tous les états, mais il est coûteux. Une heuristique est un raccourci qui ne garantit rien mais oriente la recherche. La montée de gradient consiste à choisir à chaque étape le coup qui rapproche le plus du but ; elle échoue à la tour de Hanoï, où il faut parfois s'éloigner du but apparent, par exemple placer un disque sur le mauvais piquet pour libérer le grand. L'analyse moyens-fins, au cœur du General Problem Solver de Newell et Simon, repère la différence entre l'état actuel et le but, puis se fixe des sous-buts pour la réduire.
Problèmes isomorphes et représentation
Kotovsky, Hayes et Simon (1985) ont présenté des problèmes isomorphes à la tour de Hanoï, c'est-à-dire ayant exactement la même structure formelle, mais habillés autrement, par exemple sous forme de monstres échangeant des globes. Certaines versions demandent beaucoup plus de temps que d'autres. La difficulté d'un problème ne tient donc pas seulement à sa structure, mais aussi à la représentation qu'on en construit et à la charge qu'elle impose à la mémoire de travail. En France, Jean-François Richard a développé cette idée en étudiant les restrictions que les participants s'imposent.
La tour de Londres en neuropsychologie
Shallice (1982) a proposé une variante, la tour de Londres, pour évaluer la planification. Il faut reproduire une configuration de boules en un nombre minimal de déplacements, ce qui oblige à anticiper. Les patients atteints de lésions frontales y ont des difficultés spécifiques, ce qui en fait un outil d'évaluation des fonctions exécutives.
Les pièges en partiel
Confondre algorithme et heuristique.
Oublier que la montée de gradient échoue sur la tour de Hanoï.
Confondre la tour de Hanoï, problème de recherche, et la tour de Londres, test de planification.
Négliger le rôle de la représentation montré par les problèmes isomorphes.
Les fiches de révision de L3 pour réviser toute la résolution de problèmes
Lire aussi
L'insight de Köhler et la Gestalt : résoudre un problème d'un coup (psycho)
Le problème des 9 points de Maier : solution et explication psychologique
Fonctions exécutives : inhibition, mémoire de travail, flexibilité (psycho)
Sources
Newell, A. et Simon, H. A. (1972). « Human problem solving ». Prentice-Hall.
Kotovsky, K., Hayes, J. R. et Simon, H. A. (1985). « Why are some problems hard ? Evidence from Tower of Hanoi ». Cognitive Psychology, 17(2), 248-294.
Shallice, T. (1982). « Specific impairments of planning ». Philosophical Transactions of the Royal Society of London B, 298(1089), 199-209.
Richard, J.-F. (1990). « Les activités mentales : comprendre, raisonner, trouver des solutions ». Armand Colin.
Questions fréquentes
Comment résoudre la tour de Hanoï à 3 disques ?
En 7 coups : petit disque de A vers C, moyen de A vers B, petit de C vers B, grand de A vers C, petit de B vers A, moyen de B vers C, petit de A vers C. Le principe est récursif : on déplace les deux petits disques sur le piquet intermédiaire, puis le grand, puis à nouveau les deux petits.
Combien de coups faut-il pour la tour de Hanoï ?
Le nombre minimal de déplacements est 2 puissance n moins 1, où n est le nombre de disques. Il faut donc 7 coups pour 3 disques, 15 pour 4, 31 pour 5 et 63 pour 6. La croissance est exponentielle, ce qui rend les grandes tours très longues à résoudre.
Qu'est-ce que l'espace problème ?
C'est la représentation d'un problème proposée par Newell et Simon en 1972 : un état initial, un état but, des opérateurs pour passer d'un état à un autre et des contraintes. Résoudre le problème revient à chercher un chemin entre l'état initial et l'état but dans cet espace.
Qu'est-ce que l'analyse moyens-fins ?
C'est une heuristique de résolution qui consiste à repérer la différence entre la situation actuelle et le but, puis à choisir un opérateur pour la réduire, quitte à se fixer des sous-buts intermédiaires. Elle est au cœur du General Problem Solver de Newell et Simon.
Quelle différence entre tour de Hanoï et tour de Londres ?
La tour de Hanoï sert surtout à étudier la recherche de solution dans un espace d'états. La tour de Londres, proposée par Shallice en 1982, demande de reproduire une configuration de boules en un minimum de coups et sert à évaluer la planification, notamment chez des patients présentant des lésions frontales.