Goal-Directed Search

Strategy: set intermediate goals (aka sub-goals) and move disks to achieve them.subgoal: move the largest out-of-place disk to the middle peg.maintain a stack on which further subgoals can be pushed, in case initial subgoal is not directly achievable.when completed, pop the top subgoal from the stack.

Simon's (1975) perceptual strategy involves identifying the largest disk that is not in its correct position (focus disk), and setting a goal of moving this disk to its correct position. This goal may not be directly achievable, either because the focus disk has other disks on top of it or because there is a smaller disk on the target peg. Most efficient: set of a subgoal of moving the largest blocking disk to the third peg.This setting of subgoals is guaranteed to terminate when we get to the smallest disk.

Properties of goal-directed selection: selection of moves is no longer random;selection is guided by the goal of moving the largest disk that is in an incorrect position;if the goal is not directly achievable, it is recursively broken down into subgoals;efficient strategy that avoids unproductive regions of the search space. Goal-directed selection seems to be used by experienced players. (Anzai and Simon (1979) provide evidence that this is learned.)

Strategy

Implementation

Properties