Machine Learning Can Solve Rubik's Cubes Now
Deep-learning machines have figured out how to master games like chess or Mortal Kombat. Now, computer scientists at the University of California, Irvine taken things to the third dimension by creating an algorithm that can figure out how to solve a Rubik's Cube, a surprisingly difficult change.
"Our algorithm is able to solve 100 percent of randomly scrambled cubes while achieving a median solve length of 30 moves - less than or equal to solvers that employ human domain knowledge," say the scientists in the abstract to their paper, up on Arvix.
The algorithm, called DeepCube, uses what's known as “autodidactic iteration," a form of machine learning developed by the authors of the paper. The big challenge of autodidactic iteration was to allow machines to find their own rewards in solving a puzzle, a goal they can reach. In traditional solving, the process of getting a cube to a solved state can require making it much more scrambled, which is a challenge for machines that are looking to make improvements with each turn.
DeepCube starts with the concept of a completed Cube and works backwards from there, basically. It makes attempt after attempt to turn a perfect Cube into the randomized Cube it has been given. "In each iteration, the inputs to the neural network are created by starting from the goal state and randomly taking actions," they say in the paper.
The team, which includes computer scientists Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi, see potential for autodidactic iteration to get used for things beyond devilish puzzles from the 80s. “We are working on extending this method to find approximate solutions to other combinatorial optimization problems such as prediction of protein tertiary structure,” they say.
Protein tertiary structures are what builds amino acids, and like a Rubik's Cube they are 3D structures. When the problem has an additional layer of complexity, DeepCube starts to work backwards.
Machine learning algorithms learn what their programmers want them to learn. Games are often seen as good starting points for the technology because of their clear rules and concepts of failure and success. These days, they're also used for more serious matters like serious matters like setting bail.
Source: MIT Technology Review
You Might Also Like
