A Program That Learns to Solve Rubik's Cube

Richard E. KorfAAAI 1982

This 1982 classic by Richard E. Korf represents a milestone in artificial intelligence, moving beyond the "General Problem Solver" (GPS) paradigm to tackle complex, non-serializable puzzles like Rubik’s Cube. By automatically learning "macro-operators"—sequences of moves that achieve a goal without undoing previous progress—Korf’s system demonstrated that machines could develop problem-solving strategies that rival or outperform human experts.

The Problem: Non-Serializable Subgoals

In the early 1980s, the dominant AI paradigm was the General Problem Solver (GPS), which relied on "means-ends analysis." GPS works by breaking a problem into subgoals and solving them sequentially. However, GPS has a fatal flaw: it requires that once a subgoal is solved, it never has to be "broken" again.

Puzzles like Rubik’s Cube are notoriously difficult for this approach. To place a final corner piece, you almost always have to temporarily scramble the pieces you’ve already aligned. Because GPS could not reason through this temporary violation of progress, it was effectively useless for the Cube. Korf set out to create a system that could handle these "non-serializable" subgoals by learning complex move sequences that have a clean net effect.

Methodology: The Macro Problem Solver (MPS)

The core of the research is the Macro Problem Solver (MPS). Instead of using primitive moves (like a single 90-degree twist), the solver uses macro-operators:

  1. Macro Table: The system organizes macros into a 2D table. Each column represents a subgoal (e.g., "Position Tile 1"), and each row represents the current location of that tile.
  2. Invariance: A macro for a specific subgoal is designed to be "invariant" to all previous subgoals. This means if you are working on the fifth tile, the macro might scramble tiles 1 through 4 internally, but by the end of the sequence, tiles 1 through 4 are back in their correct spots, and tile 5 is now solved.
  3. Learning via Search: To fill this table, the program uses a breadth-first search for simpler puzzles like the Eight-Puzzle. For the Rubik’s Cube, it employs a bidirectional search and macro composition (combining two known macros to create a more complex one).
A macro-operator table for the Eight-Puzzle showing sequences for different tile positions.

Key Results and Performance

The Macro Problem Solver proved remarkably efficient compared to human performance. On a VAX-11/780, the program could completely learn the macro table for Rubik's Cube in about 15 minutes, using only 200K words of memory.

  • Rubik’s Cube: The MPS generated solutions averaging 90 moves. For comparison, the "Average Human" (based on a sample of graduate students) took about 126 moves.
  • Eight-Puzzle: The MPS averaged 39 moves, nearly identical to the human average of 38.
Comparison of solution lengths for the Eight-Puzzle and Rubik's Cube across different strategies.

Discussion and Limitations

While the MPS is efficient at finding a solution, the solutions themselves are suboptimal. For the Rubik's Cube, 90 moves is significantly higher than the optimal solution (estimated at the time to be around 18-20 moves). The system's strength lies in its deterministic nature: once the macro table is learned, the program does not need to search for a path every time it encounters a new state; it simply looks up the necessary macros.

Korf’s work proved that strategic expertise could be an emergent property of basic computational rules. By allowing the "violation" of subgoals within a macro, Korf bridged the gap between simple search and high-level strategy, paving the way for more advanced heuristic search methods in AI.

Summary updated

BibTeX
@inproceedings{korf1982program,
  author = {Richard E. Korf},
  title = {{A Program That Learns to Solve Rubik's Cube}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}
Figure