Scramble a Rubik’s cube, and you will create one of 43 quintillion possible arrangements of those 54 colorful square stickers. But that part—the messing it up part—is easy. Solving it, as any amateur knows, is hard.
People are capable of figuring it out, of course, and doing so astonishingly quickly. The best, like 2019 champion Philipp Weyer, solve it in less than 7 seconds. And generally, the whizzes who specialize in getting the jumbled cube back to sides of pure red, blue, green, white, yellow, and orange, make that happen in around 50 moves.
While humans have been solving these puzzles for decades, it’s time for artificial intelligence’s turn: AI can now quickly compute a very efficient solution to a scrambled cube. And 60 percent of the time, this AI will calculate a solution that involves the fewest possible moves, which is generally around 20 or so. In fact, there’s a concept in the world of the Rubik’s cube known as God’s algorithm, which would be the way to solve a cube if an all-knowing deity eyeballed it and simply knew how to solve it in the fewest possible moves. “We are close to God’s algorithm,” says Pierre Baldi, a computer science professor at the University of California, Irvine, and the senior author on a new study describing the Rubik’s-Cube-solving bot in the journal Nature Machine Intelligence.
Before you start picturing a robot with mechanical fingers manipulating a cube and climbing atop a podium at speedcubing competitions, consider that this AI creation is just software. It solves the cube virtually. In fact, there is a decades-long tradition of using games as challenges for artificial intelligence systems, and they can already dominate at contests like chess, Go, and multiplayer Texas hold ’em poker.
When it comes to the Erno Rubik’s 1974 puzzle, traditional programs could already produce a solution to a scrambled cube using rules-based computing, but the news here is that a type of AI called deep reinforcement learning can now do so.
Since the Rubik’s cube is so complex, you can’t just expect an AI system to figure it out without training. And just virtually twisting and turning it and trying to solve it randomly definitely doesn’t work, either. Instead, the researchers behind the project began with baby steps—a cube that is very close to its solution, and just needed a few moves to complete. They progressed through “scrambles of increasing complexity” while teaching it, Baldi says.
“It’s like a child,” he says. “We first give it easy problems, and then progressively harder problems.”
So how does this algorithm stack up—how good a speedcuber is it? A version of the Baldi team’s algorithm is online, and you can try it out here. That version takes only around a second to examine a scrambled cube and then produce a solution. Its solution will be significantly less than the 50 moves or so a human typically uses to solve a cube in competition, but it’s less likely to produce a solve that’s perfectly minimal. Meanwhile, the version of the AI that the researchers report in their paper is more powerful but slightly slower: it can produce the shortest possible solution 60 percent of the time, but the computational delay for that is around 20 seconds long, according to Baldi. Still, that’s much, much faster than it would take a human, a cube in their hands, to figure out a solve that involves a minimal number of moves.
In comparison, remember that humans can do this in around 6 seconds, but since they’re working in the real world, they have to physically twist and turn it. Speedcubers can actually solve the cube using fewer moves than 50, but the faster method by time is actually for them to not to do in the fewest possible twists.
The cube is an elegant puzzle, because while there are quintillions of different ways to mess it up, and many routes to take to solve it, there’s only one destination to get to: the solved cube.
Software engineers use games as a framework for building AI algorithms, but also keep an eye on the ways that software that can play games could also be applied to real-world situations. In this case, Baldi says there could be applications in the field of robotics. For example, he imagines a robot that cleans up your kitchen. Like the cube, a kitchen can be scrambled, or dirty, in many different ways, but there’s just one solved state: a clean cooking space, with everything in its place. Algorithms like the cube-solver could be applied to situations like this one. “If the robot was to move things randomly—take dirty dishes and move them randomly around in the kitchen—the kitchen would never get cleaned,” he says. “You [can] see the similarity between certain robotic tasks and what we did.”
