A Machine Learning Approach That Beats Large Rubik's Cubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912237765001216 |
|---|---|
| author | Chervov, Alexander Khoruzhii, Kirill Bukhal, Nikita Naghiyev, Jalal Zamkovoy, Vladislav Koltsov, Ivan Cheldieva, Lyudmila Sychev, Arsenii Lenin, Arsenii Obozov, Mark Urvanov, Egor Romanov, Alexey |
| author_facet | Chervov, Alexander Khoruzhii, Kirill Bukhal, Nikita Naghiyev, Jalal Zamkovoy, Vladislav Koltsov, Ivan Cheldieva, Lyudmila Sychev, Arsenii Lenin, Arsenii Obozov, Mark Urvanov, Egor Romanov, Alexey |
| contents | The paper proposes a novel machine learning-based approach to the pathfinding problem on extremely large graphs. This method leverages diffusion distance estimation via a neural network and uses beam search for pathfinding. We demonstrate its efficiency by finding solutions for 4x4x4 and 5x5x5 Rubik's cubes with unprecedentedly short solution lengths, outperforming all available solvers and introducing the first machine learning solver beyond the 3x3x3 case. In particular, it surpasses every single case of the combined best results in the Kaggle Santa 2023 challenge, which involved over 1,000 teams. For the 3x3x3 Rubik's cube, our approach achieves an optimality rate exceeding 98%, matching the performance of task-specific solvers and significantly outperforming prior solutions such as DeepCubeA (60.3%) and EfficientCube (69.6%). Additionally, our solution is more than 26 times faster in solving 3x3x3 Rubik's cubes while requiring up to 18.5 times less model training time than the most efficient state-of-the-art competitor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13266 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Machine Learning Approach That Beats Large Rubik's Cubes Chervov, Alexander Khoruzhii, Kirill Bukhal, Nikita Naghiyev, Jalal Zamkovoy, Vladislav Koltsov, Ivan Cheldieva, Lyudmila Sychev, Arsenii Lenin, Arsenii Obozov, Mark Urvanov, Egor Romanov, Alexey Machine Learning Discrete Mathematics G.2.2; I.2.8 The paper proposes a novel machine learning-based approach to the pathfinding problem on extremely large graphs. This method leverages diffusion distance estimation via a neural network and uses beam search for pathfinding. We demonstrate its efficiency by finding solutions for 4x4x4 and 5x5x5 Rubik's cubes with unprecedentedly short solution lengths, outperforming all available solvers and introducing the first machine learning solver beyond the 3x3x3 case. In particular, it surpasses every single case of the combined best results in the Kaggle Santa 2023 challenge, which involved over 1,000 teams. For the 3x3x3 Rubik's cube, our approach achieves an optimality rate exceeding 98%, matching the performance of task-specific solvers and significantly outperforming prior solutions such as DeepCubeA (60.3%) and EfficientCube (69.6%). Additionally, our solution is more than 26 times faster in solving 3x3x3 Rubik's cubes while requiring up to 18.5 times less model training time than the most efficient state-of-the-art competitor. |
| title | A Machine Learning Approach That Beats Large Rubik's Cubes |
| topic | Machine Learning Discrete Mathematics G.2.2; I.2.8 |
| url | https://arxiv.org/abs/2502.13266 |