Self-Supervision is All You Need for Solving Rubik's Cube

• URL: http://arxiv.org/abs/2106.03157v5
• Date: Tue, 23 May 2023 17:55:46 GMT
• Title: Self-Supervision is All You Need for Solving Rubik's Cube
• Authors: Kyo Takano
• Abstract summary: This work introduces a simple and efficient deep learning method for solving 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A Machine Learning Approach That Beats Large Rubik's Cubes [32.8176720435354]
  The paper proposes a novel machine learning-based approach to the pathfinding problem on extremely large graphs. We demonstrate its efficiency by finding solutions for 4x4x4 and 5x5x5 Rubik's cubes with unprecedentedly short solution lengths.
  arXiv  Detail & Related papers  (2025-02-18T20:22:38Z)
• Node Classification and Search on the Rubik's Cube Graph with GNNs [55.2480439325792]
  This study focuses on the application of deep geometric models to solve the 3x3x3 Rubik's Rubik. We begin by discussing the cube's graph representation and defining distance as the model's optimization objective. The distance approximation task is reformulated as a node classification problem, effectively addressed using Graph Neural Networks (GNNs)
  arXiv  Detail & Related papers  (2025-01-30T18:52:43Z)
• Solving Rubik's Cube Without Tricky Sampling [0.6445605125467574]
  The Rubiks Cube, with its vast state space and sparse reward structure, presents a significant challenge for reinforcement learning. Previous research addressed this by propagating cost-to-go estimates from the solved state and incorporating search techniques. We introduce a novel RL algorithm using policy gradient methods to solve the Rubiks Cube without relying on near solved-state sampling.
  arXiv  Detail & Related papers  (2024-11-29T09:56:40Z)
• Solving a Rubik's Cube Using its Local Graph Structure [13.219469732742354]
  A Rubix Cube has six faces and twelve possible actions, leading to a small and unconstrained action space. A Rubix Cube can be represented as a graph, where states of the cube are nodes and actions are edges. Drawing on graph convolutional networks, we design a new search algorithm to find the solution to a scrambled Rubix Cube.
  arXiv  Detail & Related papers  (2024-08-15T05:39:52Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  Normalized-Cut (N-Cut) is a famous model of spectral clustering. Traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$-means or spectral rotation. We propose a novel N-Cut solver based on the famous coordinate descent method.
  arXiv  Detail & Related papers  (2023-11-26T07:11:58Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  The ML4CO aims at improving state-of-the-art optimization solvers by replacing key components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate routing configuration.
  arXiv  Detail & Related papers  (2022-03-04T17:06:00Z)
• CubeTR: Learning to Solve The Rubiks Cube Using Transformers [0.0]
  The Rubiks cube has a single solved state for quintillions of possible configurations which leads to extremely sparse rewards. The proposed model CubeTR attends to longer sequences of actions and addresses the problem of sparse rewards.
  arXiv  Detail & Related papers  (2021-11-11T03:17:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.