• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

5x5x5 centres with random-move scrambles

Joined
Dec 24, 2015
Messages
1,480
Likes
940
Thread starter #1
tl;dr: centres are significantly easier with 60-random-move scrambles, so stop using that.

In 2013, @cuBerBruce generated the distance distribution for solving a single face's centres in multiple metrics. I have confirmed the results for OBTM (since my code supports only OBTM).
Code:
total states: 112911876 (112911876 legal)
distance 0: 1 nodes
distance 1: 12 nodes
distance 2: 190 nodes
distance 3: 3210 nodes
distance 4: 47444 nodes
distance 5: 635642 nodes
distance 6: 6870327 nodes
distance 7: 41671278 nodes
distance 8: 59387592 nodes
distance 9: 4296076 nodes
distance 10: 104 nodes
average distance: 7.528574
I generated a million random states and measured the following statistics: mean move count for optimal first centre with fixed colour (6 million samples), for optimal first centre with dual CN (3 million samples), and for optimal first centre with full CN (1 million samples). The first one agrees with the theoretical distribution, of course, but we reproduce it as a sanity check.

These stats have also been measured with one million random-move scrambles of lengths from 50 to 100 (inclusive), in increments of 5.

(Note that as only 1000000 scrambles were used for each category, the results should be treated as having only three decimal places of accuracy.)

scramble type

fixed

dual CN

full CN

random state

7.529103

7.177083

6.662767

50 moves

7.213838

6.820150

6.210132

55 moves

7.293460

6.908271

6.326780

60 moves

7.351421

6.972744

6.410915

65 moves

7.392481

7.019370

6.472139

70 moves

7.424484

7.055387

6.516806

75 moves

7.447765

7.082416

6.551436

80 moves

7.465664

7.103329

6.576018

85 moves

7.478492

7.117689

6.593856

90 moves

7.489543

7.130386

6.608734

95 moves

7.497782

7.140359

6.620608

100 moves

7.503685

7.147343

6.629239



TNoodle and most timing apps generate scramble sequences with 60 moves by default, but this is clearly inadequate—the mean move count for full CN is significantly lower than with random-state scrambles.

Even with 100 random moves, it is significantly more likely to get a scramble with a first centre solvable within 4 moves compared to a random-state scramble (0.3294% vs 0.2709%), although this is still a lot less bad than just 60 random moves (1.5542%). This discrepancy in the distribution persists until around 170 random moves, at which point the difference is drowned out by sampling error.

Using 80 moves for random-move scrambles seems like a reasonable compromise between the scrambling not taking forever and having a smaller deviation from random-state scrambles, in lieu of the existence of an actual 5×5×5 random-state scrambler. (A random-state scrambler would generate scramble sequences of around 85 moves anyway—using a random-move scramble longer than that would be pointless.)
 

Attachments

Last edited:
Joined
Dec 24, 2015
Messages
1,480
Likes
940
Thread starter #2
"But," you retort, "I don't want to do longer scrambles. 60 moves already provides plenty of room for misscrambles to happen, which totally suck. Increasing scrambles to 80 moves would only make this much worse, even if this is a 'compromise'."

Here's some good news! If you apply a 3×3×3 random-state scramble with wide moves first, the centres converge to a uniform distribution much more quickly. (Actually, the rate of convergence is about the same, but it starts off much closer to uniform.)

scramble type

fixed

dual CN

full CN

random state

7.5291

7.1771

6.6628

wide random

7.3502

6.9938

6.4905

wide random + 5 moves

7.4538

7.0991

6.5855

wide random + 10 moves

7.4906

7.1374

6.6221

wide random + 15 moves

7.5089

7.1564

6.6409

wide random + 20 moves

7.5182

7.1658

6.6502

wide random + 25 moves

7.5231

7.1707

6.6557

wide random + 30 moves

7.5259

7.1739

6.6593

wide random + 35 moves

7.5270

7.1749

6.6603

wide random + 40 moves

7.5270

7.1746

6.6601

wide random + 45 moves

7.5274

7.1751

6.6610

wide random + 50 moves

7.5284

7.1758

6.6609

wide random + 55 moves

7.5283

7.1760

6.6622

wide random + 60 moves

7.5283

7.1759

6.6619

wide random + 65 moves

7.5287

7.1763

6.6623

wide random + 70 moves

7.5283

7.1763

6.6622

wide random + 75 moves

7.5288

7.1764

6.6624

wide random + 80 moves

7.5283

7.1758

6.6618



As can be inferred from the above table, for all practical intents and purposes, the centres are fully randomised after 40 random moves… which corresponds to a ~60-move scrambling sequence, since the 3×3×3 random-state scramble would take around 20 moves. As an added bonus, the midges and corners are also (exactly) uniformly distributed.

I've also generated statistics for random-move scrambles biased towards wide moves, but that turned out to be much less of an improvement than I had expected. I'll edit this post to include the table later.

"But," you retort again, "why should anyone care about a difference that is literally just a quarter of a move on average?" The answer to this is that you're asking the wrong question—if it's easy to ensure that the difference is less than a thousandth of a move on average, why wouldn't you just do that?
 
Last edited:
Joined
Nov 11, 2014
Messages
1,079
Likes
635
Location
Gauteng, South Africa
WCA
2014GRAY03
#3
That's pretty cool. I love how the 3x3 stage guarantees no bias for corners and midges. My concern is the wings. What's the distribution like for them? (probably not bad - I think you'd have to look at moves required to pair all wings with thier matching partner ignoring midges to get a meaningful measure)

I also wonder how well this can be extended to higher order cubes... For example on 7x7, if you do a 3x3 scramble with triple layer turns, then another 3x3 scramble with double layer turns, then 60 random moves, would that be better than the current 100 random move scrambles? I feel it probably would be...
 
Joined
Dec 24, 2015
Messages
1,480
Likes
940
Thread starter #4
It's not immediately clear how best to analyse the wings, which is part of why I didn't bother. On one hand, it's not really relevant, because most people use redux and even if there was some pattern to the wings, it would get mostly destroyed after you finish the centres.

On the other hand, 5BLD. (And also Yau5, Hoya5, cage, etc.)

Hmm. There are a few things we could look at. One is, like you suggest, to look at how many moves are needed to pair the wings (ignoring midges and centres), but I'm not sure this is useful or representative. Optimal edge pairing on 444 takes like 15 moves and is nothing like what human solvers do. I think it might be more worthwhile to look at cycle structures, but I expect random-move scrambles to converge to a uniform distribution fairly quickly anyway.

For 777, I already do something like what you say. I set csTimer to generate a six-cube relay, and treat them as triple, double, single, triple, double, triple layer scrambles. I have no idea whether this is actually good, but I'm moderately certain it's better than just 100 random moves. Centre blocks seem(?) to be rarer, but that might just be placebo.
 

jfly

Member
Joined
Aug 23, 2008
Messages
226
Likes
14
Location
California
WCA
2005FLEI01
YouTube
jflysohigh
#5
I could see us switching to random state 5x5 scrambles specifically for 5x5 blindfolded. It would still be a pain to scramble, but the solves are also way slower than a 5x5 speedsolve. Granted, I have no idea what's feasible in terms of 5x5 random state, but if 85 move random scrambles can be generated in a reasonable amount of time, then I'd love to see that added to TNoodle.
 
Joined
Dec 24, 2015
Messages
1,480
Likes
940
Thread starter #6
I could see us switching to random state 5x5 scrambles specifically for 5x5 blindfolded. It would still be a pain to scramble, but the solves are also way slower than a 5x5 speedsolve. Granted, I have no idea what's feasible in terms of 5x5 random state, but if 85 move random scrambles can be generated in a reasonable amount of time, then I'd love to see that added to TNoodle.
I do have a solver lying around on my hard disk, but the code is Kind of Awful and I've been putting off a rewrite for quite some time. It takes anywhere from two seconds to a minute per solve (median is around 15 seconds iirc), but it's also very memory heavy (4 GB of RAM required).
 

mark49152

Super Moderator
Staff member
Joined
Oct 29, 2012
Messages
4,654
Likes
3,167
Location
UK
WCA
2015RIVE05
YouTube
mark49152
#7
3x3 random state scramble followed by ~40 random moves sounds like a good compromise. Easy to implement and scramble length wouldn't increase by much.
 
Joined
Aug 23, 2008
Messages
226
Likes
14
Location
California
WCA
2005FLEI01
YouTube
jflysohigh
#9
I do have a solver lying around on my hard disk, but the code is Kind of Awful and I've been putting off a rewrite for quite some time. It takes anywhere from two seconds to a minute per solve (median is around 15 seconds iirc), but it's also very memory heavy (4 GB of RAM required).
Ok. That timing sounds bearable, but the memory usage would be a problem. Another thing to consider is how long it takes to generate any pruning tables/whatever you need.

We already do random state 4x4 in TNoodle, so AFAIK there's nothing to worry about here. Did you have something in particular in mind you were asking about?
 
Joined
Dec 24, 2015
Messages
1,480
Likes
940
Thread starter #10
Ok. That timing sounds bearable, but the memory usage would be a problem. Another thing to consider is how long it takes to generate any pruning tables/whatever you need.
I haven't run the table generation code in forever, but @dwalton76 mentioned that it took over half an hour on his computer. There's a slightly out of date compiled version on his GitHub account if you want to try it out. (And lookup tables in case you don't want to wait for them to be generated.)

I have ideas on a low-resource variant of the algorithm, and I just need to get less lazy and actually implement it.
 
Top