• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

For 5x5x5 Solving Programs

Status
Not open for further replies.

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
At some point in time this summer, my 5x5x5 solving program will be completed. I am aware of only one other solver for the 5x5x5 that is under development presently, and that is the one being worked on by IAssemble.

One of the things that has always motivated me has been a self-imposed deadline of sorts. Maybe we can agree on a date to meet here and demonstrate how our programs solve some random scrambles?

I have also benefited greatly from the sharing of ideas. I'd be willing to do the same here for all of those undertaking the task of coming up with a 5x5x5 solving program.

I'd like to limit the discussion to those who are actually writing code, have already written solvers for other cube sizes, or board moderators who are willing to suggest/host FRIENDLY contests aimed at demonstrating the programs' capabilities. At least one too many times in the past I have had to request a mod to lock a thread due to unwelcomed comments by those who, quite frankly, had no idea what they were talking about.
 
Last edited:

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Why does that matter? Presumably your scramble is not optimal, even if you are searching for an optimal solution, which you presumably aren't if your solver does cage.

The 5x5x5 branching factor is very large compared to the 4x4x4 and 3x3x3. Even so, the program has been able to "beat the scramble count" on a few solves. Longer scrambles tend to produce harder solves, up until a certain point. When the program takes "too long" to solve, I hunt for ways to improve it. One obvious way is to add to its knowledge base. The premise that I hold to is, that with enough knowledge, the total count of moves required to solve the cage's centers should approach the number of moves required to solve centers first. If this is true, then I can focus on the edge solving stage, which is the stage that is easiest to minimize the move count (experimentally).

Here is a solve with another 133 move scramble that required 167 moves to cage solve. The center solving stage at the end required 69 moves. From what I have seen posted around, 69 moves for solving the centers isn't that bad.

L' B' U L2 U F' U' F2 U' R2 // corners solved in 10
R F U' 2L D L' D' 2L' B F' L R' // 11 edges
L D' 2R2 D L' R D' 2R2 D R' // 15 edges
3R U' 3R' D 3F' D2 3F 3R U 3R' D // 19 edges
2U' B' D' 3R D2 3R' B 2U B' D' B // 23 edges
F' 2L' F R2 F2 R F 2L F' R' F2 R2 // 27 edges
2D2 2U' F' U' F 2D2 2U2 F' U F 2U' // 30 edges
2B U' 2B' F2 L' 2B L F2 U L' 2B' L // 33 edges
F R' F 2R2 F' R F 2R2 F2 // cage completed in 98 moves total
2R 2F' 2B' 2R' 3R' 2L' 2F2 2B 3R 2L 2F'
L' 3U 2R 3U' L R 3F' 2R' 3F R'
2R' F' 2B' 2R 2F' 2B2 2R' F 2B' 2R 2F
2U2 2R D' 2R' 2U2 2D' 2R D 2R' 2D
2R2 3F' L' 3U2 2B' 3U2 2B L 3F 2R2
R 2U' R 3U R' 2U R 3U' R2
2L2 U' 2R2 U 2L2 U' 2R2 U // 167 moves total, so centers required 69 moves


Note: Every portion of the solve shown above was pre-computed, and looked up in its databases. It required no search.

I am writing procedures now where the algorithms are searched in cascade in RAM, rather than moves being searched. The search routine recursively takes an index into an array of RAM-resident algorithms, rather than recursively calling a move generator. Surprisingly, even a "depth 2" search in this fashion can have tremendous results. Instead of having a depth 12 radius for a search horizon, it instantly doubles to 24. But, as you know, some of these moves are spent reconstructing the cage each time, so one has to whittle down this distance to get a hypothetical "effective solving range" that is somewhat lower. The problem is, all 128 GB of RAM is required to do this for my 5x5x5 program.
I don't think anyone ever tried a cascaded algorithm search, so here's what one looks like:

cqjne1o.jpg

The alternating colors indicate moves that are a part of different algorithms. So while this was a "depth 2" search (2 algs passed into the search), in this case, the depth being explored was 16 moves deep! Not a bad tradeoff (since only 35 seconds of search reached this deep, see the topmost half of the diagram).

The number reported as the search speed is "algs per second," so the actual equivalent movecount is at least 16 times faster, and up to 24 times faster when it gets to 12 move algs being paired with other 12 move algs.

And, for the sake of completeness, here is the scramble and subsequent solve of the corners that preceded the image above.

Code:
Scramble:
           2D' 2L' F'  2F' 3U  2L  F'  L'  U2  R' 
           3U' 2B' 2L  U2  2B' 2F' 2R  R   3U  F 
           2B2 B2  3R2 3F  2B  3F  L2  3R2 2U  3R 
           R2  B2  3R2 2U  3R  B'  F2  B2  R   3F 
           F'  2R  R'  2R2 3U  2D' L'  2R' 2B' D 
           3F2 R'  F'  R'  3F2 L2  2L' F2  U2  B' 
           L'  R2  2U' 3R' 2L2 U2  3F  F   U   3F2
           B2  2L' U2  D'  3F  B'  3U2 2R2 2F' 2L'
           2R  U   3F' B'  3F2 R'  2B2 2U' 3R  U 
           2U' R'  2L2 R2  B2  U   2B  L   3U' 3F2
           F'  B'  2U2 L   2U2 2B' D   2F' F2  2F2
           2U2 2L' 3R  R   2R2 3F2 2F' L'  3R2 L 
           2D  3F  F2  2B' 2L  2U  L   2F  3F  L2 
           2R2 F   L 

           (133 moves total)

                                   TOP
                                   -------------------------
                                  |&&&&|####|&&&&|XXXX|OOOO|
                                   -------------------------
                                  |~~~~|OOOO|####|####|XXXX|
                                   -------------------------
                                  |XXXX|&&&&|####|^^^^|~~~~|
                                   -------------------------
                                  |^^^^|&&&&|XXXX|&&&&|^^^^|
                                   -------------------------
                                  |XXXX|~~~~|~~~~|^^^^|XXXX|
                                   -------------------------
      LEFT                         FRONT                        RIGHT                        BACK
      -------------------------    -------------------------    -------------------------    -------------------------
     |^^^^|OOOO|OOOO|&&&&|OOOO|   |~~~~|XXXX|^^^^|####|~~~~|   |^^^^|&&&&|XXXX|OOOO|####|   |&&&&|^^^^|~~~~|XXXX|####|
      -------------------------    -------------------------    -------------------------    -------------------------
     |OOOO|^^^^|####|####|####|   |^^^^|####|&&&&|OOOO|~~~~|   |^^^^|~~~~|~~~~|XXXX|&&&&|   |####|XXXX|####|~~~~|####|
      -------------------------    -------------------------    -------------------------    -------------------------
     |&&&&|~~~~|XXXX|XXXX|####|   |OOOO|~~~~|^^^^|&&&&|^^^^|   |XXXX|&&&&|&&&&|^^^^|####|   |&&&&|^^^^|OOOO|XXXX|OOOO|
      -------------------------    -------------------------    -------------------------    -------------------------
     |~~~~|^^^^|^^^^|OOOO|####|   |XXXX|OOOO|OOOO|~~~~|^^^^|   |XXXX|^^^^|XXXX|####|&&&&|   |####|&&&&|~~~~|XXXX|XXXX|
      -------------------------    -------------------------    -------------------------    -------------------------
     |####|XXXX|^^^^|&&&&|^^^^|   |XXXX|&&&&|~~~~|^^^^|~~~~|   |^^^^|&&&&|XXXX|OOOO|OOOO|   |~~~~|OOOO|^^^^|&&&&|OOOO|
      -------------------------    -------------------------    -------------------------    -------------------------

                                   BOTTOM
                                   -------------------------
                                  |####|~~~~|OOOO|~~~~|&&&&|
                                   -------------------------
                                  |~~~~|&&&&|OOOO|^^^^|OOOO|
                                   -------------------------
                                  |&&&&|####|~~~~|OOOO|####|
                                   -------------------------
                                  |OOOO|~~~~|OOOO|XXXX|####|
                                   -------------------------
                                  |XXXX|OOOO|####|~~~~|&&&&|
                                   -------------------------

  Corners were solved with 09 moves: L'  B'  R   B'  R   U2  F   R'  U 

                                   TOP
                                   -------------------------
                                  |####|OOOO|####|####|####|
                                   -------------------------
                                  |XXXX|####|^^^^|&&&&|^^^^|
                                   -------------------------
                                  |^^^^|####|####|XXXX|~~~~|
                                   -------------------------
                                  |&&&&|OOOO|&&&&|&&&&|~~~~|
                                   -------------------------
                                  |####|^^^^|^^^^|~~~~|####|
                                   -------------------------
      LEFT                         FRONT                        RIGHT                        BACK
      -------------------------    -------------------------    -------------------------    -------------------------
     |XXXX|OOOO|&&&&|~~~~|XXXX|   |^^^^|XXXX|XXXX|^^^^|^^^^|   |&&&&|XXXX|^^^^|####|&&&&|   |OOOO|OOOO|XXXX|&&&&|OOOO|
      -------------------------    -------------------------    -------------------------    -------------------------
     |&&&&|####|XXXX|OOOO|~~~~|   |&&&&|OOOO|~~~~|####|XXXX|   |####|^^^^|&&&&|~~~~|OOOO|   |~~~~|XXXX|~~~~|&&&&|####|
      -------------------------    -------------------------    -------------------------    -------------------------
     |####|####|XXXX|^^^^|OOOO|   |~~~~|OOOO|^^^^|&&&&|OOOO|   |####|XXXX|&&&&|~~~~|OOOO|   |XXXX|XXXX|OOOO|^^^^|&&&&|
      -------------------------    -------------------------    -------------------------    -------------------------
     |&&&&|^^^^|~~~~|^^^^|~~~~|   |^^^^|~~~~|&&&&|OOOO|^^^^|   |####|####|^^^^|XXXX|&&&&|   |^^^^|~~~~|####|XXXX|####|
      -------------------------    -------------------------    -------------------------    -------------------------
     |XXXX|OOOO|&&&&|~~~~|XXXX|   |^^^^|XXXX|~~~~|^^^^|^^^^|   |&&&&|OOOO|####|~~~~|&&&&|   |OOOO|^^^^|~~~~|XXXX|OOOO|
      -------------------------    -------------------------    -------------------------    -------------------------

                                   BOTTOM
                                   -------------------------
                                  |~~~~|####|&&&&|XXXX|~~~~|
                                   -------------------------
                                  |XXXX|&&&&|OOOO|^^^^|&&&&|
                                   -------------------------
                                  |OOOO|####|~~~~|OOOO|^^^^|
                                   -------------------------
                                  |####|~~~~|OOOO|XXXX|OOOO|
                                   -------------------------
                                  |~~~~|OOOO|XXXX|&&&&|~~~~|
                                   -------------------------

 
Last edited:

adimare

Member
Joined
Oct 29, 2009
Messages
381
Location
Costa Rica
WCA
2011MARE02
The premise that I hold to is, that with enough knowledge, the total count of moves required to solve the cage's centers should approach the number of moves required to solve centers first.
What makes you think that? Intuitively I would think that not having to preserve edges will result in a lot less moves.

For instance, here's your cage solve, I removed your center solution and solved the centers manually ignoring the edges with very little effort put into doing so efficiently (I basically did what I would have done in a speedsolve).

L' B' U L2 U F' U' F2 U' R2 // corners solved in 10
R F U' 2L D L' D' 2L' B F' L R' // 11 edges
L D' 2R2 D L' R D' 2R2 D R' // 15 edges
3R U' 3R' D 3F' D2 3F 3R U 3R' D // 19 edges
2U' B' D' 3R D2 3R' B 2U B' D' B // 23 edges
F' 2L' F R2 F2 R F 2L F' R' F2 R2 // 27 edges
2D2 2U' F' U' F 2D2 2U2 F' U F 2U' // 30 edges
2B U' 2B' F2 L' 2B L F2 U L' 2B' L // 33 edges
F R' F 2R2 F' R F 2R2 F2 // cage completed in 98 moves total

// Solving centers only
R 2U 2L' B' 2L D' 2R B' 2D2 B2 2D2 B 2D' // Right
D' 2L' F 2L L F' 2U L 2U' // Front
U 2B L 2B' 3U L2 3U' D U2 2B D2 L2 2B' // Down
B' 2R B 2R' U' 2L U 2L' U 2F' L2 2F // Left
2R' U' 2R 3R U2 3R' B 2L U' 2L' U 2L U 2L' // Up and Back

61 moves to solve the centers

The center solving stage at the end required 69 moves. From what I have seen posted around, 69 moves for solving the centers isn't that bad.
69 is OK for a speedsolve, but not so much if you're attempting to solve them optimally.

Mods: I'm guessing unsolved will ask you to delete this post. If you choose to do so, please let me know which rule I broke so I can be more careful next time. Thanks.
 

mark49152

Premium Member
Joined
Oct 29, 2012
Messages
4,719
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
the program has been able to "beat the scramble count" on a few solves. Longer scrambles tend to produce harder solves, up until a certain point. When the program takes "too long" to solve, I hunt for ways to improve it.
Perhaps I missed something but I'm afraid I don't follow your logic. Why not just use 10000 move scrambles? Then you will know you have a well-randomised cube as a fair test for your solver, and also a better chance of a solution that beats the scramble count.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
What makes you think that? Intuitively I would think that not having to preserve edges will result in a lot less moves.

1. Proper English is "fewer moves" and not "less moves."
2. In my conjecture, I carefully used the words "with enough knowledge" and "should approach." Those stipulations, as stated, make the premise difficult to refute.

For instance, here's your cage solve, I removed your center solution and solved the centers manually ignoring the edges with very little effort put into doing so efficiently (I basically did what I would have done in a speedsolve).

... 61 moves to solve the centers ...

69 is OK for a speedsolve, but not so much if you're attempting to solve them optimally.

You are not understanding what is happening programming-wise. This is why I asked, in my initial post, only for programmers who are actually writing 5x5x5 code to respond. Some of the information to follow becomes revealed to the programmer at one point in time, once said programmer becomes immersed in the challenges of 5x5x5 programming. The rest of the info should underscore why these results are the beginning of what will soon become even more groundbreaking.

1. At no point in the program's center solve did it search. It did a database lookup. This is much faster than searching, and by much faster I mean about 1000 x 1000 x 1000 x 1000 times faster.

2. There are 5,249,024,392,428,376,695 nodes that need to be explored on the 5x5x5 to complete depth 11. That's pronounced "5 quintillion" in American math prefix jargon. The center database lookup retrieves up to 11-move solutions in the blink of any eye. Just to let you know, the previous speed estimate was not an exaggeration.

3. If you still find that this is not significant, re-attempt your centers-only solve with the limitation you can't execute more than 11 moves at any given time to complete an intermediate goal.

4. If you are successful at item #3 above, try and repeat it with the cage solved.

5. In case there is need of further delineation, you took 61 moves to solve the centers, while destroying everything else. The program took 8 more moves, while preserving everything. If you subtract from the program's moves all of the cage-resolving, the number drops drastically.

6. Now try and imagine how the move count will drop once the program adds all 12-turn, 13-turn, and 14-turn algs to its centers database. It is easy to see, my premise is correct. This is the "beginning of an outline" that leads to success. Adding more knowledge, while applying this technique, will eventually reduce the movecount to such an extent, it should be able to complete the centers within a cage in as many (or fewer) moves as even the keenest reduction solve where centers are solved first.

If you need a more concrete example of how pre-solved algs are the way to go for the 5x5x, I offer this:

aOIitUR.jpg


The numbers inside the curly braces indicate "alg numbers" that were fed to the recursive search. At present, I have 95,513,100 different edge algorithms. Unfortunately, pairing them all up depth after depth would take hundreds of years, but it's still possible to examine every 4-move alg against every alg 4-12 moves in length remarkably quickly. In 1:31 I basically examined every ad hoc 16-move alg possible. After 38:05, I have my first "depth 17" result, where a 5-move alg + a 12-move alg produced a position with even more edges solved.

Depth 16 has 294,643,579,537,160,864,966,536,695 nodes on the 5x5x5.
Depth 17 has 10,450,586,401,808,707,204,742,536,695 nodes on the 5x5x5.

If there is a faster way to examine such search spaces, I'd be interested in hearing about it.

EDIT: A good example of when the RAM-probed algorithms have a huge payout:

 
Last edited:

adimare

Member
Joined
Oct 29, 2009
Messages
381
Location
Costa Rica
WCA
2011MARE02
1. Proper English is "fewer moves" and not "less moves."
Thanks! It's always good for me to learn more English. It's not my first language, so it's a lot worse than my Italian and Spanish, but certainly better than my German and Japanese. I barely passed JLPT N4 last year (embarrassing, I know). Just out of curiosity, how many languages do you speak?

2. In my conjecture, I carefully used the words "with enough knowledge" and "should approach." Those stipulations, as stated, make the premise difficult to refute.
I'm just asking why you think that's the case. It seems fairly obvious that with more restrictions you'll need to spend more moves to solve pieces.

You are not understanding what is happening programming-wise. This is why I asked, in my initial post, only for programmers who are actually writing 5x5x5 code to respond.
So you wouldn't accept help from people like Herbert Kociemba or Tom Rokicki unless they happen to be working on a 5x5x5 solver? Most of the information you presented seems incredibly specific to your program, not to 5x5x5 software in general. If I were to write a solver that only uses commutators to solve the cube, for instance, I wouldn't need to figure out how many nodes need to be explored to reach depth 11.

1. At no point in the program's center solve did it search. It did a database lookup. This is much faster than searching, and by much faster I mean about 1000 x 1000 x 1000 x 1000 times faster.
2. There are 5,249,024,392,428,376,695 nodes that need to be explored on the 5x5x5 to complete depth 11. That's pronounced "5 quintillion" in American math prefix jargon. The center database lookup retrieves up to 11-move solutions in the blink of any eye. Just to let you know, the previous speed estimate was not an exaggeration.
Neat, but finding a solution quickly doesn't mean that you've found a good one.

3. If you still find that this is not significant, re-attempt your centers-only solve with the limitation you can't execute more than 11 moves at any given time to complete an intermediate goal.
For me to be able to try this, I would need to know your definition of "intermediate goal".

4. If you are successful at item #3 above, try and repeat it with the cage solved.
I probably wouldn't be able to, but that's exactly my point. You're saying that solving the centers with or without a solved cage will take a similar amount of moves (oh, I'm sorry, I should have said "with enough knowledge" and "should approach" to make it sound more plausible); a statement I disagree with. If I try this and end up spending more moves to solve the centers because I need to preserve the cage, that would agree with my position, not yours.

5. In case there is need of further delineation, you took 61 moves to solve the centers, while destroying everything else. The program took 8 more moves, while preserving everything. If you subtract from the program's moves all of the cage-resolving, the number drops drastically.
That directly contradicts your premise "with enough knowledge, the total count of moves required to solve the cage's centers should approach the number of moves required to solve centers first".

6. Now try and imagine how the move count will drop once the program adds all 12-turn, 13-turn, and 14-turn algs to its centers database. It is easy to see, my premise is correct. This is the "beginning of an outline" that leads to success. Adding more knowledge, while applying this technique, will eventually reduce the movecount to such an extent, it should be able to complete the centers within a cage in as many (or fewer) moves as even the keenest reduction solve where centers are solved first.
Take as an example my admittedly mediocre 61 move solution for the centers in the scramble you posted. I started by solving a 1x1x3 block by doing R 2U. Solving those same 3 pieces while preserving the edges requires a minimum of 8 moves, regardless of the amount of knowledge in your db. How could adding restrictions possibly result in fewer moves? (See how I used "fewer" there instead of "less"? I have you to thank for that)
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
1. I've been published in 2 different languages. I know 27 altogether, if you count verbose computer languages. I am currently cracking the riddle of the Etruscan language in my spare time. I'll the first person in 2000 years to understand it once it's solved.

2. Don't think I'm under obligation to answer every question you post. You have a belligerent attitude towards me, and I find it annoying. At any moment, I reserve the right to discontinue discussions with you without notice. Consider lack of replies on my part as a strong indication this has occurred.

So you wouldn't accept help from people like Herbert Kociemba or Tom Rokicki unless they happen to be working on a 5x5x5 solver?

Re-read my first post. If you're going to participate here, pay attention.

Neat, but finding a solution quickly doesn't mean that you've found a good one.

That either undermines the entire notion of speedsolving (if quick = "as in time") or is a complete contradiction (if quick = "as in fewest or nearly the fewest possible moves"). Therefore, I disagree.

That directly contradicts your premise "with enough knowledge, the total count of moves required to solve the cage's centers should approach the number of moves required to solve centers first".

No it doesn't. My statement, as it is written, is factual. It is possible to solve the entire cage in one fell swoop. Here is an example where 12 centers were solved at the start of the cage (and 6 of these are fixed from the start) yet after merely 11 moves, an additional 19 centers were solved.

2R2 2U' 2R 3U2 2F' 2L2 2U 2R 3U2 2F 2L2 // gaining 19 centers at once

How could adding restrictions possibly result in fewer moves?

Your thinking is very restricted. If you had any understanding of what the larger databases could do, you wouldn't be asking that question. As more algs are added, fewer cage-revisits are necessary.

Until you show me a program you have written (as you have claimed) I must conclude you are not a programmer. You simply do not demonstrate any traits that I attribute to knowledgeable programmers.
 
Last edited:

adimare

Member
Joined
Oct 29, 2009
Messages
381
Location
Costa Rica
WCA
2011MARE02
1. I've been published in 2 different languages. I know 27 altogether, if you count verbose computer languages. I am currently cracking the riddle of the Etruscan language in my spare time. I'll the first person in 2000 years to understand it once it's solved.
Which languages do you speak? Is English your main one? And no, of course I wouldn't count verbose computer languages...

Re-read my first post. If you're going to participate here, pay attention.
I was responding directly to your post, where you said "This is why I asked, in my initial post, only for programmers who are actually writing 5x5x5 code to respond". I'm not going to re-read the OP every time I post here to keep track of your constant edits.

That either undermines the entire notion of speedsolving (if quick = "as in time") or is a complete contradiction (if quick = "as in fewest or nearly the fewest possible moves"). Therefore, I disagree.
I meant quick as in time. And I was under the assumption that the intention of your program was to find near optimal solutions to 5x5x5 scrambles, not speedsolving friendly ones.

No it doesn't. My statement, as it is written, is factual. It is possible to solve the entire cage in one fell swoop. Here is an example where 12 centers were solved at the start of the cage (and 6 of these are fixed from the start) yet after merely 11 moves, an additional 19 centers were solved.

2R2 2U' 2R 3U2 2F' 2L2 2U 2R 3U2 2F 2L2 // gaining 19 centers at once
My point remains. What makes you think that you would need more moves to achieve the same (gaining 19 centers with 11 moves) if you weren't having to maintain the cage?

Your thinking is very restricted. If you had any understanding of what the larger databases could do, you wouldn't be asking that question. As more algs are added, fewer cage-revisits are necessary.
The algs you're storing in your db solve n centers at a time without affecting the rest of the cube (correct me if I'm wrong). That's fine when you have already solved a portion of the cube (ie: the cage) and don't want to destroy it. But you shouldn't assume so easily that center solutions found using that approach will outperform center solutions that don't have restrictions in how they affect edges or corners.

Until you show me a program you have written (as you have claimed) I must conclude you are not a programmer. You simply do not demonstrate any traits that I attribute to knowledgeable programmers.
Check out http://www.scrambld.cubing.net. If you input a scramble, it produces a commutator-based solution for the cube (it's not meant to be efficient, it's an implementation of the best method that's been discovered for blindfolded solving at the moment).
 
Joined
Nov 29, 2008
Messages
214
My point remains. What makes you think that you would need more moves to achieve the same (gaining 19 centers with 11 moves) if you weren't having to maintain the cage?

I believe unsolved means that his method which is making the cage first + solving the centers gives about the same move count as solving the centers first and then making the cage. This may be correct, though I would not recommend any of these two methods for a solver which claims to give short solutions.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I believe unsolved means that his method which is making the cage first + solving the centers gives about the same move count as solving the centers first and then making the cage.

My premise is essentially this: Whether you solve the centers first via reduction, or last via the cage, the sum of the moves for solving the center-portion-only will be similar, given that a program with enough knowledge is used to complete the cage, and not a human.

Think of a hypothetically-omniscient program. Technically, given any cage, it could solve the remaining centers in one pass, thereby reconstructing the cage only one time. Such a thin move count must, by definition, approach the sum of the moves taken during an optimal centers-first solve. Recall my choice of the word "approach" earlier in a prior post. Think of it as a "limit" in calculus. I never claimed a cage-center-solve always outperforms an uncaged solve of centers. I said, in time, with enough knowledge, the cage-solve-center-count will improve over the typical human count to solve centers first.

This may be correct, though I would not recommend any of these two methods for a solver which claims to give short solutions.

Getting close to God's Number of moves to solve the 5x5x5 will be very difficult. As of this moment in 2016, we don't have much data on what a "long" or "short" solution is for the 5x5x5. My program can solve the corners optimally from any scramble, but that's nothing new. The only thing I did differently was store all 24 possible rotated cube states for all corner positions, plus solve the corners with respect to centers.

Right now, I am trying for intermediate goals of sub-30 for center solving and sub-40 for cage construction. That would give an overall move count of 80 per solve. I think that is reasonably short for the 5x5x5. Once my 13-turn edge database and 12-turn centers databases are completed, I believe the program will be able to solve any 5x5x5 scramble in 100 moves or fewer.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
Writing a 5x5x5 solver seems like an interesting challenge; I might try this, but I'm not a very good programmer so it might take approximately forever to finish it.

My premise is essentially this: Whether you solve the centers first via reduction, or last via the cage, the sum of the moves for solving the center-portion-only will be similar, given that a program with enough knowledge is used to complete the cage, and not a human.

For whatever move sequence you come up with to solve the centres while preserving the cage, you can apply that exact same sequence to solve the centres first. Consequently, the shortest centre solve disregarding the cage is necessarily at most as long as the shortest centre solve while preserving the cage, and very likely to be much shorter.

If I'm interpreting you right, the problem with the centre-first approach as implemented on a computer is that your strategy of caching all move sequences up to 11 moves preserving the cage is no longer applicable (because now you have to cache all move sequences, and there simply are too many for that to be physically possible), and so you don't get amazing speedups. I don't think we should take this to mean that a centre-first approach is necessarily infeasible, just that we don't know a good way of doing it yet. (Maybe that's what I'll try?)
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Consequently, the shortest centre solve disregarding the cage is necessarily at most as long as the shortest centre solve while preserving the cage, and very likely to be much shorter.

If you remove the word "much," I would agree. If there exists an optimal solution to solve centers in "n moves" disregarding the rest of the cube, I say there is a corresponding solution in "n + k" moves, where k is small.

I don't think we should take this to mean that a centre-first approach is necessarily infeasible, just that we don't know a good way of doing it yet. (Maybe that's what I'll try?)

I did outline a way to do this a while back. It's pretty easy, because, as you mentioned, every other way of storing moves is unfeasible or just results in capturing every legal move anyway. The idea is to generate every possible position of 1 center unsolved vs. 1 center unsolved on adjacent faces, generate the move sequence that solves that, then move on to 2 against 2, 3 against 3 ... up to 8 against 8. If you disregard the rest of the cube, I think the max move length for the entire set was something like 15 moves.

I also did it for caged centers 2 against 2 (there are 328 unique positions), 3 against 3, etc. Here is the longest solution for a 2 against 2 case:

3R U' 2R U 3R' U' 2U2 2R' U2 2R 2U2 2R' U'

Fortunately, there is only one entry for 8 centers against 8 centers:

2R' U' 3R' D 2R2 3F2 2R2 3F2 D' 3R D F2 D' U 2R 2L U' D F2 U D' 2L'

And here are some examples of how to do it without preserving the cage:


image.jpg


Moving 3 centers at a time, top to front
2R U2 2L' U 2R' 3F R2 3F' 2L2 F 2L'

Moving 4 centers at a time, top to front
2R 3R U 3R' U' 2R2 F 2L 2R F 2L'

Moving 5 centers at a time, top to front
2R U 2R' U2 2L' 3F U2 3F' 2L2 F 2L'

Once you do this for all possible cases (there's not too many compared to the total node count per depth) then you have a set of algs you can apply "blindly" to a cube position without have to call a move generator. Just count the number of solved centers after you apply each sequence, and go with the winner, and repeat. You can solve the centers in seconds that way.
 
Last edited:
Joined
Nov 29, 2008
Messages
214
If you remove the word "much," I would agree. If there exists an optimal solution to solve centers in "n moves" disregarding the rest of the cube, I say there is a corresponding solution in "n + k" moves, where k is small.
Can you define "small" please? Is it small, when k=n/2 for example?
On the 3x3x3, solving the edges alone takes at most 14 moves in FTM. But solving the edges without destroying the corners takes 20 moves (for example superflip)

Right now, I am trying for intermediate goals of sub-30 for center solving and sub-40 for cage construction. That would give an overall move count of 80 per solve.
You mean solving the centers sub-30 while maintaining the cage? I do not think this is possible. Solving the centers alone without any further restrictions takes at least 20 moves in STM.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Can you define "small" please? Is it small, when k=n/2 for example? On the 3x3x3, solving the edges alone takes at most 14 moves in FTM. But solving the edges without destroying the corners takes 20 moves (for example superflip)

I would estimate k <= 8 in the case of the 5x5x5. Oddly enough, the more centers you move at once, the smaller the difference in moves between cage solving and reduction-phase-1 solving. There are some cases where k = 0; namely the only way to solve all of those centers (in that specific example) produces a sequence where the cage would be left unaffected as well.

You mean solving the centers sub-30 while maintaining the cage?

Yes.

I do not think this is possible. Solving the centers alone without any further restrictions takes at least 20 moves in STM.

In that case, I say k <= 9.

:)

Remember, I have already solved every cage position up to 11 moves. That means I can find a 22-move solution by loading up a hash table with moves made by every 11-move "alg" played in reverse from a solved cube. I loop through all 11-move algs, apply them to a cube I am trying to solve, then test to see if the resulting cube is anywhere in my 11-move hash table. If I do find a match, I know there is at least one path to the solution in 22 moves (or less). If not, I keep searching, apply the alg that solves the greatest number of centers, and try again.

One of the things that is unique about the cage: No matter what REMAINS to be solved, it must be solved by an alg that would CREATE a cage if run in reverse! Therefore you only need to run cage algs on the cage, without having to consider searching any other moves.

Here is one 22-move solution:

https://alg.cubing.net/?type=alg&puzzle=5x5x5&alg=2R-_U-_3R-_D_2R2_3F2_2R2_3F2_D-_3R_D_F2_D-_U_2R_2L_U-_D_F2_U_D-_2L-&title=moving 8 centers top to front&view=playback
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
I would estimate k <= 8 in the case of the 5x5x5. Oddly enough, the more centers you move at once, the smaller the difference in moves between cage solving and reduction-phase-1 solving. There are some cases where k = 0; namely the only way to solve all of those centers (in that specific example) produces a sequence where the cage would be left unaffected as well.

I spent the last few days coding stuff and finally finished a centre (+ wing parity) solver. (Like I said, not a good programmer, yada yada.) It's a very simple three-phase solver, using the intermediate subsets <U, D, R, L, F, B, Uw, Dw, Rw2, Lw2, Fw2, Bw2> and <U, D, R, L, F, B, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2>, and taking only the first optimal solution found for each phase. It doesn't directly extend into a solver for the whole cube, but I have some other ideas as to how to implement that.

I threw a ~180-move scramble into it, and it spat out a 33-move centre solution after about five minutes and a half. There's definitely a lot of room for optimisation here (symmetry reduction, larger pruning tables, hardcoding constants, etc.), but speed aside, I believe this should be some evidence that solving the centres without preserving the cage can be a lot more efficient in terms of move count.

(OBTM was used rather than SSTM, but I don't think that this'll affect move count significantly for centres-first. Even converted to single-slice turns, the move count of the aforementioned solution increases to only 49 moves.)

Edit: Here's the solution. (Scramble not included.)
U Fw' Uw2 Lw Dw2 Fw Bw U Lw' U Bw // phase 1
R F' B Rw2 Fw2 Bw2 Uw L' Rw2 Dw // phase 2
D2 Dw2 Fw2 R Rw2 B' Bw2 L' Rw2 B' Uw2 R Fw2 // phase 3
 
Last edited:

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I threw a ~180-move scramble into it, and it spat out a 33-move centre solution after about five minutes and a half.

That's a good start for a short coding duration. It is possible to get over 30 of the centers solved in under 11 moves in most instances, from what I have found (when I was just searching from the baseline scramble). Once you implement pruning techniques, your program should see the same type of results.

I finished adding the 12-turn edge database access code. Generating the database is one thing, getting it to work with the program is another.

My most recent test scramble of 200 moves with the cage solved in 78:

U' R' B' R' B2 R' F' // corners in 7
R L' 2B' D' F' B U' D F U 2B U'
B2 D B2 R2 D2 B2 D2 F2 U' F2 R2
2L' B' 2L2 2R B L B' 2L2 2R' B L' 2L
2R D2 B' 3R' 2D2 B D2 B' 2D2 3R B 2R'
D 2L' U 2L D' U' L2 U 2L' U' L2 2L
2L' F D2 2R' D2 2R' D2 2R' D2 2R2 F' 2L // cage completed in 78 moves


It looks like that 12-turn edge database was worth the effort! I don't think it will be able to dodge odd-parity situations forever though.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
It is possible to get over 30 of the centers solved in under 11 moves in most instances, from what I have found (when I was just searching from the baseline scramble). Once you implement pruning techniques, your program should see the same type of results.

I'm not using a hill climbing approach (well, mostly not using), so having however many centre pieces solved within the first few moves isn't important. Besides, it's always the last few unsolved pieces that take the most moves if you want to keep the solved pieces intact. I'm just copying the ideas of earlier computer solvers like Thistlethwaite's algorithm, Kociemba's, Shuang Chen's, etc. where the pieces are just "partially solved" in an early stage and fully solved in the final stage; this strategy generally seems to lead to a low-ish move count.

I think it found a 7-cycle mix of edges and wings that is probably not in your everyday alg list:

R' 2D F' D' 3R2 D2 3R2 F 2D' F' D' F R

This can be decomposed as [R' : [2D, F' D F]] (3-cycle of wings) with [D2, 3R2] (a pair of 2-cycles of midges) inserted to cancel one move. While the alg as a whole definitely isn't in anyone's repertoire, it's built from commutators, which are pretty well understood.

On another note, I did some optimisation to my centre solver and it now runs at about twice the speed, but I'm not going to put any effort into further optimisation since I'm trying to implement a five-phase reduction algorithm (plus one more phase for 3x3x3 solving) that doesn't have all the centres solved up front. I coded the third phase over the past two days, and I expect to have the full solver done in a few more days. I'll describe it in more detail if my five-phase reduction algorithm doesn't turn out to be fatally flawed.

This is probably the last time I'll be running the centre-only solver (lol):
U Lw' Bw2 Dw' F2 Lw' Fw R2 Bw' Rw Fw // phase 1
B Dw Lw2 F Rw2 Bw2 Uw Dw' R' L Uw // phase 2
U R' F Rw2 Dw2 Rw2 D F2 Rw2 D Bw2 // phase 3.1
U2 Uw2 Bw2 L Rw2 U2 B' Dw2 Fw2 Lw2 Dw2 // phase 3.2
 
Status
Not open for further replies.
Top