Solving the Rubik's Cube with Approximate Policy Iteration
Recently, Approximate Policy Iteration (API) algorithms have achieved super-human proficiency in two-player zero-sum games such as Go, Chess, and Shogi without human data. These API algorithms iterate between two policies: a slow policy (tree search), and a fast policy (a neural network). In these two-player games, a reward is always received at the end of the game. However, the Rubik’s Cube has only a single solved state, and episodes are not guaranteed to terminate. This poses a major problem for these API algorithms since they rely on the reward received at the end of the game. We introduce Autodidactic Iteration: an API algorithm that overcomes the problem of sparse rewards by training on a distribution of states that allows the reward to propagate from the goal state to states farther away. Autodidactic Iteration is able to learn how to solve the Rubik’s Cube and the 15-puzzle without relying on human data. Our algorithm is able to solve 100% of randomly scrambled cubes while achieving a median solve length of 30 moves — less than or equal to solvers that employ human domain knowledge.
Code (0)
등록된 구현이 없습니다.
Tasks
Rubik's CubeSimilar Papers 제목 키워드 기반
Sub-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 AnalysisSolving 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 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 LearningCubeRobot: 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 CubeSolving the Rubik's Cube Without Human Knowledge
A generally intelligent agent must be able to teach itself how to solve problems in complex domains with minimal human supervision. Recently, deep reinforcement learning algorithms combined with self-play have achieved s…
Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learningReinforcement Learning+2