Method-Specific God's Number?

[goodatthis]

Recently I was thinking to myself, if a method is just a bunch of steps that solve the cube, you could figure out the optimal number of moves for the method just by solving each individual step optimally. So for CFOP, if a cross can be solved optimally in N moves, and each F2L pair can be solved optimally in X amount of moves, and OLL can be solved optimally in Y moves, and PLL can be solved optimally in Z moves, then we could figure out the optimal number of moves constrained by the steps of the CFOP method.

I think that we would find that methods with larger steps, such as blockbuilding methods such as Roux or Petrus, would have much shorter optimal solutions, since the more compartmentalized you make a method, the less creative you can get, and the less gain you get from an optimal solution.

So would anyone like to find the optimal number of moves constrained by the steps of methods like Roux, Petrus, CFOP, or ZZ? (Other methods too!)

 

[Christopher Mowla]

So would anyone like to find the optimal number of moves constrained by the steps of methods like Roux, Petrus, CFOP, or ZZ? (Other methods too!)

Some official analysis has recently been done in a research endeavor by Joseph Miller which helped him earn his Phd.

I provided a link to his result in this post. (I sounded quite rude in that post, despite that that wasn't my intent, and for that, I apologize, Joseph.)

On pages 48-49 of the PDF (pages 41-42 of the paper) are the results he found for color-fixed (I'm assuming "color-fixed" means not solving as "color neutral") variants of the Fridrich, Roux, and Petrus 3x3x3 solving methods.

He explained that "a human needs to commit to memory a large number of algs to achieve the move-count means from our tables [...]", and he mentioned that he took move cancellations into account. There are 2-3 letter acronyms in the tables explaining what "type" of move cancellations were considered. Just to save you some trouble of looking up what the acronyms mean,

NC = "non-cancellation",
CC = "commutative cancellation" -- commuting moves at step interfaces,
SC = "simple cancellation" (only considers cancellation one move deep and does not exploit commuting moves as does CC.),
BPC = "best possible cancellation".

Clearly from the tables, move cancellations do not make much of a difference (which is to be expected).

It looks like, in the BPC column, the average number of moves is anywhere from 43 moves to 53 moves (HTM), considering all the variants he studied of all 3 methods.

 

[Stefan]

Whoa, my thesis has been referenced in a dissertation (Lars' cross study and others as well). Just sad he falsely says I did only 300 solves per method.

Looks like he used fixed/all orders of the F2L slots, though. I did them in greedy order, always solving a shortest slot next. I think this is closer to real speedcubing, and in my tests it was 2.05 moves shorter. Results in my thesis start on page 31. It doesn't do LL, but for pure CFOP, that's independent anyway. Adding my 28.85 for CrossF2L and Bernard Helmstetter's 9.22+11.21 for OLL+PLL you get 49.28 moves on average. Add those 2.05 and you're around Joseph's 51.6 moves. Nothing to do with God's Number, as it's just averages and not worst cases, but from my table on page 31 it looks like high 30s for CrossF2L. Which would be an upper bound, as I was really greedy and didn't check alternative equally long solutions for subgoals.

So for CFOP, if a cross can be solved optimally in X moves, and each F2L pair can be solved optimally in X amount of moves, and OLL can be solved optimally in X moves, and PLL can be solved optimally in X moves, then we could figure out the optimal number of moves constrained by the steps of the CFOP method.

Not sure how exactly you mean it, but if you meant to just treat the steps separately and then add their worst numbers (which btw shouldn't all be called X, as they probably differ), I think that's too simple and the result would be too high.

I'd define the optimal solution length for one scramble as the length of a solution where each step is done optimally. For example in fixed color CFOP, you must start with an optimal cross solution, but if there are several, any of them are allowed. And they'll likely allow different continuations and all of them must be considered. Same for F2L pairs - several remaining pairs can have the same optimal length, and each pair can have several solutions of that length. All of these and their continuations should be considered. Same with OLL - if there are several shortest algs for the case, all need to be considered (and one with shortest following PLL will win). And then God's Number is the maximum optimal solution length of all scrambles.

 

[cuBerBruce]

Looks like he used fixed/all orders of the F2L slots, though. I did them in greedy order, always solving a shortest slot next. I think this is closer to real speedcubing, and in my tests it was 2.05 moves shorter. Results in my thesis start on page 31. It doesn't do LL, but for pure CFOP, that's independent anyway. Adding my 28.85 for CrossF2L and Bernard Helmstetter's 9.22+11.21 for OLL+PLL you get 49.28 moves on average. Add those 2.05 and you're around Joseph's 51.6 moves. Nothing to do with God's Number, as it's just averages and not worst cases, but from my table on page 31 it looks like high 30s for CrossF2L. Which would be an upper bound, as I was really greedy and didn't check alternative equally long solutions for subgoals.

I note that Helmstetter's PLL figure does not take AUF into account. You should either count AUF as an extra step (0.75 moves on average, 1 move worst case), or consider PLL+AUF as a single step.

I also note that standard F2L algs generally assume a certain position for the rotation of the last layer (if applicable), and one must be careful that one doesn't omit counting the AUFs to set up the last layer for the alg. (I'm not meaning to suggest that Stefan's 28.85 figure isn't accurate, as I assume he used searches rather than canned algs.) In general, needing to preserve slots already solved may affect what's optimal for a standard F2L case. You have more flexibility in solving the first slot than the last slot. And the standard 41 cases do not directly cover cases where a piece is in a wrong slot.

I'd define the optimal solution length for one scramble as the length of a solution where each step is done optimally. For example in fixed color CFOP, you must start with an optimal cross solution, but if there are several, any of them are allowed. And they'll likely allow different continuations and all of them must be considered. Same for F2L pairs - several remaining pairs can have the same optimal length, and each pair can have several solutions of that length. All of these and their continuations should be considered. Same with OLL - if there are several shortest algs for the case, all need to be considered (and one with shortest following PLL will win). And then God's Number is the maximum optimal solution length of all scrambles.

I've written a program that does that basically does this (for a specified scramble). For CFOP, slots would be solved in any order except that the 2nd slot either had to be either adjacent to or (diagonally) opposite the first slot (user's choice). However, the number of combinations generated for CFOP was generally so large that doing a full search wasn't very feasible. (Petrus-like methods, on the hand, were quite feasible.) I also note that my program looked for cancellations in the final solution. In some cases, a solution for one step might totally cancel out the previous step. So the length of a solution was generally shorter than the sum of the lengths for its steps.

I note that using sub-optimal solutions for steps could get you better cancellations in some cases, and could result in getting a shorter overall best solution. But if using sub-optimal solutions for steps and applying cancellations is taken to an extreme, we should eventually find an overall optimal solution, rather than a solution that actually seems to be connected with the method. So if we want to define a "God's number" for a method, we need to be careful about what we allow for solutions for individual steps and if we allow cancelling moves across steps.

 

[AvGalen]

But why? Why would you want to know exactly how many moves the most horrible solve with any method would take when you also would have to define that method much more exact than anyone would ever use it?

I know this subforum is about theory, but wouldn't a "roughly 50" be good enough to cure your curiosity?

 

[goodatthis]

Why not? For me, this was less of an exact, one-answer question, and more of a rhetorical, discussion-sparking question. I think it's interesting to see factors that lie behind methods that no one would ever think about during a speedsolve. If all I wanted to know was the optimal number of moves for cross-F2L, I probably would have posted it in the one answer question thread.

 

[Stefan]

I note that Helmstetter's PLL figure does not take AUF into account.

Right, I didn't know whether/how Helmstetter and Miller handled AUF, whether they use weighted averages, and at least my experiment was inexact because it only did 10000 solves. I just meant it as a rough check, don't want to spend the time trying to be exact.

I also note that standard F2L algs generally assume a certain position for the rotation of the last layer (if applicable), and one must be careful that one doesn't omit counting the AUFs to set up the last layer for the alg. (I'm not meaning to suggest that Stefan's 28.85 figure isn't accurate, as I assume he used searches rather than canned algs.) In general, needing to preserve slots already solved may affect what's optimal for a standard F2L case. You have more flexibility in solving the first slot than the last slot. And the standard 41 cases do not directly cover cases where a piece is in a wrong slot.

Yes, I did fresh searches. AUFs count and unsolved slots are exploited.

I've written a program that does that basically does this (for a specified scramble)

Nice, do you have some statistics for this?

I note that using sub-optimal solutions for steps could get you better cancellations in some cases, and could result in getting a shorter overall best solution.

Yes, if you allow sub-optimal steps then the best solution will usually be something like an 18 moves cross . Hence my insistence that steps must be optimal. Good point about cancelling moves between steps. Not sure what to do about that...

But why? Why would you want to know exactly how many moves the most horrible solve with any method would take when you also would have to define that method much more exact than anyone would ever use it?

For CFOP I'd pretty much define it as "Solve cross, solve the four F2L pairs in any order, solve OLL, solve PLL". I don't think that's much more exact than anyone would ever use...

 

[AvGalen]

For CFOP I'd pretty much define it as "Solve cross, solve the four F2L pairs in any order, solve OLL, solve PLL". I don't think that's much more exact than anyone would ever use...

But people would insert the last pair differently to change edge orientation, build non-optimal crosses to optimize for fingertricks/lookahead/x-cross/edge-orientation, use different algs (with different movecounts) for the same OLL/PLL, etc. The resulting number from any theory would have nothing to do with how people would actually solve. Just take the way people do U-perm and you will already see a deviation from the theoretical number that is much bigger than other deviations that have been discussed here. Some people even do U, U-perm, U' while others do y U-perm for the same case.
It was interesting to read about the average number of moves for pairs with fixed order and with different greedy approaches because that was a theoretical approach to a theoretical problem that you could define and as such the resulting number had meaning. Finding Gods number for CFOP while there is a big variation in how people do CFOP would not have an interesting result.

 

[Stefan]

The resulting number from any theory would have nothing to do with how people would actually solve.

Well, it's not called people's number.

And I don't think it would have nothing to do with it.

It was interesting to read about the average number of moves for pairs with fixed order and with different greedy approaches because that was a theoretical approach to a theoretical problem that you could define and as such the resulting number had meaning.

Um...

First of all, the proposed God's number is just as much a theoretical approach to a theoretical problem that you could define and as such, according to you, the resulting number should have meaning.

Also, that previous study used optimal substeps as well, solving like people don't. Why did you like it there but despise it here? I don't get it.

 

[AvGalen]

I considered the previous study a theoretical study in a theoretical domain, which is perfectly fine with me.
Making a theoretical study about a practical domain (CFOP) means the study should adjust to the practical domain to be useful. If it changes the practical domain into the theoretical, by applying arbitrary limitations that don't fit with the practical domain, it will not produce a useful result. Maybe my thinking is too limited or too practical, that is why I asked "why".
(and I am fully aware of the "eventually all theoretical math becomes applied math" and people can of course use their time for whatever they want)

 

[Stefan]

I considered the previous study a theoretical study in a theoretical domain, which is perfectly fine with me.
Making a theoretical study about a practical domain (CFOP) means the study should adjust to the practical domain to be useful.

Are we talking about different things? If I understand you, CFOP is practical but CF theoretical? Why? I don't see the difference. Particularly because I stopped after CF and didn't do the whole CFOP only because my program wasn't good enough, not because there's some fundamental difference (I assume you meant my study, sounds like it).

 

[AvGalen]

Are we talking about different things? If I understand you, CFOP is practical but CF theoretical? Why? I don't see the difference. Particularly because I stopped after CF and didn't do the whole CFOP only because my program wasn't good enough, not because there's some fundamental difference (I assume you meant my study, sounds like it).

I don't remember cross being a part of your study. I only remember the F2L's (Humus, right?). I am saying all this from memory from ages ago. I remember that length for pairs went up as freedom of choice got reduced. The interesting thing about your study was not "Gods number for CF is 32 moves" but "given freedom to do whichever pair you do first the distribution is '4.5, 5, 6, 7' and with a fixed order it is 5.5, 6, 7, 8' (I am making up the numbers as the exact value wasn't interesting for me but the trends were. I don't believe I am far off with the numbers though).

 

[Lucas Garron]

Are we talking about different things?

I understand Arnaud and agree with him.

While at first glance it seems reasonable to ask for the maximum length a CFOP solve would take if you had perfect foresight, any actual calculation will 1) will have arbitrary limitations compared to things that are common for CFOP users, and 2) not mean very much. In particular, arbitrary decisions in the very first step will have significant but mostly meaningless consequences for the rest of the solve (no, I don't think it's "Realistic" to restrict yourself to optimal cross – and even then there are often a few options, even for a fixed color), and I'm not sure we could learn much from that. (Except what we already know from FMC: Being able to try lots of solution paths is more likely to yield a skip.)

I'd rather have people working on CFOP solvers that generate few rotations/lots of skips/whatever people like, and running that on lots of scrambles to see how easy a solve for a "typical" scramble is.

 

[AvGalen]

Let's make it a challenge: for CFOP the maximum length would be the longest PLL, OLL, 4th pair, 3rd pair, 2nd pair, 1st pair and cross all combined. We already know each of these substeps. Now the challenge for finding the upper bound for the maximum length would be to prove that there is a scramble that has a worst case (8 moves) cross and if you perform it you would always get a worst case 1st pair without cancellation, etc. If such a scramble exists we already have Gods number. In that situation it is extremely likely that nobody would solve it like that though and changing (adding) one move somewhere would already change so much that the rest of the solve would be much less moves. It will also be very hard to adjust for the fact that even optimal E can be done in 4 different ways.

...and none of the would mean anything for an actual comparison between CFOP and other methods or for the movecount of a speedcuber.

(I might have been one of the only people in the world who learned/found/knows optimal PLL-algs and used them during speedsolving. I deeply regret the day that I found an optimal Y during 4th pair insertion L' U' L F2 R' D R U R2 D' R2 U' F2 and started using that as my PLL. It has 5 different faces in the first 6 moves!)

we somewhat had this discussion before: http://www.speedsolving.com/forum/s...-PLL-288-cases&p=126715&viewfull=1#post126715

 

[Stefan]

The interesting thing about your study was not "Gods number for CF is 32 moves" but "given freedom to do whichever pair you do first the distribution is '4.5, 5, 6, 7' and with a fixed order it is 5.5, 6, 7, 8' (I am making up the numbers

Yes, I did compare two ways. The same could be done here, like compare God's Number for pure CFOP vs. God's Number for certain advanced CFOP versions.

But yes, I do find greedy averages more interesting than perfect forsight worst cases. I agree that probably not much can be learned from the latter.