## Figure 146

The problem space of legal moves in the Tower of Hanoi problem. If boxes touch each other, or are joined by arrows, this indicates that one can move from one state to the other using a legal operator.

disks piled in the same order on the last peg. However, disks can only be moved in certain ways. Only one disk can be moved at a time and a larger disk cannot be placed on top of a smaller disk. The standard version of the problem uses three disks. Figure 14.6 shows some of the legal states that make up the search space of the problem.

The state described in the problem statement, where all the disks are stacked on the first peg, is the initial knowledge state, and the goal knowledge state consists of all the disks stacked on the last peg, in order of size. Subjects can use mental operators that move disks from one peg to another, with the restriction that no move places a larger disk on a smaller disk. This gives rise to varying numbers of alternative states after each possible move. From the initial state, if one applies the move operation, two alternative new states are possible; moving the small disk from the first peg to either the second or the third peg (i.e., states 2 and 3 in Figure 14.6, respectively). Each of these intermediate states can, in turn, give rise to several alternatives (see Figure 14.6). The number of these alternative states, between the initial and goal state, increases rapidly. In order to solve the problem people have to use a variety of strategies to reduce the number of states they have to pass through to reach the goal. Newell and Simon described several such strategies, which they called heuristic methods or heuristics.

Heuristics are to be contrasted with algorithms. An algorithm is a method or procedure that will definitely solve a problem, if it is applied and if a solution exists. For example, one could use a "check-every-state algorithm" to solve the Tower of Hanoi problem; by starting at the beginning and systematically checking every alternative state until the goal state is encountered. This method will take a long time and be inefficient but it is guaranteed to solve the problem. Heuristics are "rules-of-thumb" that do not guarantee a solution to the problem, but more often than not they will succeed and save a lot of time and effort in the process.

One of the most important heuristic methods proposed by Newell and Simon was means-ends analysis. Means-ends analysis consists of the following steps:

• Note the difference between the current state and the goal state.

• Create a subgoal to reduce this difference.

• Select an operator that will solve this subgoal.

To illustrate means-ends analysis, let us assume that a problem solver is two steps off solving the Tower of Hanoi problem in state 15 in Figure 14.6. At this point, three possible moves can be made (i.e., state 11, 14, 19), but only one of these moves will bring you closer to solving the problem (see state 19 in Figure 14.6). Means-ends analysis proposes that you first note the difference between the current state and the goal state; here the important thing to notice is that the medium disk is on the second peg instead of the third peg. Second, establish the subgoal of reducing this difference; create the new subgoal of moving the medium disk to the third peg. Third, select an operator that solves this subgoal and apply it. So, the medium disk will be moved to the third peg and the problem will move closer to its solution. If you then apply this method again, the goal state will be reached in the next step of the problem. Means-ends analysis can be applied from the initial state of the problem to select a set of operators that will construct a path from this state to the goal state. However, as with any heuristic method, it is not guaranteed to be successful in every case where is it applied.

### Goal-subgoal structures in problem solving

The generation of appropriate subgoals on the way to solving the main goal is important to successful problem solving. So, if you can structure a problem into appropriate subgoals—such as "attempt to get the largest disk onto the third peg"—then problem-solving performance should improve. One possible source of such subgoal structures should be prior experience on related problems.

Several researchers have tested this prediction (Egan & Greeno, 1974; Luger, 1976). For instance, Egan and Greeno (1974) gave different groups of subjects complex five- and six-disk versions of the Tower of Hanoi. Experimental groups received prior experience on three-disk and four-disk problems, whereas controls did not. Egan and Greeno found that subjects with prior experience on the easier problems, which instilled an appropriate goal structure, showed some benefits. Furthermore, the error profiles (as measured by any deviation from the minimal solution path for each problem) indicated that subjects performed better as they neared important goals/subgoals and, conversely, tended to experience more difficulty when they were far from an important goal.

The initial state of the five-disk version of the Tower of Hanoi problem used by Anzai and Simon (1979).

Learning different strategies