Towards Automated Discovery of God-Like Folk Algorithms for Rubik’s Cube

We present a multi-objective meta-search procedure that constructs candidate algorithms for state-space search puzzles like Rubik’s cube. The candidate algorithms take the form of macro databases, i. e. , rule tables that specify sequences of actions to perform in different states. Rules are repeatedly applied until the puzzle is solved. The objectives favor candidates that are god-like (solving the puzzle in fewer steps) and folk-like (having fewer rules in the macro database). We build each candidate with a non-deterministic rule table construction, and then optimize over the non-deterministic choice points to find candidates near the Pareto-optimal trades-offs between godliness and folksiness. We prove that the rule table construction is correct: it always terminates and solves every state at termination. This is verified empirically on the full 2×2×2 “pocket” cube, where correct (but unoptimized) constructions take under one hour and the total number of rules is less than 10% the number of possible states. We also empirically assess the multi-objective optimization on restricted variants of the cube with up to 29K possible states, showing relative improvements in the objectives between 14-20%. Avenues for scaling up the method in future work are discussed.

Authors

• Garrett E. Katz
• Naveed Tahir

Keywords

No keywords are indexed for this paper.