April 14, 2000
Using Pattern Databases to Find Macro Operators
Macro operators (macros) reach subgoals without search. The goal is reached by applying macros in the order of subgoals. While macro search does not find optimal solutions, if the macros are nearly optimal the solutions are short and are obtained very fast. For the first time, we applied (semi-)automatically generated heuristics to find optimal macro operators and built optimal macro tables for the Rubik's Cube. We contrast our technique with two powerful methods: Korf's "bi-directional partial-match" and the Schreier-Simms algorithm well known in computational group theory.