Square-1 shape probability distribution

[Lucas Garron]

What version of mathematica are you using, Lucas? I have access to 5 on the physics computers here, if you are using that... and will try this tomorrow. Otherwise, I'll have to find a way to get an earlier version...

Edit: You can use Diag^n, as it is a diagonal matrix; it is a special case, which is why it is so useful.
Short example:
N^x = (P.D.P^-1)^x = P.D.P^-1.P.D.P.... = P.D^x.P^-1


Try Eigenvalues[N[]], and see if any of those are over 1... they should all be less than or = 1.

Yeah, I know about diagonalizing, but maybe I don't know enough about other eigenstuff. Anyhow, I think the issue is with Mathematica handling stuff, I'll try it again when I get version 6.

So, through dinner, I set my computer to compute the explicit, exact eigenvalues of the transition matrix. The results were so surprising, I actually laughed out loud at their beauty:

Of the 170 eigenvalues, exactly 90 are non-zero. That is certainly not a coincidence; there are 90 shapes, and hence 90 unique rows. (From minors and determinants, I can imagine that you get just the right amount of zeros. but it's still pretty, and some time I'd like to fully understand why.)

Anyhow, the 90 non-zero eigenvalues are of three forms:

• 1 (The 1 root of 1-x)
• The 64 roots of - 4991442219 + 386948115252*x + 138762924658242*x^2 - 3103222624916364*x^3 - 877640411309612746*x^4 + 6767666047147902260*x^5 + 2012337578608379698422*x^6 - 8958764174373753804464*x^7 - 2105450969798079776924812*x^8 + 11046600222902203991043312*x^9 + 1123406093781088176157756896*x^10 - 8114779285022492769604795424*x^11 - 325472049644439264188809738432*x^12 + 2962546562996861776481954741760*x^13 + 56287388574936353280108941504768*x^14 - 629949208560303852773245517141504*x^15 - 6105099366584694343157749747552256*x^16 + 86874786230163907381580006692296704*x^17 + 406640998126424132369607623831846912*x^18 - 8273097635823613171991383746279940096*x^19 - 12847215092645959516368232004260052992*x^20 + 563542116540418623958067303673961512960*x^21 - 380249727800812172360337111385392087040*x^22 - 27876394040223235000410822110796320866304*x^23 + 70200985683043152366609324564260935958528*x^24 + 995061174735599595418926716008043747737600*x^25 - 4377190735910344574289281403129530741161984*x^26 - 24483749753436884219275245277429039028502528*x^27 + 172693480479595766346198778149152449118601216*x^28 + 344268199358502700321288117865500491022073856*x^29 - 4765625577836958680705390357889539456775487488*x^3 0 + 772858710665023800732181764002139803146518528*x^31 + 93400462329952268786337346115591965649619910656*x^ 32 - 173918077700241084337687739506139579202876211200*x ^33 - 1244927272170148943873781598261313236445492674560* x^34 + 4715876999443357796546772004551277481760550551552* x^35 + 9204457647103604719171194562707870353618733367296* x^36 - 74472880131178952274776792185662826546928673619968 *x^37 + 17443350194669512509483766280210174159010360459264 *x^38 + 75191391004923599087061417545533284299211717948211 2*x^39 - 13927791249227776078240490903762146831911538246287 36*x^40 - 43280920416000808833869800194972791652726169833308 16*x^41 + 18110807337525247976881146547787829180504891067465 728*x^42 + 26446806236562635365428496318374472606945724250193 92*x^43 - 12495775864656449852395485032743618177001077355210 3424*x^44 + 18148554882138983236427680894317657290624795908295 8848*x^45 + 40633112472130591883866628308152868033344685251074 4576*x^46 - 15481266283450907844717709600230446897185206707756 72832*x^47 + 54971332503775711093793716428432978484848488873145 1392*x^48 + 55522495833400005878653420117344785319027260232082 39104*x^49 - 10580714260899344013132135083176015760588301879893 557248*x^50 - 25105401045309405161267504284860436825811213099791 81056*x^51 + 35729814707763782643150469325553615343782749037989 462016*x^52 - 47192725438731643771622400943584186952215159805015 228416*x^53 - 14671327554181472737539318334576376054183452695928 504320*x^54 + 12167762673059436924667104845242709903144850159253 1140608*x^55 - 15352842715520548924920201552945956831797069825261 4369280*x^56 + 31072468697838310383691091990364643611438025213753 688064*x^57 + 16618470174861176831016701006962041571324603760502 8462592*x^58 - 27899649455767723350693763788559080462889847255743 2274944*x^59 + 24487369234780003959879339853438500289437687257896 0588800*x^60 - 13677849536791490721479177714902447832424297082721 0883072*x^61 + 49139518222010279228071785788096857437263861359797 338112*x^62 - 10462695095295681452359646651435512209985692421953 945600*x^63 + 10111597944446833081475094750380629249919058448062 87360*x^64
• The 25 roots of -41864 + 3136179*x + 386613206*x^2 - 16868236200*x^3 - 402432346544*x^4 + 21212854848768*x^5 - 58429160850880*x^6 - 5476338956938432*x^7 + 47709591633416832*x^8 + 458983451386437120*x^9 - 6981888874709569536*x^10 - 1163160407514488832*x^11 + 392768286252547276800*x^12 - 1520451906669906886656*x^13 - 7565285380895954436096*x^14 + 68553662577750099099648*x^15 - 78233310032907038883840*x^16 - 913347325546567116521472*x^17 + 4118199373346723755720704*x^18 - 3435110820984016104062976*x^19 - 24441765912940143332818944*x^20 + 99523299112333703179665408*x^21 - 183592589424988418224422912*x^22 + 191248395143239778961457152*x^23 - 108940123945387453071753216*x^24 + 26498949067796948044480512*x^25

Okay, someone explain that.
(Note: This makes 90 roots: 1^2+5^2+8^2. Why squares?)

There is a lot of fascinating math about Square-1.
There's those equations, and I have no idea about the coefficients yet.
And I still don't know why the 613 applies to the eventual distribution. Maybe there's something to do with shape symmetries?

[Lucas Garron]

Okay, I think I can explain the probability distribution. Apparently it's mostly what I suspected.
Each shape is weighted (probability/3678) by the its degree in the full graph divided by its AUF/ADF symmetries.

So, it perfectly corresponds to the 3678, and Bruce's explanation is half of it.
Consider each shape the Square-1 can have, such that it's currently /-twistable (there's a crack going around the entire middle, and the 16 edge and corner pieces are essentially four half-sides). Each of these 3678 shapes has exactly the same probability. (If you want to consider the middle two pieces, divide the probability in half for its two possible states. But really, we can ignore the middle for most of this.)

This distribution is stable. Consider 3678 Square-1s, each in one of those shapes. The distribution of the "170" shapes is given by the probabilities I found.
Now, imagine giving each of these a / twist. The 3678 shapes will be permuted randomly (2-cycles), but each of them is still represented and each of the "170" shapes still exist with the same distribution. Performing a random AUF&ADF of each does not change the distribution, as each AUF&ADF of a shape are represented equally already, and will go to each other with equal probability.

With a little insight, it's intuitive that the distribution is stable, and it's not too hard believe that it's unique and all random walks will approximate it.

So, I think the "natural" shape distribution is resolved. But thanks to cuBerBruce and JCBM, without whom I probably wouldn't have found it, and qqwref, who specifically helped me think through the final "solution."


So all that only (yeah right, "only") leaves me to wonder now why the 90-degree characteristic polynomial factors into 3 polynomials with 1, 25, an 64 roots. (Which root corresponds to which shape? Does that even make sense to say?)

[JBCM627]

I'm having troubles getting it to diagonalize as well. It looks like it is just due to small decimal errors in mathematica though; P.Pinv isnt even giving me I, but some other matrix filled with small floating point errors. The code I posted earlier at least works for the distribution problem Stefan posted in the WCA forum, so I don't think diagonalizing like this is a problem; either something in the initialization is causing it to calculate approximately instead of exactly, or Mathematica just doesn't want to do it (I'm on a cruddy computer right now.. it took a few minutes just to open mathematica :/). I wish the other lab were open now; but I give up and will accept approximations til I can get in there.

The probability distribution is quite interesting. I was able to generate that polynomial (well, more or less... its giving me an imaginary part right now too and won't let me Re[]). It therefore also is having trouble factoring. As to why it ends up as 3 polynomials like that, I have no idea. It is certainly at least possible to match the shapes up with eigenvalues/roots, but as to if certain shapes fall into a certain polynomial, I don't know if a pattern will emerge.

Edit:
Cool visual implementation I found (not necessarily what we are looking for, though); but something like this could be done for probabilities of shape nodes: http://demonstrations.wolfram.com/Th...fARandomGraph/
Also cool (of course!): http://demonstrations.wolfram.com/RubiksCube/

And again:
Got it working in 6; it was a stupid bug... Rotate[] is already reserved (defined for some graphics thing) and I hadn't replaced all instances of it.
Package to import is just <<'Combanitorica'... I'm not sure if the correction thing replaced something else too, though. Anyhow, it looks like its working.

Yet again:
There we go. I like my computer Duh, N[]. I'll let my computer run this for a while now...

Again:
After about an hour, I'm pausing this thing. I really wish there were some way to monitor the evaluation's progress, but it appears not. I almost wonder if I could do this by hand faster, since I already know the eigenvalues. Will let it keep running when I go to bed.

And finally:
After it looks like 11 hours, I'm killing this. I don't know why its taking so long... all I did was Eigenvectors[adj].

[smskill12]

lucas you should start speedcubing with the square-1 again
unless you have been

[JBCM627]

So, we finally covered markov chains in class, after which I hit my head, and went back to Lucas's notebook.

Finding exact values is a bit easier than I initially thought - you only need to consider the eigenvalue 1 (which is now obvious to me as this is the only eigenvalue that will remain nonzero in the limit when you raise the eigenvalues to an infinite power). This also serves to further clarify that the approximate numbers are correct:

p = NullSpace[IdentityMatrix[170] - Transpose[adj]]

This gives you relative values. So to find the exact probabilities, you will need to multiply by 1/S, where S is the Sum of your elements. Not being too familiar with mathematica, I did this in a sort of roundabout way:

f = 1/Tr[p*IdentityMatrix[170]]

So, your probabilities are simply f*p.

{4/1839, 4/1839, 4/1839, 4/1839, 5/3678, 6/613, 6/613, 6/613, 8/613, \
8/613, 8/613, 6/613, 6/613, 6/613, 2/613, 4/613, 4/613, 4/613, \
16/1839, 16/1839, 16/1839, 4/613, 4/613, 4/613, 4/1839, 2/613, 2/613, \
2/613, 8/1839, 8/1839, 8/1839, 2/613, 2/613, 2/613, 2/1839, 6/613, \
4/613, 4/613, 4/613, 6/613, 6/613, 4/613, 4/613, 6/613, 2/613, 4/613, \
8/1839, 8/1839, 8/1839, 4/613, 4/613, 8/1839, 8/1839, 4/613, 4/1839, \
4/613, 8/1839, 8/1839, 8/1839, 4/613, 4/613, 8/1839, 8/1839, 4/613, \
4/1839, 4/613, 8/1839, 8/1839, 8/1839, 4/613, 4/613, 8/1839, 8/1839, \
4/613, 4/1839, 6/613, 4/613, 4/613, 4/613, 6/613, 6/613, 4/613, \
4/613, 6/613, 2/613, 6/613, 4/613, 4/613, 4/613, 6/613, 6/613, 4/613, \
4/613, 6/613, 2/613, 4/613, 8/1839, 8/1839, 8/1839, 4/613, 4/613, \
8/1839, 8/1839, 4/613, 4/1839, 4/613, 8/1839, 8/1839, 8/1839, 4/613, \
4/613, 8/1839, 8/1839, 4/613, 4/1839, 6/613, 4/613, 4/613, 4/613, \
6/613, 6/613, 4/613, 4/613, 6/613, 2/613, 2/613, 4/1839, 4/1839, \
4/1839, 2/613, 2/613, 4/1839, 4/1839, 2/613, 2/1839, 6/613, 4/613, \
2/613, 6/613, 4/613, 2/613, 6/613, 4/613, 2/613, 8/613, 16/1839, \
8/1839, 8/613, 16/1839, 8/1839, 8/613, 16/1839, 8/1839, 6/613, 4/613, \
2/613, 6/613, 4/613, 2/613, 6/613, 4/613, 2/613, 2/613, 4/1839, \
2/1839, 4/1839, 4/1839, 4/1839, 4/1839, 5/3678}

[Stefan]

Digging this out for clarification requests...

I think the "best" way to do it is to improve our current idea of scrambling: Do random moves for a really long while (rather, do something that produces equivalent scrambles).

Do I understand this thread correctly, that this is achieved by randomly picking a position from all with equal probability? 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?

So, I took the following definition: In any state, the top position can be turned a certain number of ways to realign a twistable crack, and you rotate to a random one of each. Same for the bottom. Then you do a /, and continue.

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

Random sequence of moves of U, R and D without trivial cancellations.

In other words, don't treat U and D differently from R in the definition. Does this end up being the same definition as yours or having the same result as yours? And if not, which definition is "better"?

WCA scrambler

How does the current WCA scrambler work? Looks like random moves, but I don't understand the code and how it chooses the turns (one of our two definitions?).

Also: The WCA-scrambled state is always /-turnable. But should it be? I find that slightly unnatural.

the number of shapes if we consider rotations different (e.g. a square counts as 3 because it has three possible orientations)

Why 3? Shouldn't that be 2?

[Mike Hughey]

Ugh. I should have searched for a thread like this when I was working on my square-1 BLD method. I was thinking it would be nice to have probabilities of shapes so I could learn them in order of likelihood of getting them, so I could be more likely to get the ones I had already memorized. But I guess I'm glad now that I didn't, since otherwise I might not have been as motivated to learn them all. I guess I didn't remember this thread because it wasn't something that interested me that much back then.

the number of shapes if we consider rotations different (e.g. a square counts as 3 because it has three possible orientations)

Why 3? Shouldn't that be 2?

Why not 4? For my memorization purposes, a square has 4 possible orientations. It makes getting to square consistently a little tricky because I need to make sure I always orient it the same from the previous position. (I solved it by always using minimal movement - zero or 30 degrees.) Maybe I don't understand what "orientation" means in this context.

(And by the way, I hate the lack of ability to automatically get quote trees with the new site for cases like this. Stefan's "Why 3? Shouldn't that be 2?" quote is completely meaningless without the preceding quote.)

[qqwref]

Do I understand this thread correctly, that this is achieved by randomly picking a position from all with equal probability? 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?

I would like to do this, but I don't know a reasonably efficient solving algorithm, except for Jaap's program which uses many MB of tables and doesn't have any graphical interface. Is there one? Could someone make one? Even a program which uses many MB of tables could work fine if it could be prettied up in CubeExplorer fashion, because we already use one external program to make scrambles and it wouldn't really be too much to ask to have another.

Do the results change if we [...] don't treat U and D differently from R in the definition[?] Does this end up being the same definition as yours or having the same result as yours? And if not, which definition is "better"?

I don't know about results, but there is a fundamental difference between U/D and R in the Square-1 (as it is a dihedral puzzle, not a symmetrical one where all layers work equally) so it would be inappropriate to treat the layers equally when scrambling. As for "better", well, see above - we should be trying to move towards a random-state scrambler.

Also: The WCA-scrambled state is always /-turnable. But should it be? I find that slightly unnatural.

I don't find this unnatural. You wouldn't provide a 3x3 scramble with the top layer turned 45 degrees and say that it's fine since two layers can be turned. Even though the Square-1 is bandaged, I think the same reasoning makes sense: we can always use positions that allow all layers to be turned, so we should, because other positions are between the kind of real states that we would be able to see during a non-canceling move sequence.

[Stefan]

I would like to do this, but I don't know a reasonably efficient solving algorithm, except for Jaap's program which uses many MB of tables and doesn't have any graphical interface. Is there one?

There's one here now:
http://83.169.19.211/sq1/
http://www.speedcubers.de/forum/showthread.php?tid=4901

Don't know how it works and how much resources it takes, though.

but there is a fundamental difference between U/D and R in the Square-1 (as it is a dihedral puzzle, not a symmetrical one where all layers work equally) so it would be inappropriate to treat the layers equally when scrambling.

Why? For example, what is wrong with my above definition which does treat them equally?

Does this end up being the same definition as yours or having the same result as yours?

I now think it does differ, at least compared to the WCA scrambler. I just tested the WCA scrambler a bit, did this three times:
- Generate 10 scrambles of 999 moves to get a lot of data
- Remove (0,0) from the ends cause I don't want to count that
- Count (0,y), (x,0) and (x,y)

The results:
First attempt: 1211, 1207, 4138
Second attempt: 1184, 1159, 4113
Third attempt: 1212, 1166, 4124

So (U,D) turns with U or D being 0 consistently occured significantly more than half the time.

Now consider my scramble definition: random non-canceling sequence in <U,R,D>. It can still be written in the current WCA notation, of course. Imagine we just had an R turn. Next must be a U or D turn, let's say it's D. Then next must be a U or R turn. I see two options to weigh them:

- Don't weigh them, they have equal probability. Half the time it's the R and we get a (0,D) or (U,0) turn. So the (U,D) turns with U or D being 0 should occur half the time.
- Weigh them according to how many possibilities each layer has. R only has one, U probably has several. So the (U,D) turns with U or D being 0 should occur significantly *less* than half the time.

Since the WCA scrambler appears to have them significantly *more* than half the time, not half the time or significantly *less* than half the time, we seem to differ.

As for "better", well, see above - we should be trying to move towards a random-state scrambler.

Absolutely. But my question is whether my scrambling-by-turning definition results in a different probability distribution, affecting how the random-state scrambler picks the random state.

I don't find this unnatural. You wouldn't provide a 3x3 scramble with the top layer turned 45 degrees and say that it's fine since two layers can be turned.

Imagine someone who's not already biased by knowing how to use the puzzle. In other words, a non-cuber. I'm quite sure they align the 3x3x3 properly, but not necessarily the square-1! They might very well end up with a U turn only resulting in a UF gap but not a UB gap.

[qqwref]

There's one here now:
http://83.169.19.211/sq1/
http://www.speedcubers.de/forum/showthread.php?tid=4901

Don't know how it works and how much resources it takes, though.

Neat. But it's php based so there's no way to check whether it works (or how well it works) without hacking. Maybe he has some random-state code feeding into Jaap's solver and it's all run on a server somewhere.

I now think it does differ, at least compared to the WCA scrambler. I just tested the WCA scrambler a bit, did this three times:
- Generate 10 scrambles of 999 moves to get a lot of data
- Remove (0,0) from the ends cause I don't want to count that
- Count (0,y), (x,0) and (x,y)

The results:
First attempt: 1211, 1207, 4138
Second attempt: 1184, 1159, 4113
Third attempt: 1212, 1166, 4124

So (U,D) turns with U or D being 0 consistently occured significantly more than half the time.

I see, the third number is the first two PLUS the (x,y) with nonzero x and y.

I looked at the code and it uses Jaap's scrambler which I do not think is the best one. It has some weird biases and the functioning is pretty much opaque. Of course it is pretty much impossible to get any new scrambler past the WCA so that will have to do. The scrambler in qqtimer is better and functions as follows:
- Choose a random move of the form (x,y), with x and y chosen completely randomly. If x=y=0 (unless it's the first move) or the move is impossible, try again. If we don't have enough remaining moves to do this, try again.
- After performing it, if we have at least one remaining move, do a /.
- Repeat.

Now consider my scramble definition: random non-canceling sequence in <U,R,D>. It can still be written in the current WCA notation, of course. Imagine we just had an R turn. Next must be a U or D turn, let's say it's D. Then next must be a U or R turn. I see two options to weigh them:

- Don't weigh them, they have equal probability. Half the time it's the R and we get a (0,D) or (U,0) turn. So the (U,D) turns with U or D being 0 should occur half the time.
- Weigh them according to how many possibilities each layer has. R only has one, U probably has several. So the (U,D) turns with U or D being 0 should occur significantly *less* than half the time.

Since the WCA scrambler appears to have them significantly *more* than half the time, not half the time or significantly *less* than half the time, we seem to differ.

We differ because I initially thought the official scrambler used the good scrambling algorithm, which it doesn't. I also assumed that when you said the U/D/R layers would be treated equally you were essentially forcing the first weighing. I think the second weighing is a good way to go, if we must generate the moves randomly.

Imagine someone who's not already biased by knowing how to use the puzzle. In other words, a non-cuber. I'm quite sure they align the 3x3x3 properly, but not necessarily the square-1! They might very well end up with a U turn only resulting in a UF gap but not a UB gap.

I don't think we should ever go by what people who don't "know[...] how to use the puzzle" think. If you think we should, why not just disassemble the puzzles and put them back together? Or, even worse, why not take off the stickers and reapply, for our scrambles? I prefer to go by the logical route of mixing up a puzzle as close to uniformly randomly as possible, without getting in the way of its proper functioning. Having a Square-1 in a position where / is impossible does not seem any more reasonable than having it halfway through a / move, or having a 3x3 off by 45 degrees, or having a 5x5 halfway through a V-lockup.