Technical Report CIS9617

Title: A Selective Macro-learning Algorithm and its Application to the NXN Sliding-Tile Puzzle
Authors: Shaul Markovitch and Lev Finkelshtein
Abstract: One of the most common mechanisms used for speeding up problem solvers is macro-learning. Several methods for acquiring macros have been devised. The major problem with these methods is the vast number of macros that are available for learning. To make macro learning useful, a program must be selective in acquiring and utilizing macros. This paper describes a general method for selective acquisition of macros. Solvable training problems are generated in increased difficulty. The only macros acquired are those that take the problem solver out of a local minimum to a better state. The utility of the method is demonstrated in several domains, including the domain of NXN sliding-tile puzzles. After learning on small puzzles, the system is able to solve puzzles of any size.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion