This paper describes an automated approach to generating abstractions for the
Tower of Hanoi and analyzes the use of these abstractions for problem solving. The
analysis shows that the learned abstractions produce an exponential reduction in the
size of the search space. Since few problem solvers actually explore the entire search
space, the paper also presents an empirical analysis of the speedup provided by abstraction when a heuristic search is employed. The empirical analysis shows that the
benet of abstraction is largely determined by the portion of the base-level search space
explored. Thus, using breadth-rst search, which searches the entire space, abstraction
provides an exponential reduction in search. However, using a depth-rst search, the
search reduction is smaller and depends on the amount of backtracking required to
solve the problem.