Solving Corners Last On Large Cubes

[Christopher Mowla]

But there are sequences with an odd number of moves that can create positions with only corners being unsolved, right? Or is this not what you meant.

Example:

R U' R D2 R' U R D2 R2

Odd permutation is != to an odd number of "moves". Odd permutation ==odd number of quarter turn moves.

This sequence you showed consists of an even number of quarter turn moves (12q). h moves, s moves and/or e moves (all of these terms are from Lucas's applet algorithm length counters) are irrelevant to determining if the permutation is odd or even.


@qqwref, I doubt he will understand your mention of reduction, because, by the signs I have seen in his responses since he's been a member here, and seeing his trivial big cube algorithm requests (asking for algorithms for positions which can be achieved from a direct translation of a 3x3x3 algorithm), I don't think he has ever solved a big cube with reduction before.

 

[unsolved]

The program took 11.57 seconds to get that far before running out of precomputed algs to apply. That won't last long.

EDIT: The whole point of the computer solve was to show that trying to solve edges into their correct spots + centers simultaneously, perhaps the least efficient way to execute a solve, still produces a very high count of initially solved pieces after a very shallow move sequence was applied. This is the exact opposite of what Gottlieb predicted. The program never searched. It blindly applied a "sticker count" algorithm to determine which pre-computed set of moves led to the highest count of solved stickers, awarded +2 for an edge or wing, and +1 for a center. That's why the center counts go up and down (down when more edges are found as a result of the sacrifice).

Furthermore, you'll notice the longest sequence never exceeded 9 moves. It's still building all of those algs but it had enough computed for me to test it out. And that was a "1-pass" attempt. Since there's only ~41,000 tredges algs so far, I could search every possible instance paired up, the square of that number, in about 3 seconds. That will definitely give the highest count of solved edges possible in 2 turns, which can be greater than the 1-pass approach applied twice.

Solving corners first, tredges next, and centers last will cut down the movecount drastically. A caged cube can only be solved by moves that create cages, applied in reverse. By applying all of the cage algs to a solved cube, saving the solutions, hashing them, and then applying all of the cage algs to the unsolved cage while probing the hash table of the cages in RAM, the program will have a solving radius == to twice the deepest cage alg. I don't do this as of yet. When the program is finalized, it will have a 20-move horizon that can be probed in the time required to complete a search of only 10 moves.

Solving centers-first in 51 moves (quick example)

https://alg.cubing.net/?setup=B_D2_...2_//_centers_solved_in_51_moves&view=playback

 

[ch_ts]

@unsolved: You're using the term "reduction" differently from everybody else in this forum. People use it to mean reducing a puzzle to a smaller puzzle (an easier puzzle than the original puzzle). Generally, large nxnxn cubes are reduced to 3x3x3, and then we can use 3x3x3 methods to finish it off. They could be reduced to puzzles other than 3x3x3 but it is generally more difficult. For example, a 4x4x4 cube can be reduced to other puzzles like 2x2x2 (or 3x3x4 or 3x3x2) and that could be called reduction. But what is usually done is people reduce it to 3x3x3 by solving the centers and pairing up the edges. This is what people here are calling reduction. The cube in my avatar is considered "reduced" because at this point it can be solved like a regular 3x3x3 cube (for simplicity, let's say we don't have orientation or permutation parities) using regular 3x3x3 moves (no inner layer turns) and regular 3x3x3 methods. Note that the dedges do not have to be solved into their places for it to be considered reduced. Now at this point, we know that it is at most 20 moves away from solved.

Add: Similarly for 5x5x5, the tredges do not have to be solved into their correct places. Then at that point, you'd be at most 20 moves away from solving the entire cube (tredges and corners). If using Kociemba's 2-phase algorithm, most likely under 25 moves would suffice.

 

[qqwref]

]The whole point of the computer solve was to show that trying to solve edges into their correct spots + centers simultaneously, perhaps the least efficient way to execute a solve, still produces a very high count of initially solved pieces after a very shallow move sequence was applied. This is the exact opposite of what Gottlieb predicted.

If you think this is the opposite of what I predicted, then either you misinterpreted my post or I explained my idea poorly, because I predicted nothing like this at all.

 

[Christopher Mowla]

@unsolved,

How many moves would your solver take to complete this state? I basically used Bruce's 4x4x4 solver to solve the X centers, wing edges, and corners simultaneously of your example almost-complete solution. (I used the same generating sequence.)

Also, I did a reduction solve (this is what we mean by reduction), but didn't get a very good solution. (147 moves total with 3x3x3 solver assistance for the last part of the solution.)

B 3L F' 2D' U' 2B2 L' 2B' 2U' //first center
F2 2R F 2L2 B 2U' B2 R' 2U' F B 2U2 2F' R' 2F D' U' B' 2R F D2 2L2 2F D 2F' U' 2B' R 2B D2 3B F 2U F2 2U' 3F //2nd center
U' 2B U 2B' //3rd center
2R2 U 2R2 U 2R2 U' 2R2 //4th center
2L L' U 2L' L' U 2R B2 2R' //last 2 centers
R F L D 2B' D' U2 B U' L U F R' F' 2R' F2 D F2 D' F L2 F' R' D' R D 2R L' F B D' R2 B' R' D R D' R 2F' //pair wings
U' F' 3U B' U B 3D L 3U F U2 F' 3D B D' B' 3D2 F2 3D2 L' 3D2 R D' R' 3D2 // pair tredges
D R2 F2 D2 R U B U' F D' F2 L F' U2 R' U' F U2 x' y //3x3x3

 

[unsolved]

@unsolved,

How many moves would your solver take to complete...

That depends. I can have it do a quick solve with respect to time (greater number of moves) or a long solve with respect to time, and get the fewest moves possible. I just set it up now on the long solve/lowest move count mode.

Quick Solve Mode (41 moves, but pretty fast)

https://alg.cubing.net/?puzzle=5x5x...2_2L_D-_B_3R2&title=no it ain't&view=playback

Error in new rotation code could not load other algs for center solves. Debugging that now.

Deep Solve Mode (22 moves, but 9+ hours of compute time)
D2 3R D 3R D B' 3R2 B2 3U' R 3U' R' 3U2 B' 3U' R' D R 3U R' D' R completes the cage.

https://alg.cubing.net/?puzzle=5x5x...s_solved&view=playback&title=5x5x5 Deep Solve

The rest would be uninteresting but I can have it solve it completely if you want.

 

[Christopher Mowla]

The rest would be uninteresting but I can have it solve it completely if you want.

Look at the total move count: 79 moves. The cube's state is very close to what your cube state was at 132 moves (but probably in a "much better shape" than the cube you showed at 132 moves). I was just curious to see if this could give you any ideas, but clearly it's fewer moves than your solver's current approach. (It took less than a second for Bruce's program to spit out that solution on my ordinary laptop.)

 

[unsolved]

I was just curious to see if this could give you any ideas, but clearly it's fewer moves than your solver's current approach. (It took less than a second for Bruce's program to spit out that solution on my ordinary laptop.)

1. The 132-move example was a COUNTER-solve. That is, it is the OPPOSITE of the way my solver solves things. I do not try to solve tredges + centers first. I wanted to show Gottlieb that even the worst STRATEGIC solving method could TACTICALLY still produce extremely efficient counts of "centers being solved" using very few moves. There were 29 centers solved with just 7-9 moves, I forget the exact count. He was claiming that my approach wouldn't amount to much.

2. The 5x5x5 has 234,212,260,435,431,232,696,695 nodes to search through depth 14. I completed that search in 9 hours 33 minutes. That works out to 6,822,378,690,225,203,399 per second. The final 8 moves of the 22 shown were found in under one second.

3. Since you asked for the most expedient solve, including centers, I did a search. If this was done via pre-computed algs without concern for trying to maximize centers along the way, it could have taken a fraction of a second as well.

EDIT: I recomputed the centers algorithm code. I noticed some algs were "missing" after reviewing some of the solves. My pruning mechanism was "off by 1," overpruning some entries by forgetting to take into account the depth remaining is 1-based and not 0-based. Also added a new pruning mechanism that halts move generation whenever a cage is created and more moves remain in the search. Since the only way to create a unique cage at depth "d" requires it to be completed on the last move, creating a cage after "d - n" moves can only complete a cage by making back-to-back cage sequences that have already been computed. There is no point in accumulating such "algs" as they can be created in cascade. While this slows down the search rate, the pruning effect is tremendous. Depth 9 would take 4 days previously, and now depth 10 is completed after 1 day. (Note: This includes time to write the algs to disk, which is very slow compared to RAM operations, with the net effect of making the process somewhat slow).

EDIT: Update April 12, 2016 with new numbers in bold:

Depth	Cumulative Node Count	Only Centers Unsolved	Only Tredges Unsolved	Only Corners Unsolved
0	1	0	0	0
1	46	0	0	0
2	1,666	0	0	0
3	59,086	0	0	0
4	2,095,696	432	30	0
5	74,331,496	1,296	84	0
6	2,636,431,696	39,192	628	0
7	93,510,461,296	255,072	2,452	0
8	3,316,682,338,696	4,688,250	32,715	528
9	4,172,450,898,004,696	48,049,962	165,602	(no data yet)
10	147,990,866,406,820,696	770,510,826	1,722,997	(no data yet)
11	5,249,024,392,428,376,696	(no data yet)	12,247,590	(no data yet)

Each of the sequences that produces unsolved centers or unsolved tredges is being saved as an "alg." When applied in reverse, it restores the cube. It looks like I'll have the ability to store every tredge alg through depth 12. Some of the ones at depth 11 are a bit unusual. For example:

3R2 3F 2R2 2L2 D 2R2 2L2 3F2 D' 3F 3R2

And this one at depth 12:

R L 2U2 3U R' D2 R 2U2 3U' L' F2 R'

But you can see the power of having every such alg possible pre-computed and ready for testing. Instead of spawning nodes that do nothing to get towards the solve, I'll have about 120 million algs that effect tredges without disturbing the rest of the cube. I'll still need to manually encode a few algs for last layer stuff.

EDIT: Even more surprising is the number of centers that can be jostled around with just one alg. At depth 11, here is a case where 26 of the 48 unfixed centers are in motion:

2R 3U' 2F' 2R' 3U2 2L 3U 2F 3U 2L' 3U

While a very over-specific case, it is still obvious that even an inexact match of algs like this will have the capability to get a nice chunk of centers solved in one fell swoop. At present count, I have 1.2 billion center algs, not yet 10% of the way through depth 11. I am very curious to see how this will effect the final move count.