# For 5x5x5 Solving Programs



## unsolved (Apr 13, 2016)

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.


----------



## unsolved (Apr 25, 2016)

I am working on a version of the program that uses very little RAM (my copy needs 128 GB of RAM). Here is a sample solve I started with the program where it reads all of its algs off of the hard disk.

F U2 L U' R U2 R U2 // corners solved, 8 moves total
D2 L2 R2 U' L' R U B' F L' U' // 19 moves total
R' 3U2 F 3R' B F2 U2 B' 3R F 3U2 R' // 31 moves total
B F2 R 2B R' 3U F2 3U' B' R 2B' R2 F2 R' 3U 2B2 R 
F2 R' 2B2 3U2 R2 3U // 54 moves total
R2 2R L2 D' 2R' D R2 B 2R' B' 2R L2 // 66 moves total
R U2 R' 2U' R U2 R' 2U // 74 moves total
U2 F 2D' F' U2 F 2D F' // 82 moves total
R U' B 2D2 B' U B 2D2 B' 2D2 2R 3F 2D 2U' 2R' 2U 3F' 2D R' 
// cage completed with 28 centers solved, 101 moves total
3U L 3F2 2L 2U' 3F2 2U L' 3U' 2L' // 36 centers solved, 111 moves total
2R' U2 2B' 2U' 2B2 2U 3R2 2B' 3R2 U2 2R // 44 centers solved, 122 moves total


I stopped it once I realized the solve would exceed the length of the scramble.


----------



## mark49152 (Apr 25, 2016)

unsolved said:


> I stopped it once I realized the solve would exceed the length of the scramble.


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.


----------



## unsolved (Apr 25, 2016)

mark49152 said:


> 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:



Spoiler












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.



Spoiler





```
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|&&&&|~~~~|
                                   -------------------------
```


----------



## adimare (Apr 27, 2016)

unsolved said:


> 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



unsolved said:


> 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 (Apr 27, 2016)

unsolved said:


> 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 (Apr 27, 2016)

adimare said:


> 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.



adimare said:


> 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:






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:*



Spoiler



F U' R2 D B' R F U R // corners in 9
L2 B' U' L2 R2 U L2 R' U' B F' R' // 10 edges @ 21 moves
B2 3R B2 3R' L' F2 R2 U' L2 B2 R2 D' L 3U L2 3U' // 16 edges @ 37 moves
L2 2F R' 2F' R L2 U D' 2F' U' 2F D // 22 edges @ 49 moves
R' 3R F U' R2 3F2 R2 3F2 U F' R 3R' // 26 edges @ 61 moves
D' L' 2D2 2F' L D L' D' 2F D 2D2 L // 30 edges @ 73 moves
D 2B2 R' U2 R' 2B2 R U2 R 2B2 D' // 33 edges @ 84 moves
2B' R' F2 R 2B R' F2 R // cage solved @ 92 moves
2R2 2U' 2R 3U2 2F' 2L2 2U 2R 3U2 2F 2L2 // 31 centers @ 103 moves


----------



## adimare (Apr 27, 2016)

unsolved said:


> 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?



unsolved said:


> 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.



unsolved said:


> 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.



unsolved said:


> 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.



unsolved said:


> 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".



unsolved said:


> 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.



unsolved said:


> 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"*.



unsolved said:


> 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 (Apr 27, 2016)

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.



adimare said:


> 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.



adimare said:


> 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.



adimare said:


> *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



adimare said:


> 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.


----------



## adimare (Apr 27, 2016)

unsolved said:


> 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...



unsolved said:


> 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.



unsolved said:


> 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.



unsolved said:


> 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?



unsolved said:


> 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.



unsolved said:


> 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).


----------



## Herbert Kociemba (Apr 28, 2016)

adimare said:


> 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 (Apr 28, 2016)

Herbert Kociemba said:


> 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.



Herbert Kociemba said:


> 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.


----------



## xyzzy (Apr 28, 2016)

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.



unsolved said:


> 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 (Apr 29, 2016)

xyzzy said:


> 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.



xyzzy said:


> 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:







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.


----------



## Herbert Kociemba (Apr 30, 2016)

unsolved said:


> 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)



unsolved said:


> 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 (Apr 30, 2016)

Herbert Kociemba said:


> 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.



Herbert Kociemba said:


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



Yes.



Herbert Kociemba said:


> 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


----------



## xyzzy (May 6, 2016)

unsolved said:


> 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


----------



## unsolved (May 9, 2016)

xyzzy said:


> 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.


----------



## unsolved (May 11, 2016)

In other news... I started on the 13-move edge algorithms and hooked part of it to the latest version of the program. 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


----------



## xyzzy (May 11, 2016)

unsolved said:


> 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.



unsolved said:


> 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


----------



## unsolved (May 12, 2016)

xyzzy said:


> 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.



What are the intermediate goals? I never fully understood what the objective was, other than reducing the number of moves spawned by the move generator by selectively getting certain pieces to certain locations so as to not ever have to worry about having to make those moves later.



xyzzy said:


> 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.



It's amazing what brute force will uncover without any intelligence behind it though!



xyzzy said:


> 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.



I'll have to take a look into these multi-phase reduction algorithms at one point.


----------



## xyzzy (May 12, 2016)

unsolved said:


> What are the intermediate goals? I never fully understood what the objective was, other than reducing the number of moves spawned by the move generator by selectively getting certain pieces to certain locations so as to not ever have to worry about having to make those moves later.



For my current approach, the first phase separates the UD centres to the UD faces (but possibly with U centres on the D face and vice versa), the second phase separates RL centres and FB centres as well as ensuring that the permutation of all the wing pieces is even. This prevents the occurrence of a parity case during the edge grouping step (which I've yet to code). The third phase (sort of) orients all the midges and wings, the fourth phase will fully solve some of the centres along with forming some tredges, and the fifth phase will complete the reduction to a 3x3x3 (with edges already oriented, as in the ZZ method).

And yeah, reducing the number of moves the move generator can spawn is part of the objective. Some of the benefits of using a multi-phase solver (in general, not just for reduction) are that it doesn't require storing an alg database, it doesn't constantly destroy progress built up in earlier stages only to rebuild it again, and it generally brings a lot of pieces "closer" (in a vague, air-quotes sense) to their solved locations at once.

On smaller puzzles, if we design our algorithm so that each of the phases isn't too large, we can do a breadth-first search for each phase and add up the maximum distances to get an upper bound on God's number. (This doesn't seem to be feasible with the phases I'm using for the 5x5x5, unfortunately.)



unsolved said:


> I'll have to take a look into these multi-phase reduction algorithms at one point.



Charles Tsai's four-phase reduction for the 4x4x4 is a good starting point, although the lack of fixed centres on the 4x4x4 may make it a bit confusing.

Edit (2016-05-18): Current progress on my solver:
R Dw2 L Uw B2 Fw Bw' Rw2 Uw2 F' Rw // phase 1
B Uw L Rw2 Uw' R2 F Dw // phase 2
Dw2 R F Uw2 L' Fw2 U F' L Rw2 F // phase 3.1
F Uw2 Dw2 Rw2 Lw2 F // phase 3.2
B2 Fw2 Lw2 Dw2 Bw2 D' Fw2 Rw2 Dw2 Bw2 Rw2 Bw2 // phase 4
// phase 5 (not implemented yet)
L2 U' F2 U2 R F R U' R U' R2 F' R2 U F U2 F U R B2 U2 D // phase 6 (3x3x3)

70 moves (68 not counting cancellations) in OBTM. I don't have a good intuitive feel for how many moves the fifth phase will take on average (my main big cube method is sandwich), but I expect it to be large enough that I can't just hit it with IDA*.

Edit (2016-05-19): Just finished coding the fifth phase. Had to spend just over an hour generating a pruning table for this particular phase (the rest of the initialisation time is probably 10 minutes, tops), and this is currently the only phase I have implemented any sort of symmetry reduction at all because I didn't want to spend two hours generating what's essentially the same table twice! Sample solve, with the same scramble as above.

R Dw2 L Uw B2 Fw Bw' Rw2 Uw2 F' Rw // phase 1
B Uw L Rw2 Uw' R2 F Dw // phase 2
Dw2 R F Uw2 L' Fw2 U F' L Rw2 F // phase 3.1
F Uw2 Dw2 Rw2 Lw2 F // phase 3.2
B2 Fw2 Lw2 Dw2 Bw2 D' Fw2 Rw2 Dw2 Bw2 Rw2 Bw2 // phase 4
R2 F2 D2 R' Uw2 F2 U R' Uw2 R Dw2 L2 Uw2 // phase 5.1
U D' F2 L' Dw2 R F2 B2 R' F2 B2 Dw2 // phase 5.2
R' B2 L D L F2 U2 R2 U' R2 F2 U2 F2 U2 F2 R U' R2 F2 U2 F2 U' R' // phase 6 (3x3x3)

There's still a lot of speed-related tweaking to be done, and this scramble was really an "easy" case (i.e. not representative) since phase 3 usually takes a lot more moves and time to find those moves. Phases 3, 5 and 6 are the only ones where I don't use IDA* for the whole phase, as optimally solving these phases quickly requires much larger pruning tables than I have RAM. Even with the subphases I'm using for these phases, the time taken is highly variable and can pretty much be summarised as "extremely slow on average, but occasionally fast".

The problem I'm facing now is that (other than the 3x3x3 phase) there's no obvious way to implement these problematic phases as "somewhat suboptimal but fast" algorithms, short of computing large alg databases or the like; I'm going to have to think a bit harder about this. I'll post more details about the phases at a later date, but just looking at the moves used in the sample solution above should provide enough information on what those phases are anyway.


----------



## Christopher Mowla (Jun 1, 2016)

I've finally gotten some free time, and I have (just for the sake of it), solved the cage of xyzzy's latest scramble in this thread in *59* single slice half turn moves. Obviously I have a 41 single slice half turn reduction (hand found in about 4 hours) + 18 move 3x3x3 (from Cube Explorer in about 10 minutes).

U2 L 2F R2 U 2L U' F' 2D' D F' 3D U2 R' F' 3L D' L F' L F 2B 3D F D 3F L U L 2D2 B 2D R 2D F D2 F' 2D' U2 R' 3D2 F U' F' L' U R' B' R' F2 D L R2 F D2 B' D U2 R'

This was only one pass by a human. Therefore, it's quite possible for the worst cage position of the 5x5x5 to be a at distance in the 30's.


----------

