Problem Structure And Problem Solving Behavior

Gerald A. Goldin, Assistant Professor, Graduate School of Education, University of Pennsylvania, Philadelphia, Pennsylvania, U.S.A.

Abstract

One of the most interesting questions in the study of human problem solving is the nature of the interaction between a problem's intrinsic structure and a problem solver's strategies or behaviors. The present paper suggests the use of techniques developed in research in mechanical problem solving to assist in formulating and illuminating this question. The authors also seek to develop a relationship between artificial intelligence methods and 'structuralist' theories of cognition by relating groups of symmetry trans­ formations and 'conservation' operations.

Section I: Introduction

One of the most interesting questions in the psychology of problem solving is the nature of the interaction between a problem's intrinsic struc­ ~ and the strategies or behaviors employed in attempting to solve the problem. Several studies have recently appeared addressing this subject: 1) the learning of mathematical structures such as the Klein group or the cyclic group of order four, Branca & Kilpatrick [1], 2) the study of analogy and transfer in related problem solving situations, Reed, Ernst, & Ba11erji [2], Egan & Greno in [3], 3) the development of mechanical theorem provers both in equation solving, Bundy [4], and in ele­ mentary geometry, Gelernter [5] and Goldstein [6]. This research, although from diverse points of view, shares a camnon interest: understanding the effects of problem structure - for instance, a problem's possible subproblem and symmetry decom­ positions - on efficient problem solving.

This paper suggests techniques that may further aid in form~lating and illuminating this question. More ambitiously, the authors seek to develop a relationship between artificial intelli­ gence methods and Piagetian or 'structuralist' theories of cognition.

Nilsson [7] has defined the state space rep­ resentation of a problem as the set of distinguish­ able problem configurations or situations together with the permitted moves or steps from one problem situation to another. Thus the state space of a problem consists of an initial state, together with all the states that may be reached from the initial state by successive legal moves in the problem. One or more of these successor states are class­ ified as goal states. The state space of a prob­ lem, represented as a non-directed graph, will be unique only if the problem's description clearly deliniates its initial and goal state(s) and its set of legal moves Egan & Greno [3]. Finally, the concept of the state space of a problem can be generalized to the analo9Qus structure for an N-player game, i.e., the game tree or graph.

George F. Luger, Research Fellow, Department of Artificial Intelliqence, University of Edinburqh,

scotland.

Banerji [8], Banerji & Ernst [9] and other researchers have offered mathematical descriptions to characterize state spaces. This 'state space algebra' allows such concepts as problem compar­ ison, decomposition, and extension to be well de­ fined and also allows problem solving studies in the areas of problem analogy, transfer, and qen­ eralization to be extremely precise.

In early artificial intelligence research both Gelernter's Geometry Theora~~ Prover [5] with its use of the symmetries within the syntax of a problem's description, as well as Newell, Shaw and Simon's General Problem Solver [loJ, with its utilization of a problem's possible subproblem decomposition~affirm the need for as complete as possible exploitation of a problem's structure for effective problem solving. Aqain, in plan formation, Sacerdoti [11] uses ABSTRIPS to focus on the important features of a problem's structure and to ignore the unnecessary detail that leads STRIPS to combinatorial problems.

Newell and Simon's later work [12] permits in principle a very detailed interpretation of an individual' a problem solving 'protocol' as steps in information processing. However, as the 'problem space' for this research varies from subject to subject for each individual problem it also lends to their model a definite post hoc character. Since no final c011111i tment concerning the structure of the 'problem space' is made until after the problem solving is observed, the poten­ tial for predicting the effects of a problem's structure on a subject's problem solving behavior seems to be lacking.

In the next section two ideas are introduced. Firat, we assert a fundamental correspondence be­ tween conservation operations and symmetry trans­ formations. In the sense of Piaget, a conserv­ ation operation is the ability of a problem solver to respond that two different states of the en­ vironment are equivalent when they are function­ ally the same, that is when they both possess the same value for some perceptual or cognitive vari­ able. For example, 17 is said to be equivalent to 32 modulo 3, since both have the same remainder on div~by 3. In general, a symmetry trans­ formation is a mapping which carries one problem state into another in such a way as to leave un­ changed important observable features. In the everyday sense of the word symmetry these features are geometric, for example, the transformation which changes a particular configuration of objects into its 'mirror imaqe' may leave the appearance of the configuration unchanged. We are interest­ ed, however, in a more general notion of symmetry, for example, symmetry within a problem's descrip­ tion and underlying problem structure, as well as in the more readily apparent geometric symmetries.

The second idea pursued in this section is that in problem solving, a subqoal and subproblem decomposition of a problem may govern a problem solver's behavior even when he or she is not consciously seeking to arrive at that particular subgoal, and despite the fact that the infra­ structure of subproblem's within the main· problem may not on the surface be apparent. Furthermore, given a subproblem decomposition, one kind of symmetry whose effect may be explored is the pres­ ence in the problem of subproblems of identical (isomorphic) structure.

In the third aection additional concepts con­ cerning a problem's state space are rigorously defined, and several hypotheses offered concerning effects of problem structure on subject's paths through the state space, such as a predominance of goal and subgoal directed paths, and an increased likelihooc! of congruent paths through isomorphic subproblems.

In the fourth section, the Tower of Hanoi problem (Nilsson [7]) and the Tea Ceremony problem (Hayes & Simon in [3]) are used to illustrate the main ideas developed. Finally, some suggestions for further experimental investigation are pro­ posed.

Section II: (A) Conservation Operations and Symmetry Transformations

(B) Subproblem Decompositions

(A) In Tic-Tac-Toe a player, say X, is said to 'fork' his opponent when he places his X in such a position on the board that 1) there are-as a result two possible 'winning moves' for X, and 2) o is able, in the next move, to block only one of these 'winning moves'. There are several different 'forking' positions possible on the Tic-Tac-Toe board and these relationships are conserved or in­ variant over all rotations and reflections of the game board. Thus it can be said that there is a conservation or functional equivalence among the different 'forking' si tua tiona. It is als.o poss­ ible to construct symmetry transformations of one 'forking' situation onto any other. The authors would like to establish a logical equivalence be­ tween conservation operations and groups of sym­ metry transformations for characterizing this and other problem solving situations (Goldin & Luger [13l Luger [14]).

The group is the paradigm in mathematics of the methodology which has been termed 'structur­ alist' (Piaqet [ 15]) · This methodology has been applied to fields of study as diverse as anthro­ pology, linguistics, and psychology, as well as to mathematic& [15]. According to Piaget a struct­ ure in the most general sense is a system or set within which certain relations or operations have been defined, embodying the concepts of wholeness, transformation, and self-regulation. For example a system of kinship constitutes a structure in anthropology as does a group in mathematics. In Piagetian developmental psychology, the conser­ vation operations - conservation of number, volume, quantity, etc. - are transformations which repre­ sent the cognitive structures assumed to underlie certain patterns of behavior. Acquisition of these conservation operations by children defines sequential stages in thier cognitive development.

In view of the parallel fundamental roles played by group structures in mathematics and cognitive structures in developmental psychology, it is natural to try to look at the acquisition of Piagetian conservation operations as equivalent to the acquisition of a group of symmetry trans­ forma tiona ·

For an observable (such as number, quantity, etc.) to be conserved means in fact that when a given state 1s somehow transformed into an altered state, the value of the observable is unchanged from its initial value. Of course, for the second state to be regarded as different from the first state at all, there must be at least one other ob­ servable which does change in value under the transformation, and which is not conserved by the transformation. A symmetry transformation may be defined, then, as a one-to-one mapping from the set of states onto itself which leaves invariant the specified relationships among the states. Any collection of such symmetry transformations gener­ ates a symmetry group.

Let us say that a certain symmetry group G conserves a given set of observables when for each state s is the system, all states which may be ob­ tained-from S by applying symmetry transformations from G have exactly the same values of the spec­ ified observable&. The maximal symmetry group possessing this property for a given set of observ­ ables is the group containing ~ symmetry trans­ formation which preserves the values of the spec­ ified observables.

To say that a subject 'conserves number', for example, means that no matter how a given state of the environment is transformed into an altered state by simply moving the objects within the en­ vironment around, the value of the observable 'number' - according to the subject's report - re­ mains unchanged. Thus, a group of on,-to-one surjective mappings from a region of R onto itself, maps the set of states onto itself in such a way that a state specified by n points continues to be specified by n points after it is transformed, and so has the same value of the observable 'number'. It is not difficult to see that this set of mappings fits the definition of a symmetry group conserving that observable. Thus, the ability to conserve number may be seen to be logically equivalent to the acquisition of the structure of a symmetry group, that is, the ability to undo (invert) any rearrangement transformation and to catenate any two such transformations.

It may be hypothesized that stages in the acquisition of such a symmetry group structure actually correspond to the acquisition of partic­ ular subgroups of this symmetry group. For example, a child might at some time respond con­ sistently that the number of objects is unchanged when a configuration is merely translated a cer­ tain distance in space, without its having been spread out or otherwise rearranged. If this were to occur we would say that the subgroup of K con­ taining all translations had been acquired as a symmetry structure. Verification of this hypo­ thesis would further demonstrate the usefulness of the conservation operation/symmetry group correspondence.

In arguing for the reformulation of conserva­ tion operations in terms of symmetry qroups, it seems natural to cite examples of systems in which the symmetries are familiar, but the identification of conserved quanti ties may be cumbersome. Many examples drawn from problem solving turn out to be easier to describe in terms of symmetry groups than in terms of quantities conserved by the transform­ ations in those groups. For example, in Tic-Tac­ Toe, there are nine distinguishable states which can be reached by the first move of the first play­ ar. However, modulo the rotation or reflection symmetry, only ~distinguishable states exist. In constructing the state space representation for Tic-Tac-Toe, one could choose to represent all the distinguishable states of the system, and so obtain a very large state space1 or one could use the much smaller state space obtained by raqardinq those states conjugate by symmetry as equivalent. This later choice corresponds to reduction of the state space representation modulo its symmetry transformations. ------

In studyinq human problem solving, we must take into account the possibility that the sub­ ject's behavior does not initially reflect all the symmetry which is actually present. Therefore, to map the subject's behavior faithfully, we should baqin with the eXPAnded state space repre­ sentation, i.e., the state space containing all possible laqal states of the problem. This ex­ panded state space (and its formal properties) will be constant across all subjects solving this problem and thus make possible more than a ~ ~analysis (p.2).

Tic-Tac-Toe also provides an example of a qame in which the rotation and reflection symmetry is easily recognized, but the corresponding con­ served quantities are cumbersome to define. One such quantity might be the number of Xs in corner squares, a number unchanged by the rotation or re­ flection operations. Number Scrabble [121, a game isomorphic to Tic-Tac-Toe, may be described as follows. The integers 1, 2, 3, ··.· , 9 are written on a pad, and the two opposinq players take turns selecting single numbers. Neither player may select a number already taken. The qoal is to obtain any three numbers which add up to exactly fifteen. The isomorphism between this game and Tic-Tac-Toe can be illustrated by placinq the integers 1 to 9 in the Tic-Tac-Toe grid in such a way that each row, column, and diagonal add to 15. A player tryinq to learn Number Scrabble would 4 3 8 not have available the geo­ metric symmetry presented by the Tic-Tac-Toe grid. Without prior familiarity with the 'magic square', 9 5 1 2 7 6 a 'magic' square

a player would have to seek rules such as, 'If the first player chooses 5, then the second player has to pick an even number to avoid losinq'. Unbe­ knownst to the player, the relevant 'observable a' are just those which are conserved by the Tic-Tac­ Toe symmetry - 'even numbers selected' , 'odd num­ bers excludinq ~·,and so on.

Tic-Tac-Toe and Number Scrabble illustrate (a) that symmetries may be more convenient than the quantities conserved by those symmetries for formulatinq the notion of equivalence amonq states, (b) that symmetries and conserved quantities are, however, logically interchangeable, and (c) that the rules of a game may be reformulated in such a fashion as to make identification of the conserved quantities easier or more convenient than ~e characterization of the symmetries.

Finally, the formal correspondence between a qroup of symmetry transformations and the observ­ able quantities conserved by these symmetry trans­ formations suqgests that acquisition of symmetries may be as fundamental to cognitive development as is the acquisition of conservation operations. we have also seen how the presence of symmetry may be represented in the state space of a problem·or game.

(B) A second feature of a problem which is amen­ able to study utilizinq the state space is a prob­ lem's infrastructure of subproblems. It has been commonly held that an effective problem solving technique is to establish subproblems or subqoals whose solution or attainment might assist in the conquest of the main problem. Polya [17] suqqests such an approach in discussinq his problem solvinq 'heuristics', it forms the basis of Newell, Shaw, & S~n's General Problem Solver [lol, and suqgests to Nilsson [6, p 80] one way to reduce the state space. But to establish ri9Qrously the role of such identification of subqoals in human problem solving behaviour remains difficult and psychol­ ogists are divided even over the assumption of 'goal-directedness' (Kimble [17] sec. 13) . Char­ acterization of subproblems as subspace& of the problem's state space should assist in investiqat­ inq the behavioral consequences of a subproblem decomposition by the problem 110lver. One may further discuss, independently, the qroup of sym­ metry transformations of a subproblem, or explore the effects of the presence in a problem of dif­ ferent subproblems havinq identical (isomorphic) structure.

The above considerations suqqest the utility of mappinq the problem solver's steps as paths throuqh the state space representation of the problem. Based on the formal properties of the specific problem's state space, such as its sym­ metry and decomposition into subproblems, hypo­ theses can be formulated which predict the effect of this structure on the paths generated by the problem solver. Then the door is open to the development and empirical test of general algorith­ mic or mechanical procedures that might replicate the properties of the paths generated by human problem solvers. The decision to represent prob­ lem solvinq behavior as paths throuqh the state space of the problem is further motivated by the desire to make precise the data which needs to be 'explained' by a theory of human problem solvinq.

In practice it may not always be easy to rep­ resent behavior in this fashion, since the uniqu­ ness of a problem's state space representation relies on the preciseness of the problem's state­ ment. Further, a problem solver's production of paths depends on his or her ability to discriminate amonq the perceptual or cognitive variables which characterize the states and leqal moves of the problem. The beat experimental situation then, is a problem whose states correspond to different discrete situations of an actual physical device, such as Tic-Tac-Tbe, N-pile NIM, or the Tbwer of Hanoi and Tea Ceremony problems to be discussed in section four. Other available means for re­ cording a subject's behavior as a suecession of states entered may include recordinqs of oral comments, written notes, or even qestures and eye movements (Bartlett [19], Newell & Simon [12], and Your.q (19]).

Section III: (A) Definitions and

(B) General Hypotheses

(A) Before proceedinq with further discussion, definitions are qiven for the concepts central to the present approach. These definitions are based on and expanded from those qiven by Nilsson [7]. The state space of a problem is the set of distinquishable situations or states of the prob­ lem, toqether with the permittecrtra'nsitions or moves from one state to another. The problem must specify an initial state and one or more qoal states, and so the state space may be visualized as-a--directed graph (Figure 2).

A subspace of the state space is a subset of the states, together with the permitted transitions which obtain between these states in the subset. A subproblem is a subspace of the state space with its own initial and Subqoal state(s). For a sub­ problem it is required that if the initial state is not the initial state of the problem, it can be entered from a state outside the subspace; and if a sub9oal state is not a goal of the main problem, it can be used to exit from the subspace- i.e., to enter a state of the problem outside of the subproblem. There are often many ways to de­ compose a particular problem into subproblems, which correspond to different choices of subspaces within the state space.

Two problems (or subproblems) are said to be isomorphic if and only if there is a bijective mappinq from the state space of the first onto the state space of the second and: 1) the initial state of the first problEIII is mapped onto the initial state of the second, 2) the set of goal states of the first problem is mapped surjectively onto the qoal states of the second, and 3) a trans­ ition from one state to another is permitted in one problem if and only if the corresponding trans­

ition is permitted in the other.

An automorphism of a problem is an isomorphism of the problem onto itself and is called a ~­ metry transformation or symmetry automorphism. The set of all the automorphism& of a problem forms a group under the binary operation of composition or the successive application of two automorphism&. This group is called the symmetry group or auto­ morphism group of the problem.

The states of a problem may be distinquished by virtue of having different discrete values for a set of variables called observable&. These observable&, characterizing the problem states, may refer to color, position, or number, etc. An observable is said to be conserved by a group of symmetry transformations, if and only if for any state, the value of that observable is unchanged by any element of the group of transformations.

Let s be a state of a problem, and consider the set of all states which can be obtained by applyinq automorphism& or symmetry transformations the orbit of S under the automorphism group G. Two states are said to be conjuqate modulo the symmetry group G if they are in the same orbit

from a qroup G to S. This set of states is called under G.

The orbits within the state space form mutual­ ly disjoint equivalence classes of states. A new and simpler state space may now be constructed canonically by considering each equivalence class as a state in its own right, or alternatively, by selecting one representative state from each orbit. The state space thus obtained is said to have been reduced with respect to its symmetry group G, or reduced modulo G. G may be the full automorphism group of the original state space, or any subgroup

thereof.

A ~ in the state space of a problem is a sequence of states s 1 , s 2 , · · · ,sn such that for i a 1, 2, ··· ,n-1 the pair si,si+l represents a permitted transition of the problem. A solution path for a problem is a path in which s 1 is the initial state and sn is a goal state, with s 2 , ··· , sn-l neither initial nor goal states of the prob­ lem. Two paths within respective illomorphic prob­ lems are said to be conqruent (~ the isomor­ phism) if one path is the imaqe of the other under the isomorphism.

We have seen above that one way to reduce the size of the state space is with respect to a group of symmetry automorphism& of the problem. A secor.d means of state space reduction is with re­ spect to the subproblem structure. The state space may be describe~, albeit nonuniquely, as a union of mutually disjoint subspace&, such that for any ordered pair of subspace&, a transition exists from a state in the first to a state in the second. An entire subspace may thus be regarded as a sinqle state in the reduced state space, and a trans! tion is permitted from one subspace to another whenever a transition does in fact exist from a state in the one to a state in the other. Each subspace, now a state in the reduced state space, becomes also a subproblem of the original problem whenever a particular entry state is des­ ignated as 'initial', and any or all of its exit states are designated as 'goals'. We then say that the state space has been reduced modulo its subproblem decomposition.

Finally, one may address the concept of a non-random or a goal-directed path within a problem or subproblem. Roughly speaking, a non-random path would differ locally - perhaps in the number of 'turns' or 'loops' - from random paths generated through a problem's state space representation. A qoal-directed path is a solution path which does not 'double back' on itself within the state space, moving consistently 'towards' rather than 'away from' the goal state. Criteria for defining 'loops', or 'doubling back', or 'distance from the goal state', etc., are for the present to be est­ ablished in the context of each specific problem under consideration. While these criteria may differ across problems of different structure, they will remain constant across populations of subjects solving a particular problem:

(B) In problem solving it may be assumed that the solver acts sequentially upon problem situations (states) to generate successor states, a process which can be described, as discussed above, by means of paths through a state space represent­ ation of the problem. It is nowhere suggested that the problem solver 'perceives' the state space as an entity during problem solving. The symmetry properties which have been discussed are formal properties of the state space, which may (as in Tic-Tac-Toe) or may not (as in Number Scrabble) correspond to geometrical or perceptual properties of the problem readily apparent to the problem solver.

The approach to this stage of research has been to formulate hypotheses respecting the paths generated by problem solvers in the state space of a problem. Such hypotheses 1) are motivated by the formal properties of the state space under discussion, and 2) represent the anticipated effects of the problem structure in shaping prob­ lem solving behavior. The following hypotheses of a more-or-leas general nature are suggested.

Hypothesis 1

(a) In solving a problem (or subproblem) the subject generates non-random, goal-directed paths in the state space representation of the problem (or subproblem), and (b) when sub-goal states are attained, the path exits from the respective sub­ problems.

Hypothesis 2

Identifiable 'episodes' occur during problem solving corresponding to the solution of various subproblems. That is, path segments occur during certain episodes which do not constitute the (direct) solution of a problem, but which do con­ stitute the solution of the isomorphic subproblems of the problem.

Hypothesis 3

The problem solver's paths through isomorphic subproblems tend to. be congruent.

Hypothesis 4

Given a symmetry group G of automorphisms of the state space of a problem, there tend to occur successive path segments congruent modulo G in the state space.

It may be that the validity of hypotheses 1 and 2 depends on the particular way that the state space of the problem is decomposed into subproblems since such a decomposition is often not unique. Hypothesis 4 (symmetry acquisition) is suggestive of the 'insight' phenomenon which changes the gestalt of the problem solver (Wertheimer [20]) and often plays an important role in the eventual problem solution.

These definitive indicative effects of behavior. hypotheses are not to be regarded as a list, but rather as preliminary and of the kind of analysis possible of the problem structure on the problem solver's If valid, these hypotheses would offer fairly general constraints on the properties which mechanical models must display to simulate human problem solving.

Section IV: Two Problem Solving Studies and Suggestions for Further Research

Let us seek to make the foregoing ideas more concrete by considering two problems that have been used for empirical investigation (Luger [14], [21]). The Tower of Hanoi problem has been extensively discussed in the literature [3] and its state space considered by Nilsson [7]. It is a natural problem to consider both because its well defined state space has a rich subproblem structure and because ita state space possesses somewhat more symmetry than is illmediately ap­ parent in the problem environment.

In the Tower of Hanoi problem four concentric rings (labelled 1,2,3,4 respectively) are placed in order of size, the largest on the bottom, on the first of three pegs labelled A, B, C) 1 the apparatus is pictured in Figure 1. The object of the problem is to transfer all the rings from peg A to peg C in the minimum number of moves. only one ring may be moved at a time, and no larger ring may be placed over a smaller one on any peg.

Figure 1 (1 to r) The 4-ring Tower of Hanoi & Tea Ceremony problems in their 'start' states. A,B,C,l,2,3,4 show the isomorphism relationship.

The Tea Ceremony, see Figure 1, is an isomorph of the Tower of Hanoi. Three people - a host and an elder and younger quest - participate in the ceremony. There are four tasks they per­ form - listed in ascending order of importance: feeding the fire, serving cakes, serving t-, and reading poetry. The host performs all the tasks at the start of the ceremony, and the tasks are transferred back and forth among the participants until the eldest guest performs all the tasks, at which time the ceremony is completed. There are two constraints on the one-at-a-time transfer of tasks: 1) only the least important task a person is performing may be taken from him, and 2) no person may accept a task unless it is less im­ portant than any task he is performing at the time. The object of the Tea Ceremony game is to transfer all the four tasks from the host to the elder quest in the fewest number ot. moves. As with the Tower of Hanoi, the subject attempts the game repeatedly, starting over again whenever he or she wishes until the rings are moved (or tasks transferred) in the fewest possible number of transitions.

In the isomorphic relationship between the Tea Ceremony and the Tower of Hanoi the people - host, youth, and elder - correspond respectively with peqs A, B, and C. The four tasks - feeding the fire, serving cakes, serving tea, and reading poetry - correspond respectively with rings 1, 2, 3, and 4. It can be checked that the initial state, goal state, and leqal moves of the two games correspond.

Fiqure 2 is the complete state space repre­ sentation of the Tower of Hanoi/Tea Ceremony prob­ lem. Each circle stands for a possible position or state of the games. The four letters label­ ling a state refer to the respective pegs (people) on which the four rings (tasks) are located. For example, state CCBC means that rinq 1 (fire), ring 2 (cakes), and ring 4 (poetry) are in their proper order on peq C (performed by the Elder). Ring 3 (teal is on peq B (performed by the youth) · A leqal move by the problem solver always effects a transition between states represented by neighbor­ ing circles in Fiqure 2. The solution path con­ taining the minimum number of moves consists of the fifteen steps from AAAA to ecce down the right side of the state space diagram.

The Tower of Hanoi/Tea Ceremony has a natural decomposition into nested subproblems. For ex­ ample, to solve the 4-ring Tower of Hanoi problem, it is necessary at some point to move the largest ring from its original position on peg A to peg c, but before this can be done the three smaller r!ngs must be assembled in their proper order on peq B. The problem of moving the three rings from one peq to another may be termed a 3-ring subproblem, and constitutes a subset of the state space of the 4-ring problem. The 4-ring state space contains three isomorphic 3-ring subspaces, for which the physical problem solving situations are different by reason of the position of ring 4.

Each subspace becomes a subproblem when one of its entry states is designated as the initial state, and its exit states are designated as goal states. Similarly, each 3-ring subspace contains three isomorphic 2-ring subspaces for a total of nine in the 4-ring state space; and each 2-ring sub­ space may be further decomposed into three 1-ring subspaces, comprising only three states apiece. Note the examples in Figure 2 or 1-, 2-, and 3ring subspaces.

Each n-ring subproblem, as well as the main problem, admits of a symmetry automorphism mapping a goal state of the n-ring problem onto the conjugate goal state which corresponds to transferring the n rings to the other open peg. Were the three pegs of the Tower of Hanoi board to be arranged at the corners of an equilateral triangle (as are the people in the Tea Ceremony), the symmetry auto­ morphism would represent the geometric operation of reflection about the altitudes of an equilateral triangle.

Criteria are established [14lfor 'non-random­ ness' and 'goal-directedness' of subject's paths through the Tower of Hanoi/Tea Ceremony state space · The number of ' turns ' and ' loops ' of a subject's path is compared with the 'turns' and 'loops' of a random path of the same length gen­ erated in the Tower of Hanoi/Tea Ceremony state space. A 'metric' is defined also, .a function of the number of states the subject's current state is distant from the goal state. If this function is non-increasing over the subject's path, the path is said to be 'goal-directed · · This same metric is established to measure goal directedness within subproblems. When subgoal states are attained the path that exits from the subgoal is examined to see if it also exits from the subproblem. The first trial of Figure 3 decomposes the state space modulo its 2-ring sub­ problems - each 2-ring subproblem is solved in the minimum number of steps, while the 3-ring subproblem is not. This represents a 2-ring 'episode' in the problem's solution. This same trial shows two congruent paths through isomorphic 3-ring subproblems.

The problem solving data of 45 adult subjects solving the Tower of Hanoi and 21 adult subjects solving the Tea Ceremony problems are reported in [14] & [211. Except for Hypothesis 3 (the pro­ duction of congruent paths through isomorphic subproblems) , all the hypotheses are supported by the data. Especially strong (near 100\) is the support of the special role played by subgoal states within the problem (Hypothesis lb). 86\ of all the subjects have at least one problem solving 'episode' with 60\ showing two or more of the three theoretically possible 'episodes' (Hypothesis 2). 52\ of all subjects in the studies interrupted a path and immediately pro­ duced a .path segment that was the symmetric con­ jugate of the interrupted path (Hypothesis 4) · This new path was often the minimum step solution path.

Figure 3 pictures the actual paths through the state space qenerated by one adult subject solving the Tower of Hanoi problem. This sub­ ject's behavior happened to conform to all four proposed hypotheses. The paths are both goal­ and subqoal-directed, and exit frOID the subproblem whenever a subqoal state is entered. The first two trials contain 7 instances (in 7 attempts) of minimum solution of the 2-ring subproblem, while the 3-ring subproblem has not yet been solved by the shortest path - a 2-ring 'episode'. Trial 1 illustrates two congruent non-minimum paths through 3-ring subproblems. Finally, trial 2 is interrupted and trial 3, the shortest solution path, follows as the image of trial 2 under the symmetry automorphism that exchanges pegs B and C.

Figure 4 pictures the paths of an adult sub­ ject eolvinq the Tea Ceremony problem. The paths within each problem are goal-directed, and when­ ever a subproblem's goal state is entered it is left by the unique path that also leaves the sub­ problem space. FrOID the beginning the problem is reduced modulo its 2-task subproblems, since during the problem solving 12 of 14 of the 2-taek subproblems are solved in the minimum number of steps. After the first 3-task subproblem, there is an 'episode' in which 5 of 6 of all further 3task subproblems are solved in the minimum number of steps but the entire problem (4-task) is not, reducing the problem by its 3-task subproblems. The first and second trials begin with congruent paths (non-minimum) through 3-task subproblems~ The third trial is interrupted, and its syuaetric conjugate ~ which solves the problem - is produced in the fourth trial.

In summary, the present paper eugqeets one natural way to make the strateqy/etructure distinction. We let the structure of a problem refer to the formal properties of its state space representation, such as its symmetry automorphism· and possible subproblem decOIDpositions. We con­ sider the subject's possible cognitive structures to include the conservation operations, syuaetry and subproblem decOIDpositions that the subject can apply to the problem situation. An example of this in the Tower of Hanoi is the ability of a subject to solve all 2-ring subproblems, no matter where they are in the context of the problem, in the minimum number of steps. These structures determine the states that the subject treats as distinct and those treated as equivalent. These may change ·during problem solving, leading to an effective reduction of the state space. A sub­ ject's behavior may be faithfully mapped as long as the state space representation that is utilized by the researcher is sufficiently detailed, in that it does not treat states as equivalent which the subject treats as distinct.

We let the term strategy refer to particular rules or procedures for taking steps within the state space. Different individuals may employ different strategies in solving the same problem, and the same individual may employ different strategies in solving different but isomorphic problems. The present paper does not explain strategies J2!!: .!!.· but hypothesizes that even in the context of different strategies, certain pat­ terns of behavior tend to occur as a consequence of the structure of the problem.

There are several obvious, very broad direct­ ions for further experimental research including broadening the domains both of problems and subject populations considered. Another area of investi­ gation is 'transfer' effects in the behavior of a subject solving different problems having related structure. The second author has in fact a study in progress considering transfer across isomorphic problem situations [21]; Egan and Greno [3] and Reed, Ernst, and Banerji [8] have examined transfer effects in problems of homomorphic structure.