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
- 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) - 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) - 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) - 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)
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.