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



## cubizh (Sep 21, 2013)

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	



Spoiler: Frequency Chart (Line-based)











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


Spoiler: Logaritmic Chart













Spoiler: Distribution Chart (Pie-based)











*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.


----------



## DrKorbin (Sep 21, 2013)

cubizh said:


> the number of possible combinations is the colossal number of 24! = 620448401733239439360000


More precisely, 24!/4!^6 = 3246670537110000.



cubizh said:


> I’m not sure if this was done before, but I thought I’d give it a try.


Well, I did. Also you can find a bit more research here and here.


----------



## kinch2002 (Sep 21, 2013)

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 (Sep 21, 2013)

kinch2002 said:


> 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 (Sep 21, 2013)

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 (Sep 21, 2013)

DrKorbin said:


> More precisely, 24!/4!^6 = 3246670537110000.


Thanks for the correction, I didn't account for the same color centers



DrKorbin said:


> 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?


----------



## DrKorbin (Sep 21, 2013)

cubizh said:


> How many scrambles did you try?



Don't remember, much less then 100 millions. Maybe 100'000, because it was too slow.


----------



## cubizh (Sep 21, 2013)

kinch2002 said:


> 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. 
Which was fixed.


----------



## qqwref (Sep 22, 2013)

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 (Sep 22, 2013)

qqwref said:


> 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 (Sep 22, 2013)

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?


----------



## bobthegiraffemonkey (Sep 22, 2013)

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 (Sep 22, 2013)

cubizh said:


> 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


----------



## cubizh (Sep 22, 2013)

qqwref said:


> 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.


Spoiler: 5 Centers Solved




* 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


----------



## Stefan (Sep 22, 2013)

cubizh said:


> 0.0000000308%



Actually 0.00000308%.


----------



## qqwref (Sep 22, 2013)

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...


----------



## Zane_C (Sep 22, 2013)

Nice research, thanks for sharing


----------



## cubizh (Sep 22, 2013)

Stefan said:


> Actually 0.00000308%.


Thanks, I forgot to multiply by 100 :fp


----------



## mark49152 (Mar 16, 2017)

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 (Mar 18, 2017)

mark49152 said:


> 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?


----------



## mark49152 (Mar 18, 2017)

pinser said:


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


Ur. 

I have two reasons for thinking about reorientation. First, to save moves. It might not always be worthwhile but if the default orientation is bad, say <6 solved centres, and the cube can be reoriented to solve 16, that's 5 comms saved in exchange for 4 moves to switch centres.

Secondly and for me more importantly, to shorten memo. Those extra 10 targets take more time to memo than the few seconds to check orientation. Plus on 4x4, I use audio for centres if there are <=16 targets, but am pushing my limits with nore than that so on 5x5 I use visual. If I could reorient 5x5 to have <=16 targets for either X or T-centres then I would use audio on that scramble.

However, my gut feel based on experience is that the 7-8 for 4x4 doesn't extrapolate to 14-16 on 5x5 like this, which is why I asked the question. I don't recall ever getting a scramble that good. My suspicion is that a good orientation for T-centres would rarely be as good for X-centres and vice-versa, so the most typical cases would be 11-12 centres solved.


----------



## mark49152 (Mar 25, 2017)

mark49152 said:


> My suspicion is that a good orientation for T-centres would rarely be as good for X-centres and vice-versa, so the most typical cases would be 11-12 centres solved.


Confirmed here for anyone following this thread in future.


----------

