# 4x4x4 FMC (computer and human) round 2



## ch_ts (Apr 15, 2015)

*Welcome to 4x4x4 FMC round 2!*

Time: May 15 to June 30 2015
April 15 to May 15: Prep time. I thought people might want to tune their solvers using a scramble that will actually count. (see scramble 1 below)

*Scoring:* 

Notation for solutions: SiGN
Please use only the subset of moves that turn a single slice. If your solutions requires moves like Rw or M, please write it using single slices. You may also use rotations x, y, and z. _Single slice turn metric_ will be used for this contest. Any single slice turned any amount will count as 1 move. Rotations count as 0 moves.

Your score will be the sum of your middle three solutions (after dropping the best and worst). In the case of ties, I will consider all 5 solutions, and then I will go by time submitted (earlier is better). You do not need to attempt all 5 scrambles, however, for those you do not attempt, I will score them as 1000 for scoring purposes.

*Rules:*

You may not use the inverse of the scramble or the inverse of part of the scramble in your solution. You must use the scramble in its entirety; you may not break up the scramble into smaller parts to make use of "mini-scrambles".

Computer FMC: no restrictions, no time limits. You may use code, ideas, programs that you are not the author of. Anything and everything is allowed.
Human FMC: No time limits. Virtual cubes/simulators such as alg.cubing.net are allowed, provided they do not have any solving capabilities. Insertion finder (or similar) is not allowed.

Judge's decisions are final. I may change the rules at any time, I may end the contest early. By participating, you agree to abide by the above rules.

*Submitting your solutions: *
Please submit all your computer solutions together and all your human solutions together. After you have submitted your solutions, you may continue to revise your solutions. However, please resubmit your other solutions also, and I will ignore your previous entry. If you only revise your human solutions, you do not need to resubmit your computer solutions, and vice versa. (Links are below)

*Prizes*
Two divisions: computer and human. One prize will be awarded to the winner in the computer division, one prize will be awarded to the winner in the human division.
U.S. winner: 3x3x3 speedcube of your choice (up to $19) or $15 Amazon gift card
International winner: $15 Amazon gift card

*Computer Scrambles: *
1. R2 F2 Rw' R D' Uw' L B' L' Rw2 R2 F Uw2 Fw F2 Rw2 B D B2 Rw' F2 Uw2 B' Rw R U Fw' Rw' U' Rw' B' D F2 U Fw' R2 B L2 Uw L2 U D R U2 Uw2
2. B' Fw' L' D F B2 Uw2 D2 R2 L Fw2 F R' Uw' Fw2 B2 Uw Rw2 F L R D U Rw B Fw' R2 Rw2 L' D' B D' F' L2 Uw2 Rw F2 Rw2 F Fw2 U F' Rw' R U
3. Rw F' Rw2 L' Fw2 F2 B2 U' R' L Uw B' R' Rw2 B Fw L2 Rw' Uw2 B' L B2 Fw2 Rw' U Fw Rw2 B R' Uw2 R' B Uw2 B2 Fw2 F2 D' R' B2 U Rw F' R2 Rw2 L
4. B R F' D U' R' B2 D2 B' R B' D2 F' B L2 F' D2 F' U2 R2 Uw2 Rw2 L' B U2 L' B2 Uw2 B' R' D2 B2 Uw Rw2 R2 D2 B2 U' Fw' Rw' B' F2 Uw U' R B2 U' R F2 U
5. F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U Fw2 D Rw2 R Fw2 R Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2
Submit here

*Human Scrambles: *
1. R2 F2 Rw' R D' Uw' L B' L' Rw2 R2 F Uw2 Fw F2 Rw2 B D B2 Rw' F2 Uw2 B' Rw R U Fw' Rw' U' Rw' B' D F2 U Fw' R2 B L2 Uw L2 U D R U2 Uw2
2. B2 R Uw Rw2 Uw' Rw' R' Fw U2 Fw2 B U2 Uw B' F L' D' F2 Uw' B Uw2 F' Uw2 U F' D Uw Fw2 B U' F' Uw L' Uw2 U' Fw' F' B' U2 F' Fw L U' B2 Fw2
3. U2 D2 F' D F' Uw2 F L' Rw' U2 F' L Uw2 L' R' Rw' D Uw2 L Uw U' R' Uw2 D B D' L' Rw' Fw' Uw' Rw F' Fw2 Rw2 B2 Rw' U' B' R' Fw Rw F' B U' Uw
4. L' F' U' L2 U' B L D' R' B' R2 L2 D2 F L2 F' L2 U2 R2 F2 Rw2 B' Uw2 F R Fw2 L' Uw2 Rw2 U2 Fw2 F Uw' R2 D B' R' L D2 Fw L2 Fw' Rw' Uw' Rw' R' F R' B2 R2
5. U2 B2 R' U2 R2 B2 U2 F2 R D L' D2 F U2 L' B2 D R' B R2 Fw2 D F2 Rw2 L2 Uw2 D' L' D' L B2 Uw2 R' Fw R2 B' Rw2 U' B' Rw' B Uw' Fw2 B2 L D2 B' U B U D2
Submit here


----------



## cuBerBruce (Apr 16, 2015)

in my opinion, working on a human solution should not be allowed if the person has previously done any computer searches related to the same scramble. I would strongly recommend *not* using the same scrambles for both computer and human competitions for this reason.


----------



## unsolved (Apr 16, 2015)

ch_ts said:


> *Welcome to 4x4x4 FMC round 2!*
> Notation for solutions: SiGN



Just wondering why the scramble is not given in the same notation as the solution requirement.



ch_ts said:


> . In the case of ties, I will consider all 5 solutions, and then I will go by time submitted (earlier is better).



Well yesterday I ordered the hardware for the contest I thought was starting in June, not having seen this announcement. Once it arrives, I have to build the system, test it with the parallel code I am still writing for the 4x4x4, etc. Plus I am also running several 5x5x5 scrambles on my existing hardware for *cmowla*, *Roman*, and *Stefan*, of which you might be presently aware. Just to let everyone know, I will participate, but no doubt be off to a slow start.


----------



## ch_ts (Apr 16, 2015)

cuBerBruce said:


> in my opinion, working on a human solution should not be allowed if the person has previously done any computer searches related to the same scramble. I would strongly recommend *not* using the same scrambles for both computer and human competitions for this reason.



OK, that seems like a good idea. We'll have different scrambles for computers and humans for scramble 2 through 5. I don't want to change the first scramble if people have already started on it.



unsolved said:


> Just wondering why the scramble is not given in the same notation as the solution requirement.
> 
> 
> 
> Well yesterday I ordered the hardware for the contest I thought was starting in June, not having seen this announcement. Once it arrives, I have to build the system, test it with the parallel code I am still writing for the 4x4x4, etc. Plus I am also running several 5x5x5 scrambles on my existing hardware for *cmowla*, *Roman*, and *Stefan*, of which you might be presently aware. Just to let everyone know, I will participate, but no doubt be off to a slow start.



The scramble is the old WCA style scramble but I made a little longer (45 moves OBTM instead of 40). If you're not familiar with WCA scrambles: Uw=u, Rw=r, etc. Most people here are familiar with it. It's a simple extension of SiGN, it's not like a different set of moves like T for top, B for bottom, O for opposite-front. Why did WCA use Rw instead of r? Who knows? That's a discussion for another time. Anyway it shouldn't be too much trouble to scan through it and replace it with moves suitable for your solver.

I'll extend the contest to the end of June.


----------



## Lucas Garron (Apr 16, 2015)

ch_ts said:


> Why did WCA use Rw instead of r? Who knows? That's a discussion for another time.



Probably because Ron thought it was more readable. We kept it because of momentum and clarity.
(Think of a competitor using both "u" and "U" in FMC.)


----------



## cuBerBruce (Apr 16, 2015)

Lucas Garron said:


> Probably because Ron thought it was more readable. We kept it because of momentum and clarity.
> (Think of a competitor using both "u" and "U" in FMC.)



well, I'm pretty sure that the reason had to do with the fact that Singmaster had proposed the lower case letters be used for (single) inner moves on the 4x4x4 back in 1982, and that convention for 4x4x4 was *still in widespread use at the time*. For example, the popular site bigcubes.com used (and actually still uses) the Singmaster-based notation. I assume the use of lower case letters for wide turns on the 3x3x3 was started much later (than 1982). The "w" notation apparently eventually had become widespread in the Asian community and thus seemed to provide an unambiguous notation for the WCA to use, rather using a notation that people might be confused about what it meant.


----------



## ch_ts (May 1, 2015)

Just posted another scramble. Make sure you're using the correct scrambles, as we'll be using different scrambles for the computer and human contests following cuBerBruce's suggestion. Just another half month before we're officially under way!


----------



## unsolved (May 12, 2015)

ch_ts said:


> Just posted another scramble. Make sure you're using the correct scrambles, as we'll be using different scrambles for the computer and human contests following cuBerBruce's suggestion. Just another half month before we're officially under way!



I have almost debugged an awesome new pruning mechanism that treats forward move generation the same way my TFS databases treats the back-end of the search 

All edges + centers pruning tables have been solved through 6 turns, and corners through 8 turns. I have enough RAM for this + TFS_05. Still needs some implementation debugging.

Look at these speeds...



Spoiler: Image














ch_ts said:


> *Computer Scrambles: *
> 1. R2 F2 Rw' R D' Uw' L B' L' Rw2 R2 F Uw2 Fw F2 Rw2 B D B2 Rw' F2 Uw2 B' Rw R U Fw' Rw' U' Rw' B' D F2 U Fw' R2 B L2 Uw L2 U D R U2 Uw2



So that would be this position, correct?

https://alg.cubing.net/?puzzle=4x4x..._Rw-_B-_D_F2_U_Fw-_R2_B_L2_Uw_L2_U_D_R_U2_Uw2


----------



## qq280833822 (May 13, 2015)

unsolved said:


> So that would be this position, correct?
> 
> https://alg.cubing.net/?puzzle=4x4x..._Rw-_B-_D_F2_U_Fw-_R2_B_L2_Uw_L2_U_D_R_U2_Uw2



Correct. And a solution in SiGN is https://alg.cubing.net/?puzzle=4x4x...R2_F_2F-_2U2_U2_F-_2R2_L_B_L-_2U_U_D_2R_F2_R2 for example. (It's the inverse of the scramble, which is not allowed in this contest)


----------



## ch_ts (May 15, 2015)

OK, I've posted the scrambles and we have officially started. Good luck and happy cubing!


----------



## rokicki (May 15, 2015)

*Woo hoo!*



ch_ts said:


> OK, I've posted the scrambles and we have officially started. Good luck and happy cubing!



Wow! Good luck all!

Is there any automatic validation of our solutions, or are you doing that manually?

It might be nice to know if the solutions worked or if we made a silly error.


----------



## unsolved (May 15, 2015)

rokicki said:


> Wow! Good luck all!
> 
> Is there any automatic validation of our solutions, or are you doing that manually?
> 
> It might be nice to know if the solutions worked or if we made a silly error.



Well you can copy/paste the scrambles and your solutions here to test:

https://alg.cubing.net/?puzzle=4x4x..._Rw-_B-_D_F2_U_Fw-_R2_B_L2_Uw_L2_U_D_R_U2_Uw2


----------



## ch_ts (May 15, 2015)

Yes, I'll be doing that manually by pasting them into alg.cubing.net. I never got around to writing a script to handle the entries.  Anyway, I don't expect there to be so many entries that I'll be overwhelmed by them (judging by the number of entries in last year's contest)


----------



## unsolved (May 15, 2015)

Maybe the programmers can announce their presence, the names of their programs, and any details about their solvers that won't jeapordize their secret sauce 

Program Name = *Omnia Obtorquebantur 4x4x4 version 3.0.8*

Running on: *Intel i7-3960X @ 4.7 GHz* with 32 GB RAM.

Features:


Forward Pruning Table #1 = Corners + Edges to depth 5
Forward Pruning Table #2 = Centers to depth 6
Back-End Pruning Table #3 = Entire Cube to depth 5
Fast 64-bit, Facelet-Level Move Generator, only 6 lines of C-code executed to generate any move

Pros:


Deep pruning capabilities
Generates only theoretical minimum tree size at each depth (before pruning taken into account)
2D graphical representation of the scramble
Can solve in-line rotations along with the scramble
Text output file lists every solution found
New stage solving mode (though highly experimental)

Cons:


Still needs 24 different rotated versions of all pruning data, bogging down memory
Spends most of its time exploring 0 nodes, iterating in for-loops in search of theoretical minimal move point of entrance to solution(s).
Does not yet fully support SiGN in move parsing and solution output (but 5x5x5 version does)


----------



## qq280833822 (May 15, 2015)

Program Name = Two Phase Reduction Solver + min2phase with huge table (instead of cube explorer).

Running on: Intel core i7-2670QM @2.2 GHz with 8 GB RAM.

All 5 scrambles have been solved no more than 45 moves, wherein the reduction parts of these scrambles are no more than 27 moves. (all in SSTM)

==========update==========
Huge table is equivalent to the 1.8G table used in cube explorer to accelerate the search of 3x3x3.


----------



## StachuK1992 (May 15, 2015)

The reduction parts were no more than 27moves, having an upper limit of 27 + 20 = 47 moves total (plus some for parities?).
That said it seems the ones with 27moves had 18 move 3x3 solutions


----------



## unsolved (May 16, 2015)

StachuK1992 said:


> The reduction parts were no more than 27moves, having an upper limit of 27 + 20 = 47 moves total (plus some for parities?).
> That said it seems the ones with 27moves had 18 move 3x3 solutions



I have to disqualify my 36-move result after chatting with one of the other participants. I have an algorithm that makes use of subsets of the scramble. I started working on it long before the contest when I was making my own stage solver, and I discovered an interesting way to find near-optimal or optimal solutions to just about any scramble. It's very CPU-intensive and massively parallel. So, until I come up with a new stage solving algorithm, I must remove myself.


----------



## qq280833822 (May 16, 2015)

unsolved said:


> I have to disqualify my 36-move result after chatting with one of the other participants. I have an algorithm that makes use of subsets of the scramble. I started working on it long before the contest when I was making my own stage solver, and I discovered an interesting way to find near-optimal or optimal solutions to just about any scramble. It's very CPU-intensive and massively parallel. So, until I come up with a new stage solving algorithm, I must remove myself.



You mean you have solved one of these scrambles in 36 moves, or just finished the reduction part in 36 moves?


----------



## Herbert Kociemba (May 16, 2015)

unsolved said:


> I have to disqualify my 36-move result after chatting with one of the other participants. I have an algorithm that makes use of subsets of the scramble. I started working on it long before the contest when I was making my own stage solver, and I discovered an interesting way to find near-optimal or optimal solutions to just about any scramble. It's very CPU-intensive and massively parallel. So, until I come up with a new stage solving algorithm, I must remove myself.



I do not think you have to come with a new stage algorithm. If you really have found an algorithm which finds near-optimal or optimal(!!!) solutions to just about any scramble this would be a phantastic piece of work and of course these solutions would be accepted by all other participants. SUBMIT THESE SOLUTIONS! If not I suppose these solutions are so phantastic that they only exist in your fantasies and you have a creative handling of truth.


----------



## qqwref (May 16, 2015)

unsolved said:


> My algorithm was nothing more than a fancy line-crawl @ fixed depth, solving subsets of the scramble, and rearranging the solution at the end. It reduced the solution length from 52 moves in my program's metric to 36 moves, a savings of 16 moves. The very first line of the rules forbids this very thing. I never read it. I just processed the scrambles.


Disregarding the point that this isn't even a valid FMC technique, how are you sure this will still solve the scramble? Because of 4x4x4's sets of identical centers, it's entirely possible to have move sequences A, B, C such that B and C do the same thing to a solved cube, but A B and A C don't.



unsolved said:


> Even though I only have distances of 5- and 6- respectively, they are partially additive in nature (depending on the position) and there is no more effective way to forward prune, I guarantee it.


What does "partially additive" even mean? And the last part of this is rather silly.



unsolved said:


> I don't use an *indexing function*, I use a *hash table*, which more than one of the posters on here treated with derision.


Probably because you act like it's some kind of impressive and extremely clever technique, rather than one of the fundamental data structures that even a beginning programmer ought to be familiar with.


----------



## qq280833822 (May 16, 2015)

unsolved said:


> My algorithm was nothing more than a fancy line-crawl @ fixed depth, solving subsets of the scramble, and rearranging the solution at the end. It reduced the solution length from 52 moves in my program's metric to 36 moves, a savings of 16 moves. The very first line of the rules forbids this very thing. I never read it. I just processed the scrambles.



For example, if the scramble is "A B C", then you try to find a move sequence "B*" which is equivalent to B but shorter than B, and the sequence "C^-1 B*^-1 A^-1" is a valid solution of course. And for a given scramble, you tried different split of A B C, find optimal B*, and the solution is shortened to only 36 moves?

If the algorithm is like that, then I have a question. When finding B*, you should check the equivalence between B* and B on a 4x4x4 super cube. Otherwise, although B* is equivalent to B on a solved 4x4x4 cube, A B C might not be equivalent to A B* C. Hence, have you checked the correctness of your solutions?

If your solution is absolutely correct, do not worry about the regulation as finding a valid 4x4x4 solution is extremely easy (for example, human solution). Then you can modify your algorithm as:
1. find a valid solution (although the solution is very long, e.g. 100 moves)
2. use your algorithm to reduce the length of solution to ~36 moves.


----------



## unsolved (May 16, 2015)

qq280833822 said:


> For example, if the scramble is "A B C", then you try to find a move sequence "B*" which is equivalent to B but shorter than B, and the sequence "C^-1 B*^-1 A^-1" is a valid solution of course. And for a given scramble, you tried different split of A B C, find optimal B*, and the solution is shortened to only 36 moves?
> 
> If the algorithm is like that, then I have a question. When finding B*, you should check the equivalence between B* and B on a 4x4x4 super cube. Otherwise, although B* is equivalent to B on a solved 4x4x4 cube, A B C might not be equivalent to A B* C. Hence, have you checked the correctness of your solutions?



It is much less complicated than that. And, once you see how simple it is, you will laugh.

Here is the starting position:



Spoiler: Image












Nothing fancy. The program is just making its way to a fixed depth of 13 plies. Notice only 24 nodes were explored through depth 12, and only 352 shown so far @ depth 13. When it doesn't find a solution, it chops one move off from the *beginning*, not the *end*. This way, I don't have to worry about doing too much work to splice together a working solution at the end.



Spoiler: Image











The above image should make this more clear. I just crawl down the line until I encounter the deepest position that can be solved in 13 moves. At that point, I can stop, and only search the rest of the unsolved space, from move 1-N where N might be 19 moves out. So a 19-move solution was found in 13 moves (for example, call that solution A) and you just sliced 6 moves off of the solve length. This process is repeated:

Moves 1-43, 2-43, 3-43, 4-43.... until another solution is found, call that solution B.

That way, I have moves 1-x still unsolved, then solution B, then solution A. 

Now I work on moves 1-x, 2-x, 3-x, 4-x, etc. finding solution C.

I keep going until my last solution reaches back to depth 1.

If I find no solution A after going all the way down the tree, then another set of code kicks in.


----------



## bobthegiraffemonkey (May 16, 2015)

unsolved said:


> I have to disqualify my 36-move result after chatting with one of the other participants. I have an algorithm that makes use of subsets of the scramble. I started working on it long before the contest when I was making my own stage solver, and I discovered an interesting way to find near-optimal or optimal solutions to just about any scramble. It's very CPU-intensive and massively parallel. So, until I come up with a new stage solving algorithm, I must remove myself.



I skimmed over your posts since this one. Unless I'm misunderstanding (I might be), the issue is with applying the technique to the scramble which is provided. Then, isn't it possible to fix the problem by first generating a different scramble for the same position to start with, then applying the technique to that?


----------



## qq280833822 (May 16, 2015)

unsolved said:


> The above image should make this more clear. I just crawl down the line until I encounter the deepest position that can be solved in 13 moves. At that point, I can stop, and only search the rest of the unsolved space, from move 1-N where N might be 19 moves out. So a 19-move solution was found in 13 moves (for example, call that solution A) and you just sliced 6 moves off of the solve length. This process is repeated:
> 
> Moves 1-43, 2-43, 3-43, 4-43.... until another solution is found, call that solution B.
> 
> ...



The problem mentioned by qqwref and me is still unsolved. 
For example, the scramble is X Y, where Y is a 19-move sequence. In this case, although you find a 13-move solution A such that "Y A" == solved, how can you guarantee "X Y A" == "X"?

Unless the search is on a 4x4x4 super cube.


----------



## unsolved (May 16, 2015)

bobthegiraffemonkey said:


> I skimmed over your posts since this one. Unless I'm misunderstanding (I might be), the issue is with applying the technique to the scramble which is provided. Then, isn't it possible to fix the problem by first generating a different scramble for the same position to start with, then applying the technique to that?



The rules state:



ch_ts said:


> *Welcome to 4x4x4 FMC round 2!*
> 
> *Rules:*
> 
> You may not use the inverse of the scramble or the inverse of part of the scramble in your solution. You must use the scramble in its entirety; you may not break up the scramble into smaller parts to make use of "mini-scrambles".



And, you can see, I did just that.

I had been working on this technique for a while now, testing it, about 6 weeks before the rules were even posted. It was just pointed out to me that I completely violated this rule. You can see why it is a rule though. With enough time and enough computer horsepower, you can practically optimally-solve just about any scramble.



qq280833822 said:


> Unless the search is on a 4x4x4 super cube.



I've seen this term before but never an explanation of it. I can say this: My center pruning table treats each center as being unique, even though there are 4 that appear to be the same. And my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved. So as long as they end up where they started, the solution is applied. Otherwise, you can't join the segments together.


----------



## Ranzha (May 16, 2015)

unsolved said:


> The rules state:
> And, you can see, I did just that.


You misinterpreted.

bobthegiraffemonkey was suggesting you manually find a solution (call it A), invert that to get an equivalent scramble to the originally posted scramble (A'), and plug in your result (A') into your program to start solving. This would not break the rule you mentioned.




> I've seen this term before but never an explanation of it. I can say this: My center pruning table treats each center as being unique, even though there are 4 that appear to be the same. And my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved. So as long as they end up where they started, the solution is applied. Otherwise, you can't join the segments together.



A 4x4 supercube looks like this. It uniquely identifies centres of the same colour, just like what your program is doing. You're good :tu


----------



## unsolved (May 16, 2015)

Ranzha said:


> bobthegiraffemonkey was suggesting you manually find a solution (call it A), invert that to get an equivalent scramble to the originally posted scramble (A'), and plug in your result (A') into your program to start solving. This would not break the rule you mentioned.



I think it is pretty much undermining the intent of the rule, lol. The rule makes sense though. The technique I mentioned can get you pretty close to an optimal solve almost every time. I thought this would be of interest to the group since I don't think anyone has skimmed the surface of what God's Number might be for the 4x4x4 yet (in terms of solution lengths found solely by computation). As the title of this was the "Fewest Moves Challenge" I thought any reasonable technique at solution length reduction, other than just reversing the scramble, would be permitted. But, this is really a "Shortest Stage Solve Challenge," which can only have solutions that approach the limits of known stage solving techniques, as long as the scrambles are out of range of brute force solvers.






Ranzha said:


> A 4x4 supercube looks like this. It uniquely identifies centres of the same colour, just like what your program is doing.



Thanks. Yeah I figured this out a while back


----------



## Ranzha (May 16, 2015)

unsolved said:


> I think it is pretty much undermining the intent of the rule, lol.



No, it doesn't. The intent of the rule is to disallow manipulation of the original scramble for obvious reasons. If you're manipulating a scramble that you generated without help from the original scramble, any solution from there is fair game.

That's how FMC works.


----------



## qq280833822 (May 16, 2015)

unsolved said:


> The technique I mentioned can get you pretty close to an optimal solve almost every time.



Awesome work. Have you tried longer scrambles? e.g. more than 60 or 80 moves. And see whether your solver can still return a near-36-move solution?

BTW, according to my knowledge, the algorithm you described only works if the number of canonical move sequences is much larger than the number of state at maximum search depth (e.g. 13). I'm not sure whether 4x4x4 is such puzzle in SSTM. But in OBTM, at depth 8, the number of state (44246249410) is almost equals to the number of canonical move sequences (44969120244)


----------



## unsolved (May 16, 2015)

qq280833822 said:


> Awesome work. Have you tried longer scrambles? e.g. more than 60 or 80 moves. And see whether your solver can still return a near-36-move solution?



No, this is only fully tweaked and perfected as of a few days ago. I got too distracted by messing around with my 5x5x5 program, which, oddly enough, is what led to the massive pruning discovery. I was shocked the first time I compiled the wing-edges table for the 5x5x5 and saw this:



Spoiler











I made the wing-edges table for the test position above for the (obvious) reason that corners would not be worth anything in a position like that (well, it could help the program by keeping it from "drifting" too far from a solution once the move gen length was at least one move more than half the solution length). Then I thought if I combined corners and wings, the result would probably be the same, but at least I would have corner data to use in other positions. Then I thought adding a separate "middle edge" table would be a waste of sorts, since it would require multiple probes. And I didn't finish that thought before it finally dawned on me that a ringed cube for the 5x5x5 = wings + middle edges + corners, and with one probe, you can effectively get the equivalent of three separate pruning distances.

It wasn't too much later that the thought of "ring + center" would be like bullet-proofing the forward pruning altogether, *making the ultimate mechanism* for the task.



qq280833822 said:


> BTW, according to my knowledge, the algorithm you described only works if the number of canonical move sequences is much larger than the number of state at maximum search depth (e.g. 13). I'm not sure whether 4x4x4 is such puzzle in SSTM. But in OBTM, at depth 8, the number of state (44246249410) is almost equals to the number of canonical move sequences (44969120244)



I didn't think of it in terms of that; I just let the brute force and computer science aspect do the work. Trial and error, trial and error, sometimes it takes a few failures to finally hit on the correct idea.

Here are some of my single turn counts for the 4x4x4:


DepthNodesCumulative8413,919,090,792429,650,631,855911,304,715,303,58411,734,365,935,43910308,747,751,874,992320,482,117,810,431118,432,337,451,411,8728,752,819,569,222,30312230,299,053,086,277,216239,051,872,655,499,519136,289,792,617,720,221,5686,528,844,490,375,721,08714171,783,125,652,467,209,536178,311,970,142,842,930,623154,691,639,939,891,068,296,5764,869,951,910,033,911,227,19916128,135,317,377,520,330,634,880133,005,269,287,554,241,862,079


----------



## Herbert Kociemba (May 16, 2015)

How many moves has your optimal or near to optimal solution for (U R F D L B 2U 2R 2F 2D 2L 2B)^6 ? 
Can you give the output of your program for this example? This would convince me more than the node counts for some shallow searches for depth <=16.


----------



## unsolved (May 16, 2015)

You mean U R F D L B 2U 2R 2F 2D 2L 2B U R F D L B 2U 2R 2F 2D 2L 2B U R F D L B 2U 2R 2F 2D 2L 2B ... for a total of 6 times?


----------



## Herbert Kociemba (May 16, 2015)

yes


----------



## ch_ts (May 16, 2015)

So, the case in my mind that I had when I wrote that rule was:

Take scramble 5 as an example:
F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U Fw2 D Rw2 R Fw2 R Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2

I don't want people to do:
A = F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U
B = Fw2 D Rw2 R Fw2 R Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2
Solve B, solve A, and put the solutions together. 

I want people to set up the cube using the scramble as I have given it in its entirety, and then solve that position not using the scramble anymore.

unsolved, if I added the rule: "Your solution may not intentionally visit any position that is visited by the scramble" how would you adapt to that? And I'm curious, what happens if you do what bobthegiraffemonkey suggested? (find your own solution, use the inverse as the scramble, apply your technique) Can you still find short solutions given a longer scramble (say 100 moves)? Have you tried?


----------



## rokicki (May 17, 2015)

qq280833822 said:


> Awesome work. And see whether your solver can still return a near-36-move solution?



Unsolved, if you have a 36-move solution by *any* means, that is impressive.

If you have a 36-move solution by the technique you described, that is very
surprising. Is it possible you have erred and your 36 moves do not actually
solve the position? If not, then there is something about the scramble or the
4x4x4 that I have not yet understood.

Ch_ts, are you willing to share how you generated the scrambles? Is it just
random moves, and if so, did you exclude certain adjacent move pairs or
some such?

It may be the case that for nxnxn cubes, as n increases, the state space
approaches some degree of predictability (that is, some correlation between
a structural property and the position depth) but I'm surprised if this is
happening already for the 4x4x4.


----------



## qq280833822 (May 17, 2015)

rokicki said:


> Ch_ts, are you willing to share how you generated the scrambles? Is it just
> random moves, and if so, did you exclude certain adjacent move pairs or
> some such?



I guess the first 3 scrambles are random-move scrambles, while the last 2 scrambles are generated by another solver (maybe the WCA scrambler, or a solver written by Ch_ts himself). I wonder whether the algorithm mentioned by unsolved also works well on the last 2 scrambles. If does, for a specific state, we can calculate another near-50-move generator by another solver (e.g. the WCA scrambler), and then use unsolved's algorithm to further improve the solution to near optimal.


----------



## Herbert Kociemba (May 17, 2015)

Thanks, I took a look again after 8 hours you ran your program with my proposed scramble but I cannot interpret from the output if you were able to shorten it.


----------



## unsolved (May 17, 2015)

Herbert Kociemba said:


> Thanks, I took a look again after 8 hours you ran your program with my proposed scramble but I cannot interpret from the output if you were able to shorten it.



Two things happened last night here in the Philadelphia suburbs. We had a small lightning storm, so I took a precaution and shut down while it passed. Of course, as soon as I did the shut down, I got notice that "179 Windows Updates" were being applied, and the "Do not turn off your computer" message had me praying we would not lose power. While I waited, I recompiled the code to "automatically" enter your long scramble on startup with no human intervention. But somehow it engaged the algorithm only to depth 12, which was not deep enough to find any improvement to a scramble consisting of 12-perpendicular moves repeated over and over.

But at least you could see the automation of the algorithm and how it crawls over a line looking for the maximum possible reduction. When it finds the largest one, it resumes the search for the remainder of the scramble that is still unsolved.

The program will parse over the entire scramble, one move at a time, from both the front and back end, if it does not find any improvement. Anyone who logs on now can see that this is happening. 

I also added some new text output that displays the cumulative improvements found to the line.

I'm going to relaunch in a few minutes with a deeper search mode and see what happens.



rokicki said:


> Unsolved, if you have a 36-move solution by *any* means, that is impressive.
> 
> If you have a 36-move solution by the technique you described, that is very
> surprising. Is it possible you have erred and your 36 moves do not actually
> solve the position?



Of course it is possible. When I misinterpreted Shuang Chen's solutions to be 27 moves in length, I stopped all copies of my program from running and starting looking over my source code for ways to improve it. What I should have done is pasted the solution into alg.cubing.net but I had not reconstructed it yet from the segmented output.

If there was an error, it would have to be in the supercube subset of the code. I have a new definition of "solved" that has 3 of the 4 centers using integers other than the one assigned to its cube face. They all have to be in their starting configuration in order for the chained solution to work.



rokicki said:


> If not, then there is something about the scramble or the
> 4x4x4 that I have not yet understood.



Well a picture is worth 1,000 words, as they say, so why don't you log onto my machine and take a peek at what it's doing? I'm pretty sure when you see the line crawl algorithm that it will make perfect sense.


----------



## adimare (May 17, 2015)

unsolved said:


> I've seen this term before but never an explanation of it. I can say this: My center pruning table treats each center as being unique, even though there are 4 that appear to be the same. And my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved. So as long as they end up where they started, the solution is applied. Otherwise, you can't join the segments together.


If you're going for optimal, you might have to rethink this. Take the following scramble:
(R U R' U)5 

Your program should be able to recognize that the cube is in a solved state even though 4 of the centers are not where they started. Otherwise it will miss the optimal solution (which in this case is 0 moves).


----------



## ch_ts (May 17, 2015)

Well, I gave this some thought and I've decided that unsolved may use his trimming technique if he does what bobthegiraffemonkey suggests: find a solution using some other method, invert it to use as a scramble, and use his trimming technique on that. That's definitely fair game. But not on the actual scramble itself, that just seems wrong to me. 

Anyway, my gut feeling is that it can only shorten sequences by some fraction, say 10% (which is a total guess not based on anything) and not to near optimal as unsolved has claimed. So a 50 move sequence might get shortened to 45, but a 100 move sequence might only get shortened to 90 moves. But it doesn't seem like that 100 move sequence could get shortened down to 40 moves. But that is just my gut feeling.

Sure I can share how I generated the scrambles. The first 3 scrambles are random scrambles from cstimer, with length 45. The last 2 scrambles are from worlds 2013 (so based on reduction to 3x3x3), to which I added 5 random moves to the end.


----------



## unsolved (May 17, 2015)

ch_ts said:


> Well, I gave this some thought and I've decided that unsolved may use his trimming technique if he does what bobthegiraffemonkey suggests: find a solution using some other method, invert it to use as a scramble, and use his trimming technique on that. That's definitely fair game. But not on the actual scramble itself, that just seems wrong to me.



OK, but to me, this seems like it is just a different version of the same thing the rule was designed to prevent. A subset of the original scramble is being used to generate something other than the exact scramble subset, whose use is functionally the same.



ch_ts said:


> Anyway, my gut feeling is that it can only shorten sequences by some fraction, say 10% (which is a total guess not based on anything) and not to near optimal as unsolved has claimed. So a 50 move sequence might get shortened to 45, but a 100 move sequence might only get shortened to 90 moves. But it doesn't seem like that 100 move sequence could get shortened down to 40 moves. But that is just my gut feeling.



My gut feeling is almost the exact opposite. For very lengthy scrambles, anything longer than the unknown God's Number for the 4x4x4 is not adding to the length of the solve. It may be hovering at or near the same solution length, even "accidentally" getting closer to the solved state at times, but overall it increases the chance that some fixed-depth search will solve the entire portion of the scramble being examined. It's like giving more pitches to a home run hitter; you're increasing the odds of of them will be knocked out of the ballpark.

So time to shift gears and go hunt for the giraffe.



adimare said:


> If you're going for optimal, you might have to rethink this. Take the following scramble:
> (R U R' U)5
> 
> Your program should be able to recognize that the cube is in a solved state even though 4 of the centers are not where they started. Otherwise it will miss the optimal solution (which in this case is 0 moves).



This is almost too ridiculous to even offer a comment. The first thing I generate is every non-supercube arrangement through 5 turns. Before starting any search, I probe the hashtable to see if a search is even necessary.

I can see how it is tempting to try and offer "improvements" to something you know nothing about, as you like to say so often about me before moderators delete your comments.


----------



## adimare (May 17, 2015)

unsolved said:


> This is almost too ridiculous to even offer a comment. The first thing I generate is every non-supercube arrangement through 5 turns. Before starting any search, I probe the hashtable to see if a search is even necessary.
> 
> I can see how it is tempting to try and offer "improvements" to something you know nothing about, as you like to say so often about me before moderators delete your comments.



You're right in stating that I know little about your program. Why would I? Why would I assume you look into non supercube arrangements if the information I have is you literally saying "my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved"?


----------



## qqwref (May 17, 2015)

unsolved said:


> OK, but to me, this seems like it is just a different version of the same thing the rule was designed to prevent. A subset of the original scramble is being used to generate something other than the exact scramble subset, whose use is functionally the same.


Just to clarify, since this is a pretty subtle distinction: the difference is in the knowledge you(r solver) are allowed to have. The goal is to be handled a scrambled state and solve it, without knowing the moves that got the cube to that state. When you improve the scrambling algorithm to get a solution, you are making use of knowledge of the scrambling algorithm, which is knowledge you are not supposed to have. However, when you generate a new solution and then improve it, you are not making use of knowledge of anything other than the scrambled cube you were given, so that is OK. The problem with your approach is not your method of improving a solution (which is fine), but with using the scrambling algorithm (which you should not know) as a starting point.


----------



## unsolved (May 18, 2015)

ch_ts said:


> Well, I gave this some thought and I've decided that unsolved may use his trimming technique if he does what bobthegiraffemonkey suggests: find a solution using some other method, invert it to use as a scramble, and use his trimming technique on that. That's definitely fair game. But not on the actual scramble itself, that just seems wrong to me.



Maybe for future computer contests we should be required to "parse the stickers" by either face colors or face names.

*U=BRFB/BRFF/BLRR/RFDL* would be the top side for the first scramble where B = Back, R = Right, F = Front, etc. I know we chatted about something like this before, but I forget where we left off.


----------



## ch_ts (May 19, 2015)

That's a possibility... but that would only be useful for the computer fmc, and not human fmc where a scramble is easier to apply to a cube.


----------



## unsolved (May 19, 2015)

ch_ts said:


> That's a possibility... but that would only be useful for the computer fmc, and not human fmc where a scramble is easier to apply to a cube.



Yep, that's what I implied. I wouldn't know how to even attempt such a thing as a human 



Herbert Kociemba said:


> How many moves has your optimal or near to optimal solution for (U R F D L B 2U 2R 2F 2D 2L 2B)^6 ?



So is there any supercube software out there that might be able to help me track down my supercube bug? It looks like one of the solution segments to the 36-mover from the first scramble does not recombine from the start to solve the whole cube. It is an insidious bug that does not always recreate itself after seemingly undertaking deterministic quality controls. 

This is what my supercube looks like at the start:



Spoiler












...and this is what it looks like after Herbert's 72-move scramble test.



Spoiler











If this is confirmed to be a correct representation, I can go about making sure the other 23 rotated states of the supercube code are working correctly, then relaunch the line-crawl algorithm and see what happens. Although this test took a lot of time, it will be worth it if it tracks down this bug, and the technique turns out to be useful.

*EDIT:* I think I have the quintessential supercube test position:


*2R2 F2 U2 2R2 U2 F2 U2 2R U2 2R2 U2 2R2 U2 2R U2 2R2 U2*

This is not supercube solved, but it is non-supercube solved.

There are 16 supercube solutions, one of which is:

*L' F2 D2 B2 R' L U2 B2 D2 R*

If this is correct, I think it is safe to say I can resume the hunt.


----------



## Herbert Kociemba (May 20, 2015)

unsolved said:


> ...and this is what it looks like after Herbert's 72-move scramble test.
> 
> 
> Spoiler
> ...


Yes it is ok as it can be seen easyly here
https://alg.cubing.net/?alg=_(U_R_F_D_L_B_2U_2R_2F_2D_2L_2B)6
&puzzle=4x4x4
Then let's see what happens.


----------



## unsolved (May 21, 2015)

Herbert Kociemba said:


> Yes it is ok as it can be seen easyly here
> https://alg.cubing.net/?alg=_(U_R_F_D_L_B_2U_2R_2F_2D_2L_2B)6
> &puzzle=4x4x4
> Then let's see what happens.



Yes but that does not show the supercube centers. I'm pretty sure I have the supercube stuff working right now, but I await independent confirmation.


----------



## Herbert Kociemba (May 21, 2015)

I can confirm that your supercube centers are in the right positions for this scramble.


----------



## unsolved (May 29, 2015)

cmowla said:


> Search for "Analysis of 3x3x3 corners only" to find that the number you are seeking is *14* (*11* is when we ignore all of the puzzle except for corners, meaning that we are able to destroy other piece types in order to solve the corners themselves optimally).



Oh, right. The corners-only pruning table has no concern for other piece types.



Herbert Kociemba said:


> Since you not only have to solve the corners but also have to keep the edges, the shortest solution is longer. The shortes solution using only outer face turns is 18 moves: U (B' U2 D' F2)^4 U' (18f*).



Thanks.

=============================================================

In other news, now that the 3-stage approach I have seems to be working, I have a few questions.

1. Is there a "God's Number" that is known once "the cage" has been solved? (all corners + all edges correct).
2. Is the estimate for the number of moves required to solve all centers *first *smaller than the number to solve all of the centers *last*?
3. I am hunting for the most difficult cube position where 4 sides are solved in entirety plus the cage is solved. One such case is shown below:

https://alg.cubing.net/?puzzle=4x4x...=U-_2R_2D2_U_2L-_U2_2L_2D2_U_2R-_U-_2L-_U2_2L

So far, I have 13 moves as being the greatest number of moves required to solve centers exchanged between two adjacent faces. Are there any known positions with longer solutions?


----------



## Herbert Kociemba (May 30, 2015)

In general I would say that it is not optimal to define intermediate states of a multi-stage solver which fix certain pieces in their final position. This is more or less a "human" approach. Superior to this seems an approach where the intermediate states are defined by reducing the allowed moves from step to step, for example use only outer face turns in the last step.
Concenrning the centers I have the result that in worst case it will take 11 moves (SSTM) to restore the centers in such a way that the centers of opposite faces are at least on the same axis again (but still the two colors can be mixed on the two opposite faces).
But this is with totally ignoring the edges and corners. If your want to keep the corners and edges of your cage and also want to completely fix the centers it will take considerably more moves.


----------



## unsolved (May 30, 2015)

Herbert Kociemba said:


> In general I would say that it is not optimal to define intermediate states of a multi-stage solver which fix certain pieces in their final position. This is more or less a "human" approach. Superior to this seems an approach where the intermediate states are defined by reducing the allowed moves from step to step, for example use only outer face turns in the last step.



I am taking the human approach because I simply don't know how to do it any other way 

I am doing something a little different in my 3 stages.

Stage 1 = all 24 edges (very, very long time to resolve).
Stage 2 = complete "cage" or "ringed cube" (only requires face turns after stage 1, so this is usually the fastest stage).
Stage 3 = solve the cube (does not require calling the move generator at all and is very quick)

During stage 3, I convert the ringed cube hash table into a linear array of "solving algs." I have every move sequence that will create a caged cube in 4- through 10-turns. The program simply goes through this list (at a rate of about 27,000,000 algs/second) and applies the moves. It tests to see if the cube is solved. If the cage is not 10 turns (or less) from the solved state, the cube won't be solved. If this is the case, the program applies the 4- and 7-turn solutions in cascade, making an ad hoc 11-turn alg out of the combined two. Since all caged cube algorithms do not disturb the cage (the set is "closed") I can apply them blindly and just test for a final result.

I apply all of the solutions in pairs. (4x7) and (7x4), (5x6) and (6x5) give me all of the ad hoc 11-turn solutions.
(4x8),(8x4),(5x7),(7x5), and (6x6) give me all of the ad hoc 12-turn solutions.
I repeat this process and also sample the solved cubie population along the way. If I don't solve the cube after running through the entire list up to (10x10), I apply the solution that gives me the highest solved cubie population (usually 92+ out of a possible 96 at this point) and then just brute force solve the rest.

Stage 2 is in the neighborhood of 9- and 10-turns on average (from the test positions I have given the program).
Stage 3 is sometimes 18-20 moves because this approach is clearly not optimal (but it is fast given the depth).

But there's no getting around the fact that stage one can take up to 2 weeks until I figure out a better way.



Herbert Kociemba said:


> But this is with totally ignoring the edges and corners. If your want to keep the corners and edges of your cage and also want to completely fix the centers it will take considerably more moves.



I am still trying to discover this upper bound.


----------



## rokicki (Jun 2, 2015)

Will there be intermediate results posted at any time? It might be interesting to see how people are doing.

Unless of course no one has submitted solutions yet.


----------



## unsolved (Jun 2, 2015)

rokicki said:


> Will there be intermediate results posted at any time? It might be interesting to see how people are doing.
> 
> Unless of course no one has submitted solutions yet.



I can demonstrate something that is humorous and interesting, without spoiling the contest. Recall Herbert asked for a solution to his 72-move scramble while my program was still using a (flawed) supercube approach before I switched on-the-fly to a 3-stage solver where all of the edges were solved first. Well I noticed the alg was doing fine, conquering most of the edges after 18 plies of search.

https://alg.cubing.net/?alg=F2_2R2_...4x4x4&setup=_(U_R_F_D_L_B_2U_2R_2F_2D_2L_2B)6

But, you will notice, with a few edges remaining to be solved, the colors are incorrect for the bottom and left faces 

So my "wonderful" fastest-edge-solving portion of the stage solver went awry somewhere.


----------



## ch_ts (Jun 2, 2015)

Yes, I can post some intermediate results when I get more entries. So far, only computer entries from you and qq280833822. No human entries yet.


----------



## ch_ts (Jun 13, 2015)

Not many people have entered, but the solutions received were very good solutions indeed!

Computer Leaderboard: (as of June 13)
1. rokicki
2. qq280833822

rokicki has a slight lead. No human entries.


----------



## cuBerBruce (Jun 15, 2015)

I am off to a slow start. I have worked out "human" solutions for 2 of the 5 so far, but even these I would like to improve on. I should at least get a set of human solutions submitted by the end of the month.


----------



## unsolved (Jun 15, 2015)

ch_ts said:


> Not many people have entered, but the solutions received were very good solutions indeed!



I was banking heavily on the "line crawl" technique, which was functionally illegal if not completely illegal, and it did not pan out as expected. Still, some good came out of it. I have a 4x4x4 supercube solving mode now that I can eventually integrate into the interface.

That left me in the awkward position of re-investigating stage solving code I had written before (which was time consuming and not really worth mentioning the long solves it produced) or coming up with a new one altogether. It is strange how sometimes it is better to start from scratch rather than build on code that is even slightly unfamiliar. So that's what I did.

My stage solver hunts for all edges to be in their correct location as expediently as possible, with some "time cutoff" parameters that will "settle" for correct facelet colors if the edge can't be "totally correct." Next it solves the corners, and finally the centers.

I now have a new edge pruning mechanism that requires 0 RAM and no pre-loading of table data. It needs to be refined, and I spent too much time making sure this was "admissible" as a legitimate implementation. I have decided it might be worth trying to perfect this at the expense of not finishing on time. I might have some interesting solutions to these after the contest is over. 

I was surprised to see that corners take so long to solve after the edges are in place. I incorrectly assumed 11 turns was the max distance based on the corner pruning data. More than one corner solution required over 15 moves for stage 2 alone.

Stage 3 is always fun to watch, even though it is not optimal. The program flies through its list of cage-solving algs, and you can see the line of play extend from 10-11-12-13-14-15-16 moves rather quickly.

I am loading up the machine before I take a short vacation. In case I don't get back in time and you might be curious about the edge solving solution, here is one of them.



Spoiler



https://alg.cubing.net/?puzzle=4x4x...R2_2U_2B-_D2_R_2U-_2B-_R2_B_D2_F_2L2_F-_D2_B-


----------



## Herbert Kociemba (Jun 17, 2015)

unsolved said:


> Stage 3 is always fun to watch, even though it is not optimal. The program flies through its list of cage-solving algs, and you can see the line of play extend from 10-11-12-13-14-15-16 moves rather quickly.



How many moves does it take on average to solve stage 3 if the centers are randomly scrambled?

The discussions in this thread motivated me to give a three stage solver a try too. It will be based on the concept of restricting the allowed moves from stage to stage. In the moment I am working on stage 1 and definitely it will take several more weeks before I hope to be able to have some results. Definitely not before the end of the contest.


----------



## unsolved (Jun 18, 2015)

Herbert Kociemba said:


> How many moves does it take on average to solve stage 3 if the centers are randomly scrambled?



For functionally random center scrambles, my data sample is small: 4.

It took 14, 17, 20, and 21 moves.

The 21-move solution was composed of 9-7-5 turn "algs" applied in cascade.


----------



## rokicki (Jun 27, 2015)

ch_ts said:


> *Welcome to 4x4x4 FMC round 2!*
> 
> Time: May 15 to June 30 2015



When you say June 30th, is this noon June 30th in Hawaii? Or some other specific time?

It's not a big deal probably but might as well get it right; I'd hate to submit my final
solution 20 hours after the contest ended.


----------



## ch_ts (Jun 27, 2015)

OK, let's say June 30 11:59pm GMT officially, but unofficially I'll accept solutions until I check on July 1.


----------



## ch_ts (Jul 1, 2015)

*Results*

These were incredible solutions in the computer division! Both rokicki and qq280833822 found very short solutions. Very impressive solutions! In the human division, cuBerBruce defends! Well, there were no challengers but I'm sure it would have been difficult to beat him anyway, as he was sub-80 in all his solutions.

*Computer Division*

rokicki: 36 (35) 36 (37) 36 => 108


Spoiler



1. 2R' 2L2 B' 2U D L2 D R2 2D 2B 2L' U2 2F F' R' F' 2R 2B2 R' 2U' D' R' F' R2 U F' B2 U' D' B2 U B2 R2 B2 R B
2. 2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D' L2 D2 2R U L D R' F2 D' L2 F L F2 U' R B'
3. R' F' 2U' D' 2F2 2L2 2B 2L' F D 2R' B' L2 R' 2U 2L 2F2 2R' 2F' 2R2 2F2 2L' L2 U' B2 D2 F2 R' D2 B2 D' F' U2 R' D' L2
4. R' 3Fw2 3Uw' 3R F 3U2 3Uw2 R 3Fw 2U' 3Fw' 3U' 3F' U2 3R2 3Uw' 3F 3Fw2 3U' U' R L' D L' U R B2 U' F2 U F L U D' F L F
5. 2R' F 2D' 2L2 2F' 2D 2R 2F2 U2 B2 2L2 L' 2F2 2D' R2 U' 2B D 2F' L2 R' D' F' L B2 U2 L' U2 F' R B D' R L2 U2 B2



qq280833822: (37) 37 37 37 (38) => 111


Spoiler



1. R 2L' 2U' F U' 2D2 2L B2 U' R' D' B' 2D' 2R' 2B' z R2 B' 2L2 U' 2U2 2F2
R2 F' R2 U' R2 F2 U' F2 L R B D2 R D2 F' R2
2. B 2F R' 2L B L' U' L 2U2 2B 2L2 2U B 2F2 2U z R2 D2 B2 2U2 2R2 B 2R2
F R D' B' L B2 R' U' B U L2 F' L U' F2 
3. U R2 2B2 D 2D2 R F' 2U2 R2 B 2R' U2 2U 2B F U 2F2 U 2U2 F' 2U2
D L' F2 D' L2 B D R U2 L2 B' U' B U' B' U
4. 2R 2B U' 2B R B U R 2B L' 2U2 2L' U L2 2F z B' D2 F' 2L2 B 2U2
R B R D2 R2 B D' F' D L B' D R U' F D2
5. 2U2 2R F' L 2U' 2D' B' 2B U' 2R' 2F L2 F U' 2U2 F2 2L2 B' U' 2R2
R2 D' U' R' F' L' B2 R2 D' F R' F D2 R U2 F2 R2 U2



ch_ts: 50 (49) (1000) 1000 1000 => 2050


Spoiler



1. F2 2L2 2U F2 D 2F
D' 2L 2D2 D' 2R R 2D2 L
D U F' 2U2 U B 2R2 F
R2 2F2 R2 2B2 U' 2R2 F2 U' R2 2F2
D' L' D2 R2 F U R' B2 R2 B' L B L B D2 L2 F2 B2
2. F' U2 2L 2U' D2 R2 2B'
2R' R' B' 2R2 2U2 D B 2R L
B 2L2 U2 B 2R2 2U2 F 
R2 2F2 2L2 D' 2F2 U' R2 2F2 2R2 
F D' F' U B2 D' F' R2 B' U' F2 U F' U2 F2 R2 B



*Human Division*

cuBerBruce: (73) (79) 77 76 75 => 228


Spoiler



1. 2R 2U 2F' 2D' R' 2D U' D R2 D' L D R2 2F B 2L2 U 2L' U2 2L' U 2F U 2F' x2
R' U' 2L B' R2 B D' R D 2L'
U2 L 2B U' F2 B U 2B2
L' D F' L D' 2B
R' B' U F' R' F' R' F U2
L' U L F' U2
L' D2 R' B' R D2 L' F L' F' L
2. L' 2D 2R2 F2 2R F2 L 2D U' 2F R2 2F' B2 R 2D'
L 2U2 L 2U' B' 2U' y2
2R D R2 D' 2R'
L' F' U' F' 2D' L D' L' R' D2 R B' D B 2D
D 2F U B' U' 2F'
B' U' R F' U'
D' B' D B D2
F L2 F' L2 F L F'
L' B L2 B' L' B L2 B'
F U L U' L' F' L
3. L' 2F' U' 2R' R' 2U' R2 2U D' 2R L' 2U2
D 2L B U' 2L2 D2 2L U2 L D 2F2 z
2R U R2 U' F' L' F 2R'
U B 2R' F' R2 F D' R' D 2R
L2 U 2L' D' B R' D B' 2L
L' U2 L R' U R U
R2 F R B' R' F2 R B U' R' U F'
R2 F' U' B2 R' L' B U2
4. B 2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2
R' 2U' R B2 2U2 R2 2U'
L F' 2L2 F' R' F B L B' 2L2
D L 2D' B U B' R U' R' 2D
2R F' L F 2R'
L' R2 B D' R' B2 R B
U' L' U R2 U' L U B2 R
D2 U R' D R U' R' B' R2
L' B2 L'
5. F2 2U L 2U D' 2B R2 2B'
D' 2R' U B' D' 2R' U2 2R' B2 2R D2 2R z' y2
R U 2R D' L' R D B' R B 2R'
L B2 L 2U' R D2 R' F2 U' B2 U F U' B2 F 2U2
L' U L 2U'
B2 U' B' R2 U' R B' R
B U R
F' U' F R' B R B' R' F D' L D' L'


----------



## rokicki (Jul 1, 2015)

*Writeup*

Thanks for running the contest! I spent way too much time on it
but had a lot of fun. Here are my notes.

Two-phase solver for 4x4x4

My approach for this contest was to implement a two-phase solver
for the 4x4x4. The first phase finds optimal and suboptimal
reductions (move sequences that take the input position to the
subgroup (U, F, R, D, B, L)), and the second phase uses standard
3x3x3 optimal solvers to finish the solution. Only the first
phase is new work, so I will focus on that here.

I must open by saying this is not a practical 4x4x4 solver;
using a high-powered machine (16 cores) with a lot of memory
(256GB) running nearly non-stop for nearly two months, I was
able to directly find only 42 actual reduction solutions.
However, through the use of near-miss solves and derived
solves, I was able to generate more near-optimal reduction
solutions that helped me find shorter solutions.

Pruning Tables

My reduction solver used two large pruning tables, one for the
edges and one for the middles. Since each table was too
large to fit into memory, rather than using a subgroup indexing
approach, I instead used a hashing approach with collisions
to generate an inexact pruning table. I allocated four bits
per hash entry; the value in those four bits is always the
least value of all positions that hash to that value. Given a
maximum distance for hash table generation, I simply filled
each table with that distance plus one, then did an iterated
depth-first exploration from solved, hashing each position
solved and updating hash table entries along the way. For my
edge pruning table, I used 5GB of RAM, and for my middle
pruning table, I used 215GB of RAM. I explored edges out to
a distance of 10, and middles out to a distance of 10.
For both edges and middles, most entries of the hashtable
were unset by the search from solved to a depth of 10, so
for most random positions, the pruning table returned an
immediate lower bound on distance of 11.

For edges, if I had spent the time to complete a search
from solved of depth 11, I would have probably sped up the
program a fair bit; it would probably have taken about
four days to generate this table. In hindsight this
would probably have been wise; the search through depth
10 for edges only touched a total of 2.3B out of the 430B
hash table entries. I guess I was in just too much of a
hurry to get results. I may do this and see how performance
differs in the coming weeks; this may make the solver
significantly faster! Writing this at the end of the contest,
I'm disappointed I did not consider this earlier.

The hash function I used implicitly reduced the positions by
48 ways of symmetry. Also, the moves I considered were
restricted to keep a particular corner fixed, giving me an
additional reduction by a factor of 24. Details of the hash
function themselves are somewhat intricate and I would be
willing to write them up if anyone has interest.

My code is written to support the slice turn metric, block
turn metric, and outer block turn metric; I have focused on the
slice turn metric for this contest but am considering exploring
the other metrics as well.

The target subgroup for edges for my pruning table is that where
edges are matched and the total edge parity is even. (Note that
rotations and conjugation by rotations/mirroring does not change
the parity of the edge permutation.) The target "subgroup" for
middles was with each face a solid color (but not necessarily to
have the colors in a solved position). I put subgroup in
quotes because of course the middle positions do not form a
group because not all pieces are distinguishable.

Designing pruning tables is still somewhat more of an art than
a science. I considered generating one big pruning table that
combined edges and middles, but experiments showed that this
pruning table got too "wide" too quickly, and I could get better
average distances by using separate edge and middle pruning
tables. I did not fully implement and optimize a combined
pruning table so I do not have conclusive evidence that it would
be worse.

Initial Results

These are the initial results based on just using the simple
reduction solver and an optimal 3x3x3 solver with no additional
improvements. The input positions were as follows:

!: R2 F2 Rw' R D' Uw' L B' L' Rw2 R2 F Uw2 Fw F2 Rw2 B D B2 Rw' F2 Uw2
B' Rw R U Fw' Rw' U' Rw' B' D F2 U Fw' R2 B L2 Uw L2 U D R U2 Uw2
2: B' Fw' L' D F B2 Uw2 D2 R2 L Fw2 F R' Uw' Fw2 B2 Uw Rw2 F L R D U Rw
B Fw' R2 Rw2 L' D' B D' F' L2 Uw2 Rw F2 Rw2 F Fw2 U F' Rw' R U
3: Rw F' Rw2 L' Fw2 F2 B2 U' R' L Uw B' R' Rw2 B Fw L2 Rw' Uw2 B' L B2
Fw2 Rw' U Fw Rw2 B R' Uw2 R' B Uw2 B2 Fw2 F2 D' R' B2 U Rw F' R2 Rw2 L
4: B R F' D U' R' B2 D2 B' R B' D2 F' B L2 F' D2 F' U2 R2 Uw2 Rw2 L' B
U2 L' B2 Uw2 B' R' D2 B2 Uw Rw2 R2 D2 B2 U' Fw' Rw' B' F2 Uw U' R B2
U' R F2 U
5: F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U Fw2 D Rw2 R Fw2 R
Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2

For all positions but number 2, the optimal reduction was of length
19; for position 2, the optimal reduction was of length 20. (Surprisingly
position 2 is also the position we found the shortest solution for.)
An example optimal reduction for the moves is shown here:

1: 2R2 R B2 2U2 2F 2U 2B' 2R2 2U2 D' 2R2 2F' B' L 2F2 2D 2L2 L' 2F' (19*)
2: 2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D 2L (20*)
3: 2F L2 R' 2D' F 2D' D L' 2F2 D 2L 2U' 2L' 2B B2 2R' U' D' 2F' (19*)
4: R' B2 U' 2B' R 2U2 U2 B R 2F' R' 2U 2R D2 2F2 U' 2B' B2 2U (19*)
5: 2R' F 2D' 2L2 2F' 2D 2R 2F2 U2 B2 2L2 L' 2F2 2D' R2 U' 2B D 2F' (19*)

The count of direct reductions we found (limited to those sequences
that do not end in a face turn):


```
19   20    From 19   From 20  Best
1:   2   10   19+18=37  20+16=36   36
2:   0    2             20+16=36   36
3:   2   10   19+18=37  20+17=37   37
4:   2    6   19+18=37  20+17=37   37
5:   2    6   19+17=36  20+18=38   36
```
We completed reduction search through a depth of 19, and finished
a fair fraction (maybe 30%?) of the search through depth 20.

We optimally solved all the positions remaining after reduction,
and listed the best results in the table above (the format is
the reduction length, a plus sign, the best 3x3x3 result,
an equals sign, and then the resulting best sum. We list the
best overall result in the last column. As you can see we
were able to solve all positions in 37 or fewer moves, and
three of them in only 36 moves.

The optimal reduction solutions show that four of the five
positions have an optimal reduction length of 19. This means
it is more likely than not that the median reduction length
over all 4x4x4 positions is 19.

This result gave us an average of median 3 of 36.3, and an
overall average of 36.4. But we can do better.

Near Misses

Not all positions that were obtained by solving the edges and
middles separately but simultaneously were actually reduction
solutions. For instance, in some solutions the colors for the
middles were properly paired (for instance, the white middle was
not opposite the yellow middle). In some solutions, the middles
were properly paired, but the middles were in a mirror image
position. Finally, in some solutions, the total parity of the
corners and the combined edges was odd. When one of these
conditions was true, I considered the solution a "near miss";
this happened most of the time (about 87% of the time). Early
on, I ignored these near misses as they could not be solved
by a 3x3x3 solver. But later I found a way to exploit them.

First-phase solves always came in pairs (or larger sets).
The final move of any first-phase solve was always a slice move
(if it was not a slice move, the position before the final move
would also have been a first-phase solve). When I say slice
move I mean inner slice; an outer slice move is just a face move.
If moving an inner slice brings the position to a phase one
solution, then moving the opposite inner slice the other way
*also* brought the position to a phase one solution.
There are additional ways that first-phase solves can come in
bursts but they are less frequent so we will not discuss them
further here.

Given how much CPU time I was spending to compute the phase one
solutions, I decided to see if there was a way I could obtain
additional related solutions directly from those solutions, so
I took each phase one solution, trimmed off all but the first
eight moves, and ran it through the phase one solver again.
This generated a surprising wealth of additional solutions at
distances only a bit more than the original. The additional
solutions were not the trivial ones generated by appending
face moves, but were usefully different ones that, in some
cases, generated better overall solution lengths. Further, not
just the actual reduction solves themselves but in addition
the near misses also generated actual phase one solutions that
were only slightly longer. Finally, the additional solutions
were generated in seconds, so this was an easy way to leverage
a solution or near miss into many additional phase one solutions
that let me do more probes into phase two.

This table has a count of the phase-1 solutions found
organized by input sequence and length:


```
19     20     21     22     23     24     25     26
1:      2     10    112   1498  17002  19558   7023     18
   +18=37 +16=36 +16=37 +16=38 +14=37 +14=38 +14=39 +17=43
2:      0      4     30    174   1174   2785     12      0
          +16=36 +17=38 +13=35 +15=38 +14=38 +17=42
3:      2     14    119    850   6979  25281  62431      0
   +18=37 +17=37 +16=37 +14=36 +14=37 +13=37 +13=38
4:      2     22     72    304   3037   7835   2181    490
   +18=37 +17=37 +16=37 +16=38 +14=37 +14=38 +15=40 +16=42
5:      2     16     55    535   4317   9865   2362      2
   +17=36 +17=37 +17=38 +15=37 +15=38 +14=38 +15=40 +18=44
```
With these additional probes we were able to find a
length 35 solution to input sequence 2 and a length 36
solution to input sequence 3.

Of course, with tens of thousands of candidate phase one
solutions, solving them all optimally with a 3x3x3 solver
would have taken a fair amount of CPU. But generally, once
an overall solution was known for the original 4x4x4
position, we no longer cared about longer solutions, so the
3x3x3 optimal solver could be instructed to only search to a
useful overall length, and give up if no such short solution
was found.

Let us deconstruct the two better solutions that were found
with this strategy. The length 35 solution to the second input
position was found as follows.

First, a length-20 reduction solution was found:

2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D 2R

By trimming off two moves and running this through our reduction
solver again, we find the following reduction solution of length
22:

2R2 2F 2L 2D' R' D' F' 2U' 2L' 2U' F' U 2B 2R' 2F U B 2R D' L2 D2 2R

The phase one reduction is longer, but the 3x3x3 solution now is only
13 moves:

U L D R' F2 D' L2 F L F2 U' R B'

for a total of 35 moves.

For input 3, the process was as follows. We found the following
length-19 near-miss:

R' F' 2U' D' 2F2 2L2 2B 2L' F D 2R' B' L 2U2 2L2 2F 2D2 2L' 2U'

This near miss was rejected because of parity. But by trimming the
last seven moves and resolving with the reduction solver, we find the
following valid reduction of length 22:

R' F' 2U' D' 2F2 2L2 2B 2L' F D 2R' B' L2 R' 2U 2L 2F2 2R' 2F' 2R2 2F2 2L'

This has a 3x3x3 solution of only 14 moves, for a total of 36 moves:

L2 U' B2 D2 F2 R' D2 B2 D' F' U2 R' D' L2

Some questions remain that are worth exploring:

1. What is a good target subgroup for phase 1? I happened
to use one that ignored overall corner/edge parity
and middle color permutation, and it worked well, but
is there a larger subgroup that would provide more
opportunity to exploit near-misses for phase 2 probes?

2. Is there a better way to construct either separate or
combined hash functions for phase one search that
generates a higher overall depth, or that is faster
to compute?

3. What exactly is the relationship of all the solutions
generated by trimming and re-solving phase one
solutions and near-misses? Is there an alternative
or faster way to generate these that does not require
search?

4. Given the approximate nature of the pattern database,
what is the best way to compress this in order to
obtain higher average probe depth, without compromising
performance or random access?


----------



## cuBerBruce (Jul 1, 2015)

Congratulations to Tom on his winning computer solutions!

Here are my explanations for my human solutions.

First, here is a summary of my solutions by phases:

Insertions for the 3x3x3 phases are counted against the 3x3x3 phase, regardless of where in the skeleton the insertion occurs.


```
Scramble  Total   Centers   Edge Pairing    3x3x3

    1      73       20          24           29
    2      79       21          26           32
    3      77       23          27           27
    4      76       22          25           29
    5      75       20          26           29
```

In the spoiler, are my detailed explanations.



Spoiler





```
1.
Scramble: R2 F2 r' R D' u' L B' L' r2 R2 F u2 f F2
r2 B D B2 r' F2 u2 B' r R U f' r' U' r'
B' D F2 U f' R2 B L2 u L2 U D R U2 u2

Solution: (73 = 20+24+29)
2R 2U 2F' 2D' R' 2D U' D R2 D' L D R2 2F
B 2L2 U 2L' U2 2L' U 2F U 2F' x2
R' U' 2L B' R2 B D' R D 2L'
U2 L 2B U' F2 B U 2B2
L' D F' L D' 2B
R' B' U F' R' F' R' F U2
L' U L F' U2
L' D2 R' B' R D2 L' F L' F' L

Explanation:

Reduction phase:
First center: 2R 2U
2nd center: 2F' 2D' R' 2D U' . L D 2F
(2 other centers 3/4 completed)
3rd & 4th centers: B 2L2 U 2L' U2 2L'
Last 2 centers: U 2F U 2F' x2
(2 dedges already formed)
3rd - 6th dedges: R' U' 2L (B' R2 B) (D' R D) 2L'
7th - 10th dedges: U2 L 2B (U' F2 U) (U' B U) 2B'
Last 2 dedges: 2B' L' D F' L D' 2B
L' D F' L D' 2B

3x3x3 phase:
"Scramble":
L2 U2 F' U B' U2 F U' B R L U2 R' L'
U' L U2 L2 U' L2 U' L2 U L F' U'
F U F' R' F R2 U2 R' L U2 L B2
R F' L2 B' R' F' R2

3x3x3 phase solution:
For 3x3x3 phase, use L2 premove (cancelling first move of above scramble).
2x2x2: R' B'
2x2x3: U F' R' F' R'
Pseudo F2L-1: F U2 L' U L
All but 4C, 2E: F' U2
2C2E "insertion": L' (D2 R' B' R D2 L' F L' F' L2) L
Premove correction: L2
Insertion for last 3 corners at ".": D R2 D' L D R2 D' L'
(4 moves cancel)

2.
Scramble: B2 R u r2 u' r' R' f U2 f2 B U2 u B' F
L' D' F2 u' B u2 F' u2 U F' D u f2 B U'
F' u L' u2 U' f' F' B' U2 F' f L U' B2 f2

Solution: (79 = 21+26+32)
L' 2D 2R2 F2 2R F2 L 2D U' 2F R2 2F' B2 R 2D'
L 2U2 L 2U' B' 2U' y2
2R D R2 D' 2R'
L' F' U' F' 2D' L D' L' R' D2 R B' D B 2D
D 2F U B' U' 2F'
B' U' R F' U'
D' B' D B D2
F L2 F' L2 F L F'
L' B L2 B' L' B L2 B'
F U L U' L' F' L

Explanation:

Reduction phase:
First center: L' 2D 2R2 F2 2R
(with half of opposite center solved)
2nd center: F2 L 2D U' 2F R2 2F'
3rd center: B2 R 2D'
Finish centers: L 2U2 L 2U' B' 2U' y2
(1 dedge formed)
2nd  - 3rd dedges: 2R D R2 D' 2R'
4th - 9th dedges: L' F' U' F' 2D' (L D' L') (R' D2 R) (B' D B) 2D
Last 3 dedges: D 2F U B' U' 2F'

3x3x3 phase:
"Scramble":
R' F R F D' F' B2 D' F D R' D' F' U F
D2 B U2 B2 U' B R' U R U2 B U2 B' U L'
D L U' L' D' L U2 B2 U' F' U B2 U' F

3x3x3 phase solution:
2x2x2: B' U' R F' U'
Siamese 2x2x2s: D' B' D B D2
F2L-1: F L2 F' L2 F L F'
F2L: L' B L2 B' L' B L2 B'
LL: F U L U' L' F' L

3.
Scramble: U2 D2 F' D F' u2 F L' r' U2 F' L u2 L' R'
r' D u2 L u U' R' u2 D B D' L' r' f' u'
r F' f2 r2 B2 r' U' B' R' f r F' B U' u

Solution: (77 = 23+27+27)
L' 2F' U' 2R' R' 2U' R2 2U D' 2R L' 2U2
D 2L B U' 2L2 D2 2L U2 L D 2F2 z
2R U R2 U' F' L' F 2R'
U B 2R' F' R2 F D' R' D 2R
L2 U 2L' D' B R' D B' 2L
L' U2 L R' U R U
R2 F R B' R' F2 R B U' R' U F'
R2 F' U' B2 R' L' B U2

Reduction phase:
Tricolor 2 opposite centers: L' 2F' U' 2R' R' 2U' R2 2U
3rd center: D' 2R L' 2U2
Tricolor centers: D 2L B U' 2L2 D2 2L
Finish centers: U2 L D 2F2 z
(2 dedges formed)
3rd - 6th dedges: 2R (U R2 U') (F' L' F) 2R'
7th - 10th dedges: U B 2R' (F' R2 F) (D' R' D) 2R
11th - 12th dedges: L2 U 2L' D' B R' D B' 2L

3x3x3 phase:
"Inverse scramble":
R' U' L U' B' U
R' F D2 R2 B R2 B'
D' F' D F2 D2 F D2
F R F2 R' F2 R F R' F' R F2 R'
D' F2 L D F D' F' L2 F2 L D2
U F2 D' U' L' F R' F2 L F' R F2

Inverse scramble solution:
2x2x2: U2 B' R L B2
Another 2x2x1: U F R2 F U'
Siamese 2x2x2's: R U R' . F R2
F2L-1: U' R' U' R
Edges (all but 3 corners): L' U2 L
Insert at ".": R B' R' F2 R B R' F2

4.
Scramble: L' F' U' L2 U' B L D' R' B' R2 L2 D2 F L2
F' L2 U2 R2 F2 r2 B' u2 F R f2 L' u2 r2 U2
f2 F u' R2 D B' R' L D2 f L2 f' r' u' r' R' F R' B2 R2

Solution: (76 = 22+25+29)
B 2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2
R' 2U' R B2 2U2 R2 2U'
L F' 2L2 F' R' F B L B' 2L2
D L 2D' B U B' R U' R' 2D
2R F' L F 2R'
L' R2 B D' R' B2 R B
U' L' U R2 U' L U B2 R
D2 U R' D R U' R' B' R2
L' B2 L'

Explanation:

Reduction phase:
2 oppsosite centers: B 2R R D 2B2 D 2B' F 2L' U2 2L
3rd center: R F L' 2U2
Finish centers: R' 2U' R B2 2U2 R2 2U'
(1 dedge formed)
2nd - 4th dedges: L F' 2L2 (F' R' F) (B L B') 2L2
5th - 9th dedges: D L 2D' (B U B') (R U' R') 2D
10th - 12th dedges: 2R (F' L F) 2R'

3x3x3 phase:
"Inverse scramble":
B L2 D' F2 R' B2
F U2 F2 L F U' F2
R2 B L B2 U B U' R2
D L2 D2 B D B' D L2 D'
U' L D' R2 D L' U
D' L U' R2 U L' D

Inverse scramble solution:
Premoves (for inverse scramble): R2 L
2x2x2: L B2 L
pseudo 2x2x3: R2 B . D' R D2
F2L-1: R' B2 * R2 D
Edges: D' B' R' B2 R D B'
Premove correction: R2 L
Insert at ".": R U R' D' R U' R' D
Insert at "*": U' L' U R2 U' L U R2

5.
Scramble:
U2 B2 R' U2 R2 B2 U2 F2 R D L' D2 F U2 L'
B2 D R' B R2 f2 D F2 r2 L2 u2 D' L' D' L
B2 u2 R' f R2 B' r2 U' B' r' B u' f2 B2 L D2 B' U B U D2

Solution: (75 = 20+26+29)
F2 2U L 2U D' 2B R2 2B'
D' 2R' U B' D' 2R' U2 2R' B2 2R D2 2R z' y2
R U 2R D' L' R D B' R B 2R'
L B2 L 2U' R D2 R' F2 U' B2 U F U' B2 F 2U2
L' U L 2U'
B2 U' B' R2 U' R B' R
B U R
F' U' F R' B R B' R' F D' L D' L'

Explanation:

Reduction phase:
First center: F2 2U L 2U
Opposite centers: D' 2B R2 2B'
Centers paired: D' 2R'
Finish centers: U B' D' 2R' U2 2R' B2 2R D2 2R z' y2
First 6 dedges: R U 2R (D' L' D) (D' R D) (B' R B) 2R'
7th - 9th dedges: L B2 L 2U' (R D2 R') (F' . U' F) 2U
10th - 12th dedges: 2U L' U L 2U'

3x3x3 phase:
"Inverse scramble":
U F B' U B2 R2 F2 U'
B D R B2 D2 R2 B'
D F D F' D2 R' D' R
L' D2 L D' B D
R D R' D' B'
D B D B' L' F' D' F L D'
B R' B L2 B' R B L2 B2
D' B' D F D' B D F'

Inverse scramble solution:
Use premove (on inverse scramble): B U B2 (for fixing 2 2x2x1 blocks)
2x2x2: L D L' D F'
2x2x3: R B R' B'
F2L-1: R F' U F
Edges (leaves corner 3-cycle): R' U' B' R' B R' U R2
Premove correction: B U B2
Insert at "." (in reduction phase): F' U' B2 U F U' B2 U
```


----------



## rokicki (Jul 1, 2015)

cuBerBruce said:


> Here are my explanations for my human solutions ...



I'm completely blown away by this. I can't believe you have such short human
solutions for these positions. I can't even fathom how you found such short
solutions for just the centers.

Congratulations!


----------



## cuBerBruce (Jul 2, 2015)

rokicki said:


> I'm completely blown away by this. I can't believe you have such short human
> solutions for these positions. I can't even fathom how you found such short
> solutions for just the centers.
> 
> Congratulations!


Thanks.

I figured solutions in this metric should be comparable to OBTM solutions. My solutions are generally longer than my OBTM solutions on the earlier competition. I attribute this to not spending the same amount of time as the first competition.

I note that it was proved several years ago that 22 moves is an upper bound to solve centers in this metric. (Except for the fact that this proof did not consider OLL parity.)

Finding a good centers solution largely involved a lot of trial and error. Of course, you also want to avoid "OLL parity" in this step, so you want to complete the third center having made the correct parity of inner layer moves. It is also important to get a good solution here, as the other steps will need to be totally redone if you decide to change the centers solution.

Some other techniques I tried.

Try to preserve any paired up centers - 2 adjacent (not diagonally) center pieces of the same color. (But this can also end up adding too many moves.) Getting 3 pieces of the same color on a face can also be beneficial.

Using insertions.

Getting opposite-face colors on the same face.

After getting a centers solution, try changing the order of consecutive face moves. This does not get a shorter centers solution, but may allow you to get more edges paired up for free.

Using inserted moves. 

For example, for scramble 4, the start:
2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2 R' 2U' R B2 2U (19)

appears to require something like R' 2U R2 2U to finish, resulting in a 23-move solution.

2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2 R' 2U' R B2 2U R' 2U R2 2U' (23)

But adding the move B at the beginning allows the ending to be changed to 2U R2 2U'.

This simplifies to:

B 2R R D 2B2 D 2B' F 2L' U2 2L R F L' 2U2 R' 2U' R B2 2U2 R2 2U' (22)

Thus, the inserted move allowed a net reduction of one move. Note that the back face after the scramble had two colors represented in the center pieces. These corresponded to the last two colors solved. Turning the back face had the "visible effect" of swapping two of the center pieces. Using the right "swap" allowed a more efficient ending.


----------



## ch_ts (Jul 2, 2015)

Ha, I noticed in rokicki's writeup he stopped saying "I" and started saying "we" to mean "me and my machine" 

In my opinion, cuBerBruce's solutions are especially strong in the edge-pairing step. I think I could match him on the centers and maybe in 3x3x3 (if I spend enough time), but not in edge-pairing. Dunno, it seems easy seeing his solutions...


----------



## cuBerBruce (Jul 2, 2015)

ch_ts said:


> In my opinion, cuBerBruce's solutions are especially strong in the edge-pairing step. I think I could match him on the centers and maybe in 3x3x3 (if I spend enough time), but not in edge-pairing. Dunno, it seems easy seeing his solutions...



Of the 3 basic phases (centers, edge pairing, 3x3x3), I estimate edge pairing is where I spend the least amount of time.

Some basic techniques/principles I use in edge pairing:

1. Use any axis for "slicing." Choose the axis separately for each n-at-a-time pairing sub-step.

2. Try to find pairs that are already "set up" for pairing. In my solution for the 3rd scramble, I not only was able to get 2 dedges for "free" during centers solving, but I also was set up for immediate "slicing" into a 4-at-a-time pairing sub-step. In only 8 moves, I was "half done" with edge pairing. You need to look for these "lucky" situations.

3. Extending the preceding point, always look for setting up pairs (particularly in the front end) that can be set up in the least number of moves.

4. Try to get paired edges for "free" during centers solving as I mentioned in my previous post. If it takes on average 2.5-3 moves to do each pairing, getting 2 dedges for "free" saves about 5-6 moves during edge pairing.

5. 6-at-a-time pairing may not be all that great a strategy. The third pair on the front end always takes (at least) 3 moves to set up (unless you get cancellations), and you generally have 9 or more moves total (barring cancellations) for the three pairs on the back end (not counting the "slicing back").

6. On the front end, you generally have two choices for which edge pair to set up for the 2nd pair. The same holds for the third pair if you do 6-at-a-time pairing. Choose the one that can be set up most efficiently.

7. In speedsolving, you generally set up the pairs on the back end in a specific order. (You "store" the front end pairs in a specific order). In FMC you have no need to do these in a specific order once you know what needs to go where. This may help get cancellations or avoid bad 4-move setup cases.

8. Avoid 4-move setups for a single pair. Choose a different pair to set up or choose to do fewer "at a time" to avoid the bad case.

9. Of course, avoid PLL parity at the end of edge edge pairing. If you get to a point where you have two dedges left, the algorithm 2D' L' F U' L F' U 2D or its mirror (2D R F' U R' F 2D') will work (this of course assumes the unpaired edges are at FL and FR with the pairs horizontal, not diagonal).

10. Don't just do one edge pairing attempt. Do a few attempts and take the best one (or possibly one that leaves a good starting point for the 3x3x3 phase).

As for 3x3x3 solving, I am not very good at finding sub-30 solutions very quickly. I typically took several hours to find each sub-30 solution. Good FMCers these days seem to be usually able to come up with sub-30 solutions within an hour, and perhaps not just sub-30, but often down in the 24-27 range as well.


----------



## ch_ts (Jul 2, 2015)

This is what I do (when not using cmowla's reduction method) :

Centers
1. Remove 2 opposite centers from 2 faces. Let's say white/yellow. Remove white/yellow from L and R faces, so they're on F, U, B, D.
2. Make 1x2 blocks stashing them in one slice (say 2L) when necessary.
3. Make 2x2 centers by merging the 1x2 blocks. Let's say I put them on U and D
4. 3rd and 4th centers. Let's say I'm doing green and red. Make 1x2 blocks alternating green/red/green/red on R, F, L, B. If I need to solve orientation parity, put the 1x2 blocks in a slice (say 2D slice) and do an extra 2U (or Uw). Then turn two of the blocks into the U slice, do 2U2 (or Uw2)
5. Do 5th and 6th centers.

Goals:
centers: 20 moves.
centers + edge pairing together: 50 moves.
3x3x3: 30 moves.


----------



## Herbert Kociemba (Jul 2, 2015)

My congratulation too to the three contestants, 36/37 moves in the computer division on average and 76 moves in the human division are absolutely amazing! 
I hope the three phase solver I am developing will give some solutions which are not too far away from 40 moves. Phase 1 which I consider the hardest already works, it puts the cube into a position which is generated by <U,R,D,L,F2,B2,2U2,2R2,2D2,2L2,2F2,2B2>. I did not encounter a position which needed more than 14 moves for this step. Phase 2 is on the way, it puts the cube into <U,R,D,L,F2,B2>. In phase 3 there is a 3x3x3 cube left with already fixed edge orientations which wil take about 17 moves to solve on average. We will see how suboptimal solutions contribute to better overall solutions with this approach.


----------



## Christopher Mowla (Jul 3, 2015)

I also would like to congratulate all contestants. The computer solution move-counts are breath-taking, and Bruce's human solution move-counts are very nice as well.


----------



## rokicki (Jul 3, 2015)

ch_ts said:


> Ha, I noticed in rokicki's writeup he stopped saying "I" and started saying "we" to mean "me and my machine"



I wish I could say we had been so clever! It's just poor writing.

I also want to correct a few things I have wrong in that writeup. The distance-10 positions in the middle
pruning table numbered 45B, not 4.5B, so extending the table to include distance-11 positions would
not have been useful (as almost all table entries would have been set to 11, so very few table entries
would have a value of 12).

There's a number of ways I can proceed from here. Perhaps the most natural is to simply use the
reduction solver to optimally find reductions for a larger set of random positions, and gather some
statistics on that distribution. Another is to try to determine what near-misses are most productive
in terms of generating actual reductions that are only slightly longer.

Certainly gaining more confidence in the "median of 19" solution length for reduction is worthwhile as
this sets a clear target for solvers that use reduction built out of more than one stage.


----------



## ch_ts (Jul 3, 2015)

Herbert Kociemba said:


> I hope the three phase solver I am developing will give some solutions which are not too far away from 40 moves. Phase 1 which I consider the hardest already works, it puts the cube into a position which is generated by <U,R,D,L,F2,B2,2U2,2R2,2D2,2L2,2F2,2B2>. I did not encounter a position which needed more than 14 moves for this step. Phase 2 is on the way, it puts the cube into <U,R,D,L,F2,B2>. In phase 3 there is a 3x3x3 cube left with already fixed edge orientations which wil take about 17 moves to solve on average. We will see how suboptimal solutions contribute to better overall solutions with this approach.



My estimate is this will result in solutions about 42 moves. It's a guess (but not total guess). 

One of the variations I tried does your 1st phase in 2 steps, and your 2nd phase in 2 steps also, and then puts the cube into <U,D,F,B,R2,L2>. For example, for scramble 3 I have for reduction:
U 2F2 R2 2B' F' 2U D2 2L' F L U 2R R2 B 2L
B' D2 B' 2U2 F2 2U2 2R2 F R2 2R2 U2 2L2 2F2 2R2 R2 U' 2L2
and then the cube is in <U,D,F,B,R2,L2>. 
view


----------



## Herbert Kociemba (Jul 5, 2015)

ch_ts said:


> My estimate is this will result in solutions about 42 moves. It's a guess (but not total guess).
> 
> One of the variations I tried does your 1st phase in 2 steps, and your 2nd phase in 2 steps also, and then puts the cube into <U,D,F,B,R2,L2>. For example, for scramble 3 I have for reduction:
> U 2F2 R2 2B' F' 2U D2 2L' F L U 2R R2 B 2L
> ...


Did you use suboptimal solutions from phase1/2 to get shorter solutions in phase 3/4?

The search space of my phase 2 (your phase 3/4) is quite small and you could try to do this in one step. In phase 2 I use two coordinates: an "edge pairing" coordinate with a "raw" index from 0..12!/2, reduced by 16 symmetries the index runs from 0..14999139 and a center coordinate. I built the pruning table for "edge pairing" coordinate today and the maximum depth is 13 with an average of about 10-11 moves. So we have the preliminary result that edge pairing alone can always be done with 13 moves in phase 2.
The center coordinate for phase 2 should have 70*70*6 entries, but I have not implemented this coordinate yet.


----------



## Herbert Kociemba (Jul 10, 2015)

I finished the coding of the phase 2 now too. The center coordinate for phase 2 has not 70*70*6 but 70*70*12 values btw. Without using suboptimal solutions, just taking the first solution of each phase I got the following for scramble 1:
3F 3U 2R2 3U 3u 3R2 3U 3F2 R 3U2 3f' 2U 3R .U L' F2 U 2B2 B2 2U2 D' 2F2 U L U' 2R2 .L' U' R' B2 L2 D L' U' L2 U L U D2 F2 D2 L2
The total length is 13+13+16=42. Using suboptimal solutions a < 40 move solution should be no problem.

Also 13/13/16 for scramble 4:
3f 3U2 R' 3r' 3F' 2U' F' R' U 2R F 3R2 3F.B2 U2 2L2 L 2D2 D B2 R' 2L2 2F2 B2 L 2U2.F2 L2 U2 D R2 D F2 R' L2 D2 B2 L2 F2 U' F2 R2


----------



## Herbert Kociemba (Jul 10, 2015)

I tried if and how good a solution I get if applying the phase 1 and phase 2 solver to the single dedge flip. Using just the first solution which popped out for phase 1 and then applying phase2 solutions until the cube was compeletly solved I found the following 9+12=21 and move solution

2R U2 2R2 F2 U2 2R' U2 F2 2RU R2 2B2 R2 U 2R2 U' R2 2B2 R2 U 2R2  

Another 9+11 solution is

2R U2 2R2 F2 U2 2R' U2 F2 2R' U 2F2 R2 2F2 U 2R2 U' 2F2 R2 2F2 U 

Using suboptimal phase 1 solutions I found a 11+8 solution:

3u 2F' R2 3u2 2F' 3u2 R2 3u' 2R2 U2 2R'U' R2 U 2R2 U' R2 U' 2R2

... and a 11+7 solution:
2R F2 2R' F2 2R U2 2R2 F2 2R' F2 2R'2U2 F2 2R2 F2 U2 2R2 2U2


----------



## ch_ts (Jul 10, 2015)

No I didn't try that... I think I may revisit my solver, there are some changes I'd like to make with it.


----------



## Herbert Kociemba (Jul 11, 2015)

I let the dedge flip solver run over night and now found a 12 + 5 = 17 move solution in SSTM and STM for the single dedge flip

U2 3R' F2 3R U2 3R' U2 2R2 F2 3R U2 2RD2 F2 2L2 F2 D2 

I hope this is quite remarkable because in https://www.speedsolving.com/wiki/index.php/4x4x4_Parity_Algorithms#One_Dedge_Flip I see only a single dedge flip algorithm which is 17 moves in STM but it is more in SSTM.


----------



## rokicki (Jul 11, 2015)

Herbert Kociemba said:


> I let the dedge flip solver run over night and now found a 12 + 5 = 17 move solution in SSTM and STM for the single dedge flip
> 
> U2 3R' F2 3R U2 3R' U2 2R2 F2 3R U2 2RD2 F2 2L2 F2 D2
> 
> I hope this is quite remarkable because in https://www.speedsolving.com/wiki/index.php/4x4x4_Parity_Algorithms#One_Dedge_Flip I see only a single dedge flip algorithm which is 17 moves in STM but it is more in SSTM.



Wow, only a 15-move reduction! That should be easy for my program; I should have
been able to find this with my new reduction solver fast enough.

I'm going to have to try running through a bunch of last-layer positions and see what
I can do. Is OBT or SST more interesting for this?

Congratulations, Herbert.


----------



## Herbert Kociemba (Jul 11, 2015)

rokicki said:


> Wow, only a 15-move reduction! That should be easy for my program; I should have
> been able to find this with my new reduction solver fast enough.
> 
> I'm going to have to try running through a bunch of last-layer positions and see what
> ...



Thanks! Personally I would prefer OBTM, I surely will modify my solver to this purpose sooner or later. But my solver is not really finished yet, so I will stay with SSTM for some time.


----------



## ryanj92 (Jul 11, 2015)

Herbert Kociemba said:


> I let the dedge flip solver run over night and now found a 12 + 5 = 17 move solution in SSTM and STM for the single dedge flip
> 
> U2 3R' F2 3R U2 3R' U2 2R2 F2 3R U2 2RD2 F2 2L2 F2 D2
> 
> I hope this is quite remarkable because in https://www.speedsolving.com/wiki/index.php/4x4x4_Parity_Algorithms#One_Dedge_Flip I see only a single dedge flip algorithm which is 17 moves in STM but it is more in SSTM.



this is cool! i have been playing with this alg, and tried to make it more fingertrick friendly...

rewriting moves like 3R gives U2 2L F2 2L' U2 2L U2 2R2 F2 2L' U2 2R D2 F2 2L2 F2 D2 

then, removing the U2 at the beginning, swapping the single slice moves for wide moves and making a couple of adaptations gives 2r U2 2r' U2 2l U2 2r2 F2 2l' U2 2r D2 F2 2l2 F2 D2
i think this could be improved still, might come back to it later


----------



## Herbert Kociemba (Jul 11, 2015)

It even gets better:

3R' 3u2 3R 3u2 2R F2 3R2 U2 2R' U2 3R' F2 U2 2R2 U2 

15 Move Dedge Flip!!!

written more common:

2L D2 2R' D2 2R F2 2L2 U2 2R' U2 2L F2 U2 2R2 U2


----------



## unsolved (Jul 11, 2015)

Herbert Kociemba said:


> It even gets better:
> 
> 3R' 3u2 3R 3u2 2R F2 3R2 U2 2R' U2 3R' F2 U2 2R2 U2
> 
> 15 Move Dedge Flip!!!



There are over 200 known solutions of length 15 for STM


----------



## Herbert Kociemba (Jul 11, 2015)

unsolved said:


> There are over 200 known solutions of length 15 for STM



Who computed them? Where do I find them? To whom these solutions are known?

EDIT: Ok, I found it
https://www.speedsolving.com/forum/...lver&p=983757&highlight=dedge+flip#post983757

Thanks! The parity algorithm Wiki should be updated.


----------



## cuBerBruce (Jul 11, 2015)

(I believe this question is more applicable to Tom's solver than Herbert's.)

Do you use the fact that if you have a reduction state, and you have OLL parity (ignoring whether or not you have PLL parity), then you know you must be at least 13 BTM/OBTM/SSTM from solved (or from any "true" reduction state for that matter)?


----------



## rokicki (Jul 11, 2015)

cuBerBruce said:


> (I believe this question is more applicable to Tom's solver than Herbert's.)
> 
> Do you use the fact that if you have a reduction state, and you have OLL parity (ignoring whether or not you have PLL parity), then you know you must be at least 13 BTM/OBTM/SSTM from solved (or from any "true" reduction state for that matter)?



No I don't; once I have a reduction state, I just use a 3x3x3, and until I have a
reduction state, centers aren't solved, so this doesn't apply, right?

And the edge permutation parity is one of the elements of my edge pruning
table so the only reduction solutions I encounter are those where the total
edge parity is even.

I'm sure you're onto something that is useful; I just need to figure out how.

(That is a good point, though; when I say "reduction solve" I actually mean
reduced to a legal 3x3x3 position. My "near misses" do not include situations
where the edge parity is wrong, only where the centers are not in the proper
axes, or the centers are mirrored, or the 3x3x3 edge/corner parity is off.
When a human is doing a "reduction" solve, usually, they include the
edge parity, do not include the center mirror/axis problem, and do include
the edge/corner total parity. So we are talking slightly different things
between the two. The fact that I see some axis problems with center solves
and count them as "near misses" is actually due to the way my pruning
table for centers is set up, and it was a bit of a surprise to me that that
happens.)


----------



## cuBerBruce (Jul 11, 2015)

rokicki said:


> No I don't; once I have a reduction state, I just use a 3x3x3, and until I have a
> reduction state, centers aren't solved, so this doesn't apply, right?



Well, it doesn't necessarily mean centers aren't solved. If you have the pure single dedge flip position (for instance), the centers are solved, but you don't have "true" reduction. So (since it has OLL parity, what you've called edge parity) you know you're 13 moves away from a "true" reduction state. So this generally is not so useful for "random" positions, but may effective for many positions that are 3x3x3 reduced except for the reduction parities (notably the ones that have OLL parity but not necessarily PLL parity), or very close to such positions.

By "true" reduction, I mean a position that is solvable with just (single-layer) face turns. (So each face must have like-color centers, opposite face colors must be on opposite faces, and you can't have the mirrored configuration of colors. Also edges must be all paired up, and you can't can't have the 3x3x3 edge/corner parity, aka PLL parity). 

So doing this might prune out some of what you call your "near miss" solutions, at least ones due to bad center configurations.

So if your solver indeed generates optimal "true reduction" solutions, it should be able to verify my number of 13 moves for whatever metrics (of BTM, OBTM, SSTM) that it supports. Just run it on the pure dedge flip and the standard double parity case (dedges UF and UB swapped, with one of them flipped).


----------



## Christopher Mowla (Jul 12, 2015)

Herbert Kociemba said:


> Who computed them? Where do I find them? To whom these solutions are known?
> 
> EDIT: Ok, I found it
> https://www.speedsolving.com/forum/...lver&p=983757&highlight=dedge+flip#post983757
> ...


Why? Isn't a link to my post enough? (There are two sections on "pure" single dedge flips.)

However, it's cool that you wrote a solver to find optimal solutions for this case. Too bad god's number for the single slice quarter turn metric isn't as easily reachable right now though. (The current upperbound is 23 single slice quarter turns, but it could be 21 when I found an alg like 2R' F 2L' F2 2R F 2R' F2 D F' D 2L D' F D' 2L F2 2R.)


----------



## Herbert Kociemba (Jul 12, 2015)

Christopher Mowla said:


> Why? Isn't a link to my post enough?



Obviously not, else I would not have been confused. Especially because your link points to the section "Pure Flips/OLL Parity Algorithms* which Don't Preserve the Last Layer*" and you should not be surprised if some people including me think that these algorithms *do not preserve the last layer*.


----------



## Christopher Mowla (Jul 12, 2015)

Herbert Kociemba said:


> Obviously not, else I would not have been confused. Especially because your link points to the section "Pure Flips/OLL Parity Algorithms* which Don't Preserve the Last Layer*" and you should not be surprised if some people including me think that these algorithms *do not preserve the last layer*.


In no particular order,


I assume that those know what the term "pure flip" means and those that know what "/" means in the English language (when put in between two words with no spaces) can deduce that the algorithms listed in this section are *both*. 
I clearly put "this case image and this case image" at the beginning of that section to visually explain that these algorithms are _both_. 
I expect for people to at least be open to read the few bulleted comments at the beginning of a section to clear up any misunderstandings and in fact explain _everything_. 
Context clues alone from the main titles themselves can tell you that I am listing algorithms which preserve less and less as the page progresses, considering that the next main title is simply "OLL Parity algorithms Which Don't Preserve the Last Layer", and the next is "OLL Parity Algorithms Which Don't Preserve F3L", ... , "Parity Algorithms Which Don't Preserve F3L or the Colors of the Centers". 
I made the time to translate all algorithms into SiGN notation and linked them to alg.cubing.net for animation on just about any device. If the viewer somehow fails to understand all of the previous four (independent) hints listed above that this set of algorithms is both pure flips and algorithms which don't preserve the last layer, he or she can simply click an algorithm and view its effect. *I do link to the pure versions in this particular section, after all.* 

If someone else thinks these five ways I have attempted to make clear of the nature of the algorithms in this section Mr. Kociemba and I are talking about are still not enough that I have to post *all *248 15 btm single dedge flip solutions *twice* on that page, please let me know.

Yes, there are A LOT of algorithms on that page, BUT I do not have any duplicate algorithms or any algorithms which are equivalent by a transformation (unless I say name the algorithm "...(v1)", "...(v2)", etc. to say "version 1", version 2", etc.) on that page.

I purposely made a serious and time-consuming effort to structure this page this way to:


"factor out" algorithm equivalences, 
accurately demonstrate unique algorithms and/or unique algorithm paths (for those interested in parity algorithm theory), and 
guarantee that when speedcubers insert their own custom cube rotations into an algorithm or speed optimize it in another form, that they are not going to get another algorithm on that page.


----------



## qqwref (Jul 12, 2015)

Christopher Mowla said:


> those that know what "/" means in the English language (when put in between two words with no spaces) can deduce that the algorithms listed in this section are *both*.


The confusion was that you interpreted it as "Pure Flips or (OLL Parity Algorithms which Don't Preserve the Last Layer)" whereas he interpreted it as "(Pure Flips or OLL Parity Algorithms) which Don't Preserve the Last Layer". Surely you can see how that would be confusing. And of course, if someone thinks something's clearly the wrong section, they surely aren't going to read all the details of that section and click through to the alg.cubing.net links for each alg.


----------



## Herbert Kociemba (Jul 19, 2015)

I made a lot of improvements to the reduction part (phase 1 and 2) of my three stage solver. It seems that 24 move reductions can be found in a time now that are acceptable for a solver to be used interactively. The time only depends on how deep we have to search in phase1. The goalstate of phase 1 is a cube from where it can be transformed to the reduction state using only <U,R,F2,D,L,B2,2U2,2R2,2F2,2D2,2L2,2B2> after some eventual full cube rotations. The full cube rotations between phase 1 and phase 2 could of course be omitted if the phase 2 moves would be transformed appropriately. 

Nr 1: < 1 second for 12+12=24 move reduction 

3F' 3R2 U' 2U 2F2 3r2 F R 3F' 3U 3f 3r' y z U2 2L2 U' 2D2 R 2U2 D L 2D2 2L2 L 2F2

Nr 2: < 1 second for 12+12=24 move reduction

R 2F' 2R2 3f' 2U' 3R' F' R' 2U 3u' 3F R' y z U L' 2F2 2R2 D' R' 2D2 L D' 2F2 R 2U2 

Nr 3: < 1 second for 12+11=23 move reduction

3u 3R2 3u 2F2 3f' 2U2 3r 2U2 F2 2R 3U' 2F x' z' U 2R2 2U2 F2 U 2F2 D 2F2 U2 L' 2F2

Nr 4: < 2 minutes for 14+10=24 move reduction 

3r2 3f 3u R' 3u2 3r2 2U R 2R' 3F2 U 3f 2R' 3F y z 2U2 2F2 R F2 R2 2F2 U2 R' 2F2 2R2 

Nr 5: < 6 seconds for 13+11=24 move reduction

F 3f 3R2 3F 2U 3f 2U' 3u' 3r 3f' 3U' 3R' 3U L U2 B2 U 2R2 L 2U2 2L2 2F2 U 2R2

There are some large pruning tables and the program needs 15 GB of RAM. I use a DELL precision T5810 with 64 GB of RAM installed. All computations used only one thread.


----------



## rokicki (Jul 23, 2015)

Herbert Kociemba said:


> Nr 1: < 1 second for 12+12=24 move reduction
> Nr 2: < 1 second for 12+12=24 move reduction
> Nr 3: < 1 second for 12+11=23 move reduction
> Nr 4: < 2 minutes for 14+10=24 move reduction
> Nr 5: < 6 seconds for 13+11=24 move reduction



That's pretty impressive! How well do other multistage reduction solvers do?

I presume you also get additional longer solutions. Any thought of hooking
up a standard optimal solver to work on those as they come through? Doing
shallow searches with an optimal solver for a large set of 26-move reductions
can be very fast. I.e., you keep an increasing queue of reduction solves of
whatever length, with one thread for that, and in another thread or three you
run a 3x3x3 optimal solver that picks out the best candidates/depths to try.


----------



## Herbert Kociemba (Jul 24, 2015)

Indeed I want to implement some kind of optimal 3x3x3 solver for the third stage. But I have no time within the next few weeks to work on this so I do not think I have results before october.


----------



## clement (Nov 23, 2015)

Wow, I've not been here for ages.
This is so nice to see a computer contest for 4x4x4 FMC. I will dig my code from the graves and see how it goes on the 5 scrambles. I remember it having an average solution of 40 moves, but it was designed for fast solutions (about 1 sec), I've no idea if it can produce lower solutions.


----------



## Christopher Mowla (Nov 23, 2015)

clement said:


> Wow, I've not been here for ages.
> This is so nice to see a computer contest for 4x4x4 FMC. I will dig my code from the graves and see how it goes on the 5 scrambles. I remember it having an average solution of 40 moves, but it was designed for fast solutions (about 1 sec), I've no idea if it can produce lower solutions.


Hi, Clément! I'm a big fan of your contributions to the 4x4x4 parity algorithm domain. Wow, I thought you were never going to be active on this forum again. (I can't recall you being very active since I've been a member, at least. )

Just a random note, but, using Cube Explorer, I made a complete and organized list of all (unique) possible 15 btm single dedge flip algorithms and posted them in the bottom of this post. (I stated their relationships with each other as well.)

I am very curious to see what your old solver is capable of, since I have been blown away with the solutions you found with it to PLL parity cases. In fact, your solver's algorithms for PLL parity cases has been a marvel to me. I recently found an old Yahoo Group post of yours regarding the diagonal corner swap case.





I added that page as an external link on the 4x4x4 parity algorithms wiki page to show everyone some history!

Just to let you know that your work as been appreciated by non-speed cubers such as myself, in this post, I decomposed your favorite of your solver's diagonal 15 btm solutions and found a 16 btm one by hand! Because the formatting of my post got messed up with forum updates, I have rewritten what I posted there below so that it's readable.


Spoiler: Decompositions






Christopher Mowla said:


> After A LOT of arithmetic and expansion, I broke this algorithm into 5 pieces. It was difficult to do this since many of the moves in this outline were not within the original algorithm itself, but this IS the outline for this computer-generated algorithm:
> 
> Rw2 F2 U2 r2   __________________________Preliminary
> r2   ___________________________________ Extra turn to induce PLL Parity
> ...






Now, I'm not sure if you have seen that wikipage before, but I'm sure you will enjoy it if you haven't. I do give you due credit for your algorithms, and I provide an external link to the 4x4x4 parity algorithm sets you have contributed to the community. (If there are other resources that I missed, please let me know, and I will add them!)
In addition, I (and I believe many others) was always curious as to why you didn't provide a solution for the adjacent corner swap case.




Can you possibly recall if your solver found solutions such as z 2R2 U2 R' U2 R' U2 R x U2 r2 U2 B2 L U2 L' U2 r2 U2 z' y' for this adjacent corner swap case?

I have been wanting to see what your solver generates to solve the adjacent case (besides my hand-found algorithms)
I guess, while I'm asking, I am very curious to see the shortest solutions your solver creates for adjacent double parity. (I found (y' 2R2 F r' F') 2R2 U2 2R' U2 2R' U2 2R' U2 (F r F' 2R2 y) by hand, which is 16 btm. I can recall that Per loved the structure of this algorithm!)





Lastly, I wanted to let you know (just in case you haven't seen that wiki page before) of some notable algorithms that I found which tackle various parity cases. (Just click on the links to Lucas Garron's new cube applet to see the case, animation and the algorithm.) There are of course many more that I find notable, but here is a good sample of them.

Apart from this small set of K4LL 1 3-cycle and 1 2-cycle parity algorithms, the remainder of the algorithms in this post can be found on the 4x4x4 parity algorithms page, but I wanted to select these for which I believe, based on your past contributions, might be of the most interest to you in one way or another.

*Computer-found algorithms
*A single dedge flip algorithm which is almost "pure".
2R' F 2L' F2 2R F 2R' F2 D F' D 2L D' F D' 2L F2 2R (21,18)

A brief wide turn OLL parity algorithm which has slice turns in two directions!
r2 F2 U2 r' F' u L' U2 L u' F' r' U2 r2 F2 r (23,16)

Three semi-fast OLL parity algorithms
r' U' r' U B2 U' r U' r' U2 r' x' U2 r U2 l' U2 r2 (23,17)
r2 U2 l' U2 r U' r' U B2 U' r U' r' U2 r' x' U2 r' (23,17)
l r U' r U' F2 U r' U' x U2 r' U2 r' U2 l U2 r2 x (23,17)

One of several 3 dedge flip algorithms in the slice M.
2L 2R F2 2L B 2U' B D2 B' 2U B 2R' D2 B2 2L2 F2 2R' (23,17)

*Computer-Human Interaction Found algorithms*
_All of these are from me learning from cuBerBruce's specialized parity algorithm solvers and making algorithms which "mimic" the same idea, just as I did the same to make that (27,16) diagonal corner swap algorithm by studying your solver's (27,15) algorithm._

Two single F3L slot destroyer parity algorithms
2R' U2 F' U2 F U2 2R' U2 2R' U2 2R' F' U2 F 2R' (21,15)
2L U2 F' U2 F U2 2L U2 2L U2 2L F' U2 F 2L (21,15)

An additional two single F3L slot destroying parity algorithms in a "prettier" move set.
2R' U R U2 R' U' 2R' U2 2R' U2 2R' U' R U2 R' U 2R' (21,17)
2L' U' R U2 R' U 2L' U2 2L' U2 2L' U R U2 R' U' 2L' (21,17)

Two OLL parity algorithms nearly in the <M,U> move set.
2R U' m' U m' U' m' U' m u2 2R u2 U' m' U2 m' U m U2 m U m' U m U m' U' 2L'
2R' U m' U' m' U m' U m u2 2L' u2 m' U m U' m' U m' U m U2 m' U2 2R (double parity)

*Hand-found algorithms*

12 btm flipped PLL parity
F2 2L e F2 e' 2L' 2R' e F2 e' 2R F2 (16,12)
F2 2L e' F2 e 2L' 2R' e' F2 e 2R F2 (16,12)

Adjacent PLL parity
(r' U R U l' U2 r' U2) 2R2 (U2 r U2 l U' R' U' r) (22,17)

Supercube safe O permutation PLL parity algorithms:
2L 2R 3d' L R 2U' L' R' 3d m2 3d L' R' 2U' L R 3d' 2L 2R (20,19)
2L' 2R' 3d' L' R' 2U L R 3d m2 3d L R 2U L' R' 3d' 2L' 2R' (20,19)
2L 2R 3d L R 2U L' R' 3d' m2 3d' L' R' 2U L R 3d 2L 2R (20,19)
2L' 2R' U y L' R' 2U' L R 3d' m2 3d' L R 2U' L' R' U y 2L' 2R' (20,19)

"Pure" Single Dedge Flips
x' r2 U2 l' U2 2R U2 l F2 U 2R U' F2 U 2R' U r2 x (23,16)
x r2 U2 r U2 2L' U2 r' F2 U' 2L' U F2 U' 2L U' r2 x' (23,16)
z d' m D l' u' 2R' u l u' l2' b' 2R' b r' R' 2U y' m' u x2 z' (19,18)
r' e u2 f u r' 2R' f' 2R f r u' f' u 2R u e' r (19,18)
l' s b2 d 2R d' b d 2R' d' 2R' b' 2R b 2R b s' l (19,18)
l' F' 2B' r' b' r 2U r' b r 2U2 b' 2U b 2U 2B F l (19,18)
r U2 r U r U2 r U2 r' U2 r' U 2R' U' r U2 r U2 r' U2 r' U 2R2 U2 r' U2 r' (37,27)
r U2 r U' r U2 r U2 r' U2 r' U' 2R' U r U2 r U2 r' U2 r' U' 2R2 U2 r' U2 r' (37,27)

Last layer 3 dedge flip + PLL parity
r' U2 2R U2 r' x' U2 2R' U' R' U' r' U2 r U R U' r R U2 x (24,19)

A ZBLL brief single F3L slot destroyer:
2L U2 2L' F U R U' l' D2 2R D2 2R U2 r' U2 l F (22,16)

Last layer opposite two wing edge swap
z r' U 2L' u' r u 2L' f' 2L' f 2L2 u' r' 2U r z' (16,15)

Last layer diagonal wing edge swap
u l' u' 2L' u l f' l2 u' 2L' u l' L' f u' (16,15)
u l' u' 2L' u l2 d' l u' 2L' u L' d l' u' (16,15)
u l' b' 2R' b l2 b' r f' 2R' f R' b l' u' (16,15)
r2 F2 U2 2R U2 x U2 r2 U2 2R' U2 2L 2R U2 2L' U2 x' (25,15)

 Last layer adjacent "oriented" wing edge swap.
(These are one move shorter than the L' B' (opp. 2 wing edge swap) B L combo.)
r2 u' b 2R' b' u b r' u' 2R' u r 2R b' r2 (17,15)
r2 2F u' b d 2R' d' 2R' b' 2R b 2R b' u r2 (17,15)
y' f2 2L u' b u 2L' u' 2L' b' 2L b 2L b' u f2 y (17,15)
y' z' f2 r' d 2L' d' r d l' b' 2L' b l 2L d' f2 z y (17,15)
Here's a 16 quarter turn algorithm for the same case:
u r' u' 2R' u r b' r' 2R' u' 2R' u R 2R' b u' (16,16)
Although longer than the previous two (but still equivalent to the combo algorithm btm move count), I also found algorithms such as.
2R' u l u' 2R2 f2 l' f 2R' f' l f2 2R' u l' u' (19,16).
(This alg resembles the form of Frédérick Badie's single dedge flip algorithm (2R' U2 2L F2 2L' F2 2R2 U2 2R U2 2R' U2 F2 2R2 F2)

Last layer adjacent "close-unoriented" swap:
2L2' U l U2 2R' U2 r' U2 x U' 2R' U x' U2 x U' m' 2L' (20,15)
z F' r2 2B' u l' u' 2B u 2B l 2B' l' 2B' l u' r2 F z' (19,17)
z F' l2 u b' 2L b u' b' l u 2L u' l' 2L' b l2 F z' (19,17)
z F' r2 z' r b' 2L b r' b' l d 2L d' l' 2L' f r2 F z' (19,17)
l' 2B u2 l u 2F' u' l' u 2F' l 2F' l' 2F2 u 2B' l (19,17)

Last layer adjacent "far-unoriented" swap:
2L2' U' l U2 2R' U2 r' U2 x U 2R' U' x' U2 x U m' 2L' (20,15)
r 2R z 2L f' u f 2L' f' 2L' u' 2L u 2L u' f z' r' 2R' (17,17)
r 2R y r' d 2L' d' r d l' b' 2L' b l 2L u' r' 2R' (17,17)
l 2R u' f 2L' f' u f l' u' 2L' u l 2L f' l' 2R' (17,17)

Last layer checkerboard algorithms which are similar in structure Stefan Pochmann's PLL parity algorithm: (r2 F2 U2) 2R2 (U2 F2 r2).
(2F2 2U' 2R2 u2 s') 2R (s u2 2R2 2U 2F2) (17,11)
(2F2 2U 2R2 u2 s') 2R (s u2 2R2 2U' 2F2) (17,11)

"OLL Parity" algorithms which don't preserve the centers or the Pseudo 3x3x3 state
r' U' R' U' r F' R' F' r' (9,9)
r' U' R U' r F' R F' r' (9,9)
r U' R U' 2R' D' R D' r (9,9)


----------



## ch_ts (Nov 23, 2015)

Hi Clement, what were the steps that your solver used?


----------



## clement (Nov 23, 2015)

Here are my solutions:
1. L' D2 2L2 U' F' U2 2D 2F2 L' 2R' 2U' F 2B 2D B2 2L' 2F2 R2 F B2 2U' F' B2 2D' F2 R2 2U2 L2 B 2D2 F2 U2 F 2R2 U2 2F2 2L2 U2 2L2 2F2 2L2 (41)
2. 2F' D F' 2F2 2U2 B2 R D F2 L' U' 2L' 2U F2 2D' 2L2 2F 2L' 2U2 2R2 U' B2 R2 2F2 2L' 2U2 D B2 U' 2L2 2B2 R2 D 2B2 U2 R2 2F2 2R2 B2 2D2 2L2 F2 (42)
3. L F' D' B L 2L 2U B R' U' L2 2U 2F2 R B2 R 2B 2U' R2 2F2 D2 2F2 L 2U' L' 2U' U2 R' 2B2 U2 L U2 F2 L 2L2 B2 L2 D2 F2 (39)
4. U2 L2 D2 F 2F' R 2F 2R 2B D' R' 2F2 D2 2D 2B 2L F' 2U' 2F' D2 U2 B' 2U' L2 2D' F2 2U' F' L2 2R2 B2 D2 B R2 U2 F 2D2 2B2 L2 2D2 2F2 (41)
5. 2L2 2U L F2 D2 2F2 L' U' F2 R' 2B2 2L 2U2 L2 D' 2L' D2 2B U' 2L2 2B2 U' 2D2 2L 2B2 2R U 2R2 2B2 D2 2F2 U' D2 B2 U 2D2 F2 2F2 (38)

EDIT: Each solution took about ten minutes to produce.

Christopher, that's nice to see you have been digging a lot in this topic. I see you have taken care of crediting everyone 
I've been searching on my old files, but I didn't find my results for the pll parity cases. I guess that I didn't publish results for cases when I didn't find improvements other known algorithms. They were produced with a very naive program though, just bruteforce searching and storing hashes of all positions close to the solved state.

Hey ch_ts, I'm using a 5-stage solver who's principle was designed by Bruce (http://cubezzz.dyndns.org/drupal/?q=node/view/62). This solver does not reduce to a 3x3x3 solve, but reduce to the squares coset. One advantage of this solver is that each step is well defined in terms of representing cosets, whereas the solver using 3x3x3 reduction has a problem with parity if I remember correctly. Each step except the third one is small enough so that a complete pruning table can be stored, using clever symmetry reduction (up to a 192 factor reduction for stage 5). The problem of this solver is that you cannot use the known work and results from 3x3x3 solving.
Currently, I can solve each stage very fast, but I don't have a good strategy to produce short multistage solutions. Right now, I solve stage by stage, and I keep the best 100,000 solutions(+pruning of the next stage) of each to the next one.
I also tried to just produce each optimal solution from stage 1, then for each solution produce all optimal solution from stage 2, etc. My problem is that for a given stage, I have a lot of optimal solutions that look very close, and combining all those solutions for five stages is making the search very very long, just for optimal solutions of each stage.
The source code is here: https://github.com/clementgallet/FiveStage444


----------

