Thursday 19 July 2012

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 1025 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?

4 comments:

  1. Great post! I was an undergrad at Waterloo when Rubik's Cube came out and spent many hours in stats class playing with it. My C&O roomate eventually devised an algorithm to solve it, but it was by no means optimal.

    ReplyDelete
  2. Jonathan: I don't have much to add to the conversation here, but I do want to note that I appreciate reading your blog posts -- they're inspiring and interesting!

    Regards,

    -kb

    ReplyDelete
  3. Just curious but is this the most optimal algorithm possible or just the most optimal one that anyone has found so far? Any chance of a physical demo something like this: http://www.youtube.com/watch?v=5fAn5A0HbhU (or would the mechanical contraints of the LEGO robot alter the optimization?). Regardless would be fun demo to have...if you built a few you could even have student races to see whether anyone could beat your algorithm!

    ReplyDelete
  4. The algorithm produces an optimal answer: the minimum number of rotations that need to be performed to solve an instance of Rubik's Cube. So, the solution, once found, cannot be beaten. The hard part is finding the solution -- the search space for Rubik's Cube is enormous. The research is in finding algorithms that are "smarter" in their quest to find the needle in the haystack.

    Thanks for the video. I have not seen a robotic Rubik's Cube solver before.

    ReplyDelete