ZZ F2L Move Count

[Stefan]

How about <U,D,R,L>? I think that's more realistic for speedsolving, D turns are easier than F2 and B2.

 

[cuBerBruce]

Wow, excellent work! Thanks

So in this case, using <U,D,R,L,F2,B2> rather than <R,U,L> improves efficiency by ~13%

Would it be possible to adapt the program to calculate the move count for the other side as well, to give a total for left + right (solved separately)?

Also, if you have the time it would be interesting to know the average optimal move-count for solving both sides simultaneously, as well as solving all four Fridrich F2L slots simultaneously. The information wouldn't be very meaningful from a speedsolving perspective, but would certainly be of interest to FMC'ers.

Considering both left and right blocks greatly increases the number of puzzle states to deal with. So no, it is not a simple change.

How about <U,D,R,L>? I think that's more realistic for speedsolving, D turns are easier than F2 and B2.

I edited my previous post to include <U,D,R,L>.

 

[Stefan]

Thanks. Nice to see that just adding D saves 0.67 of the 1.29 moves that adding D+F2+B2 saves, that's more than half the way.

 

[cuBerBruce]

I've also now computed optimal EOCross, for whomever might be interested. I've computed it for both FTM and QTM. It's a little less than 2 additional moves on average than optimal ordinary cross.

distance      FTM         QTM
--------      ---         ---
    0           1           1
    1          15          10
    2         178          85
    3        1982         744
    4       21041        6194
    5      204732       49009
    6     1645039      360175
    7     8477633     2277947
    8    12917628     9529222
    9     1061851    11407300
   10         140      699495
   11                      58
         --------    --------
total    24330240    24330240

Average FTM: 7.5308
Average QTM: 8.3959

 

[miniGOINGS]

Seeing these threads makes me wonder if this could be useful for FMC.

 

[Cride5]

I've also now computed optimal EOCross

Thanks again, that's great. So based on the numbers posted by Johannes91 for 4x <R,U,L> F2L slots the average for optimal EOCross based F2L is ~35.63 moves HTM.

 

[jazzthief81]

Also, if you have the time it would be interesting to know the average optimal move-count for solving both sides simultaneously...

Considering both left and right blocks greatly increases the number of puzzle states to deal with. So no, it is not a simple change.

I already have a partial answer to this problem:

0	         1
1	         6
2	        27
3	       135
4	       624
5	      2963
6	     13958
7	     65487
8	    305078
9	   1403488
10	   6404528
11	  28587553
12	 123866634
13	 507806834
14	1876501812
15	5443124864
16	8684416076
17 	...

The search is still running and I think it will take another 10 days before it has generated the full table.

I started this project 6 weeks ago but I had to restart the search twice. The first time it completed but the numbers didn't add up because of a bug in the code. The second time it nearly finished but my trusted iMac blew up I'm now running it for a third time on a slightly lower end laptop.

I had to come up with a few tricks because the full pruning table doesn't fit in memory (20,575,296,000 cases). At each level, the algorithm dumps sorted binary files to disk that contain all children of the previous level. Then it compacts all the files by removing all the duplicates and states that were already encoutered at a previous level.

I also did a bunch of other ZZF2L move analyses, basically all possible strategies for splitting up the two 3x2x1 blocks in separate steps. I was going to save them for an article series on that topic when the God's Algorithm analysis was going to be finished so I could use that as a yardstick. I think most of it has already been done by other people.

 

[Cride5]

... only about 4 billion cases to go!

Great work so far though, it will be nice to see the final result. I'm guessing average will be about 15.7 moves.

I'm crossing my fingers for your laptop, I hope it survives!

EDIT: Your analysis on the other ZZ F2L move counts would certainly be useful in creating a more complete picture. The figures I posted for 2 blocks separately were only an estimate based on 100 solves, as were those posted by Stephan.

 

[jazzthief81]

Here are some more results for solving 3x2x1 blocks after EOLine:

First 3x2x1 block (fixed side)    First 3x2x1 block (any side)    Second 3x2x1 block
HTM using R,U,L moves             HTM using R,U,L moves           HTM using R,U moves  

      0          1                      0         113399              0          1    
      1          3                      1         340185	      1          3    
      2          9                      2        1020515	      2          9    
      3         48                      3        5442002	      3         27   
      4        182                      4       20624126	      4         73   
      5        769                      5       86992281	      5        215  
      6       2938                      6      330431260	      6        614  
      7      10783                      7     1188117385	      7       1730 
      8      35330                      8     3629618668	      8       4374 
      9      89070                      9     7393787191	      9       9620 
     10     136195                     10     6613172985	     10      17082
     11      77681                     11     1281665000	     11      17005
     12       9769                     12       23963478	     12       5593 
     13        102                     13           7525	     13        344  
								     14         10   

     Average  9.69                     Average      9.09             Average 10.03

The first table confirms the results obtained by Bruce for building a specific 3x2x1 block. The second table is for building whichever of the left and right 3x2x1 blocks is the shortest.

 

[jazzthief81]

The analysis for solving the complete F2L in one step finished about a month ago and I've finally gotten around to writing up a post:

http://qblog.be/2010/04/zzf2l-move-count-analysis/

More to follow soon...

 

[Cride5]

Wow, great to see the results. A huge thanks for doing this Lars. I hope your laptop is OK

It would be interesting to compare this to the optimal move-count for solving all-four Fridrich slots simultaneously. Do any stats for this exist?

... I'm guessing average will be about 15.7 moves

.. yay, only 0.06 moves out

 

[jazzthief81]

Wow, great to see the results. A huge thanks for doing this Lars. I hope your laptop is OK

Yeah, the laptop is fine! The desktop has been relegated to the graveyard though.

It would be interesting to compare this to the optimal move-count for solving all-four Fridrich slots simultaneously. Do any stats for this exist?

I was thinking just that! I could use the same approach as I did for ZZF2L, the difference being that with ZZF2L all intermediary states are also possible starting positions, which is not the case with 4 slots because you break up the cross all the time.

This makes it a little bit more "complicated" at first sight, but I guess it's mostly just a little bit different. The number of cases is also signifcantly lower (3,657,830,400).

It also would be good to come up with some kind of an "efficiency ratio", meaning the ratio between the average optimal solution and the average solution of a human solver. And then you could compare those efficiency ratios between different methods.

My hunch is that Fridrich would score rather badly because you tend to break up and restore things all the time. This is something I already alluded to in my blog post.

 

[Stefan]

Meh. Fridrich's freedom of movement is limited by cross, ZZ's is limited by edge orientation. I predict optimal Fridrich F2L will average *fewer* moves.

 

[jazzthief81]

Meh. Fridrich's freedom of movement is limited by cross, ZZ's is limited by edge orientation. I predict optimal Fridrich F2L will average *fewer* moves.

So do I. There area less pieces to solve and more faces you can turn. It's almost certain it will be less moves.

But I think by breaking it up into steps, which is what all people do, Fridrich becomes a lot more inefficient and ZZ doesn't suffer from that faith that much.

 

[Stefan]

I think I somewhat did that before, 4-step Fridrich F2L averaged fewer moves than 4-step ZZ-F2L.

 

[Cride5]

But I think by breaking it up into steps, which is what all people do, Fridrich becomes a lot more inefficient and ZZ doesn't suffer from that faith that much.

I would tent to agree with this. A Fridrich solve normally involves: (1) build pair, (2) open-slot, (3) insert pair, then (4) close slot. In ZZ once I've built my 1x2x2, the slot doesn't necessarily get closed straight away, and in fact it is sometimes more efficient to leave it in the open position so that the final 1x1x2 can be inserted directly, without 'opening' the slot. Keeping track of the state of each side is pretty easy.

 

[ravenguild08]

I'm looking for the statistics to complete F2L from EOLine (edges already oriented and DF and DB placed). EOLine takes ~6.127 moves avg and 9 moves max (FTM) to do optimally.

That number 6.127, how was it obtained? Is it for a predefined color scheme (e.g. the Line is the white/blue+white/green edges), or is it color neutral? I've been refining my EOLine and averaging closer to 8 or 9, and it's bugging me...