Richard Korf colloquium at HMC
Bob Keller
CS Colloquium
Thursday 20 February 1997 at 4:15 p.m.
in Galileo/Edwards Hall, Harvey Mudd College
Finding Optimal Solutions to Rubik's Cube Using Memory-Based Heuristics
Richard E. Korf
Computer Science Department
University of California, Los Angeles
Abstract: We have found the first optimal solutions to random instances of
Rubik's Cube. The median optimal solution length appears to be 18 moves. The
algorithm used is Iterative-Deepening-A* (IDA*), with a lower-bound heuristic
function based on large lookup tables stored in memory. These tables store the
exact number of moves required to solve various subgoals of the problem, in
this case subsets of the individual movable cubies. We characterize the
effectiveness of a heuristic function by its expected value, and show that this
extremely simple model allows good prediction of the nodes generated by IDA*.
The overall performance of the program appears to obey a relation in which the
product of the time and space used approximately equals the problem size.
Thus, the speed of the program increases linearly with the amount of memory
available. As computer memories become larger and cheaper, we believe that
this approach will become increasingly cost-effective.
Biography: Richard Korf is a Professor of computer science at the University of
California, Los Angeles. He received his B.S. from M.I.T. in 1977, and his
M.S. and Ph.D. from Carnegie-Mellon University in 1980 and 1983, respectively,
all in computer science. From 1983 to 1985, he served as Herbert M. Singer
Assistant Professor of Computer Science at Columbia University. His research
is in the areas of problem solving, planning, and heuristic search in
artificial intelligence. He is the author of "Learning to Solve Problems by
Searching for Macro-Operators" (Pitman, 1985). He serves on the editorial
boards of the Journal of Applied Intelligence, the Journal of Artificial
Intelligence Research, and Artificial Intelligence. Dr. Korf is the recipient
of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential Young
Investigator Award, the first UCLA Computer Science Department Distinguished
Teaching Award in 1989, and the UCLA Engineering School First Annual Student's
Choice Award for Excellence in Teaching in 1996. He was elected a Fellow of
the American Association for Artificial Intelligence in 1994.
Travel Directions:
From the West, take Interstate 210 to where Foothill Blvd. branches off.
Follow Foothill Blvd. to Dartmouth Ave. in Claremont,
OR take Interstate 10 to Indian Hill Blvd, then go north to Foothill Blvd.,
turn right and proceed four blocks to Dartmouth Ave.
From the East, take Interstate 10 to Monte Vista Blvd. Go north to
Foothill Blvd., turn left and proceed four blocks to Dartmouth Ave.
Parking is along Foothill and on Dartmouth Ave. From the corner of Foothill
and Dartmouth, walk in towards the center of campus and go down into the
courtyard by the fountain. Galileo/Edwards is inside on the right.
--
Robert M. Keller, Professor and Chair kel...@cs.hmc.edu
Computer Science Department 909-621-8483
Harvey Mudd College http://www.cs.hmc.edu/~keller/ fax 909-621-8465
Claremont, CA 91711 USA secretary 909-621-8225