Solving a Rubik's Cube Using its Local Graph Structure
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Rubik's CubeMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Solving Rubik's Cube Without Tricky Sampling
The Rubiks Cube, with its vast state space and sparse reward structure, presents a significant challenge for reinforcement learning (RL) due to the difficulty of reaching rewarded states. Previous research addressed this…
Policy Gradient MethodsReinforcement Learning (RL)Rubik's CubeA Machine Learning Approach That Beats Large Rubik's Cubes
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 pathfindi…
Rubik's CubeSelf-Supervision is All You Need for Solving Rubik's Cube
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, rep…
AllCombinatorial OptimizationRubik's CubeSelf-Supervised LearningSub-Optimal Multi-Phase Path Planning: A Method for Solving Rubik's Revenge
Rubik's Revenge, a 4x4x4 variant of the Rubik's puzzles, remains to date as an unsolved puzzle. That is to say, we do not have a method or successful categorization to optimally solve every one of its approximately $7.40…
Rubik's CubeTime SeriesTime Series AnalysisCubeRobot: Grounding Language in Rubik's Cube Manipulation via Vision-Language Model
Proving Rubik's Cube theorems at the high level represents a notable milestone in human-level spatial imagination and logic thinking and reasoning. Traditional Rubik's Cube robots, relying on complex vision systems and f…
Decision MakingLanguage ModelingLanguage ModellingRubik's Cube