April 14, 2000
3:30

Istvan Hernadvolgyi

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.

http://www.site.uottawa.ca/~istvan/phd/presentations/macro.html