Warning: touch() [function.touch]: Utime failed: Permission denied in [path]/includes/class.latex-vb.php on line 167
Square-1 shape probability distribution - Page 3
Page 3 of 4 FirstFirst 1 2 3 4 LastLast
Results 21 to 30 of 37

Thread: Square-1 shape probability distribution

  1. #21
    Member Stefan's Avatar
    Join Date
    May 2006
    WCA Profile
    2003POCH01
    YouTube
    StefanPochmann
    Posts
    6,374

    Default

    Quote Originally Posted by qqwref View Post
    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)

    Quote Originally Posted by qqwref View Post
    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.

    Quote Originally Posted by qqwref View Post
    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".

    Quote Originally Posted by qqwref View Post
    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

    Quote Originally Posted by qqwref View Post
    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?).

  2. #22
    Member qqwref's Avatar
    Join Date
    Dec 2007
    Location
    a <script> tag near you
    WCA Profile
    2006GOTT01
    YouTube
    qqwref2
    Posts
    6,879

    Default

    Quote Originally Posted by StefanPochmann View Post
    Or asking (I just did)
    Saw your post on the forum. Unfortunately I don't speak German.

    Quote Originally Posted by StefanPochmann View Post
    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.

    Quote Originally Posted by StefanPochmann View Post
    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.


    Quote Originally Posted by StefanPochmann View Post
    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
    Computer cube PB averages of 12: [Clock: 5.72] [Pyraminx: 3.33] [Megaminx: 49.52]
    [2x2: 2.66] [3x3: 8.45] [4x4: 29.06] [5x5: 52.69] [6x6: 1:34.78] [7x7: 2:20.34]

  3. #23
    Member Stefan's Avatar
    Join Date
    May 2006
    WCA Profile
    2003POCH01
    YouTube
    StefanPochmann
    Posts
    6,374

    Default

    Quote Originally Posted by qqwref View Post
    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...

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

  4. #24
    Super Moderator Mike Hughey's Avatar
    Join Date
    Jun 2007
    Location
    Indianapolis
    WCA Profile
    2007HUGH01
    YouTube
    MikeHughey1
    Posts
    7,959

    Default

    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 by Mike Hughey; 10-13-2010 at 02:27 PM.
    My square-1 BLD method: http://skarrie.se/square1blind/

  5. #25
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,049

    Default

    Quote Originally Posted by Stefan View Post
    Do the results change if we use a more 3x3x3-like definition like this?
    No.
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net

  6. #26
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,049

    Default

    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.
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net

  7. #27
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,049

    Default

    Quote Originally Posted by Stefan View Post
    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.

    Quote Originally Posted by Stefan View Post
    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 by Lucas Garron; 10-16-2010 at 10:04 AM.
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net

  8. #28
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,049

    Default

    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% ({\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 by Lucas Garron; 10-16-2010 at 03:59 PM. Reason: Correction: only about 1.5 times as likely, not 3.
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net

  9. #29
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,049

    Default

    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 by Lucas Garron; 10-21-2010 at 07:56 AM.
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net

  10. #30
    Member qqwref's Avatar
    Join Date
    Dec 2007
    Location
    a <script> tag near you
    WCA Profile
    2006GOTT01
    YouTube
    qqwref2
    Posts
    6,879

    Default

    Quote Originally Posted by Lucas Garron View Post
    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.
    Computer cube PB averages of 12: [Clock: 5.72] [Pyraminx: 3.33] [Megaminx: 49.52]
    [2x2: 2.66] [3x3: 8.45] [4x4: 29.06] [5x5: 52.69] [6x6: 1:34.78] [7x7: 2:20.34]

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •