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

Square-1 shape probability distribution

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
But it's php based so there's no way to check whether it works (or how well it works) without hacking.
Or asking (I just did)

I see, the third number is the first two PLUS the (x,y) with nonzero x and y.
That's another way to look at it, I guess. I never said x and y are nonzero, so with that I just meant *all* U+D turns, and the first two numbers were those where only one layer got turned. I should've written that in words to make it clearer, sorry.

Jaap's scrambler [...] has some weird biases and the functioning is pretty much opaque.
Yeah, some documentation and descriptive variable names would be good. Biases... well, my two definitions (weighing or not weighing the turns) are also biased. And yours might still differ, I'm not quite sure. Question still is whether in the long run, they all end up with the same distribution, and if not, which is "best".

I don't think we should ever go by what people who don't "know[...] how to use the puzzle" think.
But they truly are the most unbiased :)

Square-1 in a position [...] halfway through a / move
Ooh, YEAH, my favorite shape. Let's go for this! Not sure whether I'm kidding, to be honest :D. Though I guess I'll just have to wait until some inventor mixes a 2-layer Square-1 with a 2x2x2... (or does that exist already?).
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Or asking (I just did)
Saw your post on the forum. Unfortunately I don't speak German.

That's another way to look at it, I guess. I never said x and y are nonzero, so with that I just meant *all* U+D turns, and the first two numbers were those where only one layer got turned. I should've written that in words to make it clearer, sorry.
Sure. But the natural interpretation to me of "most turns have at least one zero" is "there are more turns with at least one zero than with no zeroes", so I was initially very confused when I saw that the sum of the two numbers was less than the third.

Yeah, some documentation and descriptive variable names would be good. Biases... well, my two definitions (weighing or not weighing the turns) are also biased. And yours might still differ, I'm not quite sure. Question still is whether in the long run, they all end up with the same distribution, and if not, which is "best".
I mean biased as in the code has some weird weightings, which are basically just mystery numbers. I don't remember what the code does now, but I figured it out once, and in the part where it decides what turn to do next I basically said to myself "why would anyone set it up like this?". Oh well. In the long run they might not end up random, but who knows about 40 moves. That's not very much. Run a million scrambles with Jaap's scrambler and my idea (take the code from qqtimer), and yours too if you feel like coding it, and see how closely they match the distribution Lucas gave.


Though I guess I'll just have to wait until some inventor mixes a 2-layer Square-1 with a 2x2x2... (or does that exist already?).
http://twistypuzzles.com/forum/viewtopic.php?f=15&t=14733
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel

Mike Hughey

Administrator
Staff member
Joined
Jun 7, 2007
Messages
11,303
Location
Indianapolis
WCA
2007HUGH01
SS Competition Results
YouTube
Visit Channel
For what it's worth, I incorporated the probabilities of the various cubeshapes into my square-1 BLD page. Since I really just took the chart from Christian Eggermont (with his permission), it actually makes a somewhat reasonable chart for learning to get to square optimally. Well, except for the fact that I mostly just used his paths to square, which are very old and therefore pretty bad in some cases (optimal, but very much not speed friendly). I'm realizing now that maybe I should have looked around for better ones before I did this; the algorithm for 7 moves to square is particularly bad.

You can sort that list by letter code, distance to square, or probability, in case anyone finds that useful.
 
Last edited:

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
For clarification: I've held back on here until I could rewrite my code to check the distribution of all 3678 shapes with one-layer turns. You'll have to trust me for now because the code is ugly.
If anyone wants to double-check, please go ahead.

I believe the same argument proves this (intuitively), but I didn't want to say that until I verified it with calculation.

Now that we know the definitions are equivalent, I think the proper distribution we should use is pretty clear.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Do I understand this thread correctly, that this is achieved by randomly picking a position from all with equal probability?
Yes, if you use the right definition of "position."
If you use "one of the 3678" (e.g. AUF matters, but we only allow /-twistable shapes) then it turns out to be the same as the limit of doing a lot of random moves (for either the one-slice or the two-slice definition; can we call them "Stefan-style" and "Lucas-style?" :p). I consider it by far the most natural definition from a math perspective.

So could one for example randomly permute the 16 pieces and then put them in that order clockwise from the top front gap, then clockwise from the bottom front gap (just making sure it's actually two halves and starting over if not)? Would that represent the many-random-moves idea?
Yes, but the "starting over" is important. Backtracking changes the distribution.

I looked into this, and there seem to be a few ways to place the pieces randomly.

1) Select random permutations until the gaps are okay
This will occur with probability 3678/12870, so on average it will take about 3.5 tries to find a valid permutation.

2) Repeatedly: Choose with probability 1/2 from edge vs. corner (if both are possible, else 1 with whichever is). Then randomly choose a remaining piece of that type
Bad.

3) Keep picking randomly among all remaining pieces, selecting an edge if you only have 1 space left until a gap
Bad.


I mention this because I can imagine an amateur programmer doing 2) or 3) without thinking about it. 2) forces everything to align to negative powers of 2, and 3) isn't any better. It's a cool realization that the greedy algorithm works, but too much effort to make it equal-distribution.

The best is to select a truly random state of the 3678. If you're worried that the program might get unlucky and try forever (practically impossible with a decent PRNG), it is possible to do this deterministically: Select a shape using the proper distribution, then randomly assign the pieces into the shape.
(Worried about the middle layer? Just flip the right side with probability 1/2.)

There is actually a lot of math going behind the scenes, but it works out pretty simple.
 
Last edited:

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Sorry for the quadruple post, but I want to keep my posts separate to delimit separate points.

Here's an image of how bad the current scrambler is:

sq1_distribution_bias.png



The graph is sorted by MRSS probability. Yellow means that the current is that much higher than it should be, red means lower.
For example, I compute that you're about 1.5 times as likely to get one of the 10 star shapes from the current scrambler as you should (not experimentally confirmed).

I made a few slight assumptions, but the general nature of the result should be correct.


EDIT: The original post said "3 times as likely" instead of "1.5 times as likely." I had meant to re-do the computation since it didn't agree with the chart, but accidentally just quoted the quick computation. Whatever the actual statistics are, we still should go Markov-Random-State.

EDIT 2: An interesting statistic is comes from asking how often the scrambles from one distribution would need to be changed to correspond to a correct distribution. I compute about 25.4% (\( {\sum_{s\in shapes} min(randommoves_s, mrss_s)} \)).

EDIT 3: I'm not even taking into account piece permutations. I suspect the issue is even worse there.
 
Last edited:

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
First one ever, I believe: sq1_mrss.zip

Code:
$ wget http://archive.garron.us/code/2010/sq1_mrss.zip
$ unzip sq1_mrss.zip
$ g++ -O5 -o sq1_mrss *.cpp
$ ./sq1_mrss
Generating 12 Square-1 Markov-Random-State Scrambles...
1) 7FC8AG36B4E2H1D5/    ( 1, 6)/( 5,-4)/( 1,-2)/( 3,-1)/(-3, 0)/( 5,-3)/(-5,-2)/( 0,-4)/( 0,-3)/(-1, 0)                           [9|25]  (511ms)
2) BAEHD25173G846FC-    ( 4, 0)/( 6,-3)/(-4,-1)/(-5,-3)/( 3, 0)/( 2,-5)/( 6,-2)/(-3, 0)/( 2,-4)/( 6,-4)/                          [10|27]  (358ms)
3) 5EH7FDAC63G81B24-    ( 1, 3)/(-1, 5)/( 4,-5)/( 0,-3)/(-4, 0)/( 3, 0)/( 6,-3)/( 3,-5)/( 0,-2)/( 0,-4)/( 0,-2)                   [10|26]  (695ms)
4) 4E2G1B3C7D658AHF-    ( 6, 5)/(-5,-2)/( 2,-1)/( 0,-5)/( 0,-3)/( 3,-1)/(-5,-2)/( 0,-2)/( 2,-1)/( 3,-4)/(-5,-2)                   [10|29]  (559ms)
5) HDE364G28CA1FB57/    ( 0, 5)/(-3, 0)/(-3, 0)/( 6,-3)/( 3,-5)/(-3,-3)/( 3, 0)/( 1,-5)/( 0,-2)/( 2, 0)/(-1, 0)/( 6, 0)           [11|27]  (1263ms)
6) 785H6GFBE13CD42A-    ( 4, 6)/( 5,-4)/( 3,-3)/( 4,-2)/( 3,-4)/(-3, 0)/(-3, 0)/( 2, 0)/( 2,-5)/( 2,-1)/( 6,-2)/(-4, 0)/          [12|32]  (2363ms)
7) 5CF3ADE78HBG4621/    ( 4, 3)/(-4,-1)/(-5,-2)/(-1,-3)/(-3, 0)/( 3,-1)/(-2,-5)/(-3, 0)/( 2, 0)/( 3,-4)/( 0,-4)/( 0,-2)           [11|30]  (926ms)
8) GAH7E3618F5B24DC-    (-2, 3)/(-1, 5)/( 3, 0)/( 3,-3)/(-5, 0)/( 6,-3)/( 1,-3)/( 5,-1)/( 1,-3)/( 6, 0)/( 4,-5)                   [10|29]  (352ms)
9) D3H172FCEGB864A5-    ( 3,-4)/( 1, 4)/(-3,-3)/( 2,-4)/( 6,-3)/( 1,-3)/( 3, 0)/( 0,-3)/( 6,-3)/(-5,-4)/( 6,-4)                   [10|30]  (118ms)
10) 57E32FGH64D81CAB/    ( 3,-4)/(-5, 4)/( 0,-3)/( 0,-4)/(-3,-3)/( 3, 0)/(-4,-4)/( 2,-4)/(-2,-4)/(-4,-4)                           [9|26]  (1196ms)
11) 5GD68E124HFB73CA-    ( 6, 2)/( 1, 4)/(-1,-4)/(-3,-3)/( 3,-2)/(-3,-3)/( 3, 0)/( 1,-1)/( 0,-2)/( 0,-4)/(-1, 0)                   [10|28]  (497ms)
12) H6728CEF41BG5A3D-    ( 1, 3)/(-1, 5)/(-5,-2)/( 2, 0)/( 3, 0)/( 1,-4)/( 0,-4)/(-4,-5)/( 2, 0)/(-2, 0)/( 6, 0)                   [10|26]  (514ms)

EDIT: Also, live scripting demo.

EDIT 2: For the lazy Unix-lovers who trust me: wget http://archive.garron.us/code/2010/sq1_mrss.zip ; unzip sq1_mrss.zip; g++ -O5 -o sq1_mrss *.cpp; ./sq1_mrss
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
1) Select random permutations until the gaps are okay
This will occur with probability 3678/12870, so on average it will take about 3.5 tries to find a valid permutation.

Not for you, Lucas, but for anyone else reading: the general form of this is a really great trick to know if you want to ensure a uniform choice but don't have a native "randomly choose an element from this set" function (or, if you don't want to have to actually generate that set, which is the other way to do it). Basically, if you want to uniformly randomly select from the set of elements from a bigger set A which satisfy some property p, a simple way is to simply randomly select elements from A until you find one which satisfies p. The only real downside is that it often takes a few tries to get one of the right elements (and may in theory take infinitely many if you are infinitely unlucky) - on average, one over the probability that an element in A satisfies p. Fortunately, generating random numbers is generally pretty fast.

This trick is useful for a lot of calculations involving randomness that, on first glance, seem quite tricky to program. You can use it to select valid positions on a Square-1 or similar bandaged dihedral puzzle; you can use it to select random numbers from 1 through N if all you can generate is random bits (e.g. with a PRNG like the Mersenne Twister); you can use it to choose random cube positions with some weird criterion, like having no 1x1x2 blocks.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I somewhat dislike of the use of the "starting over if an invalid scramble state is generated" technique. For instance, if from a given state of the PRNG, it takes 10 tries to get a valid scramble, then this implies there are at least 10 different initial states of the PRNG that will end up returning the same scramble position. This may mean that this particular scramble position may have a higher probability than others of being the first scramble position generated. In turn, this could mean a higher than expected probability of two different competitions having the same scrambles.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
I somewhat dislike of the use of the "starting over if an invalid scramble state is generated" technique. For instance, if from a given state of the PRNG, it takes 10 tries to get a valid scramble, then this implies there are at least 10 different initial states of the PRNG that will end up returning the same scramble position. This may mean that this particular scramble position may have a higher probability than others of being the first scramble position generated. In turn, this could mean a higher than expected probability of two different competitions having the same scrambles.

1) In my implementation here, I use a Mersenne Twister library (default seeded by current time), which should by far be good enough to mitigate 10 or even more being thrown away while staying random. I'm not sure it's even a big problem for smaller PRNGs.
2) The expected number of attempts is only 3.5, in exchange for much simpler code. As an alternative, I also described a deterministic algorithm that always takes 1 try (but requires longer initialization or precomputed probability tables).
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I somewhat dislike of the use of the "starting over if an invalid scramble state is generated" technique. For instance, if from a given state of the PRNG, it takes 10 tries to get a valid scramble, then this implies there are at least 10 different initial states of the PRNG that will end up returning the same scramble position.
Mm, yes. But we should already be using a PRNG big enough that there are many instances of each scramble in the period, so that the number of states "before" each individual instance of the scramble-number ends up getting lost in the huge number of possibilities.

Mersenne Twister, for instance, has a period of about 2^19937 ~= 4 * 10^6001. Each element in the period is a 32-bit number; we can generate a potential Square-1 situation with two of these numbers, giving us 2 * 10^6001 possible situations. Dividing by 3.5 and then by the number of Square-1 positions gives that each position occurs roughly 1.3 * 10^5989 times. I think this is enough that the distance between each one and the next is irrelevant.


PS: If you're generating, say, a random permutation of 16 elements, you know that there are 16! possibilities. Now, 16! * 107 is about 2^(50.9916), i.e. it takes up just under 51 bits. This means it takes up 99.42% or so of the positions. So one way to generate random piece permutations without wasting too many bits is:
- Generate two 32-bit numbers and drop all but 52 bits (51 + one for the middle slice).
- Check to see that the first 51 bits form a binary number strictly less than 16! * 107. About 0.58% of the time, this won't happen, so start again. If it works, take that number mod 16! and then convert the result (an integer from 0 to 16!-1) into a random permutation on the 16 pieces. You can now check if that is a valid permutation of the Square-1.

EDIT: And if you are really insane, you can use 16! * 440828, which spans all 63 bits (last one is for the middle slice) 99.9997786% of the way, so you'll only have to discard one number in every 451,769 or so attempts.
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
1) Select random permutations until the gaps are okay
This will occur with probability 3678/12870, so on average it will take about 3.5 tries to find a valid permutation.

3) Keep picking randomly among all remaining pieces, selecting an edge if you only have 1 space left until a gap
Bad.

I still can't really pinpoint "why" 3) is bad, but I finally managed to convince myself *that* it is bad (that its result does differ from that of 1).

Imagine we're only doing one layer and have edges a/b/c/d and corners E/F/G/H. One possible order is abcdEFGH. That would be chosen by first picking 'a' with probability 1/8, then b with probability 1/7, and so on until G with 1/2 and H with 1/1. The probability for choosing that order is thus 1/8!. However, because we want a gap in the middle, fewer than all 8! orders are acceptable. And since we want the acceptable ones to occur with equal probability, their probability should be higher than 1/8!.

I hope that's right, and I'd still like a better understanding of "why" it goes wrong and how to do it right...
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
I hope that's right, and I'd still like a better understanding of "why" it goes wrong and how to do it right...

That's exactly right. A position like this position is less likely than it should be. Positions with edges before the gap are made more likely because we sometimes keep trying until we get one of them. The easiest way to fix it, of course, is to start over completely, so that all *possible* arrangements are equally likely to get picked in the end.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
A position like this position is less likely than it should be.

Yeah, it's like these positions that got through creation unobstructed haven't heard the good news that other positions died along the way so there's now more cake for everybody still alive.

I kinda envision this like a lot of settlers on their way to reach the west coast. Initially they're all given a piece of cake (of the same size), but some some die on the trip and others near them pick up their cake. In the end, at the west coast, some settlers will have more cake than others.

Positions with edges before the gap are made more likely because we sometimes keep trying until we get one of them.

Nice, I really like that explanation. Although, the "keep trying" isn't directly from the description which said to just select an edge. For that perspective, I have another way to express it now: When creating a position and we so far have let's say abcE (three edges and a corner), nothing has intervened with the (1/8)*(1/7)*(1/6)*(1/5) probability of getting to that point. Without the gap, this probability would be spread evenly among the continuations abcEd, abcEF, abcEG and abcEH. But since the latter three aren't possible and we *are* going to continue, continuation abcEd absorbs the probability of the other three. Or in other words, it eats the cake that they just dropped.

The easiest way to fix it, of course, is to start over completely, so that all *possible* arrangements are equally likely to get picked in the end.

I know, I just wanted to understand the failure better (I now do) and perhaps fix it because your "It's a cool realization that the greedy algorithm works, but too much effort to make it equal-distribution" gave me *some* hope. But I wrote a small program that told me there are 26496 valid positions, which is 24*24*46, and I suspect there's no way to explain the prime factor 23 without really thinking about possible shapes, which I don't want to.
 
Top