5 August 2019 (Chania, Crete) – Ah, the delight of summer break! Time to catch up on my science reading – that being a stack of unread “Nature” magazines plus about 500 MB of science articles I have downloaded the past year.
For the first time, a deep-learning algorithm has taught itself an efficient way to solve a Rubik’s cube. A Rubik’s cube has over 43 quintillion possible combinations – but only 1 solution, which is achieved by manipulating the cube until all 9 squares on each of the cube’s faces are the same colour. It’s a challenge for an algorithm to teach itself to solve such a puzzle if it is not given any strategic hints on how to do so.
Pierre Baldi and his colleagues at the University of California in Irvine developed a deep neural network – a type of artificial-intelligence algorithm – that figures out how to solve a Rubik’s cube. Their program works backwards from a solution to a given configuration to observe how closely the two are related. It repeats that process for a large number of configurations and combines those observations to determine optimal moves for solving the puzzle.
The algorithm solved the cube on every trial and, in more than 60% of trials, solved the cube with the smallest possible number of moves. The program could be applied to other puzzles with a vast number of potential combinations and a very small number of solutions.
The full paper is behind a very expensive pay wall that I am not at liberty to share, but you can read a review of the paper here, and you can get an idea of how a team at Stanford University used a deep reinforcement learning approach to solve the puzzle by clicking here.