Square-1 shape probability distribution

[Stefan]

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

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/viewt...p?f=15&t=14733

[Stefan]

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.

Maybe. I must admit I don't care all that much about Square-1 yet and this sounds like more work...

http://twistypuzzles.com/forum/viewt...p?f=15&t=14733

omg WANT!!! I should really at least keep an eye on their "new puzzles" section...

[Mike Hughey]

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.

[Lucas Garron]

Do the results change if we use a more 3x3x3-like definition like this?

No.

[Lucas Garron]

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]

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?" ). 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.

[Lucas Garron]

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:




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% ().

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

[Lucas Garron]

First one ever, I believe: sq1_mrss.zip

$ 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

[qqwref]

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.