• 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
cubizh
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
kinch2002
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
Korbinification
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
kinch2002
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
cubizh
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
cubizh
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.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,830
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
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?
 

cubizh

Super Moderator
Staff member
Joined
Oct 2, 2011
Messages
602
Location
Portugal
WCA
2014GOME07
YouTube
cubizh
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
qqwref2
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?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
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
cubizh
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
qqwref2
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,694
Location
UK
WCA
2015RIVE05
YouTube
mark49152
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
210
WCA
2016GOHT01
YouTube
channel/UCeru241De87ZCpPGLb4ZS0g
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?
 
Top