Solution Strategies, Transfer,
and Computational Resources I
|
In this
section we consider the relation between solution strategies
and the transfer of learning as well as the relation between
solution strategies and the computational resources required
to support the solution strategy. The presentation is based on
a classic paper written by Herb Simon that was published in the
journal Cognitive Psychology in 1975.* The Tower of Hanoi
Problem was used as the example around which to organize this
discussion. You will recall
that this problem involves transferring a pyramid of disks from
one peg to another. The three disk problem is depicted graphically
below. Clicking on this graphic will bring up a window which
provides more background on this puzzle.
This
puzzle as well as various river crossing problems were often
used in psychological research on problem solving. And, because
there is an elegant recursive solution to the Tower of Hanoi
problem, it is often used as an example of recursion in AI and
computer science. But, there are many ways in which to solve
this particular problem - indeed, there are always many ways
to solve any problem (although a particular way may be inelegant
and/or inefficient). For example, one could always mount an exhaustive
state space search and when the solution is discovered, simply
"memorize" this solution. Simon referred a strategy
such as this as a "Rote Strategy" and he provided
a formulation of this strategy as a set of production rules.
This formulation is shown in the figure below.
|
| This
system simply retrieves a linearly ordered list. There are three
production rules; P1, P2, and P3. The convention followed is
that the numeric ordering of the rule corresponds to the dominance
ordering in the Recognition Act Cycle of this production system.
Thus, the 'ELSE' in P3 is a kind of short hand to indicate that
this rule will always be enabled if P1 and P2 are not enabled.
P1 terminates the system when the "END" of the list
is encountered. P2 matches a pointer to the last element
on the list that was retrieved. The right hand side then carries
out a retrieval of the next element on the list of moves, sends
the command to make that move, and resets the variable 'LAST-MOVE'
to this move. |
Adapted from Simon,
Herbert A. "The functional equivalence of problem solving
skills." Cognitive Psychology, 1975, 7, 268-288. |
|
Note
that this rote strategy requires very little working memory
- only the value of the variable LAST-MOVE must be retained.
Of course, the requirements for long term memory will
be directly related to the length of the solution. And, we can
expect no transfer from this problem to any other that
might be defined in the state space associated with the Tower
of Hanoi Problem. Even if a new problem's solution were a prefix
of the memorized solution there would be no transfer. This production
system provides access to only a single element of the solution
at any point in the execution of the system. In this sense it
is quite similar to some of the ideas discussed in the context
of the Basic "Learning
FSM."
Another
strategy that can be imagined is one that simply provides some
control of the search through the space of states. With a little
reflection it becomes apparent that in the Tower of Hanoi Problem
the smallest disk must be involved in every other move. Note
first,that the smallest disk can always be moved. Since
there is no smaller disk, the rules of the game guarantee that
no other disk can ever be above it. Thus, it is always clear.
Similarly, it can be moved to any peg since no peg could possibly
have a smaller disk already on it.
Now,
since there are only three pegs, the smallest disk is either
- on the target disk which is
to be moved next - in which case the smallest disk must
be moved; and, moved to the peg other than the one to which the
target disk is to be moved;
- on the peg to which the target
disk must be moved - in which case it must be moved;
and, moved to the peg other than the one on which the target
disk currently rests; or
- on the peg which neither holds the target disk nor is the
destination of the target disk; in which case it must not
be moved.
Next. consider the plight of
the disks other than the smallest disk. If one of these disks
can be moved, then it must not be covered by the smallest
disk. But the smallest disk is on some other peg. Consequently,
the disk that is movable can only be moved to one of the
pegs other than the one it currently occupies. That is, it can
only be moved to the peg which does not hold the smallest disk.
|
 Clicking on the image to the left opens
a pop-up window showing the state space for the 3 Disk Tower
of Hanoi problem. Notice that the nodes at the vertex of the
triangle (those where all of the disks are on the same peg) have
an outdegree of two. All other nodes have an the outdegree of
three. However, one of these paths would return the problem solver
to the state that has just been left...i.e.,the move would create
a cycle of length one. Taking all of these facts into account,
one can synthesize a strategy that yields a unique choice of
move - except for the initial move. This is because in the initial
state of the problem the smallest disk can be moved to either
of the other pegs. |
|
Note that these general considerations hold for any problem that
can be specified in this state space. This knowledge enjoys this
degree of transfer since it reflects a global property of the
state space. But, of course, if the wrong initial move is chosen
this strategy will not yield the solution.
The
addition of one more rule resolves the uncertainty concerning
the first move in a Tower of Hanoi problem. The rule is: "If
the number of disks is odd, then the first move should
be to move the smallest disk to the goal peg. If the number of
disks is even, then the first move should be to move the
smallest disk to the other peg (the non-goal peg).
With
this rule we have arrived at a solution strategy that is often
referred to as a Move-Pattern strategy. The pattern is
most easily discerned if you think of the pegs as arranged in
a triangular pattern. If the number of disks is odd then they
are moved in a counterclockwise fashion, if even in a clockwise
fashion.
|
| This
Move-Pattern strategy is another of those considered by Simon.
However, an additional distinction is introduced to develop the
prodction system for this strategy. When humans work on problems,
they often perform some of the actions before developing the
solution to its conclusion. This allows a person to perceptually
consult the current state of the problem and potentially lessen
the working memory resources required to support problem solution.
These ideas are further developed on the following page. |
*Simon, Herbert A. "The functional equivalence of problem
solving skills." Cognitive Psychology, 1975, 7,
268-288.
|
|
|
