- blogs
- projects

- source code (Zip)

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

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-

6 0 1 2 3 4 5and 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