Solving (and attempting to solve) Rubik’s Cube has delighted millions of puzzle lovers since 1974 when the cube was invented by Hungarian sculptor and architecture professor Erno Rubik. Now, a group of UC Irvine researchers has developed a new algorithm – Autodidactic Iteration – able to solve Rubik’s Cube with no human assistance. The work is an advance in what’s called deep reinforcement learning (DRL), a form of DL that combines classic reinforcement learning, deep learning, and Monte Carlo Tree Search (MCTS).
“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,” write the researchers in their – Solving the Rubik’s Cube Without Human Knowledge – published in May on arXiv.com. They called the resulting solver, appropriately, DeepCube.
Rubik’s Cube is a member of a class of problems whose solution has proven difficult for DRL because there are a large number of states and only one reward state. In this instance, Rubik’s Cube has a large state space, with approximately 4.3 × 1019different possible configurations. The lack of many ‘reward states’ makes it difficult to develop a solving strategy.