Source: engadget.com
Researchers at the University of California, Irvine have created an artificial intelligence system that can solve a Rubik’s Cube in an average of 1.2 seconds in about 20 moves. That’s two seconds faster than the current human world record of 3.47 seconds, while people who can finish the puzzle quickly usually do so in about 50.
However, UC Irvine’s DeepCubeA doesn’t hold the record for automated Rubik’s Cube solving. Last year, researchers built a robot that could complete the puzzle in 0.38 seconds. Massachusetts Institute of Technology’s min2phase algorithm, which isn’t an AI system, solved it three times faster than DeepCubeA. While other methods were specifically designed to solve the cube, DeepCubeA had to forge its own path.
Curiously, the researchers aren’t quite sure exactly how DeepCubeA figured out how to make sure the Rubik’s Cube had a solid block of color on each of its six faces. There are billions of possible combinations for the cube, but only one completed state. While the scientists showed the AI what the end result looked like, DeepCubeA had to figure out how to get there and they don’t yet have a full understanding of how it developed its strategies.
The researchers started with a simulated version of a completed Rubik’s Cube, then scrambled it. DeepCubeA then trained itself to solve the puzzle over two days, improving its skill as it attempted increasingly difficult combinations. According to a paper published in Nature, researchers gave DeepCubeA 10 billion combinations and urged it to solve the puzzles in 30 or fewer moves.
The AI was then put to the test on a thousand combinations. It cracked the puzzle every time, and did so in the minimum number of moves in around 60 percent of attempts. The algorithm can also find solutions to other games including the sliding tile puzzle, Lights Out and Sokoban.
DeepCubeA uses a neural network (which apes how the human mind processes information) along with machine learning techniques, in which an AI system learns by detecting patterns and theorizing with little human input. It adopts a reinforcement learning approach, by which it learned “how to solve increasingly difficult states in reverse from the goal state without any specific domain knowledge.”
The researchers previously published a paper on a different approach to the puzzle, Approximate Policy Iteration. While that also solved the Rubik’s Cube every time, it did so typically in 30 moves with a median solve time of 10 minutes.
Since DeepCubeA wasn’t specifically designed for solving maddening plastic puzzle cubes from the ’70s, the algorithm could have some broader implications. “How do we create advanced AI that is smarter, more robust and capable of reasoning, understanding and planning?” computer science professor and study senior author Pierre Baldi said in a statement. “This work is a step toward this hefty goal.”
