CubeNet M1: Neural Networks with Classic DQN Algorithm for Solving Rubik's Cube

Abstract

This research presents Cubenet M1, a novel neural network architecture optimized for solving Rubik's Cube. This research does not chase low-latency or fast problem solving, but no matter how big the model is, focuses on finding the optimal; minimum actions.

Introduction

We are glad to introduce our first generation Rubik's Cube solving AI, CubeNet M1.

A 3X3X3 Rubik's Cube has $4.3 \times 10^{19}$ possible states. Traditional Reinforcement Learning approaches like DQN fail because the reward signal is too sparse. You are blindly exploring a universe of quintillion states and only get a +1 reward when the cube is perfectly solved.

Using a single Nvidia H100 (VRAM 80GB) GPU and a custom parallel Deep Q-Network, the model had been trained itself from random flailing to level 14 scramble proficiency (solving 14-move scrambles) in less than an hour. Simulating 1.8B(1,795,686,400) moves and crushing the curse of spare rewards with massive parallelism.

Note: Rokicki, Kociemba, Davidson, and Dethridge(2013) had proven that Rubik's Cube can be solved in 20 moves or less. By setting our minimum goal to the level of 20 scramble, we can admit that it's true cube solving AI model. But there's a critical design issue with training scramble level of 13 $\rightarrow$ 20. The performance gets worse when it hits to a critical point in a training session. Which we'll fix and improve at the next generation.

Architecture

1. Neural Network

Standard CNNs like ResNet are designed for images (cats and dogs). But a Rubik's Cube is a graph of connected stickers wrapped in 3D space.

So we decided to design a custom Deep ConvNet specifically for this topology.

• Input: One-hot encoded state ($36 \times 3 \times 3$ tensor). 36 presents the multiplication of the counts of colors(6) and faces(6). So we don't let the model misunderstand the color that there's no relations in each colors by separating them.

• Conv Layers: We used a Dense Escalation strategy, expanding channels from 36 $\rightarrow$ 256 $\rightarrow$ 512. This allows the network to memorize complex pattern combinations (like F2L pairs).

• MLP: 1,024 fully connected neurons with ReLU activation function.

Total Parameters: ~6M

2. Strategy

You cannot just show a random AI a fully scrambled cube; it will never solve it by chance (Approximately 1 in quintillions).

So we implemented a Dynamic Curriculum Monitor. Unlike human strategy(The cube formula), it learns from minimum(1) $\rightarrow$ max(20) scrambles. As the level go up, the number of cases dramatically increases. So to make sure let it experience diverse patterns, we ruled it needs to hit $1000 \times level$ solves for the next level.

Also, we have split two different epsilon decay sections.

• Phase 1 (Level 1 $\rightarrow$ 2): It cannot make a shortcut. Epsilon decaying from 1.0 for discovery.
• Phase 2 (Level 3 $\rightarrow$ 20): Shortcut can be created. Epsilon decaying from 0.5 because it already have discovered the shortest way in previous session.

Finally, by setting bonus reward for finding shortcut and timeout($level \times 2$ actions are given) punishment, we could train our first generation CubeNet.

3. Limitation

While on the experiment of the final test, we hit a wall at Level 14. The state space became so vast that the random exploration (Epsilon) couldn't find a single win in given movement. The Win Rate eventually dropped to 2.0% at Level 17.

The Replay Buffer filled with failures (98% timeouts) and then the agent forgot how to win. We had to stop training immediately and find the sweet spot it can be on. Which was Level 14.

Conclusion

Cubenet M1 demonstrated that AI can solve Rubik's Cube without any given fomula. It explores the path, and creates it's own way that nobody has taught. Even though it struggles to solve complex scramble, we can expect it to get better with partial fixes.