Research map / Learning theory and algorithms / Combinatorial and search optimization
A machine learning approach that beats Rubik's cubes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a multi-agent pathfinder that trains ResMLP networks to predict random-walk (diffusion) distance to the solved state and uses beam search, achieving state-of-the-art Rubik's cube solution lengths for 3x3x3, 4x4x4 and 5x5x5 cubes.
Problem
Finding short paths on huge Cayley/Schreier graphs (e.g., 4x4x4 and 5x5x5 Rubik's cube groups with up to 10^74 elements) where exact search methods are infeasible.
Approach
Train a residual MLP on random-walk scrambles to regress the number of steps from the solved state (a diffusion distance estimate), then run beam search guided by these predictions; an ensemble of independently trained agents (each with different random training data) is run and the shortest solution is kept.
Key results
- Multi-agent (26 agents) 10-layer ResMLP reaches 98.4% optimality on the DeepCubeA 3x3x3 dataset vs 69.8% for reproduced EfficientCube and 60.3% for DeepCubeA.
- For 4x4x4, 29 agents achieve average solution length 46.51 on the Santa 2023 dataset, versus 53.49 for the best Santa results and below the conjectured diameter of 48.
- For 5x5x5, a 69-agent ensemble achieves average length 92.16 vs 96.58 for Santa Challenge best results; the method is about 26x faster than EfficientCube at solving 3x3x3 with 18.5x less training time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase beam width from 2^18 to 2^24 (ablation) | Ours, 10-layer ResMLP · 3x3x3 Rubik's cube, DeepCubeA dataset | average solution length: 21.137 -> 20.691 | Helped |
| Increase beam width from 2^12 to 2^24 (ablation) | Ours, 10-layer ResMLP, 4M train set · 3x3x3 Rubik's cube | average solution length: 22.15 -> 20.65 | Helped |
| Increase beam width from 2^16 to 2^24 (ablation) | Ours, 10-layer ResMLP, 4M train set · 4x4x4 Rubik's cube | average solution length: 61.88 -> 50.4 | Helped |
| Increase the number of agents (ablation) | Ours, multi-agent solver · 3x3x3, 4x4x4, and 5x5x5 Rubik's cubes | average solution length: up to 8 moves | Helped |
| Increase training set size beyond the tested plateau (ablation) | Ours, ResMLP pathfinder · 3x3x3 and 4x4x4 Rubik's cubes | average solution length | No clear effect |
| Use an 8B-state training set rather than 4B or 16B (ablation) | Ours, 10-layer ResMLP · 3x3x3 and 4x4x4 Rubik's cubes | average solution length: 21.16; 21.12; 21.19; 55.4; 55.11; 55.84 | Mixed |
| Use a 10-layer ResMLP instead of a 1-layer MLP (ablation) | Ours, single-agent solver · 3x3x3 Rubik's cube, W=2^24 | average solution length: 20.829 -> 20.691 | Helped |
| Use multiple agents instead of one agent (ablation) | Ours, 10-layer ResMLP, W=2^24 · 3x3x3 Rubik's cube, DeepCubeA dataset | optimality: 97.3% -> 98.4% | Helped |
| Replace EfficientCube with Ours, 10-layer ResMLP at the same beam width | 3x3x3 Rubik's cube solving · DeepCubeA dataset | average solving time: 287.78 s -> 10.91 s | Helped |
| Use Ours, 10-layer ResMLP instead of EfficientCube | 3x3x3 Rubik's cube solver training · DeepCubeA dataset | training time: 86 hours 25 minutes -> 4 hours 40 minutes | Helped |
Surprising findings
- Increasing the training set size beyond a point (around 8B states) yields little improvement in solution length, while larger beam width robustly helps.
- A single-layer MLP with about 0.34M parameters achieves 90.4% optimality on 3x3x3, comparable to much larger models.
Limitations
- Limited computational resources; results could improve with larger beam widths and more agents.
- Some hard scrambles (e.g., DeepCubeA scramble No.17) were never solved optimally, with no explanation of why.
- Agent count needed for high optimality is large (26 to 69), making ensembles costly in aggregate.
Experimental setup
Datasets: DeepCubeA dataset Kaggle Santa 2023 dataset random-walk generated states
Benchmarks: DeepCubeA 3x3x3 dataset Kaggle Santa 2023 3x3x3, 4x4x4, 5x5x5 datasets
Metrics: average solution length optimality rate solving time
Baselines: DeepCubeA EfficientCube Santa Challenge best results Optimal PDB solver Genetic algorithm
Builds on: DeepCubeA EfficientCube DAVI AlphaZero
Closest papers by meaning
- Solving the Rubik's Cube with Approximate Policy Iteration (ICLR 2019 · similarity 0.85)
- Faster Local Solvers for Graph Diffusion Equations (NeurIPS 2024 · similarity 0.84)
- LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation (ICML 2022 · similarity 0.84)
- DiffAssemble: A Unified Graph-Diffusion Model for 2D and 3D Reassembly (CVPR 2024 · similarity 0.83)
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs (NeurIPS 2026 · similarity 0.83)
- Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.