1997 · 255 citations · 9 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationComputational ComplexityHeuristic OptimizationHeuristic SearchMemory Hierarchy OptimizationMetaheuristic OptimizationHeuristic Function DesignMemory-bounded SearchOptimization HeuristicsPattern DatabasesSearch HeuristicsState Space ExplorationState Space SearchState-space Structure
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 lowerbound heuristic function based on large memory-based lookup tables, or “pattern databases ” (Culberson and Schaeffer 1996). 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 an admissible heuristic function by its expected value, and hypothesize that the overall performance of the program obeys a relation in which the product of the time and space used equals the size of the state space. 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.
9
Depth-first iterative-deepening
Richard E. Korf · Artificial Intelligence · 1985 · 1.6K citations
Macro-operators: A weak method for learning
Richard E. Korf · Artificial Intelligence · 1985 · 297 citations · Full text
A world championship caliber checkers program
Jonathan Schaeffer, Joseph Culberson, Norman Treloar et al. · Artificial Intelligence · 1992 · 162 citations
Machine discovery of effective admissible heuristics
Armand Prieditis · Machine Learning · 1993 · 68 citations · Full text