• 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!

"Most common best # of 4BLD centers solved" problem

cubizh

Super Moderator
Staff member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
I’m not sure if this was done before, but I thought I’d give it a try.

Introduction:

The first step in doing 4BLD is to choose an orientation for the cube.
Usually this step is done trying to maximize the number of solved centers to reduce both memorization and execution.
However, there are 24 different possible orientations for the cube and it’s not always trivial to see which solution is best, especially if there is no bar on any face, or if there are multiple ones.
So, in order to do this automatically, for a given center scramble, I made a program to check for each of the 24 orientations, which was the best, and how many centers were solved for every orientation.
But this lead me to think about the following problem:

Problem:

What is the most common number of centers solved for any given scramble. Since there are no restrictions for centers, the number of possible combinations is the colossal number of 24!/4!^6 = 3246670537110000 (since centers of the same color are equivalent) which is a very big number to check all cases. I didn’t want to go deeper in weeding out isomorphic scrambles. I just thought I’d test with random (or pseudo-random) scrambles with the only restriction is being different from one another.

Results:

The sample I used had 100 million (100.000.000) different scrambles, which is ridiculously small compared to the total number of possible scrambles (namely 0.00000308% of the whole thing).
For each scramble, it was tested what was the highest number of solved centers for all possible orientations, and in the end scrambles with the same ammount of maximum centers solved were summed to see what was their frequency.
Here are the results I achieved:

Number of Solved Centers Number of Scrambles
5 165268
6 7698835
7 31876637
8 33138395
9 17870290
10 6680225
11 1965825
12 482093
13 100858
14 18330
15 2833
16 359
17 48
18 4

Since the values are of very different order of size, I created a logaritmic chart:

Discussion:
From the results obtained, it's easy to see that the most common optimal 4BLD solved centers is 8, very close to 7.
Another thing you can see is you always have more than 4 centers solved for any given orientation, the minimum being 5.
And having 18 centers solved (6 unsolved) is so rare for a random (or pseudo-random) case that only happened 4 times in 100 million.
 
Last edited:

kinch2002

Premium Member
Joined
Dec 22, 2008
Messages
2,504
Location
Guildford! UK!
WCA
2009SHEP01
YouTube
Visit Channel
Nice research. I can't find where I posted something before on this. But basically I'm not a coder so I made a little* thing in Excel and ran a load of scrambles through (thousands). I'd like to compare my results to these ones. Anyone remember?

* Actually it was a pretty epic spreadsheet and took me a good few hours
 

DrKorbin

Member
Joined
Aug 10, 2011
Messages
707
Location
Russia, Moscow
WCA
2011GRIT01
YouTube
Visit Channel
Nice research. I can't find where I posted something before on this. But basically I'm not a coder so I made a little* thing in Excel and ran a load of scrambles through (thousands). I'd like to compare my results to these ones. Anyone remember?

* Actually it was a pretty epic spreadsheet and took me a good few hours
I only can find this post and the next one.
 

kinch2002

Premium Member
Joined
Dec 22, 2008
Messages
2,504
Location
Guildford! UK!
WCA
2009SHEP01
YouTube
Visit Channel
Hmmm yeah I don't have average centres solved there. Oh well.
Your results will be more accurate anyway :)
As I ran 20k scrambles and I should have had 0.01 17 centre scrambles, so it's cool that I found one.
 

cubizh

Super Moderator
Staff member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
More precisely, 24!/4!^6 = 3246670537110000.
Thanks for the correction, I didn't account for the same color centers

Well, I did. Also you can find a bit more research here and here.
I admit I searched the forum before creating this thread, and I couldn't find your posts, so thank you for pointing them out.
It's nice to see we pretty much reached the same conclusion, which is good.
How many scrambles did you try?
 

cubizh

Super Moderator
Staff member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
As I ran 20k scrambles and I should have had 0.01 17 centre scrambles, so it's cool that I found one.
I thought about doing Excel, but generating 100 million scrambles which would be impossible to do in there in a couple of hours.
A funny fact is I generated this huge ammount of random scrambles, but I only had 1 repeated scramble out of the whole bunch. :eek:
Which was fixed.
 

cubizh

Super Moderator
Staff member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
I notice you got rather a lot of 5-center scrambles, but no 4-center scrambles.

So of course it makes me wonder, are 4-center scrambles impossible? Or just extremely rare? Can anyone find one, or prove they don't exist?
I can keep going for more and more scrambles, (I didn't time it, but took me around 7 hours to create/parse 100 million different center scrambles) to try to find it, but given the fact that it just cuts to 5 and 5 being in a rather large ammount comparatively, it's probably not possible. Would be nice to see that mathematically proven.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,830
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
That could mean it's impossible, but it could also mean that a 4-center position is so constrained that only a few exist, and they are very rare compared to being "almost" a 4-center position.

Could you post a couple of sample 5-center positions to give us an idea of what they tend to look like?
 
Joined
Apr 23, 2010
Messages
1,391
Location
Scotland, UK
WCA
2009SHEE01
YouTube
Visit Channel
Huh, I did a 4BLD earlier with 20 centre targets (3 solved), I feel silly now. I guess I need to practice picking an orientation. Has anyone ever looked into a system for picking an orientation that quickly finds a (near-)optimal solution?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
Visit Channel
I can keep going for more and more scrambles
You could do local search, like starting with a random state but then instead of throwing it away and trying an independent random state, try all those reachable from the first by let's say swapping two stickers, and among all these neighbour-states, continue with the one with fewest centers solved. And only start with a new independent random state after reaching a local minimum.

qq are you sick? Usually you answer such questions, don't ask them :p
 

cubizh

Super Moderator
Staff member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
Visit Channel
Could you post a couple of sample 5-center positions to give us an idea of what they tend to look like?
Here's 10 scrambles that the program gave me.
Hope you understand the notation.
UP LEFT FRONT RIGHT BACK DOWN
BBGG GOBY RORW OBYG WRWY WOYR
BBGG OBRG YORW BGYW OWRY RWOY
BBGG RORW BGOY WWRY BGYO RWYO
BBGG YOOR RWOR YOGB RGWB WWYY
BBGG YWGB RYOW RGOB WYOR OWYR
BBGO BGRY OGRY RRWB OGYW WYWO
BBGO BOWY YRWG WBOR WRGG ROYY
BBGO BOYG YRRG RWYO GBWR WWYO
BBGO BRBO GWGR WYOY YWRG ROWY
BBGO BRYG RBGW WOGY YOWR OYRW
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,830
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I just had a thought about this. Each individual center piece must be correct on exactly 4 of those orientations, so there are exactly 96 centers correct over all the orientations. But we can also add up the number of centers correct in each of the 24 orientations and get this same number. The only way for the maximum correct centers in any orientation to be exactly 4 is if *every* orientation had exactly 4 centers correct - otherwise, if some had less than 4, there would be fewer than 96 total correct centers.

Looks like I was correct about that "so constrained that only a few exist" thing. If any 4-correct-center positions exist they probably have a pretty strict setup where any deviation will change the number of correct centers in two or more orientations. Of course, this argument also proves there can be no 3-correct-center positions.

Thanks for the output, cubizh - I'll take a look at those.


EDIT: nvm, something went wrong :(

EDIT2: I set up a local search to minimize the total discrepancy (defined as the sum of |x-4|, with each x being the number of centers correct at one of the orientations). Unfortunately, it ended up with the following configuration, which has a total discrepancy of 16 and a best-case of 6 centers correct:
up = RBOG
left = GOBY
front = BGRW
right = OBYG
back = WRWY
down = WOYR
If my program is correct, there should be no lower-discrepancy positions within three 2-swaps of this position...
 
Last edited:

mark49152

Super Moderator
Staff member
Joined
Oct 29, 2012
Messages
4,703
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
I'm thinking about reorientation in 5BLD and wondering how the analysis above might apply to 5x5.

Is it reasonable to assume similar proportions? So there would be an average of 8 solved centres in default orientation, and in most cases 14-16 solved centres in optimal orientation?

How would this be affected by the fact only half of the orientations can be chosen due to centre parity?
 

pinser

Member
Joined
Feb 12, 2014
Messages
209
WCA
2016GOHT01
YouTube
Visit Channel
I'm thinking about reorientation in 5BLD and wondering how the analysis above might apply to 5x5.

Is it reasonable to assume similar proportions? So there would be an average of 8 solved centres in default orientation, and in most cases 14-16 solved centres in optimal orientation?

How would this be affected by the fact only half of the orientations can be chosen due to centre parity?
I've been wondering the exact same thing. Gut instinct tells me it's not worth it, but I could be wrong.
I was planning to write a script and get some numbers, but I'm kinda swamped with exams right now.
I should get to it within the next few weeks, but if someone else did it that would be great too.

Also, off-topic, but what's your +-centers buffer?
 

Want to hide this ad and support the community?
Top