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 |

<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

^{25 }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?

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.

ReplyDeleteJonathan: 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!

ReplyDeleteRegards,

-kb

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!

ReplyDeleteThe 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.

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