Strict Standards: Declaration of action_plugin_blog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/blog/action.php on line 13

Strict Standards: Declaration of action_plugin_captcha::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/captcha/action.php on line 0

Strict Standards: Declaration of action_plugin_discussion::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/discussion/action.php on line 0

Strict Standards: Declaration of action_plugin_include::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/include/action.php on line 0

Strict Standards: Declaration of action_plugin_indexmenu::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/indexmenu/action.php on line 0

Strict Standards: Declaration of action_plugin_popularity::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/popularity/action.php on line 0

Strict Standards: Declaration of action_plugin_safefnrecode::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/safefnrecode/action.php on line 0

Strict Standards: Declaration of action_plugin_tag::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /home/p77/sw7d.com/a/lib/plugins/tag/action.php on line 0

Warning: Cannot modify header information - headers already sent by (output started at /home/p77/sw7d.com/a/lib/plugins/blog/action.php:13) in /home/p77/sw7d.com/a/inc/auth.php on line 352

Warning: Cannot modify header information - headers already sent by (output started at /home/p77/sw7d.com/a/lib/plugins/blog/action.php:13) in /home/p77/sw7d.com/a/inc/actions.php on line 180
sw7d:pawel:projects:rubiks_cube [sw7d]

Rubik's cube solver implemented in LISP

  • source code (Zip)

Technical report for AI class for which this code was written.

Solving Rubik's Cube in LISP
Technical Report by Pawel Slusarz

Abstract
I have written some universal structures to allow me to run any type of search after writing a high level search function. 3 searches were investigated: a* (and its greedy variation), bidirectional, and iterative deepening with a lookup table. The last of those has proven the best, solving 13 move puzzles in under a day. While it is comparable to some early results from scientific papers, currently programs exist which solve up to 20 moves in similar time. However, they use the same algorithm, so it is a matter of platform choice to achieve comparable results.

Introduction
Rubik's cube is a puzzle with a branching factor of 11. The language, LISP, was assigned by the professor. I ran my programs on a Celeron 400 Mhz PC, with 96MB RAM, running NetBSD 1.4, and I used CLISP as the interpreter.

The cube was initially represented as a list of lists. Each side of the cube was assigned a number, and will be further referred to as "face." The operations are RIGHT-, and LEFT-. The centerpiece of a face is fixed with respect to these operations, so it was removed from the model, to provide better efficiency. Face numbering is following:

        6
0 1 2 3 4
        5
and the list is arranged in layers as follows:

(0 0 0) (1 1 1) ... (0 0) (1 1) ...(0 0 0)(1 1 1) ...)
where each number refers to one of the 9 squares on a face, and the middle square (the one which gives the face its name-number) was removed.
In later implementations, the list was replaced with an array to provide a better efficiency. It speeded things up by an order of magnitude.

Structures and implementation
Heap was used to implement a priority queue. Priority queue makes it possible to run depth first search, breath first search, greedy search, and a* search, by changing the heuristic. A binary search tree was used to allow for indexing of positions encountered by each of the 2 bidirectional searches. Hash table would have been more efficient in practice, but there's no way to control the hash function in the hash table implementation provided in common LISP. Later, binary search tree is used to store the lookup table of all moves which are a fixed depth from the solution (depth 6 takes up about 60MB RAM on my PC). Here, a hash table could have been used, but I wanted to demonstrate the robustness of my design, and simply re-wrote the high level search function.

Greedy and A* search
A position is popped from the heap, and expanded. If the expanded depth is equal to the cut-off, and it is not the solution, the node is thrown away. Else, the value of each expanded position is evaluated, and they're put on the heap.

Research has shown that a heuristic to reduce the complexity of the problem has not been discovered yet. In my program, I used a simple heuristic which counts the number of mini-squares which are on the same face as their respective centerpieces. IT turns out not to be very useful, except that it promotes all the positions which are one move away from the solution. Setting the heuristic to return 1 each time, would make this a depth first search, while setting it to be equal to depth of a position, would make it a breath first search. A* search can be implemented by combining the mini-square counting heuristic with some function of the depth.

This was my first shot at the problem, after implementing the cube mechanics. It solves a 6-move position in several hours, which I defined to be "reasonable time." Note that because of the branching factor, it'd take 11 days to solve a puzzle one move further away. In this search, memory is not a factor, because heap remains relatively small. For simplicity I assumed that the depth of the solution is known in advance. It is easy to modify the functions so that they do not assume a known depth.

Bidirectional search
Based on the results from the tests, I reasoned that it was possible to solve a 12-move puzzle by running 2 greedy searches - one from the solved position into the given state, another from given state into the solved position, and hoping that they'd meet half-way. That's the basic premise of bi-directional search.

The practical issue to solve is indexing and looking up the moves that each search has encountered to be able to determine when the 2 searches "meet." I used a binary search tree for that. The key was a unique number which specified state of the cube, and I attached a flag to each entry, to determine which search it came from. If a position was encountered that came form the same search, it was discarded. If the encountered position was from the other search, a solution was printed. Even though I discarded the obvious sequences of moves like LEFT-0 followed by RIGHT-0, the search still reported repeating of over 10% of the positions. This is an interesting property of the cube, but it is irrelevant to the complexity of the problem.

The tests have indeed proven that the expectations were correct. 12 move solutions were obtained in reasonable time. However this search has exponentially growing memory requirements, so 12 moves is an absolute limit here.

Iterative Deepening search (IDS) with a lookup table
Prompted by a colleague, I decided to try an IDS, which has linear memory requirements. It's a brute force approach, where the search tree is rebuilt during each iteration of increasing depth. The search was augmented by a lookup table of all positions 6 moves away from the solution. In the implementation, this was not all that different from the bi-directional search. I ran one search from the goal position for 6 moves to fill in the entries in the "lookup table." The table was implemented as the same binary search tree I used for indexing positions in the bi-directional search.

After the first search terminated, I ran a second one form the start position, which went to a given depth. It'd check whether the expanded position existed in the lookup table, and if so, print the solution. Else, if the position was below the cut-off depth, it'd put the node back on the heap for further expansion. This search is only limited by the size of the lookup table, which was 6 on my machine (takes up 60 Mb). It turned out to be Extremely efficient, and solved 13 move puzzles in the same time it took the bi-directional search to solve 12 moves. This search could be further made faster by implementing the lookup table as a hash table.

Conclusions
It turned out that the simplest approach was also the best in this case. One important lesson is efficiency and implementation, which often allows for speed-up of the orders of magnitude. Changing from list to array implementation gave a 10 times speedup. Changing from a binary search tree to a hash table would give a similar speed-up, as was demonstrated by my colleague (Ken T.; I think his program solves 15 move puzzles). Implementing the same algorithm in C would accomplish several orders of magnitude speedup, as the currently available software solves 21 move puzzles in reasonable time, using the IDS algorithm.


Appendix
Here is some benchmarking information, which also makes it clearer how to run the program:

the 10 move benchmark from previous versions:

Solution found: (LEFT4 LEFT5 LEFT4 LEFT3 RIGHT2 LEFT1 RIGHT0 LEFT1 RIGHT2 LEFT3) 
SOLUTION1: NIL 
SOLUTION2: (LEFT4 LEFT5 LEFT4 LEFT3 RIGHT2 LEFT1 RIGHT0 LEFT1 RIGHT2 LEFT3) 
Exiting loop.
Examined 129570 moves.
Repeated positions: 16834. 

Real time: 122.92835 sec.
Run time: 113.56721 sec.
Space: 184455900 Bytes
GC: 44, GC time: 20.756811 sec.
NIL

improved by introducing snodes:

Solution found: (RIGHT2 LEFT3 LEFT5 LEFT4 LEFT4 LEFT3 RIGHT2 LEFT1 RIGHT0 LEFT1 RIGHT2 LEFT3)
SOLUTION1: NIL
SOLUTION2: (RIGHT2 LEFT3 LEFT5 LEFT4 LEFT4 LEFT3 RIGHT2 LEFT1 RIGHT0 LEFT1 RIGHT2
LEFT3)
Exiting loop.
Examined 341049 moves.
Repeated positions: 44313.
 
Real time: 327.27075 sec.
Run time: 320.64438 sec.
Space: 507075460 Bytes
GC: 89, GC time: 74.18981 sec.
NIL
[24]>  (time (twoway (left2 (right3 (left4 (right5 (left4 (right3 (left2 
(right1 pos1)))))))) sixface 6 6 'h-color-count 'h-color-count-2 'abhash)) 

another 12 move solution and stats

 Solution found: (RIGHT0 LEFT1 RIGHT2 LEFT1 RIGHT0 RIGHT4 LEFT5 LEFT3 RIGHT0 LEFT1
RIGHT2 LEFT3)
SOLUTION1: (RIGHT0 LEFT1 RIGHT2 LEFT1 RIGHT0 RIGHT4 LEFT5 LEFT3 RIGHT0 LEFT1 RIGHT2 LEFT3)
SOLUTION2: NIL
Exiting loop.
Examined 1339541 moves.
Repeated positions: 185688.
 
Real time: 8965.858 sec.
Run time: 3781.4375 sec.
Space: 5634121940 Bytes
GC: 292, GC time: 1361.983 sec.
NIL
[25]>  (time (twoway (left0 (right1 (left2 (right1 (left0 (right5 (left4 (right3 
pos1)))))))) sixface 6 6 'h-color-count 'h-color-count-2 'abhash)) 


12 move solution on bi-directional and stats

 Solution found: (RIGHT0 LEFT1 RIGHT2 LEFT1 RIGHT0 RIGHT4 LEFT5 LEFT3 RIGHT0 LEFT1
RIGHT2 LEFT3)
SOLUTION1: (RIGHT0 LEFT1 RIGHT2 LEFT1 RIGHT0 RIGHT4 LEFT5 LEFT3 RIGHT0 LEFT1 RIGHT2 LEFT3)
SOLUTION2: NIL
Exiting loop.
Examined 1339541 moves.
Repeated positions: 185688.
 
Real time: 8965.858 sec.
Run time: 3781.4375 sec.
Space: 5634121940 Bytes
GC: 292, GC time: 1361.983 sec.
NIL
[25]>  (time (twoway (left0 (right1 (left2 (right1 (left0 (right5 (left4 (right3 
pos1)))))))) sixface 6 6 'h-color-count 'h-color-count-2 'abhash))    

same solution on DFS
Examining move 1041001. Depth: 6.
Current
#S(IDANODE :MOVES (LEFT3 RIGHT1 RIGHT5 RIGHT0 LEFT1 RIGHT0)
   :POS
   #(3 4 3 0 4 4 1 2 0 0 3 4 4 5 5 1 0 5 3 5 1 4 3 0 0 5 4 2 1 5 1 1 2 2 2 0 3 3 5
     1 0 2 2 1 3 4 2 5
    )
   :HASHFUN 1984575
  ).
Interval: 3 sec
Solution found: (RIGHT0 LEFT1 RIGHT2 LEFT1 RIGHT0 RIGHT4 LEFT5 LEFT3 RIGHT0 LEFT1 RIGHT2 LEFT3)
 
Real time: 7207.9033 sec.
Run time: 7149.943 sec.
Space: 12610796740 Bytes
GC: 631, GC time: 2166.201 sec.
NIL                              

sw7d/pawel/projects/rubiks_cube.txt · Last modified: 2009/11/15 19:52 by p77
CC Attribution-Noncommercial-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0