Towards Automated Discovery of God-Like Folk Algorithms for Rubik’s Cube
Authors: Garrett E. Katz, Naveed Tahir10210-10218
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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%. |
| Researcher Affiliation | Academia | Garrett E. Katz, Naveed Tahir Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY, 13244 {gkatz01,ntahir}@syr.edu |
| Pseudocode | Yes | Algorithm 1: A(M, R, s), Algorithm 2: QUERY(R, s), Algorithm 3: INCORPORATE(R, s(t) T t=0, a(t) T t=1), Algorithm 4: RCONS(H), Algorithm 5: Back-tracking Monte-Carlo Optimization |
| Open Source Code | Yes | 1https://www.github.com/garrettkatz/cubbies |
| Open Datasets | No | For the computer experiments in this paper, we implemented SCRAMBLES by sampling possible states uniformly at random without replacement, paired with their optimal solution paths. No specific link or formal citation for a pre-existing public dataset is given. |
| Dataset Splits | No | No specific dataset split information (percentages, sample counts, citations to predefined splits, or detailed splitting methodology) for training, validation, or testing was found. The paper describes evaluating on 'every possible state s' rather than predefined splits. |
| Hardware Specification | Yes | An empirical evaluation was performed on a Linux workstation with 8-core Intel i7 CPU, 32GB of RAM |
| Software Dependencies | Yes | Python 3.7.3, and Num Py 1.20.0 (Harris et al. 2020). |
| Experiment Setup | Yes | Given a maximum solution length M... If the depth-limit D (fixed at 1 in this paper) is reached... We set M = 30 for the 5040 variant and M = 50 for the 29K variant... We set n = 32 in our experiments, and stop the optimization early once 256 forks have been constructed. |