Two directional serch for cube solutions...



I was wondering if anyone has ever build a bi-directional tree search for solving specific cube positions.
Let me explain.

Suppose one starts with a solved cube (3x3x3) and find all the configurations after one rotation, and so on say until 10 or 11 rotations. The resulting tree will contain a large number of nodes, but not completely unreasonable.

Now suppose you wish to find the shortest solution for a specific configuration. You may start building another tree similar to the above and look for collisions between nodes of the two trees. After exploring say 10 or 11 levels of the tree it is very likely that the two trees will connect and the shortest path can be obtained.

Anybody ever tried that ?

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Bi-Directional Search

It's been done, and it works. But a bidirectional search is really not very practical in the exact manner in which you describe it. First of all, at 10 or 11 moves from start there will be too many nodes to store in memory. Second, you will have to have two such collections and compare them to each other.

The method to do this that does work (sort of) is called the Shamir algorithm. It works by producing the nodes for the two directions in lexicographic order. That way, the two collections don't really all have to be stored in memory at the same time, and a comparison of the two collections is fairly easy. However, the Shamir algorithm is pretty slow, and there are faster algorithms available for solving a particular position.

Jerry Bryan

Optimal Cube Solver

Have you seen Cube Explorer? It will solve any puzzle in 20 moves or less initially, but also has an optimal puzzle solver. It's help file has full descriptions and even some source code to expain the authors methods. It is a non-commercial, educational product. It is freeware and the result of scientific research. You can download it here. It will also assist you in finding patterns.

Interesting

I remember when the cube first came out, theorist speculated any cube could be solved in around 25 moves. However, if this site is solving consistently in under 20 and not claiming that as optimal, then the actual maximum number of moves needed must be in the teens.

The fact that this typically solves cubes in 18 or so moves does not prove that some position would not require 25 moves, but that does not seem likely. What is most likely is that more than 90% of all scrambled positions can be solved in no less than the theoretical maximum.

Regardless, I still think an optimal solution could be done on home computers in around 10 years.

> However, if this site is so

> However, if this site is solving consistently in under 20 and not claiming that as optimal, then the actual maximum number of moves needed must be in the teens.

The superflip (to take a well-known example) requires 20 (q+h), so the maximum is at least 20. There are other positions known at depth 20, see

http://www.math.ucf.edu/~reid/Rubik/symmetric.html
http://www.geocities.com/jaapsch/puzzles/symmetr1.htm

So far as I am aware, all of the known cases at depth 20 have a high degree of symmetry.

> Regardless, I still think an optimal solution could be done on home computers in around 10 years.

If you mean optimal solutions to specific problems, Cube Explorer (or Mike Reid's program) will already do that for you, as kcushing mentioned. If not... I am unsure what you mean.

Diameter of the Cube Group

Just a followup. In the face turn metric (q turns and h turns allowed), no position has been found that takes more than 20 moves, and positions have been found that do take the full 20 moves. There is no proof that I know of that 20 moves is maximal. The fact that Cube Explorer "always" finds a solution in 20 face turns or less is not a proof that no positions exist that do take more than 20 face turns.

In the quarter turn metric, a position has been found (by Mike Reid) that requires 26 moves.

Cube Explorer works in the face turn metric. The algorithm that it uses is better suited to the face turn metric than it is to the quarter turn metric.

I may implement this.

I am not familiar with what may have been done already, but I may implement this. Doing some rough analysis, I don't think success for a truly scrambled cube would be possible with today's PCs. But it may work for a cube known to be 13 or 14 positions from solved.

The way I see it, memory is the big challenge. If there are 4.33X10^19 possible combinations, I am guessing you would need to store the square root of that in each direction in order to have an expectation of getting a hit. The square root is around 7 billion, which is a lot.

It could be stored, but you need 7 billion positions from the solved state and 7 billion from the scrambled state for around 14 billion total positions. Some may theorize that this would be 11 moves in each direction, but the number of moves does not even matter as much as the number of positions reached.

The good news is that you would not need to make 7 billion times 7 billion comparisons. That is 43.3 quintrillion and seems like not much improvement over a one way search. But for each of the 7 billion on one side you would do a binary search on the other side (probably actually stored in a binary tree). The way I see it, this algorithm would be on order of log N * sqrt(N), with N being the total number of combinations in the Rubik's cube. Perhaps todays processors are strong enough to do that in a week or two given a good implementation. Trouble is it would need at least 200 Gigs of memory. This memory would need to be RAM. I don't think you could systematically load a subset of this memory and not use the other parts for long stretches. Your algorighm could not predict what parts would or would not be needed on the upcoming step.

Someone on this thread suggested strong 5 moves from each direction and searching beyond there without storing the positions. The trouble with this, the way I see it, is that you could not binary search the tree on the other side. That approach leads to an order N algorithm, unless I've missed something.

Perhaps this algorithm would run on computers available 10 years from now. 10 years ago, I think 2 or 4 megs of RAM was common (I could be a little off). Now 512 Meg is common and a Gig is not out of reach for home PCs. Assuming the same growth, we might expect 256 Gigs to be available on PCs 10 years from now. That would still make it tight, but the algorithm seems viable in about 10 years.

>Someone on this thread sugge

>Someone on this thread suggested strong 5 moves from each direction and searching beyond there without storing the positions.

It's workable, though I have not tried it myself (IDA* is almost certainly faster in practice, on any machine with sufficient memory)... the detailed description of the Fiat algorithm can be downloaded from here.

The paper is an old one (1989): I'm not sure whether you would need an IEEE subscription to read it (but see also the link below).

All the states at depth 10, say, from both ends can be generated in O(N^0.5) time by combining pairs of permutations at depth 5. The key point (mentioned in my earlier post) is that those states are generated in a definite order, so that all matches can be found without storing more than a tiny fraction of the search fronts in memory.

A good description (with an explicit example) of how the states can be generated "in order" was given in Cube Lovers by Alan Bawden. His explanation is considerably clearer than the original article.

another possibility

A kind of bidirectional search has already been used by David Moews (CubeLovers: Shamir's method on the superflip, 23 Jan 95 and follow-up posts). It uses ideas of Schroeppel & Shamir and Fiat.

Suppose you are interested in depth 20. Instead of trying to store the whole search tree to depth 10, only states to distance 5 from each end are generated and stored. It is then possible to combine all pairs of paths of length 5 to obtain those at distance 10 from each end and look for a match between them. Rather importantly, those states at depth 10 can be generated in a definite order, so that not all of the two search fronts needs to be kept in memory at any moment.

Probably someone here could elaborate on this method far better than I -- the book-keeping seems rather nasty compared with IDA*.

The David Moews Algorithm AKA Shamir

I have used half of the Shamir algorithm to calculate the number of positions out to ten face moves from Start and out to thirteen quarter turns from Start. The results out to ten face moves and out to twelve quarter turns were posted to the old Cube-Lovers. The results out to thirteen quarter turns were calculated after Cube-Lovers shut down, and so far have not been posted anywhere. The algorithm is fairly slow and takes a lot of memory. I'm working on some improvements as we speak.

By "half the algorithm", I mean simply that you start a unidirectional search at Start, producing positions in lexicographic order in order to eliminate duplicates. You don't do the other half of the bi-directional search.

In order to calculate out to 2n from Start, you have to store all the positions out to n from Start.

Indeed, the bookkeeping is very nasty.

Jerry Bryan

small world...

.
Thanks to everyone who wrote back about this question.

Funny how small the world is; the paper many of you refer to as Shamir's method was written by a bunch of people whose main interest is Cryptography, the science of secret communication. This is indeed my field of research, including quantum cryptography and quantum teleportation (http://www.cs.mcgill.ca/~crepeau/index_en.html).

For the record the authors of the paper are Fiat, Moses, Shamir, Shimshoni and Tardos. It is the tradition in our field to list authors in alphabetical order, regardless of each other's contribution. A proper way to refer to their work is to use the accronym "FMSST89".

On may 22, 1987 Adi Shamir gave a lecture at MIT on early work towards FMSST89. I was a grad student at MIT at the time but unfortunately I was away on that day and missed his lecture...

Of course Shamir is the most famous of these people (because of the RSA cryptosystem) but all five of them deserve our recongnition. Funny that "RSA" is indeed a very rare exception to the alphabetical order rule. I assume they knew the tremendous significance of their invention and decided to be listed according to contributions instead of alphabetically.

To summarize what I found in your answers and in e-mail discussions with some of you:
1) Tom Rikicki developped a C program that optimally solves Rubik's cube configurations (http://tomas.rokicki.com/rubsolv164.c) and requires 700Mb to run.
2) Herbert Kociemba developped "cube explorer" a windows-only program that also computes optimal solutions.

Being a Mac OS person, I didn't manage to try "cube explorer" yet. I am hoping to compile Rikicki's C program on my Mac but have not found the time to do that yet (I need to find a gcc compiler). I am not sure what method neither of these programs use exactly. Please correct me if I have missed anybody else's software...

Cheers, Claude

Other programs

There are also

(3) Herbert Kociemba's old program Cube Optimizer, available as C++ source code (easily compiled). Not as fast as the optimal solvers in the current Cube Explorer, but very useful for working in batch mode.

(4) Mike Reid's program. C source only, but uses symmetry reductions and can do QTM or HTM. Needs a little fiddling around to get it to compile with non-GNU compilers. See
http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html

Either program will run with about 90Mb RAM.

Search to level 11 for q+h

If we use the q+h metric, i.e. one move can be a quarter or half turn then level 9 is 17.5*10^9. Branching factor will be around 13.2 so level 10 will be approximately 231x10^9 (or 231 billions, at least in North America), and level 11 is close to 13.2 times that again, so then we have about 3*10^12 (3 trillion in North America).

I think it is doable. Maybe Herbert or Jaap known a position that needs more than 20 turns? Maybe bi-directional search could find such a position. On a 32-bit machine the array limit is 2 billion, at least with the compilers I use, so virtual memory is needed.

Jerry Bryan may have calculated to level 10 using virtual memory techniques, I'll check the archives. Going to level 11 is necessary because we already know that some positions require 20 moves. Perhaps 12-flip + something? :)

Yes, I think with a 64-bit system and a big hard drive definitely possible, but I never tried it...

> level 10 will be approximat

> level 10 will be approximately 231x10^9 [positions]
> I think it is doable.

You could indeed generate that list, and store it completely if you had about 2 Terabytes of space, assuming you use about 66 bits per position. This can be much reduced by using some trickery. The list should be in sorted order, so that looking up a position is fast.

You then need to consider those positions as permutations, and apply the inverse permutation to the position wou want to solve. This essentially generates another list of the same size. Any position these lists have in common will give a solution.

This second list need not be stored, and could be checked against the first list as it is generated. I suspect however that unless you could somehow have that first list in Ram, the disk seek time will make it extremely slow.
You could instead generate and store the second list level by level. At each level sort it, and compare the sorted list to the first sorted list. This is much quicker since you are reading through the first list in order, and are comparing many more positions as you do so.

> Maybe Herbert or Jaap known a position that needs more than 20 turns?

There are no q+h positions >20 turns that I know of. Tom Rokicki has done a lot of searching with his optimal solver and not found any in over 10000 positions.

> On a 32-bit machine the array limit is 2 billion
Isn't that just the limit on the index? Why not use a 2 dimensional array then.

> Going to level 11 is necessary because we already know that some positions require 20 moves.
Level 10 would be enough to solve all the positions we know of. Level 11 would only be necessary when we happen to get one of those elusive positions that require more than 20 moves (and then the level 10 list is enough to prove it is >20 moves).

So far I would say that for solving individual positions, this method would be overkill. The standard IDA* searches are pretty effective.
On the other hand, if you wanted to prove that all positions can be solved in 20 moves, or search for positions that need 21 moves then such a table would be a very good start.

I would actually store the positions not in one long list but as an array of lists. The array is indexed by the corner arrangement, and the list is of all edge arrangements that occur with that corner arrangement. This also makes it easier to make the table smaller taking into account the symmetries of the cube.

For any corner arrangement it should then be easy to check whether all positions with that corner arrangement are solvable within 20 moves. Then to search for positions of 21 moves, you could start by checking the more likely corner arrangements first (e.g. supertwist)



Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

32 bit limits

Jaap,

I'm pretty sure the limit in my case is from the 32-bit address limit. I'll have to look at the code again to see if it was signed or unsigned.
The absolute limit would be 4 gigabytes on a 32-bit machine. I never actually maxed out the memory in this system so the program was using the swap space as virtual memory, which turned out better than I thought it would.

64 bit motherboards and processors are becoming very affordable so it's the price of memory that concerns me. Assuming I can use DDR400 SDIMM modules it's about $250 Canadian per gigabyte. The biggest hard drives seem to be around 160 gig so it may be a while before we can search for more antipode(s).

> I'm pretty sure the limit i

> I'm pretty sure the limit in my case is from the 32-bit address
> limit. I'll have to look at the code again to see if it was signed
> or unsigned.
> The absolute limit would be 4 gigabytes on a 32-bit machine.

The internal workings of the modern PC are a bit of a mystery to me. Is >4Gb really not possible without a 64-bit architecture? I thought memory was paged anyway so that should not be a problem.
Sure, you can't have an array with more then 2^32 entries, simply because the index is a 32 bit integer, but that is why I thought that using multi-dimensional arrays could work. I know you can't have files that are more then 4Gb on most OSes, because the file pointers are usually ints too.
Anyway, there is no need to have the whole lot in a single file/array. By using multiple (or multi-dim) arrays/files, you should be able to get around such artificial limits.

Then again, all this may be completely off base, as it is mostly speculation.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

>Tom Rokicki has done a lot o

>Tom Rokicki has done a lot of searching with his optimal solver and not found any in over 10000 positions.

I haven't seen a report of this work. Do you happen to know what distribution of states was, w.r.t. depth in the q+h metric? And, especially, did he find any at depth 20 in his sample?

Sorry, I remembered wrong. It

Sorry, I remembered wrong. It was 'only' 22700 or so cubes, and another 34000 in q metric:

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/8541

There were no 20 q+h positions, and 23 is the deepest in q metric.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

Diameter of the Cube Group

Mike Reid found a position requiring 26 moves in the quarter turn metric. Given that random and exhaustive searching apparently found no position requiring more than 23 moves in the quarter turn metric, I would be dubious that 20 moves is maximal in the face turn metric.

Jerry Bryan