DeepCubeA AI Algorithm Solves Rubik's Cube Without Neural Network or Human Assistance
A paper written by researchers at the University of California and published Monday in Nature Machine Intelligence outlines the development of DeepCubeA, a computer algorithm that can solve a Rubik's Cube without human assistance in under a minute. 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. 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.