Learning by Discovering Macros in Puzzle Solving

Abstract

This paper proposes a model of learning by discovery. The model consists of a program which discovers macro operators while conducting a best first heuristic search in the domain of puzzles. This work extends some recent work on permutation puzzles (Korf, 1982) and operator-decomposable puzzles (Korf, 1983), and is related to the earlier work on MACROPS (Fikes, Hart, and Nilsson, 1972). This work is part of a doctoral dissertation currently in progress at MIT, in which the model will be used to explore learning in conjunction with additional search paradigms and numerous alternative heuristics for macro generation and selection. The specific heuristic reported on here is that of using peaks of the evaluation function to segment the paths of the search tree in order to discover macros. The technique seems particularly valuable in difficult puzzles where only imperfect or approximate evaluation functions ar available.