Exploration et planification dans le problème des anneaux chinois : la découverte des règles à partir des propriétés - article ; n°4 ; vol.105, pg 625-647

Megalakaki

Description

L'année psychologique - Année 2005 - Volume 105 - Numéro 4 - Pages 625-647
Contrairement aux autres problèmes récursifs de type puzzle, comme la Tour d'Hanoi, l'espace de recherche du problème des Anneaux chinois (PAC ou baguenaudier) est linéaire : il n'y a qu'un seul chemin de 21 états qui mène de l'état initial à l'état final, si bien que pour atteindre le but, il suffit de ne pas revenir en arrière. Or en pratique, PAC se révèle être un problème très difficile : les participants mettent jusqu'à plus de 300 coups pour le résoudre. Nous montrons qu'une part de cette difficulté provient de l'heuristique « ne pas s'éloigner du but » appliquée à la configuration des états mais que, d'autre part, la correspondance entre les règles du problème et la configuration des états favorise l'apprentissage à partir de la découverte des propriétés pertinentes.
Summary : Exploration and planning with the Chinese rings puzzle, discovering object properties
Solving the Chinese Rings Puzzle (ChRP, or baguenaudier) consists of removing tokens according to a recursive rule. Contrary to other puzzle problems, such as the Tower of Hanoi, the ChRP problem space is linear and a 21-state path leads from the initial to the final state : to reach the goal, it is enough to never return backwards. However, in practice, participants make up to 300 moves to solve the ChRP. We show that the heuristic « reduce the distance that separates the current state from the goal state (hill climbing) » and states informativeness are some of the factors explaining ChRP difficulty.
23 pages
Source : Persée ; Ministère de la jeunesse, de l’éducation nationale et de la recherche, Direction de l’enseignement supérieur, Sous-direction des bibliothèques et de la documentation.

Informations

• Publié par: L-annee-psychologique
• Publié le: 01 janvier 2005
• Nombre de lectures: 150
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Olga Megalakaki
Charles-Albert Tijus
Exploration et planification dans le problème des anneaux
chinois : la découverte des règles à partir des propriétés
In: L'année psychologique. 2005 vol. 105, n°4. pp. 625-647.
Résumé
Contrairement aux autres problèmes récursifs de type puzzle, comme la Tour d'Hanoi, l'espace de recherche du problème des
Anneaux chinois (PAC ou baguenaudier) est linéaire : il n'y a qu'un seul chemin de 21 états qui mène de l'état initial à l'état final,
si bien que pour atteindre le but, il suffit de ne pas revenir en arrière. Or en pratique, PAC se révèle être un problème très difficile
: les participants mettent jusqu'à plus de 300 coups pour le résoudre. Nous montrons qu'une part de cette difficulté provient de
l'heuristique « ne pas s'éloigner du but » appliquée à la configuration des états mais que, d'autre part, la correspondance entre
les règles du problème et la configuration des états favorise l'apprentissage à partir de la découverte des propriétés pertinentes.
Abstract
Summary : Exploration and planning with the Chinese rings puzzle, discovering object properties
Solving the Chinese Rings Puzzle (ChRP, or baguenaudier) consists of removing tokens according to a recursive rule. Contrary
to other puzzle problems, such as the Tower of Hanoi, the ChRP problem space is linear and a 21-state path leads from the initial
to the final state : to reach the goal, it is enough to never return backwards. However, in practice, participants make up to 300
moves to solve the ChRP. We show that the heuristic « reduce the distance that separates the current state from the goal state
(hill climbing) » and states informativeness are some of the factors explaining ChRP difficulty.
Citer ce document / Cite this document :
Megalakaki Olga, Tijus Charles-Albert. Exploration et planification dans le problème des anneaux chinois : la découverte des
règles à partir des propriétés. In: L'année psychologique. 2005 vol. 105, n°4. pp. 625-647.
doi : 10.3406/psy.2005.30495
http://www.persee.fr/web/revues/home/prescript/article/psy_0003-5033_2005_num_105_4_30495L'Année psychologique, 2005, 105, 625-647
Laboratoire ECCHAT,
Université de Picardie*
Laboratoire CNRS FRE 2627 Cognition & Usages-Lutin
Université Paris 8 - Saint-Denis**
EXPLORATION ET PLANIFICATION
DANS LE PROBLÈME DES ANNEAUX CHINOIS :
LA DÉCOUVERTE DES RÈGLES
À PARTIR DES PROPRIÉTÉS
Olga MEGALAKAKI*1 et Charles TlJUS**
SUMMARY : Exploration and planning with the Chinese rings puzzle,
discovering object properties
Solving the Chinese Rings Puzzle (ChRP, or baguenaudier) consists of
removing tokens according to a recursive rule. Contrary to other puzzle
problems, such as the Tower of Hanoi, the ChRP problem space is linear and a
21-state path leads from the initial to the final state : to reach the goal, it is
enough to never return backwards. However, in practice, participants make up
to 300 moves to solve the ChRP. We show that the heuristic « reduce the
distance that separates the current state from the goal state (hill climbing) »
and states informativeness are some of the factors explaining ChRP difficulty.
Key words : problem solving, exploration, planning, rule discovery,
Chinese Rings Puzzle.
Les études désormais classiques sur la résolution de problè
mes de type puzzle (Newell et Simon, 1972 ; Simon, 1979 ; Ruiz
et Newell, 1989 ; VanLehn, 1991 ; Anderson, Kushmerick et
Lebiere, 1993 ; O'Hara et Payne, 1999 ; Davies, 2000 ; Del Mis-
1. La correspondance est à adresser à Olga Megalakaki, Laboratoire
ECCHAT, Université de Picardie, Faculté de philosophie, sciences humaines et
sociales, Chemin du Thil, F80025 Amiens Cedex 1, France. Adresse e-mail :
[e-mail]. 626 Olga Megalakaki et Charles Tijus
sier et Fum, 2002 ; Altmann et Trafton, 2002 ; Guimberteau,
2003) accordent une grande importance aux problèmes sémanti-
quement pauvres tels que la Tour de Hanoi (TOH), les Cannibales
et Missionnaires (C&M), les Crapauds et Grenouilles (C&G), les
Anneaux Chinois (PAC), etc. Le matériel de ces problèmes est
simple, et les instructions, sous forme de règles données aux par
ticipants, sont également simples à comprendre. Utiliser des pro
blèmes sémantiquement pauvres a longtemps été considéré
comme une des possibilités de mettre en évidence les processus
de planification et les heuristiques de recherche du plus court
chemin dans l'espace des états du problème, sans l'intervention
de connaissances.
Pour les théories de la résolution de problème basées sur la
planification, la difficulté de est considérée comme
relevant de la stratégie de recherche (Newell et Simon, 1972),
elle-même sous la dépendance de la capacité de la mémoire à
court terme (Kotovsky, Hayes et Simon, 1985 ; Kotovsky et
Fallside, 1989). Ainsi la plus ou moins grande difficulté à planif
ier de manière rétroactive les coups à jouer, la plus ou moins
grande difficulté à évaluer un coup selon le nombre de comparai
sons à faire, ou encore la quantité d'informations à mémoriser et
le nombre d'opérations à faire sont autant de facteurs qui déter
mineraient la difficulté du problème.
Cette première approche classique de la résolution de problè
mes, basée sur l'idée d'une parfaite compréhension des instruc
tions et sur la notion de charge mentale, a eu un indéniable suc
cès, mais elle se heurte à deux faits expérimentaux troublants.
Le premier fait expérimental concerne la difficulté qu'éprou
vent les participants pour la résolution du Problème des
Anneaux Chinois (PAC). Le matériel de ce problème comporte
cinq pions qui doivent tous être ôtés selon une règle recursive
donnée. L'espace problème est linéaire et comporte 21 états dif
férents. Selon la théorie de la planification, PAC devrait être le
plus facile des problèmes à résoudre puisque l'espace problème
est linéaire et réduit à un seul chemin, le chemin de la solution.
Ainsi, un participant qui éviterait de défaire un coup joué (une
des heuristiques majeures des théories de la planification), mett
rait 21 ou 41 coups pour résoudre ce problème, selon le premier
coup joué (voir l'espace problème donné dans le tableau 1).
Pourtant, PAC se trouve être parmi les problèmes les plus diffici
les, car il nécessite parfois plus de 500 coups (Kotovsky et Exploration et planification dans la résolution de problèmes 627
Simon, 1990). Alors, comment expliquer la grande difficulté
de PAC qu'on trouve, par exemple, auprès de participants qui
résolvent le problème en mettant jusqu'à 850 coups ?
Le second fait expérimental concerne les problèmes isomor
phes qui ont le même espace problème mais un habillage sémant
ique différent. Ces problèmes isomorphes, qui devraient être
d'égale difficulté, présentent de fait de grandes différences dans
le nombre de coups mis par les sujets pour les résoudre. C'est le
cas avec le problème des Cannibales et Missionnaires (C&M) lor
squ'on les remplace simplement par des jetons blancs et noirs, ou
encore par des gendarmes et des voleurs. Ce phénomène se
retrouve avec des isomorphes de la Tour de Hanoi (TOH) qui
consistent, par exemple, à remplir trois récipients avec de l'eau
en mettant l'accent, soit sur le contenu (variable continue), soit
sur le niveau (variable discrète). Bien que 7 suffisent, les plus
difficiles des problèmes TOH sont résolus avec plus de 60 coups et
les plus simples en moins de 12 coups (Kotovsky, Hayes et
Simon, 1985 ; Richard, Clément et Tijus, 2002). Pour étudier la
difficulté de PAC, Kotovsky et Simon (1990) ont comparé la réso
lution de deux versions isomorphes. Dans la première version, il
faut dégager cinq anneaux, alors que la deuxième est une ver
sion graphique où les cinq anneaux sont remplacés par cinq
pions disposés sur une suite de cinq cases alignées avec un pion
par case. Aucun sujet n'arrive à résoudre la première version
dans un laps de temps inférieur à deux heures, alors que tous les
sujets résolvent l'isomorphe graphique en une demi-heure. Les
approches en termes de charge cognitive n'expliquent pas à elles
seules ces différences de difficulté de résolution qu'on trouve