Self-Supervision is All You Need for Solving Rubik’s Cube
Authors: Kyo Takano
Venue: Accepted by TMLR ()

Abstract: Existing combinatorial search methods are often complex and require some level of expertise. This work introduces a simple and efficient deep learning method for solving combinatorial problems with a predefined goal, represented by Rubik's Cube. We demonstrate that, for such problems, training a deep neural network on random scrambles branching from the goal state is sufficient to achieve near-optimal solutions. When tested on Rubik's Cube, 15 Puzzle, and 7$\times$7 Lights Out, our method outperformed the previous state-of-the-art method DeepCubeA, improving the trade-off between solution optimality and computational cost, despite significantly less training data. Furthermore, we investigate the scaling law of our Rubik's Cube solver with respect to model size and training data volume.

Published in Transactions on Machine Learning Research (07/2023)
Self-Supervision is All You Need for Solving Rubik's Cube
Kyo Takano
kyo. Sgpo.takaano@@mmmlaaaes.coo
Reviewed on OpenReview: https: // openreview. net/ formm? id= bnBeNFB276
Abstract
Existing combinatorial search methods are often complex and require some level of expertise. This work introduces a simple and efficient deep learning method for solving combinatorial problems with predefined goal, represented by Rubik's Cube. We demonstrate that, for such problems, training deep ncural network random scrambles branching from the goal state is sufficient lo achieve near-oplimal solutions. When lested on Rubik's ' Cube, 15 Puzzle, and 7x7 Lights Out, our method outperformed the previous saate-of-the-arn method DeepCubeA, improving the trade-off between solution optimality and computational cost, despite significantly less training data. Furthermore, we investigate the scaling law of our Rubik's Cube solver with respect model size and training data volume. Our code www.oooooaakkeeeeeo taayoootaaaoo/aao tff http//etcciiiieeieeeeeeee available at github. cechub..cmm/eeee www.com///yy/.
F'URDD'BED
The proposed learning algorithm for solving Rubik's Cube. We train a Deep Neural Network (DNN) on sequences of random moves applied to the predefined goal. At each step, the DNN learns to predict the last scramble move based on the resultant state. To solve a scrambled state, we sequentially apply the reverse of the moves predicted by the trained DNN.
Figure 1:
1 Introduction
Combinatorial scarch important both thoory and practice. One representative example Traveling Salesman Problem, in which a salesman tries to visit multiple cities in the shortest. path possible (Applegate et al., 2011; Russell & Norvig, 2021). Despite how easy it may sound, the problem is classified NP-hard due to its combinatorial complexity (Papadimitrion & Steiglitz, 1998); as the number of cities grows, the number of possible combinations to search for explodes, easily exceeding the limits of classical computer. In the real world, algorithms for such problems have many applications, including plamning, scheduling, resource allocation, and so on.
Moving forward from the impracticality of a naive brute-force search, variety of search methods have emerged over time, aiming to address the computational complexity of combinatorial problems. These

---

Published in Transactions on Machine Learning Research (07/2023)
include exact algorithms systematically find an optimal solution within an acceptable time frame, and heuristic algorithms to quickly find a reasonably good solution. In recent years, deep learning has established itself as a potent method for automatically training heuristic function optimized for a given objective. Deep reinforcement learning, in particular, has shown promise for training a Doep Neural Network (DNN) to solve a combinatorial problem near-optimally, even without labeled data or exlensive memory (Mazyavkina el al., 2021; Vesselinova al., 2020). By rewarding efficient moves/actin actions, DNN can learn to find increasingly better solutions.
Nevertheless, combinatorial search remains a challenging task. Implementing an explicit search algorithm often necessitates domain expertise, substantial computational resources, and extensive human effort. Rein- forcement learning, though it can automate parts of the process, still demands a comprehensive understanding of the methodology itself and significant amount of time spent in trial and error.
In the present study, we propose a novel method to solve specific class of combinatorial cabllmms-namcle those with a predefined goal. The idea is straightforward: train DNN on mere random scrambles branching from the goal, as illustrated in Figure 1. We evaluate method in comparison to DeepCubeA (Agostinelli et al., 2019), the previous state-of-the-art deep learning method, by experimenting with Rubik's Cube and a few other related problems.
2 Related Work
Rubik's Cube is quintessential example of goal-predefined combinatorial problems. This three-dimensional puzzle consists of six faces, each with nine color stickers, and the objective is to manipulate the faces so that each face displays only a single color. With approximately 4.3 x 1019 unique states, optimally solving this puzzle is an NP-complete problem(Demaing et al., 2018). To generalize, the task in problems like Rubik's Cube is to find a soquence of moves that will reach the predefined goal, starting from a given state. Henceforth, we view such combinatorial problems as a pathfinding task on an implicil graph, where each node represents unique state and edges indicate moves connecting adjacent nodes.
Among various methods for solving these problems, we pay particular attention to two leading methods known for their high levels of optimality: Iterative Deepening A (IDA*) and DeepCubeA. IDA is a complete search algorithm that is guaranteed to find an optimal solution in a reasonable time frame (Korf, 1985; 1997). DeepCubeA, on the other hand, is a near-optimal method that leverages deep reinforcement learning (Agostinelli et al., 2019). Both are forward search methods to find a solution path by expanding nodes from given state, in order of their estimated distances.
Korf (1985) invented IDA* as the first admissible search algorithm to optimally solve 15 Puzzle, another gred-peed combinatorial problem (see Section 6.1 for problem description). It merges two algorithms: Iterative Deepening Depth-First Search (IDDFS) and A search (Hart et al., 1968). IDDFS is depth- first search that iteratively deepons until a solution is found. Like the breadth-first. scarch, it is a complete search algorithm, but it can be infeasible to run within a reasonable time frame for large state spaces. To enable IDDFS in such vast state spaces, Korf (1985) incorporated the idea of A* search, which expands nodes in order of their estimated total distance formulated as
f(x) = g()) + h(x)
(1)
where is an expanded node, g(x) is the depth from the starting node, and h(z) is the lower bound of the remaining distance to the goal informed by group theory. Using the same formula, IDA* * iteratively increases the threshold for f(x) instcad of depth, greatly reducing the number of expanded nodes without compromising the optimality. Later, Korf (1997) exlended IDA * as the first optimal Rubik's Cube solver, incorporating a pattern database that precomputes lower bounds of distances corresponding to particular patterns. Since then, more efficient implementations followed this approach (Korf, 2008; Arface et al., 2011; Rokicki et al., 2014). Even so, the implementation of IDA* remains proeiem-specific and requires domain knowledge of group theory and search.
2

---

Published in Transactions on Machine Learning Research (07/2023)
DeepCube was the first to formulate Rubik's Cube as reinforcement learning task and successfully solve it (McAleer et al., 2018), which soon evolved as DeepCubeA with significant, performance improvement (Agostinelli et al., 2019). DeepCubeA trains a DNN in lieu of h(x)) in Equation (1) to estimate the distance from a given state to the goal. By relatively discounting g(x) like weighted A* (Pohl, 1970; Ebendt & Drechsler, 2009) and expanding a certain number of nodes per iteration, DeepCubeA then searches for a solution so that the approximate lower bound of total distance f(x as small as possible. DeepCubeA is also shown applicable similar problems like 15 Puzzle and its variants, as well Lights Out and Sokoban (Agostinelli et al., 2019).
In contrast to IDA*, which relies on group theory to estimate distance, DeepCubeA automatically trains a DNN to serve as a distance approximator. The use of DNN is well-suited for this task because it effectively learns complex patterns in data with a fixed number of parameters and also generalizes well to instances unscen during training. This adaptability is particularly convenient. when a state space is too large to exhaustively explore and store in memory. However, it essential recognize that deep reinforcement learning carries inherent complexities and instability, necessitating meticulous design and hyperparameler tuning. In training DeepCubeA models, Agostinelli et al. (2019) had to check regularly that the training loss falls below certain threshold to avoid local optima and performance degradation.
Although both are effective methods, they still require complex implementation with specialized knowledge. To this end, we propose a more direct method to infer the path itself, without the need for distance estimation to guide a search. Our method involves training a DNN on random scrambles from the goal, treating them as reverse solutions from the resulting states.
3 Proposed Method
We propose a novel self-supervised learning method for solving goal-predefind combinatorial problems, regarding the task as unscrambling the act of tracing a scramble path backward to the goal. Although the actual scramble is not observable, we aim to statistically infer a plausible sequence of moves that would lead to the current state. At the heart our method is a DNN trained to predict the last random move applied to given state, We find a solution path by sequentially reversing the predicted moves from a scrambled state. Our method assumes and capitalizes the inherent bias of random scrambles, which originate from the goal, toward optimality. The miniature example in Figure 2 illustrates the operations of our proposed method during training and inference.
When training a DNN, our method initializes the target problem with its goal state and applics a se- quence of random moves to scramble it At each step, the DNN learns predict the last move ap- plied based on the current state's pattern. As the training loss, we compute the categorical cross- entropy between actual and predicted probability distributions of the last move. Algorithm 1 outlines the training process, and Figure/ presents an ex- ample data point on Rubik's 's Cube.
Algorithm 1 The proposed training algorithm.
G: Goal state
MI: Set of moves
Require:
B: Number of scrambles per batch
N: Number of moves per scramble
fo: DNN paramcterized by 0
Ensure: fe: Trained DNN
while not converged do
T + Ø
We search for a solution path tracing back the goal state by sequentially reversing the predicedd moves. We employ best-first search algorithm and prioritize the most promising candidate paths, which we evaluate based on the cumulative product of the probabilities of all their constituent moves. AThe cumulative product can be represented as II P.: where P. denotes the predicted probability that the i-th move is reverse move toward the goal.
for b b= 1 to do
S S+G G
for to N do Sample m + rM)dom(MM
Update S + S o
Add (S. m) to T
Updale So using T
3

---

Published in Transactions on Machine Learning Research (07 (072))
b
Outgoing moves
Incoming moves
Inverse moves
Inverse paths
Figure 2: A miniature instance of combinatorial search with predefined goal. Arrows symbolize moves, with their lengths and widths indicating the associated probabilities. Left: During training, random moves {a, b, e} are feasible at each node with an equal probability of 1/3. These moves, in combination, form probabilistic paths from Goal to Scramble. By accumulating the probabilities of paths terminating with each move, we derive the probability distribution of incoming moves at every node. Right: During inference, we follow the learned distribution Candidate paths are evaluated and ranked based the cumulative product of their estimated probabilities. In this instance, the path [b', b'] is estimated to be the most optimal among the other two-move paths.
traverse backward from S to G with the reverse moves {a', b d').
Our method leverages a fundamental property of combinatorial search: the shorter path, the more likely it is to occur randomly. This means the cunulative probability random training scramble increases as the number of moves decreases: 1/|M/|, where M. represents the of moves and N denotes the path length, Note that since different paths with various probabilities are convoluted for specific state/pattern in the training process, the most frequent moves might not always comprise optimal paths. To mitigate the impact of such latent irregularities during inference, we evaluate candidate paths based on their cumulative proba- bilities, rather than merely the probability of the latest move. Based on these, we assume that generating random scrambles from the goal state establishes a correlation between the optimality of paths and their estimated probabilities.
Lastly, we note that God's Number the minimum number of moves required to solve any state or its upper bound should be known for the problem of interest. Let N be the scramble length and No be God's Number. If N < NG. the trained DNN would not generalize well to more complex states requiring more than N moves during inference. On the other hand, training data covers all possible complexities as long as NG & N. Although redundant paths with more than Na moves would undermine the training efficiency, they have a negligible impact on the learned distribution due to the significantly lower probabilities than shorter ones. When neither NG nor its upper bound is known, it may be beneficial to gradually increase N to the point where the DNN cannot make cetter-than-chiee predictions. If the N-th moves are unpredictable, it implies that N is exceeding the maximum complexity of the problem (N No).
4 Experiment
We assess the effectiveness of our proposed method for solving Rubik's Cube, using the same problem setting, reprosentation, dataset, and DNN architecture as DecpCubeA (Agostinelli et al., 2019). We then compare our result to the published result of DeepCubeA and its update provided GitHub²
4.1 Rubik's Cube
We represent Rubik's Cube as a 324-D vector by assigning an index to each color at every sticker location (6 colors x 54 sticker positions). To manipulate states, we use the quarter-turn metric (a 90º turn of face counts as one move, whereas 180 turn counts as two), meaning 12 possible moves for any state. In this notation, U, D, L, R, B, and F denote 90 clockwise turn Up, Down, Left, Right, Back, and Front faces of the puzzle, respectively; if followed by prime (?), counterclockwise.
4

---

Published in Transactions on Machine Learning Research (07 2022)
4.2 Dataset
We utilize the publicly available DeepCubeA dalaset on Code Ocean which comprises 1, 000 Rubik's Cube test cases. Each case is scrambled with a range of 1, 000 to 10, 000 moves.
4.3
Model
The DNN consists of two linear layers (5000-D and 1000-D), followed by four residual blocks (He et al., 2016) cach containing two 1000-D linear layers. Reetified Lincar Unit (RcLU) activation (Nair & Hinton, 2010; Glorot et al., 2011) and batch normalization (loffe & Szegedy, 2015) are applied after each linear layer. Finally, the DNN has 12-D linear layer to return logits as an output, which are then transformed into a probability distribution using the Softmax function.
4.4
Training
We train a DNN following the self-supervised approach outlined in Algorithm 1, where the DNN learns predict the last move of random scrambles based the resulting state. The DNN parameters are updated using Adam optimizer (Kingma & Ba, 2014) with an initial learning rate of 10-3. In this experiment, we set the maximum scramble length to 26, which is God's Number for Rubik's Cube in the quarter-turn metric (Kunkle & Cooperman, 2007). Additionally, the training process excludes clearly redundant or self-canceling permutations, such as R following R', when generating random scrambles. We train the DNN for 2, 0,000, 000 steps with a batch size of 26, 000 (26 moves per scramble x1, 000 scrambles per batch), which equivalent to billion solutions.
4.5 Inference
We use beam search, heuristic search algorithm known for its efficiency, to solve Rubik's Cube using the trained DNN. While not guaranteed to always reach the goal, beam search can efficiently find solutions by prioritizing the most promising candidates.
Starting from depth 1 with a given scrambled state, at every depth i, the DNN predicts the probability distribution of the next possible moves for each candidate state. We set a beam width of and only pass the top & candidate paths to the next depth i 1, sorted by their cumulative product of probabilities. The scarch procoeds until any one of the candidate paths reaches the goal, at which point the search depth matches the solution length.
To investigate the trade-off between the number of nodes expanded and the optimality of solutions, we systematically increase the beam width & from 2 to 218 in powers of 2. This also allows us to test whether our method needs to expand more nodes than DeepCubeA to achieve the same level of solution optimality.
5 Results
Figure 3 displays the performances of different methods based on two parameters: the solution length and the number of nodes expanded. For reference, we also include the performance of an optimal solver by Agostinelli et al. (2019), which extended Rokicki al. (2014)'s implementation of IDA that relies on 182 GB of memory. With A > 27, our method effectively solved all test cases using the trained DNN. The result also reveals a smooth trade-off between computational load and solution optimality, with stably predictable number of nodes to expand for specific beam width. Below, we specifically report our result obtained with the maximum beam width == 218
Alongside Figure 3, we summarize the comparative performance of the different methods in Table 1. We aligned the temporal performance of our method and DeepCubeA's paper result with the mean por-node time of DeepCubeA's GitHub result, in order to account for external factors affecting the metric, such the number of GPUs and code quality
Ptoi..org/10... 24433/CO. 4958495.vr
We used single GPU (NVIDIA T4), whereas Agostinelli et al. (2019) employed four GPUs (NVIDIA TITAN V).
5

---

Published in Transactions on Machine Learning Research (07 2023))
Performances of different methods in solving Rubik's Cube. We present average values for solution length, number of nodes, and time taken solve per test scramble. Optimality (%) denotes the percentage of optimal solutions achieved by each method. For our method and DeepCubeA's Ass paper result, the time taken is normalized based on the per-node temporal performance of DeepCubeA's GitHub result, with the actual wall-clock time in parenthesis for reference.
Table 1:
Method
Solution length Optimal (%)
Number of nodes
Time taken (s)
Optimal solver
20.64
100.0
2.05 x 106
2.20
Ours
21.26
69.6
4.18 X 108
38.73 (483.61)
DeepCubeA (GitHub)
21.35
65.0
8.19 x 10
75.61
DeepCubeA (Paper)
21.50
60.3
6.62 x 106
61.14 (24.22)
Frequency
250
0
26
27
24
29
12
Solution length
22
15
20
18
Optimal
DeepCubeA
16
+ Ours
104
106
10 0 500
Number of nodes
Frequency
Figure 3: Joint distributions of solution length and the number of nodes expanded in solving Rubik's Cube by different methods. Each colored dot represents unique solution, while diamond markers signify their mean coordinates by methods. Frequency distributions for each parameter are presented along each axis. The pink solid line indicates our method's ''s trade-off between solution optimality and node count, annotated by the increasing beam widths.
The comparison indicates that our method outperforms DeepCubeA in terms of solution length and search efficiency, albeit not matching the optimal solver backed by 182 GB of memory. First, our solutions are more optimal than those of DeepCubeA on average. While optimal solutions average 20.64 moves in length, our method produced an average solution length of 21.26 moves, with 696 of the 1,000 solutions being optimal. On both metrics of optimality, our method surpassed that of DeepCubeA, whose solutions averaged 21.35 moves with 65.0% optimality rate. Moreover, Whereas DecpCubeA expanded an average of 8.19 x 106 nodes per solution, ours expanded only about half the number of nodes to achieve the higher optimality.
solutions were also computationally search-efficient.
Remarkably, our method achieved this superior result also with higher training efficiency. While Deep- CubeA learned from 10 billion examples (1, 00000, 000 iterationsx10, 000 scrambles per iteration), our method efficiently trained the DNN on the equivalent only billion examples. These findings underscore the overall advantage of our proposed method over DeepCubeA in solving Rubik's Cube.

---

Published in Transactions on Machine Learning Research (07 (07/2023)
6 Additional Evaluations
To see the versatility of this method, we extend our evaluation to two additional goal-predefined combinatorial problems: 15 Puzzle and 7x7 Lights Out. Like in the preceding Rubik's Cube Experiment, for both of these problems, we train a DNN of the same architecture and test it on the DeepCubeA dataset, which contains 500 cases each. While Agostinelli et al. (2019) also trained a DNN on 10 billion examples for each problem, we train ours with substantially less data demonstrate the training efficiency of our method.
6.1
15 Puzzle
15 Puzzle is a 4x4 sliding puzzle consisting of 15 numbered tiles and one empty slot. The goal is to arrange these tiles in ascending numerical order by swapping the empty slot with its neighboring tiles multiple times. There are approximately 1.0 10a3 possible states for the puzzle, with God's Number standing at 80 moves (Brüngger et al., 1999; Korf, 2008).
We trained a DNN on the equivalent of 100 million solutions (100, 000 batches x 000 scrambles per batch); each scramble length being 80. This training data volume is equivalent to 1% of DeepCubeA, which used 10 billion training examples. Subsequently, we tested the trained DNN on 15 Puzzle subset of the DeepCubeA dataset. We note that, in similarity to the Rubik's Cube experiment, we removed redundant moves like [-}] after [+]] in both the training and inference phascs.
Figure 4 and Table 2 show the comparative performances of different methods, including the IDA optimal solver by Agostinelli et al. (2019) as reference, which runs on 8.51 GB of memory. As illustrated in Table 2, our method solved all test cases using beam width 2 < k & 2 progressively finding incrcasingly optimal solutions by expanding more nodes. With k = 216, we obtained optimal solutions for all test cases, while expanding 22.6% fewer nodes than DeepCubeA.
6.2 7x7 Lights Out
Lights Out is a combinatorial puzzle composed of multiple ON/OFF binary lights. In the 7x7 version, 49 lights are arranged in a square grid. Each light toggles the state of itself and its adjacent lights, and the goal is to switch off all the lights starting from a given random state. As a goal-predefined combinatorial problem, it possesses a more relaxed setting due to the following characteristics. First, because every move is binary, applying the same move twice is clearly redundant. Also, the puzzle is commutative, meaning that the order of moves applied is irrelevant to the resulting state. This characteristic suggests that each move within given sequence holds an equal probability of being the last move. Hence, for a DNN, the problem is essentially a pattern recognition task to predict the combination of moves, rather than specifically the last move in the permutation. According to Agostinelli et al. (2019), an optimal solution is identified when the list of moves contains no repetitions.
Since God's Number unknown for this particular problem, we set the training scramble length to 49 moves, the upper bound for when you need to loggle every button. We trained DNN of the same architecture to predict all moves applied to the problem up to given point in scramble. In total, the DNN learned from the equivalent of 10 million solutions (10, 000 batches x1, 000 scrambles/batch).
As described in Table 3, our method solved all Lest cases optimally using a greedy search, which expands only the most prospective node at every depth. Despite using only 0.1% equivalent of training examples compared to DeepCubeA, our method significantly outperformed it in search efficiency, expanding only necessary nodes composing the optimal solutions. However, it must be noted that this flawless result on this particular dataset does not certify the completeness of the trained DNN as search heuristic.

---

Published in Transactions on Machine Learning Research (07 2023))
Performances of different methods in solving Puzzle. We present average values for solution length, number of nodes, and time taken solve per test scramble. Optimality (%) denotes the percentage of optimal solutions achieved by each method. For our method and DeepCubeA's paper result, the time taken is normalized based on the per-node temporal performance of DeepCubeA's GitHub result, with the actual wall-clock time in parenthesis for reference.
Table 2:
Method
Solution length Optimal (%)
Number of nodes
Time taken (s)
Optimal solver
52.02
100.0
3.22 x 104
0.0019
Ours
52.02
100.0
2.54 X 106
6.83
(313.89)
DeepCubeA (GitHub) DeepCubeA (Paper)
52.02
100.0
3.28 x 106
8.82
52.03
99.4
3.85 x 106
10.37 (10.28)
Frequeney
250
250
70
Optimal
DeepCubeA
+ Ours
60
20
Solution length
55
22 L4 1
50
45
40
35
102
10a
106
50
Number of nodes
Frequency
Figure 4: Joint distributions of solution length and the number of nodes expanded in solving 15 Puzzle by different methods. Each colored dot represents unique solution, while diamond markers signify their mean coordinates by methods. Frequency distributions for cach parameter are presented along cach axis. The pink solid line indicates our method's 's trade-off between solution optimality and node count, annotated by the increasing beam widths.
Table 3: Performances of our method and DeepCubeA in solving 7x7 Lights Out. Since both our method and DeepCubeA reached optimal solutions across all cases, report average values for solution length, the number of nodes, and the wall-clock time without normalization. We have omitted DeepCubeA's 's paper result here since both solution length and node count are consistent with its GitHub result..
Method
Solution length
Number nodes
Wall-clock time (s)
Ours
24.26
24.26
0.053
DeepCubeA
24.26
1.14 x 106
5.90
8

---

Published in Transactions on Machine Learning Research (07/ 2203))
7 Scaling Law
A DNN can better approximate a target data distribution with an increased number of parameters (N) or training data samples (D), as demonstrated across multiple domains (Hestness et al., 2017; Rosenfeld et al., 2019; Kaplan et al., 2020; Hoffmann et al., 2022; Zhai et al., 2022). Since our method involves training a DNN too, we expect to see the same scalability in our Rubik's Cube solver. However, these two factors model and data sizes have a trade-off relationship for a fixed FLOPs budget (C). Thus, it is crucial to estimate the optimal balance between N and D as a function of a given compute budget C. In this section, we formulate such a scaling law for our neural Rubik's Cube solver to obtain the best possible model. We subsequently evaluate the scaled models on the downstream task of solving the puzzle.
To estimate the scaling law for our Rubik's Cube solver, we adopt Hoffmann al. (2022)'s power-law formulation for large language models. Hoffmann et al. (2022) defined the optimal allocation of training compute as a lask of minimizing the cross-ent ropy loss L(N, D), where C zs 6N for training Transformers. They explored three approaches, one of which fitted the following parametric function:
A No
B D8
L(N,))
(2)
Here, E, A, B, a, and 8 are parameters to be estimated by the L-BFGS algorithm (Nocedal, 1980) using set of observations (N, D, L) Following this approach, we estimated the scaling law for our solver by minimizing the mcan squared error between L(,, D) and L. To fit the parameters with L-BFGS, we used grid of the following initial values: A and B from 2 10), and a and / from (0.1, 0.5.. We note that C ~ 3ND for our DNNs, which primarily consist of dense linear layers.
We initiated the experiment by training 30 random low-budget DNNs, each with a compute budget between 1.4 x 1 and 3.2 x 10'5. We subsequently started fitting Equation (2) and progressively increased the compute budget, updating the optimal N and D estimation at each scaling step to train the next model. This strategy helped us to gradually explore the scaling space and reduce uncertainty attributed to extrapolation in higher-compute regions. It should be mentioned that this experiment differs from the main experiment (Section 4) in a few aspects. First, every DNN has a uniform mumber of latent dimensions per layer, and there are no residual connections. We also employed the half-turn metric, whereby both 90a and 180 turns count as one and God's Number for the puzzle is 20 (Rokicki et al., 2014). Accordingly, we set the scramble length to 20.
Figure 5 depicts the estimated scaling law, model data points (N, (N,D, L), as well the trajectory of pro- gressively scaling our Rubik's Cube solver. We fitted total of 36 models and empirically estimated the parameters for Equation (2) as E = 0.892, A = 4.0, B = 6.2, = 0.178, and / = 0.134. The a : B ratio of 0.57 : 0.43 suggests that model size and training data volume should be scaled in roughly equal proportions for optimal performance, aligning with Hoffmann et al. (2022)'s finding on autoregressive language models. The final model was trained with C- = 5.14 x 10 FLOPs, allocated to N s 119 million parameters and D ~ 144 billion states (7.2 billion examples). We used about 12.1% of the total compute to estimate the scaling law while dedicating the remaining 87.9% to train the largest model.
We further evaluated the three largest. models' capabilities in solving Rubik's Cube, using the DeepCubeA dataset once again. To evaluate them not merely on the basis of solution length but also the optimality rate, we employed IDA* * (Korf, 2008) to prepare optimal solutions in the half-turn metric. Figure 6 affirms that increased training compute resulted in improved performance, yielding shorter and more optimal solutions with fewer nodes expanded. This result supports our assumption that the probability distribution of random scrambles, which the DNNs approximate, correlates with solution optimality. On the other hand, the result also reveals the near-saturating benefit of scaling model size for temporal performance, plausibly due to the increased latency of running larger models. Since temporal efficiency is also important aspect of combinatorial scarch, one could also consider estimating the scaling law for optimal temporal performance, although this would heavily depend on the execution environment. In our experimental setup", , we would benefit from increasing training data, but not model parameters.
We used single NVIDIA T4 GPU
9

---

Published in Transactions on Machine Learning Research (07 (07/202) /023)
10
2.0
Scaling trajectory
10a
Efficient frontier
10a
1.8
Parameters (M
Parameters (M)
Validation loss
* Best
Samples (D)
10t0
10²
10
1.6
106
106
8
1.4
000
10a
0
6og
10$
10a
1.2
108
10 Samples (D)
10
10
1015
10
FLOPPs (C)
FLOPs (C)
The scaling law estimation for our Rubik's Cube solver. The gradient surface each subplot represents Equation (2) with the empirically estimated parameters. The blue dashed line indicates the compute-optimal frontier, ie., the theoretical optimum train the best model for given compute budget. Each colored dot represents a unique model approximated as C s 3N; D;. The black lines visualize the trajectory of our progressive scaling strategy. As either model size or training data volume increases, the validation loss diminishes (left). The derived scaling law enables us to estimate the compute-optimal values of N and D for any given compute budget C (middle and right).
Figure 5:
data point (N; D,, L,). where the training compute is
22
22
1=
Solution length
663.61
20
C=5.14199
18
18
10
106
10
10a
10a
40
40
Optimal (%)
10
106
10
10
10a
Number of nodes
Time taken (s)
Figure 6: Downstream performance comparison of the three largest models. Each dotted line depicts the mean solution length (top) and the optimality rate (bottom) as a function of node count (left) and time taken (right) for each model. As the training FLOPs and thus the model size increase, our solver needs to expand fewer nodes reach a specific level of optimality. However, the marginal utility of scaling model size seems diminishing in terms of temporal efficiency.
10

---

Published in Transactions on Machine Learning Research (07 2203))
8 Discussion
We have introduced a novel self-supervised learning method to directly solve a combinatorial problem with a predefined goal, reframing the task as unscrambling. Training DNN on mere random scrambles, our method statistically infers a sequence of reverse moves that lead back to the predefined goal.
In the Experiment with Rubik's Cube, our method outperformed DeepCubeA, the previous statc-of-the- art deep learning method, in terms of both optimality and elficiency, having trained DNN of the same design with 80% less training data. We also demonstrated the applicability of our method to 15 Puzzle and 7 x 7 Lights Out in Additional Evaluations. Our method outperformed DeepCubeA on these problems too, visiting fewer nodes to find optimal solutions. These results provide empirical evidence that our method is generalizable to goal-predefined combinatorial problems.
The Scaling Law analysis indicated that our method scalable with the number of model parameters and the number of training data samples, as well as the effectiveness of random scrambles as supe-supennision signals for the downstream task. However, the benefit of increasing model size on temporal efficiency will plateau at certain point, depending on the environment.
Nonetheless, our method has some limitations. First, it requires the target problem to have predefined goal, which might not be the case in combinatorial optimization problems like Traveling Salesman Problem whose objective is to find the optimal combination itself. For such problems, classic heuristic or approximation algorithms would remain the best approach (Rego el al., 2011; van Bevern Slugina, 2020), although there also are deep learning methods leveraging reinforcement learning and graph neural networks (Mazyavkina et al., 2021; Joshi et al., 2022). Second, our method implicitly assumos the reversibility of moves. If the problem's ss scrambles solutions do not follow a reversible process, such as when state transitions are non- deterministic and subject to randomness, our method may not be effective.
9 Conclusion
We proposed simple and efficient method for solving Rubik's Cube and other goal-predefined combinatorial problems. Our experiments demonstrated that a DNN can learn to solve such problems only from random scrambles, leveraging the statistical lendency of these scrambles to be optimal. Despite the randomness of training data, our method efficiently generates highly optimal solutions. We hope that our work provides insights into search and related problems in the field of machine learning.
References
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's Cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356 363, 2019.
David L Applegate, Robert E Bixby, Vašck Chvátal, and William J Cook. The traveling salesman problem. In The Traveling Salesman Problem. Princeton University Press, 2011.
Shahab Jabbari Arfaee, Sandra Zilles, and Robert Holte. Learning heuristic functions for large state htt.o/.orr/1..1/////11 10111///................
spaces. Artificial Intelligence, 175(16):2075-200) -0988, 2011. doi: https///o.ooo//....00o//arattt11 000000.0.0.00000000000..11
Adrian Brüngger, Ambros Marzetta, Komei Fukuda, and Jürg Nievergelt. The parallel search bench ZRAM and its applications. Annols of Operations Research, 90:45-63, 1999.
Erik D Demaine, Sarah Eiscnstat, and Mikhail Rudoy. Solving the Rubik's Cube optimally is NP-complete. arXiv:1706. 0766::1006.0670882) 2018.
Rüdiger Ebendt and Rolf Drechsler. Weighted a* scarch-unifying view and application. Artificial Intelligence, 173(14):1310 1342, 2009.
Xavier Glorot, Antoine Bordes, and Yoshua. Bengio. Deep sparse rectifier neural networks. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15, pp. 215-323. Proceedings of Machine Learning Research, 2011.
11

---

Published in Transactions on Machine Learning Research (07/2023)
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEFE Transactions on Systems Science and Cybernetics, 4(2):100 1010000-07,,000 1968.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEFE Conference. Computer Vision and Pattern Recognition, 2016.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Pat- wary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling predictable, empirically. arXiv 2017.
preprint Xtv::1711.0000
Jordan Hoffmann, Scbastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optinal large language models. arXiv preprint arXiv:2203.15555 2022.
Sergey lofle and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Machine Learning, pp. 4484456. Proceedings of Machine Learning Research, 2015.
Chaitanya K Joshi, Quentin Cappart, Maris-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, pp. 1 29, 2022.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXie preprinl arXiv:2001.0883 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv: 1rXiv:1412.6980, 2014.
Richard E Korf. Depth-first iterative deepening; An optimal admissible tree search. Artificial Intelligence, 27(1):97-109, 1985.
Richard E Korf. Finding optimal solutions to Rubik's Cube using pattern databases. AAAI, pp. 700-705, 1997.
Richard E Korf. Linear-tine
implicit graph search. Journal of the ACM, 55(6), 2008.
Daniel Kunkle and Gene Cooperman. Twenty-six moves suffice for Rubik's Cube. In Proceedings of the 2007 International Symposium on Symbolic and Algebracc Computation, pp. 235 235-242, 2007.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combi- natorial optimization: A survey. Computers Operations Research, 2021.
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's Cube with approximate policy iteration. International Conference on Learning Representations, 2018.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. Tn International Conference on Machine Learning, 2010.
Jorge Nocodal. Updating quasi-newton matrices with limited storage. Mathematics of computation, 35(151): 773 782, 1980.
Christos H Papadimitrion and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complerity, Courier Corporation, 1998.
Ira Pohl. Heuristic search viewed as path finding in graph. Artificial Intelligence, 1(3-4):193-204 1970.
César Rego, Dorabela Gamboa, Fred Glover, and Colin Osterman. Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211 (3):427-4411 2011.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge. The diameter of the Rubik's Cube group is twenty. STAM Review, 56(4):645-66) 670, 2014.
12

---

Published in Transactions on Machine Learning Research (07/2023)
Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. orXiv preprinl ar Xix:::1909 12673, 2019.
Stuart Russell and Peter Norvig. Artificial Intelligence: Modern Approach. 4th. Pearson, 2021.
René van Bevern and Viktoriaa A. Slugina. A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. Historia Mathematica, 53:118-127, 2020. ISSN 0315-0860. doi: http://d..o.r.11000000.......mm. pi1/8933500602030244..
URL htpp:///ww..ccencccireee.. com/science//rricct///
Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8:120388-12000 2020.
doi: 10.1109 Btt/:/ACCESSS00...00000
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2104-12113, 2022.
13


Reviews:
[{"review_id": "9PKnQSuCHw", "reviewer": "Reviewer_v4Mr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Surprising results: just predicting the action from random actions is enough. \n- Extensive experiments\n- Clear writing \n\nWeaknesses:\n- The results aren't a lot better than DeepCubeA", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors show that, surprisingly, you can learn to solve the Rubik's cube and other planning puzzles without any reinforcement learning and just by predicting the action that was taken to get to that state from the solved state. They provide extensive experiments on Rubik's cube, lights out, and 15-puzzle, achieving SoTA results compared to DeepCubeA. They also show scaling laws demonstrating that this method continues to improve with data and size of the network, similar to LLMs. This result is noteworthy because it provides a more scalable approach compared to the deep RL in DeepCube. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see more discussion / experiments about the number of scrambles. In the paper the authors set the number of scrambles to be equal to God's number. Intuitively this roughly makes sense, but it would be nice to be more rigorous here. What if there is one weird state with a super high number (so God's number is very high) but every other state is reasonable? It seems that if you set N to be equal to God's number in this case the entropy would be too high to learn anything useful. \n\nThis is a very important part of the paper because too low N and too high N simply won't work. ", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nE9zokrLcM", "reviewer": "Reviewer_nQS3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the method is neat and intuitive, and echoes the self-supervision techniques deployed in large language models. The experimental results are impressive.\n\nWeakness: Lack of certain clarity. Few typos/errors in the draft.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper purposes to solve Rubik's Cube via a beam best-first search using the predicted culminated probability toward the goal state as the evaluation function. Specifically, the novelty of the approach is to train a deep generative model using randomly scrambled trajectories from the goal state, to predict the likely next move to the goal state. Therefore the culminated probability can be evaluated via random rollout using the generative model. The author demonstrated that their approach outperforms the previous state-of-the-art, DeepCube, on the solution length, optimality, number of nodes expanded and the running time. The authors also provide evaluations on other domains. The authors also empirically investigate the scaling law of their method, i.e., the relation between the performance and the model size/training size under a computation budget.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "While I admire the elegant algorithmic approach in this paper, there are a few places that I would like to ask the authors to address:\n\n1. Using randomly scrambled trajectories to train the model doesn't sound very \"optimal\". I would imagine a another way to produce the quality training trajectories is to use other algorithms (say a standard RL agent) to find an approximate optimal path from the goal state to some arbitrary states. Can the authors elaborate more on why you consider the randomly scrambled trajectories are correlated with the optimal path?\n\n2. It will be great if the author can also include the pseudocode for the beamed best-first search. If I understand correctly, the evaluation function of the search is the culminated probability towards the goal state, whose probability is estimated by the trained DNN? And how do you produce these candidates? Are they generated by random rollouts by the DNN?\n\n3. For the experimental results, are there notions of confidence intervals? E.g., do you compute the average performance by one particular run of the algorithm per instance, or average across multiple runs?\n\n4. I am not sure whether Table 3 makes sense: the number of nodes expanded for your method is 24.26, while for DeepCubeA is 1.14*10^6. Can the author clarify this huge gap.", "broader_impact_concerns": "I do not have ethical concerns about the results of this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "K3o4LaqOKj", "reviewer": "Reviewer_43Jt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The method is simple and the writing is clear to follow.\n* The authors discuss important assumptions of the proposed method (section 3). They also give some intuitions on why the method would work given those assumptions.\n\nWeaknesses:\n* The experiment design _may be flawed_. It’s not clear if the 1000 Rubik’s Cube test cases are already covered in the self-supervised training set. Although the Rubik’s Cube state space is huge O(10^19), the test cases were obtained by randomly scrambling the solution state with 1000~10000 moves. The states obtained this way are likely not uniform samples from the true state space. Since pseudo random number generators are used, it is entirely possible that the same states (or small perturbations of them) have already been covered in the self-supervision stage. If so, the DNN can just memorize the (reversed) trajectories.\n* The proposed self-supervision method probably only works for this special type of combinatorial search problems: unscramble to the know solution state. The neural network may exploit certain biases and structures in the task generation process. I am not convinced the method would work for other type of combinatorial search problems. (In fact, the authors also acknowledged such limitations in section 8).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a method to solve combinatorial problems with a predefined goal, such as Rubik’s Cube. These problems share the commonality that the starting states are obtained by randomly scrambling the _unique known_ solution state, and the task is to recover the solution state using a sequence of operations. The proposed method trains a deep neural network to unscramble – one step at a time. \n\nMain contributions:\n* A self-supervised method to collect labeled training data. At inference time, the classifier is used with beam search to iteratively generate candidate paths. \n* Experiment results suggest the proposed method is better than the baseline method (DeepCubeA): it uses fewer samples to train the model and the resulting solver is closer to optimal and takes less wall-clock time (after normalization). \n* The method shows advantage on two other problems: 15 Puzzle, 7x7 Lights Out.\n* Authors also study the scaling law for their models and leverage the law to optimize model size and training data samples given a compute budget. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* [critical] Please provide analysis to show how much (or little) of the success is due to memorization. At the least, I would like to see a report on how many of the 1K Rubik’s Cube test cases were already seen in the self-supervision stage. Furthermore, it would be great to see how much of the intermediate states during beam-search have been seen before, especially for the intermediate states that are close to the starting states.\n* [critical] In Figure 3, there are _far fewer_ red colored dots (proposed method) compared to black and blue ones. (The volumes of the histograms also don't match.) Please clarify.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I recommend accepting this paper because all the reviewers are positive and both acceptance criteria have been met, but I have some reservations about this paper that I urge the authors to think about.

The result is rather narrow. It applies to needle-in-a-haystack style problems, and specifically it leverages domain knowledge to its full extent: the only thing that makes the domain hard, which is the where the needle is, and how to move out of the haystack. So yes, of course by training a DNN close to the goal states you will be more efficiently solve these problems; classic heuristic search techniques have done exactly that for years (e.g. this is how Checkers was solved). The interesting problem, from the machine learning perspective, is how to do this *generally*, without access to this golden knowledge. Take, as an analogous example, Montezuma's Revenge in the Arcade Learning Environment, widely known to be this kind of problem. If researchers had started from the goal state, this would have been considered cheating, because the purpose of the problem is to figure out how to reach the goal state by interacting with the world and acquiring general knowledge to help get to the goal state. 

The paper is incremental in that it improves upon DeepCubeA by being more efficient on this narrow class of problems. It simply removes the distance estimation, but the amount of domain knowledge used is still quite high (just like DeepCubeA).

I'm left unsatisfied -- if I want to solve Rubik's Cube and I'm ok with using privileged information such as starting from the goal state and working backward, why wouldn't I simply use the classic heuristic search methods? I would not have to train a deep network, and the implementation could be specialized to that setting, so it can solve it in a matter of milliseconds, as shown in Table 2. 

In the end, the main contribution is that this paper shows a technique to increase the efficiency of neural network work-back-from-the-solution style solvers, and this method was was mostly already proposed by the authors of DeepCubeA. 

Decision: Accept (poster)