Methods for Forming 2-Cycle Odd Parity Algorithms for Big Cubes

[xyzzy]

Not just challenging; I don't have any clue on how to go about doing that either! What I used was this: solving four wing pieces (the UF dedge and two other pieces), five centre pieces, and one corner piece; this was done with two small pruning tables (~4-5 million entries). I then multiplied the resulting pruning value by 2, which makes it almost certainly not optimal, and filtered the solutions (which can have up to 16 unsolved wings and 17 unsolved centres) for those that had only fixed points and 3-cycles.

Now I'm running a full optimal search (i.e. solving only the UF dedge, no restrictions on other pieces), but it's only finished exploring 25 moves so far. (The code is… not fast.) Edit: finished searching up to 27 moves now; still hasn't found anything. Edit 2: oops, found a bug—it was searching something completely different. Disregard this whole paragraph!

 

[abunickabhi]

Wow, that's impressive. Gotta ask, how did you find it? Making a pruning table that enforces only three-cycles seems challenging.

Is making three-cycle pruning table that hard? I have no idea how to go about it.

 

[rokicki]

Maybe making a three-cycle pruning table is not hard, but I don't know how to do it.

Minimum length is now 50 (the depth-49 search completed).

 

[Christopher Mowla]

I mentioned in the fourth video of my 2-gen series about "Type 3" == <r,Uw> that there is room for improvement. In the video, I derived a 61 move algorithm. Below is a derivation of a 53 by simply reusing the 37 move algorithm I found which is in <r,3Uw> ("Type 2"). (An algorithm which I derived without repetition.)

Specifically,

Spoiler: Derivation

[1] Below is the algorithm which is derived by 16:03 of the video on <r,3Uw>.
[Link]
r
r2 3Dw2 r2 3Dw2 r2
3Dw2 r'
3Dw2 r2 3Dw2 r' 3Dw2 r2 3Dw2
r2
r 3Dw2
r'
3Dw r 3Dw r2 3Dw' r' 3Dw' r 3Dw r 3Dw r2 3Dw' r' 3Dw' r'

[2] Converting all 3Dw to Uw moves,
[Link]
2R
2R2 Uw2 2R2 Uw2 2R2
Uw2 2R'
Uw2 2R2 Uw2 2R' Uw2 2R2 Uw2
2R2
2R Uw2
2R'
Uw 2R Uw 2R2 Uw' 2R' Uw' 2R Uw 2R Uw 2R2 Uw' 2R' Uw' 2R'

[3] Shifting the last 10 moves to the beginning of the algorithm,
[Link]
Uw' 2R Uw 2R Uw 2R2 Uw' 2R' Uw' 2R'
2R
2R2 Uw2 2R2 Uw2 2R2
Uw2 2R'
Uw2 2R2 Uw2 2R' Uw2 2R2 Uw2
2R2
2R Uw2
2R'
Uw 2R Uw 2R2 Uw' 2R'

[4] Conjugate with essentially the same setup moves as I used in the video on "Type 3":
[Link]
2R2 Uw2 2R' Uw' 2R' Uw 2R Uw' 2R' Uw 2R2

Uw' 2R Uw 2R Uw 2R2 Uw' 2R' Uw' 2R'
2R
2R2 Uw2 2R2 Uw2 2R2
Uw2 2R'
Uw2 2R2 Uw2 2R' Uw2 2R2 Uw2
2R2
2R Uw2
2R'
Uw 2R Uw 2R2 Uw' 2R'

(2R2 Uw2 2R' Uw' 2R' Uw 2R Uw' 2R' Uw 2R2)'

[5] Simplifying and cancelling moves:
= r2 Uw2 r' Uw' r' Uw r Uw' r' Uw r2 Uw' r Uw r Uw r2 Uw' r' Uw' r2 Uw2 r2 Uw2 r2 Uw2 r' Uw2 r2 Uw2 r' Uw2 r2 Uw2 r' Uw2 r' Uw r Uw r2 Uw' r Uw' r Uw r' Uw' r Uw r Uw2 r2 (73,53)

Since the move optimal algorithm in <r,Uw> (again, I was using old WCA notation) is 27, then this algorithm is about double that, obviously.

 

[rokicki]

Maybe making a three-cycle pruning table is not hard, but I don't know how to do it.

Minimum length is now 50 (the depth-49 search completed).

The depth-50 search completed yesterday, so the minimum length is now 51. Still running.

Here's a cute little algorithm that does it in 3150 moves (clearly not optimal):

(3u2 r 3u r 3u2 r' 3u' r 3u r)315

I have still not been able to beat the record 102 set by xyzzy. But I have found that there is no sequence shorter than 26 moves that when repeated 3 times is a pure double edge flip on UF.

 

[Christopher Mowla]

The depth-50 search completed yesterday, so the minimum length is now 51. Still running.

Here's a cute little algorithm that does it in 3150 moves (clearly not optimal):

(3u2 r 3u r 3u2 r' 3u' r 3u r)315

I have still not been able to beat the record 102 set by xyzzy. But I have found that there is no sequence shorter than 26 moves that when repeated 3 times is a pure double edge flip on UF.

I wrote a little routine in Mathematica earlier this year to find repeats of short sequences via a random scramble. (I did this to see if I could find alternate short move sequences to repeat 5 times to get OLL parity.) I just adjusted it to the given constraints and it is giving me move sequences with a random number of required repeats.

Below are the shortest so far (I started with "depth"/Length 8).

All of these flip a single dedge, but most do not flip the UF one. Ones which do flip the UF dedge have an * next to them. My program is finding one sequence every few seconds, on average.

Length of 8 (All are 4,680 moves.)
(3Uw' Rw2 3Uw Rw 3Uw' Rw' 3Uw2 Rw)585
(Rw' 3Uw2 Rw 3Uw Rw' 3Uw' Rw2 3Uw)585
(Rw 3Uw Rw2 3Uw' Rw 3Uw2 Rw' 3Uw')585
(Rw' 3Uw Rw2 3Uw' Rw' 3Uw Rw 3Uw2)585
(3Uw' Rw' 3Uw2 Rw 3Uw' Rw2 3Uw Rw)585
(Rw2 3Uw' Rw' 3Uw Rw 3Uw2 Rw' 3Uw)585
(Rw 3Uw Rw' 3Uw' Rw2 3Uw Rw' 3Uw2)585
(Rw 3Uw2 Rw' 3Uw' Rw 3Uw Rw2 3Uw')585
(Rw2 3Uw Rw' 3Uw2 Rw 3Uw Rw' 3Uw')585
(3Uw Rw2 3Uw' Rw 3Uw2 Rw' 3Uw' Rw)585
(3Uw Rw 3Uw' Rw' 3Uw2 Rw 3Uw' Rw2)585
(Rw2 3Uw Rw 3Uw' Rw' 3Uw2 Rw 3Uw')585
(3Uw2 Rw 3Uw Rw' 3Uw' Rw2 3Uw Rw')585
(3Uw2 Rw' 3Uw Rw2 3Uw' Rw' 3Uw Rw)585
(Rw 3Uw2 Rw' 3Uw Rw2 3Uw' Rw' 3Uw)585
(3Uw2 Rw 3Uw' Rw2 3Uw Rw 3Uw' Rw')585
(Rw2 3Uw' Rw 3Uw2 Rw' 3Uw' Rw 3Uw)585
(Rw 3Uw' Rw' 3Uw2 Rw 3Uw' Rw2 3Uw)585
(3Uw Rw' 3Uw2 Rw 3Uw Rw' 3Uw' Rw2)585
(Rw' 3Uw' Rw 3Uw Rw2 3Uw' Rw 3Uw2)585
(3Uw2 Rw' 3Uw' Rw 3Uw Rw2 3Uw' Rw)585
(3Uw' Rw' 3Uw Rw 3Uw2 Rw' 3Uw Rw2)585
(Rw' 3Uw Rw 3Uw2 Rw' 3Uw Rw2 3Uw')585
(3Uw' Rw2 3Uw Rw' 3Uw2 Rw 3Uw Rw')585
(3Uw' Rw 3Uw2 Rw' 3Uw' Rw 3Uw Rw2)585

Length of 10 (Tom, it also found the same sequence you posted which is of length 10, so I didn't include it.)

All of the following are obviously 150 moves.
(3Uw' Rw2 3Uw2 Rw2 3Uw2 Rw 3Uw2 Rw' 3Uw2 Rw)15
(Rw' 3Uw2 Rw 3Uw2 Rw2 3Uw2 Rw2 3Uw' Rw 3Uw2)15
(Rw2 3Uw' Rw 3Uw2 Rw' 3Uw2 Rw 3Uw2 Rw2 3Uw2)15
(3Uw2 Rw' 3Uw2 Rw 3Uw2 Rw' 3Uw Rw2 3Uw2 Rw2)15
(3Uw2 Rw' 3Uw2 Rw2 3Uw2 Rw2 3Uw Rw' 3Uw2 Rw)15
(3Uw2 Rw' 3Uw2 Rw 3Uw' Rw2 3Uw2 Rw2 3Uw2 Rw)15
(3Uw2 Rw 3Uw2 Rw' 3Uw2 Rw2 3Uw2 Rw2 3Uw Rw')15
(3Uw2 Rw 3Uw2 Rw' 3Uw2 Rw 3Uw' Rw2 3Uw2 Rw2)15
(Rw' 3Uw2 Rw 3Uw' Rw2 3Uw2 Rw2 3Uw2 Rw 3Uw2)15
(Rw2 3Uw2 Rw2 3Uw2 Rw' 3Uw2 Rw 3Uw2 Rw' 3Uw)15
(Rw' 3Uw' Rw' 3Uw2 Rw 3Uw Rw' 3Uw' Rw' 3Uw2)315 (3150 moves)*
(Rw2 3Uw' Rw' 3Uw Rw' 3Uw' Rw2 3Uw2 Rw' 3Uw2)285 (2850 moves)


It seems that algorithms of Length 8 is the minimum, but I can't prove this. I am running my solver again to see if it finds any solutions which consist of repeating an algorithm 7 moves long. In addition, I may run it for Length 30 or so to see if I can beat xyzzy's alg length.

 

[xyzzy]

24×5 = 120 moves: (3u r2 3u2 r3 3u2 r3 3u r3 3u3 r 3u3 r2 3u2 r 3u2 r 3u2 r 3u2 r2 3u r2 3u2 r2)5

24 is optimal for UF flip + 5-cycles. (This is assuming centres are distinguishable, as on a supercube. My code doesn't handle the normal, non-supercube case.)

 

[rokicki]

24x5 is minimal for a normal non-super-cube as well.

These are the numbers I see:

315x10
117x11
15x13
9x18
5x24

I'm still looking for the minimum sequence of 3.

 

[Christopher Mowla]

Maybe we could observe xyzzy's algorithm as a product of commutators, conjugates, and short repeated sequences to perhaps find other short algorithms?

3u r' 3u2 r2 3u2 r 3u' r 3u2 r 3u2 r' 3u2 r' 3u' r' 3u2 r 3u r' 3u2 r 3u' r2 3u2 r' 3u r2 3u r2 3u' r2 3u r2
=
[3u r' 3u2: r2] [r 3u2 r 3u2: r'] [r 3u r' 3u2 r: 3u] (r' 3u2 r')2 (r 3u2)2 [3u', r2]2

 

[rokicki]

Finally found one (or two). This is not necessarily optimal. It has a length of 31, but there are
move cancellations when repeating it thrice so the total length is 91.

r 3u' r' 3u2 r' 3u' r' 3u2 r' 3u r' 3u2 r' 3u2 r 3u' r2 3u2 r2 3u2 r2 3u' r' 3u2 r 3u2 r' 3u2 r 3u2 r

Any shorter sequence that repeated thrice gives the UD edge flip must be of length at least 27.

These deep searches take a long time to run (days) for me.

 

[rokicki]

Here's a better one; this one has more cancellations so the total length of the result is 87.

r' 3u r 3u' r' 3u' r 3u r 3u' r' 3u r 3u r2 3u' r 3u r 3u r' 3u r 3u2 r 3u r 3u2 r' 3u r