In a world-first, researchers at the University of California have developed a computer algorithm that can solve a Rubik’s Cube without a neural network, machine learning techniques, “specific domain knowledge” or human assistance.
The algorithm, entitled DeepCubeA, solved 100% of the 1,000 test trials, with each cube being scrambled between 1,000 and 10,000 times from the completion state, using the smallest possible number of moves 60.3% of the time. In 36.4% of the trials, the algorithm solved the puzzle using just two moves more than the possible minimum.
A young competitor tries to solve a Rubik cube puzzle during the French Rubik’s cube championships, on April 20, 2012 in Paris. Image: AFP/Thomas Samson via AFP Relaxnews
In addition to being able to solve a Rubik’s Cube, the DeepCubeA algorithm successfully completed additional types of puzzles including various tile sliding puzzles, Lights Out and Sokoban. These were finished far more frequently than the Rubik’s Cube using the smallest possible number of moves.
According to the scientists, “the generality of the core algorithm suggests that it may be applications beyond combinatorial puzzles, as problems with large state spaces and few goal states are not rare in planning, robotics and the natural sciences.”
By successfully being able to solve a Rubik’s Cube without initially being trained on previous information, the DeepCubeA algorithm represents the gradual shift in machines from making carefully-directed computations to making those which appear to resemble human-like reasoning and decision-making. HM/JB
RELATED STORIES:
Robotic fish swims with real fish to explore marine life
Just like humans, gorillas form ‘complex societies’