Solving a Rubik's Cube Using its Local Graph Structure

• URL: http://arxiv.org/abs/2408.07945v1
• Date: Thu, 15 Aug 2024 05:39:52 GMT
• Title: Solving a Rubik's Cube Using its Local Graph Structure
• Authors: Shunyu Yao, Mitchy Lee,
• Abstract summary: 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.
• Score: 13.219469732742354
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The Rubix Cube is a 3-dimensional single-player combination puzzle attracting attention in the reinforcement learning community. A Rubix Cube has six faces and twelve possible actions, leading to a small and unconstrained action space and a very large state space with only one goal state. Modeling such a large state space and storing the information of each state requires exceptional computational resources, which makes it challenging to find the shortest solution to a scrambled Rubix cube with limited resources. The 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 heuristic, weighted convolutional distance, for A star search algorithm to find the solution to a scrambled Rubix Cube. This heuristic utilizes the information of neighboring nodes and convolves them with attention-like weights, which creates a deeper search for the shortest path to the solved state.

Related papers

• CubeRobot: Grounding Language in Rubik's Cube Manipulation via Vision-Language Model [1.644433638087587]
  We introduce CubeRobot, a novel vision-language model (VLM) tailored for solving 3x3 Rubik's Cubes. We incorporate a dual-loop VisionCoT architecture and Memory Stream, a paradigm for extracting task-related features from VLM-generated planning queries. In low-level Rubik's Cube restoration tasks, CubeRobot achieved a high accuracy rate of 100%, similar to 100% in medium-level tasks, and achieved an accuracy rate of 80% in high-level tasks.
  arXiv  Detail & Related papers  (2025-03-25T02:23:47Z)
• 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)
• CubeFormer: A Simple yet Effective Baseline for Lightweight Image Super-Resolution [55.94314421887744]
  Lightweight image super-resolution (SR) methods aim at increasing the resolution and restoring the details of an image using a lightweight neural network. Our analysis reveals that these methods are hindered by constrained feature diversity, which adversely impacts feature representation and detail recovery. We propose a simple yet effective baseline called CubeFormer, designed to enhance feature richness by completing holistic information aggregation.
  arXiv  Detail & Related papers  (2024-12-03T08:02:26Z)
• 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)
• Understanding Energy Level Structure Using Quantum Rubik's Cube [2.7038841665524846]
  This study combines the quantum Rubik's Cube matrix with the Benalcazar Bernevig Hughes model. In order to make the operation of the quantum Rubik's Cube matrix clearer, we use a Josephus ring to draw a topological graph of the Rubik's Cube expansion.
  arXiv  Detail & Related papers  (2024-03-02T12:23:02Z)
• XCube: Large-Scale 3D Generative Modeling using Sparse Voxel Hierarchies [56.460739605550565]
  We present XCube, a novel generative model for high-resolution sparse 3D voxel grids with arbitrary attributes. In addition to generating high-resolution objects, we show that our model can be used to solve a variety of tasks such as user-guided editing, scene completion from a single scan, and text-to-3D.
  arXiv  Detail & Related papers  (2023-12-06T16:23:26Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  The minimax algorithms for neural networks have been developed to solve many problems. In this paper, we propose two types of minimax algorithms. For the setting, we propose DRSGDA and prove that our method achieves a gradient.
  arXiv  Detail & Related papers  (2023-02-08T01:42:45Z)
• Towards Learning Rubik's Cube with N-tuple-based Reinforcement Learning [0.0]
  This work describes in detail how to learn and solve the Rubik's cube game (or puzzle) in the General Board Game (GBG) learning and playing framework. We describe the cube's state representation, how to transform it with twists, wholecube rotations and color transformations and explain the use of symmetries in Rubik's cube.
  arXiv  Detail & Related papers  (2023-01-28T11:38:10Z)
• Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw Puzzles [67.39567701983357]
  Video Anomaly Detection (VAD) is an important topic in computer vision. Motivated by the recent advances in self-supervised learning, this paper addresses VAD by solving an intuitive yet challenging pretext task. Our method outperforms state-of-the-art counterparts on three public benchmarks.
  arXiv  Detail & Related papers  (2022-07-20T19:49:32Z)
• 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)
• Solving Rubik's Cube via Quantum Mechanics and Deep Reinforcement Learning [0.0]
  Rubik's Cube is one of the most famous puzzles involving nearly $4.3 times 1019$ possible configurations. We develop a unitary representation of Rubik's group and a quantum formalism to describe the Cube from its geometrical constraints. The Cube is solved in four phases, all based on a respective Hamiltonian reward based on its spectrum, inspired by the Ising model.
  arXiv  Detail & Related papers  (2021-09-15T10:30:27Z)
• Self-Supervision is All You Need for Solving Rubik's Cube [0.0]
  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.
  arXiv  Detail & Related papers  (2021-06-06T15:38:50Z)
• Self-supervised Video Representation Learning by Uncovering Spatio-temporal Statistics [74.6968179473212]
  This paper proposes a novel pretext task to address the self-supervised learning problem. We compute a series of partitioning-temporal statistical summaries, such as the spatial location and dominant direction of the largest motion. A neural network is built and trained to yield the statistical summaries given the video frames as inputs.
  arXiv  Detail & Related papers  (2020-08-31T08:31:56Z)
• node2coords: Graph Representation Learning with Wasserstein Barycenters [59.07120857271367]
  We introduce node2coords, a representation learning algorithm for graphs. It learns simultaneously a low-dimensional space and coordinates for the nodes in that space. Experimental results demonstrate that the representations learned with node2coords are interpretable.
  arXiv  Detail & Related papers  (2020-07-31T13:14:25Z)
• 3D Sketch-aware Semantic Scene Completion via Semi-supervised Structure Prior [50.73148041205675]
  The goal of the Semantic Scene Completion (SSC) task is to simultaneously predict a completed 3D voxel representation of volumetric occupancy and semantic labels of objects in the scene from a single-view observation. We propose to devise a new geometry-based strategy to embed depth information with low-resolution voxel representation. Our proposed geometric embedding works better than the depth feature learning from habitual SSC frameworks.
  arXiv  Detail & Related papers  (2020-03-31T09:33:46Z)

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.