Solving the Rubik's Cube Without Human Knowledge

Abstract

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 superhuman proficiency in Go, Chess, and Shogi without human data or domain knowledge. In these environments, a reward is always received at the end of the game, however, for many combinatorial optimization environments, rewards are sparse and episodes are not guaranteed to terminate. We introduce Autodidactic Iteration: a novel reinforcement learning algorithm that is able to teach itself how to solve the Rubik's Cube with no human assistance. 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.

arXiv commentFirst three authors contributed equally. Submitted to NIPS 2018

References in corpus (4)

• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Evolutionary Algorithms for Reinforcement Learning
• Thinking Fast and Slow with Deep Learning and Tree Search
• From Machine Learning to Machine Reasoning

Cited by in corpus (6)

• Backplay: "Man muss immer umkehren"
• AlphaD3M: Machine Learning Pipeline Synthesis
• Learning to Solve a Rubik's Cube with a Dexterous Hand
• Application of variational policy gradient to atomic-scale materials synthesis
• A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search