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

Garrett E. Katz, Naveed Tahir

Research output: Chapter in Book/Entry/PoemConference contribution

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAAAI-22 Technical Tracks 9
PublisherAssociation for the Advancement of Artificial Intelligence
Number of pages9
ISBN (Electronic)1577358767, 9781577358763
StatePublished - Jun 30 2022
Externally publishedYes
Event36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
Duration: Feb 22 2022Mar 1 2022

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022


Conference36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Towards Automated Discovery of God-Like Folk Algorithms for Rubik's Cube'. Together they form a unique fingerprint.

Cite this