We Have The World’s Fastest Computer Program For Solving Rubik’s Cube. Who Cares?

Niagara Falls, Ontario.  The fourth annual Symposium on Combinatorial Search (SoCS) started this evening. Fifty-five of the top people in this research area will spend two days intensely discussing the latest results. I hope to come away with at least one good idea from this event.

Let me tell you a bit about my research and then use that to motivate the point I want to make in this blog posting. I am best known for my work in applying artificial intelligence technology to computer games and puzzles (one-player games). Consider the well-known Rubik’s Cube. This puzzle is daunting to solve for a human, but what about a computer? Combinatorial search, the subject of the SoCS conference, includes the search techniques used to sift through the myriad of move sequences that one can try to solve the puzzle. Humans solve Rubik’s Cube non-optimally, using many unnecessary moves to orient the Cube into a familiar position. As computer scientists, we do not want just any answer; we want the optimal answer – solve it in the minimum number of moves.

Technology developed by Joe Culberson and I (pattern databases) in the mid-1990s is used by many puzzle-solving programs. For Rubik’s Cube, Rich Korf (UCLA) used our work to build the first practical solver. Today, a team of Israeli (Ariel Felner) and University of Alberta (Robert Holte and I) researchers have the fastest program for getting an optimal solution to this challenging puzzle. Fastest. In the world.

From an article on Rubik's Cube and my work on Checkers
www.sciencenewsforkids.org/2007/09/play-for-science-2

 We’re number 1! We’re number 1!

<Wait for applause>

<Deadly silence>

<Sheepish person bravely speaks up>

“Excuse me, sir. Who cares that a computer can solve Rubik’s Cube?”

<Pause while I compose myself>

Solving Rubik’s Cube, in and of itself, isn’t earth shattering. The world is not a better place because computers have super-human skills here. It's not the application that's important; it's the techniques used to solve the problem. Where can this technology be used? Real-world problems such as:

• Path finding: finding the shortest route between two locations. This is used in GPS systems, computer games, and even on Mars (the Mars Rover). It would be pretty cool if I found out I had created “out of this world” technology.
•  Scheduling: produce a schedule that satisfies constraints. The technology can be used for arranging a trip (minimal travel distance), airline schedules (guarantee that the planes will be in the right location at the right time), and classroom bookings (accommodate all the classes at appropriate times without conflicts).
• DNA sequence alignment: measuring the similarity of two strands of DNA. The measure is important to researchers as they attempt to decipher the human genome.

Working with puzzles is an example of curiosity-based research. You investigate a challenging problem to devise better ways of solving it – perhaps getting an answer faster, or getting a better answer. If all your new technology can do is solve that one problem, then it’s probably not interesting (unless the problem being solved is important). More often than naught, the application domain is a placeholder for a class of problems. In my case, I use games and puzzles as my experimental test-bed because a) they are fun to work with and b) they map to real-world situations.

Over the past decade, research funding in Canada has become increasingly targeted towards projects that have direct industrial applications. The reasoning is obvious: potential economic impact. But this is a short-term view. What about research that produces results for which there is no obvious “usefulness”? Consider the recent discovery of the Higgs boson. There are no commercial products that will likely come out of the discovery itself. However, there can be side effects. For example, building the billion-dollar infrastructure needed to “see” the Higgs may have real impact; surely creating the technology needed to find a particle so small that you can pack 10²⁵ of them into a kilogram will translate into products.

Research does not have to have commercial value to be valuable. One can never predict how ideas will eventually be used. For example, in my area of games, an innocuous Ph.D. thesis of less than 30 pages published in the early 1950s has enormous commercial impact today. Three decades later, John Nash’s work on equillibria in games (showing that in some games a state can be reached where neither player has an incentive to change their strategy) became essential for diverse applications such as auctions and military strategy. Nash won the 1994 Nobel Prize in Economics and was the subject of the Academy-Award-winning film A Beautiful Mind.

As a society we must continue to fund – even grow – our investments in curiosity-driven research. A faster Rubik’s Cube solver may not mean much today, but who knows about tomorrow?