Computer solving: a 4-list algorithm

[bcube]

Hi,

contrary to popular belief, Cube Explorer was not probably the first solver capable of finding optimal solutions - at least up to 16 moves in HTM in reasonable time.

To my knowledge, Richard Korf was the first one who reported in 1997 at the latest that his algorithm can optimally solve randomly scrambled cubes. Later in the same year, Michael Reid came up with his optimal solver for randomly scrambled cubes using phase 1 of Kociemba´s two-phase algorithm from 1992 (Korf´s paper got poblished on Jul 27. Reid´s message in Cube-lovers mailing list is from Jul 5, but he is referencing to Korf´s paper in his message => Korf was the first one).

In 1989, the 4-list algorithm (link 1, link 2) was published. In theory, a solution being at most 20 moves long is guaranteed to be found using this algorithm. One reason it wasn´t used for optimal solving of randomly scrambled cubes could be a very long search time, another reason might be insufficient computer memory not being able to handle all permutations that reach depths 0-5. Instead, it seems all permutations that reach only depths 0-4 were being used back then. In their paper, though, the authors are talking about the 4-list algorithm as "the first practical algorithm for finding the shortest solution for any given state of Rubik's Cube" or as "we have a feasible implementation of God's algorithm".

Example solves (see #1 and #6).

 

[qq280833822]

I studied this algorithm a few years ago. I believe it does have some potential, but it also has some inherent flaws.
As far as I know, its advantages are:
The theoretical time-space complexity tradeoff (time*space) is O(n^0.75), where time is O(n^0.5) and space is O(n^0.25), while the IDA* algorithm is usually O(n), that is, the search time is inversely proportional to the memory
And its disadvantages are:
When we have more than O(n^0.25) space, its time complexity is difficult to reduce. Specifically, for a complete 17f search, you need to traverse all 9f states during the search anyway, and their number exceeds 17B. For the IDA* algorithm, as long as I use more than 2G memory, most of the 9f states will not be searched.

 

[UMichSpeedCubist]

This is quite facinating.

In the second link, the writer claims the size of L is 621,649 to list all the 5-movers. But I thought it was instead 574,908 according to Rokicki's work. And it looks like the number they got of 621,649 was found programmatically. What am I missing?

 

[bcube]

In the second link, the writer claims the size of L is 621,649 to list all the 5-movers. But I thought it was instead 574,908 according to Rokicki's work. And it looks like the number they got of 621,649 was found programmatically. What am I missing?

You are missing all 4-movers, 3-movers, 2-movers, 1-movers and 0-mover.
574,908 + 43,239 + 3,240 + 243 + 18 + 1 = 621,649
Also note that in their paper (link is included in the linked wiki article above), the authors are saying "[...] all we have to do is to create the list L of all the 911,250 permutations which can be generated by non-redundant compositions of 5 face rotations [...]". I assume that number was calculated as following: 18 * 15 * 15 * 15 * 15 = 911,250.

I believe it does have some potential

Potential for what?
Personally, just like Herbert, I am also operating on the narrow sense of IDA*. As such, I perceive the 4-list algorithm as an alternative to the IDA*-based algorithms listed in the wiki article. Oh, and it sure has potential to be one of the 20MM .