Scrambling Procedure for Sq-1

UMichSpeedCubist (2008-05-30 23:15:58 +0000)
I'd like to understand the scrambling procedure for Square-1. The length of the scrambles must be 40, but the way the current scrambler does not display '/' makes it unclear wheather or not to do the last '/'. If you do it after every ')' then you might do a length 41 scramble. And if you don't do the last '/' every time you might get a length 39 scramble instead of the intended target. I believe the '/' notation needs to be back in for the 2009 draft of the regs! It would make having initial "(0,0)" unnecessary as well. I am interested in writing a scrambling program in Java (not Javascript). After carefully looking over Jaap's code in the official WCA one, I am still very confused because he doesn't use good naming and it makes it very hard to read. I'd like the procedure explained in plain English. What turns are allowed and when? How do we count turns and what does "length 40" really mean? What statistical distribution is used in picking the turns? Surely we don't allow "-6" if we have 6 instead. And if we allow both then that turn gets twice the probability of occurrence. Is stuff like "(6,6)/(6,6)/(6,6)/..." legal? Do we pick a random number -5,..,6 (inclusive) in uniform distribution for U and then for D? Or do we instead pick a single number in the cross-product space of 144 elements? Do we reject "(0,0)" unless it's at the start of the scramble? There are also issues near the end of the scramble when 40 is about to be reached. Currently (X,0) is much more common than (0,X) at the end. Does this need to be addressed? And I think we need to also differentiate if there is really a '/' that follows. I probably will need a response from Jaap - does he check this forum? I better e-mail him. This is for "Rubik's JTimer" project the new and improved JNetCube, for which I have already done a scrambler for Pyraminx, Megaminx, 2x2, 3x3, 4x4,5x5 (WCA legal, I think...) as well as generating their respective Images. A program to display a Megaminx scrambles might be useful for running competitions with the event... Speaking of 5x5 scramblers. Is there a general procedure for picking moves for any NxMxL puzzle? There should be. For multislice, simply translating all the r' to Rw', l to Lw, etc. is not sufficient to result in a legal scramble. And it is unclear to me whether Hunt's original code for 4x4 and 5x5 are WCA legal (under the previous non-multislice policy). I'd like to implement a multislice scrambler for 4x4 and 5x5 as well. There are a lot of subtleties involved that must not be overlooked. For 4x4 (r' l) is legal but (Rw' Lw) is not. Is (Rw2 L2) legal? Is (Rw2 L R2) legal? (Rw Lw) is not legal I bet. So many question! Although it may be beyond the scope of things... (Rw' l) is illegal because it could have been accomplished with (L') and a whole-cube rotation correct? Screenshots of RJT here: http://i296.photobucket.com/albums/mm17 ... soView.jpg http://i296.photobucket.com/albums/mm17 ... ptions.jpg Download development snapshots here: http://code.google.com/p/rubiks-jtimer/downloads/list -Doug
Ron (2008-05-31 06:15:27 +0000)
Hi Doug, Thanks for your feedback. The (good) points that you are making were the subject of a private discussion between Takao and Jaap. The conclusion IMHO was that the scramble quality is good enough, but that indeed we may improve the scramble program for future versions. The notation should not be a problem. (x,y) means you always have to do a half turn at the end. This means we will never end up with a position that needs horizontal moves before you can do the half turn again. I prefer to have the scramble programs in JavaScript, because it generally works on all pc's and does not require additional installation of software packages (like Java runtime). But... if we would have one program that manages all scrambles, instead of a program per puzzle, then I would gladly accept the additional software packages. ;-) Thanks, Ron
UMichSpeedCubist (2008-05-31 07:24:59 +0000)
I wasn't really trying to make any points. I was seeking guidance on how to go about witting such code. The Javascript code for the official scramblers are very hard to read, and it almost feels like it was done on purpose to make it all the more cryptic due to using 1-letter naming of vars. I think that it needs to be clear how the moves are picked, and the regulations be so clearly described that a programmer can go about writing their own scrambler and could know it would be "WCA-legal". The restriction I put on my scrambler function is that it not use any API-specific Java (so like no Vectors), so it can be easily converted to Javascript if needed. Although, Javascript is a very awful language for many reasons... I wonder if the old JNC used the proper WCA policy on picking turns for 2x2 - 5x5. Hunt's old Pyraminx code (tip turns last) certainly does not match WCA standards, so I changed it, and now RJT has it perfectly right. Although forcing length 25, with all tip turns in front means that it does 0-4 tip turns then (25 minus the number of tips turns) of core turns, make it a kinda of strange procedure. I also believe I implemented a WCA-legal Megaminx scrambler for RJT. But RJT can import both WCA 2008 and WCA 2007 type Megaminx scrambles and display their images with color customization. Note that CCT does not use 2008 standard, and produces incorrect results for 2007 ("ABCDEFabcdef" type) ones. CCT swapped 'c with f' and 'd with e' I found. I have independent sources verifying that my Megaminx images are correct and would be happy if WCA would promote that aspect of RJT, seeing as the official scrambler lacks images. I also have a superior Pyraminx image generator. Eventually I'd like to get RJT to be able to export many scramble-image pairs like the WCA ones do. This could be very helpful for WCA... having everythign in one package like you said. But in the meantime I need help. I have an outline of how to write a flat Square-1 image generator, given a scramble alg. I can have it detect invalid/impossible turns as well. I am in need of a procedure for picking turns for the Sq-1, for the 4x4 with wide-turns only (multislice), and for the 5x5 with wide-turns only. -Doug
jbcm627 (2008-06-01 19:41:00 +0000)
Re: your big cubes question, I'm not 100% sure how Jaap's scrambler works either, but I think the basic idea is as follows. I guess some of the variables may be single letters, but Jaap has done a good job picking them appropriately and commenting them to explain what they were, which is helpful. So: -Pick a random axis. -Generate moves on the axis, with a 2/3 probability each time of switching to a different axis (or switching when no more moves on the current axis are possible), and make sure you don't repeat moves on that axis. -Pick a different axis and repeat above. The random part may be slightly biased, and tend to generate more turns on the same axis than ideally should be, as the 2/3 is rigid. For example, on a 3x3, after doing a U, there are 5 more faces that can be turned, 4 of those not on the [U] axis, so the 2/3 should perhaps ideally be 4/5. A formula would follow from this (confirm my reasoning, someone)... (# slices on cube - # slices on axis) / (# slices on the cube - # slices moved on axis) This should also eliminate the need for the statement to switch axes when no more moves are possible; for example, the ratio would be 4/4 when U and D have both been moved on a 3x3, so there would be a 4/4 = 100% chance it switches axes. This would also apply to NxMxL cubes, I believe. In terms of variables from Jaap's program for strict NxNxN cubes, the ratio would be something like: ((size - 1)*3 - (size-1)) / ((size-1)*3 - moved), which simplifies to: 2*(size-1)/(3*size-3-moved), but I haven't tried this so don't take my word for it :)
UMichSpeedCubist (2008-06-02 01:37:38 +0000)
That's only scratching the surface of my question, but thanks for trying. Here's a good way to re-phrase it: Let's say I want to generate scrambles for NxMxL puzzle using only PENCIL, PAPER, and a DICE. For the case 2x2x2, 3x3x3, 4x4x4, 5x5x5 they should match perfectly in distribution to WCA standards for when it wasn't multislice. Then I also want the answer if it is multi-slice. Specifically I am particularly interested in the case of 4x4x4 no-multislice, 5x5x5 no-multislice, 4x4x4 with multislice, and 5x5x5 with multislice. The method should ideally be NxMxL, but should at least be general enough to extend to 6x6x7 and 7x7x7 for it to be useful for me. I am going to post this on the Yahoo forum now too, since it's actually quite interesting from a mathematical point of view. -Doug
jbcm627 (2008-06-02 05:34:17 +0000)
The aforementioned algorithm should work well for all cube size cases, even irregular ones, if you just had a pencil, paper, and die. As in: 1 - Use the die to pick an axis 2 - Use the die to pick a 'break' on that axis. (Note: Earlier I used 'slice', that was poor word choice on my part; it should be worded as 'break'. As in, a 4x4 has 3 breaks on each axis, or a 5x5 has 4.) Then generate a move per the chosen break; as in record what move should be applied to misalign the layers on either sides of the break. 3 - Use the die to randomly decide if you should move to another axis based on the above formula, then repeat #2. This inherrently assumes multislice is on, but is actually OK, since per WCA regulations doing an inner slice counts as 2 misalignments anyways. Thus, turning multislice off becomes an unwanted complication; and shouldn't necessarily even be relevant to scrambles. For instance, this is obvious when considering a 3x3, since a move such as M obviously affects 2 'breaks' as an inner slice on a 4x4 would, and thus may be broken down to R' and L. It also interestingly restricts how you may note moves, as it considers a move like Dw' the same as Uw' on a 4x4 for example; so one of these would need to be designated prefferential. Perhaps choosing more trigger friendly faces to be prefferential would be a good idea for scrambling :). I'll try and implement this for an NxMxL scrambler tomorrow... hopefully actual code instead of just an outline should do a bit more than just 'scratch the surface' :) So I guess it may be helpful to try not to think of scrambles as moving faces, but instead as moves misaligning 2 adjacent layers. These are what you do not want to repeat.
jbcm627 (2008-06-02 18:22:31 +0000)
[url:22adkfra]http://www.thewonderidiot.net/timer/scramble.html[/url:22adkfra] ...see comments in src code
UMichSpeedCubist (2008-06-03 03:41:44 +0000)
Is that WCA legal for the cases of "NxMxL" equal to 2x2x2, 3x3x3, 4x4x4 no-MS, 5x5x5 no-MS, 4x4x4 with-MS, and 5x5x5 with-MS? Is doing "Math.floor(Math.random()*3)" better, worst, or equivalent to how JNC/RJT does it using "(int)(Math.random()*3)"? Hem maybe I should use Math.floor now that I think about it. This will take a while for me to read over and understand. After I get familiar with the code, I will likely have a bunch of questions for you... Thanks a bunch. -Doug
jbcm627 (2008-06-03 04:35:58 +0000)
This is more or less just a quick rewrite of the current WCA scrambler (minus the image generation). It removes the bias in switching axes, and just extends the current concept to allow NxMxL, so it should be WCA legal, if not moreso than the current scramble generators. Although I won't guarantee its bug-free as its sort of hard to test something like a 20x4x9 :P If the reasoning I used in making the scrambler is correct, with-MS should sort of become standard; as doing an inner slice is actually 2 misalignments, not 1. I would really like to have this confirmed, though. If so, I'd recommend just not including multislice off as an option, and keep it always on. I guess I just used Math.floor because I needed a 0,1, or 2; I think Java includes a random integer generator (nextInt) in some math package, right? That might be easier. Casting as an int should be equivalent to Math.floor in Java, though. Note that this is a generator for sort of abnormally superfunctional NxMxL cubes; if you had something like a 2x2x1 (adam zamora had one, I think...), then due to the build the moves along the 2-axes would probably have to be restricted to double turns. Perhaps I'll make an option to include this restriction. It currently also won't let you enter sides of 1, as it would need to generate repeat (or undefined) moves on the same axis if they were allowed, or even enter an infinite loop if you entered a 1x1x1 cube :) But yeah, especially with larger cubes coming out soon, picking the current scramblers apart is probably a good thing... RubiksJTimer does look great, too... :)
jbcm627 (2008-06-03 22:00:03 +0000)
I added in a bit more support now, too. Maybe I'll get around to generating images sooner or later...
UMichSpeedCubist (2008-06-04 05:40:18 +0000)
[quote="jbcm627":1s27aqji]This is more or less just a quick rewrite of the current WCA scrambler (minus the image generation). It removes the bias in switching axes, and just extends the current concept to allow NxMxL, so it should be WCA legal, if not moreso than the current scramble generators. Although I won't guarantee its bug-free as its sort of hard to test something like a 20x4x9 :P If the reasoning I used in making the scrambler is correct, with-MS should sort of become standard; as doing an inner slice is actually 2 misalignments, not 1. I would really like to have this confirmed, though. If so, I'd recommend just not including multislice off as an option, and keep it always on. I guess I just used Math.floor because I needed a 0,1, or 2; I think Java includes a random integer generator (nextInt) in some math package, right? That might be easier. Casting as an int should be equivalent to Math.floor in Java, though. Note that this is a generator for sort of abnormally superfunctional NxMxL cubes; if you had something like a 2x2x1 (adam zamora had one, I think...), then due to the build the moves along the 2-axes would probably have to be restricted to double turns. Perhaps I'll make an option to include this restriction. It currently also won't let you enter sides of 1, as it would need to generate repeat (or undefined) moves on the same axis if they were allowed, or even enter an infinite loop if you entered a 1x1x1 cube :) But yeah, especially with larger cubes coming out soon, picking the current scramblers apart is probably a good thing... RubiksJTimer does look great, too... :)[/quote:1s27aqji] I see your points. I guess originally my question was not entirely well-formulated. But it's good that you understand what I'm trying to investigate. The parts about the misalignment count and axis-switching bias is at the heart of what I need to know. I think I have enough to go on, I'm just extremely tired of coding these days. So I'll look at your code when I go back at it in a few days. For RJT, I have been so concerned with fixing minor bugs and improving userablity, that I have not done the major feature additions people have been asking for. Still it was about 10 hrs of coding a day for nearly 3 weeks, and now that everything is at a very stable milestone, I don't want to touch it for a long time. Still can't help but think about writing scramble generator functions when I'm bored though. You sound very confident of your code, and that you know what you are talking about, so I believe that your code will have the answers I am looking for. Thanks again. -Doug
jbcm627 (2008-06-05 04:19:07 +0000)
Wow thats a lot of coding! Its good to take a break. I preffer Javascript to Java for the reason that its a lot easier to write code, and especially debug... and therefore takes a lot less time :) After looking a bit more at RJT, I think I have a bit of an idea of how it works... if you would like any help in making a general MxNxL generator class, let me know. I'm off of school (finally!) tomorrow, and would have the time to work on it. It shouldn't be too much trouble to convert the javascript to java... As for an image generator, well an MxNxL one hopefully would be achievable as well :) And this forum needs to get these smileys working...
UMichSpeedCubist (2008-06-07 03:57:08 +0000)
Actually, I originally started taking about Sq-1 scrambler cuz I wanted to include one into RJT. The NxMxL thing was only a theoretical question to help shed light into how I could A) prove or convince myself of the validity of the current 2x2-5x5 scramble generator functions, B) write a separate multi-slice scramble generator for 4x4 and then for 5x5, and C) unify the 2x2-5x5 non-multislice scramblers since currently they are in separate *.java files. In fact, they are a single class with a single public static method... and that's not really ideal I think. There have been a lot people asking for the feature request of multi-slice scrambles for 4x4 and 5x5. It's not hard to do at all. But to do RIGHT... that is something very few people have attempted it seems. I mean to do it so perfectly correct that it is WCA legal - even more so... that it becomes the *new* WCA standard perhaps because it is stricter in whatever sense or because it is less biased or more biased in the ways we want or don't want. I am starting to think I need to be talking to the CCT coders on how they did it, because it is highly likely they did it with great confidence. Until I have reached such confidence in my picking procedure, I cannot include one for RJT. Square-1 is the trickiest of them all - the swiftness of the tiny amount of Jaap's code WCA uses left me quite unsatisfied. -Doug
JohannesLaire (2008-06-07 06:59:28 +0000)
[quote="UMichSpeedCubist":33chvk69]I mean to do it so perfectly correct that it is WCA legal[/quote:33chvk69] What does that actually mean? The regulations say almost nothing about how the scrambles should be generated.
UMichSpeedCubist (2008-06-11 05:50:55 +0000)
[quote="JohannesLaire":rss0ggpr][quote="UMichSpeedCubist":rss0ggpr]I mean to do it so perfectly correct that it is WCA legal[/quote:rss0ggpr] What does that actually mean? The regulations say almost nothing about how the scrambles should be generated.[/quote:rss0ggpr] No it does. It says that competition organizers must use the scrambling programs provided. So what I mean by "WCA legal" is that the distribution of the scrambles matches exactly that of those Javascript programs. Moreover, I think the regulations should be entirely explicit about how the scrambles are generated - especially since someone has already gone though the trouble of making all the decisions pertaining to the this. Working backwards from the code to the picking procedure seems an awfully way for me to have to go about things.
jbcm627 (2008-06-11 18:20:29 +0000)
I'd think the obvious definition of a scramble would be a completely random (solveable) state on a cube. Of course, generating these for 4x4, 5x5, and NxN cubes isn't as easy; so we can resort to an alternate definition, which also seems obvious: randomly misaligning layers while being careful not to undo a previous misalignment. (That is at least, before affecting the layer with a misalignment from another axis.) But, then again... even the current 4x4/5x5 scramblers, as well as other twisty puzzles such as megaminx, don't adhere to either of these definitions... so perhaps "pseudo-random" is a better word choice.
jazzthief81 (2008-08-09 22:46:31 +0000)
This discussion seems to have died, but the original point made by the topic starter was actually a very valid one and didn't seem to be acknowledged as such. There is a problem with the notation used by the current WCA scrambler for Square-1. At the Czech Open I was scrambling for the other group of competitors when it caught my attention that my scramble was one move away from the scramble that Martin Zahradník did, who was sitting right next to me. Martin then explained that you had to do an extra half turn at the end because all the moves before add up to 39. Arnaud van Galen then counted the moves of the other 2 scrambes and it turned out that on the second scramble no extra half turn needed to be made at the end. On the third scrambled an extra half turn needed to be made again. Clearly this is not ideal, since it requires the scramblers to count the amount of moves leading up to the end of the scramble and then deciding whether an extra half turn should be applied or not. This can easily be fixed by just putting the '/' back wherever a half turn needs to be applied.
Mike Hughey (2008-09-03 17:07:00 +0000)
I thought it had already been explicitly stated that, with the new scramble generator, an extra half turn is always required at the end. Every pair assumes a half turn after it. Is that not the case?
AvGalen (2009-02-13 10:05:55 +0000)
This discussion seems to have died again, but I do agree with Lars and not with Ron on this one. The rules state that a scramble should have 40 moves. The slice/R2 turn counts as a move. But always adding the slice/R2 turn at the end means that some (actually most) scrambles will get 41 moves. The reason Ron gives (never a horizontal move needed at the start of the solve) is not a valid reason because the current scrambler always ends with a position that allows that anyway (how else could you always do a slice/R2 turn after the scramble?) The request is simple, please do either a) Add a (0,0) at the end of the scramble if a slice/R2 turn is meant b) Add the / back to the scrambles
Mike Hughey (2009-04-14 15:59:27 +0000)
I just today realized that the rule I thought was true is in fact codified in the rules: 12c) Notation for Square-1 : (hold smallest slice in middle layer on left side of front face) * 12c1) (x,y) means: turn upper layer x times 30 degrees clockwise, turn bottom layer y times 30 degrees clockwise, turn right half of the puzzle 180 degrees. But as Arnaud mentions, this conflicts with the rule that states a scramble should have 40 moves. So either the scrambling notation should have the / added back, or else we should change the rule for scrambling to say the scramble length is "40 or 41 moves". In the meantime, I intend to continue to scramble following 12c1, rather than following the 40 move rule. (Except on Arnaud's online competitions, of course.) :)
qqwref (2009-05-04 05:25:59 +0000)
I think adding the / back is the best idea. I can't really think of any good reason to remove it other than space efficiency (but clearly that is not an issue since we could very well do without parentheses or even commas - we can turn (-5,5) (6,0) (3,-3) (-1,-4) into -55603-3-1-4 and it is still uniquely readable). It necessitates "workarounds" like (0,0) moves, makes things more confusing since it is different from all other types of scrambles by implying moves that are not written, and as we have seen leads to arguments about how exactly to read the scrambles. As long as / is a legal move after the final position, I think we should simply put the / back in.
qqwref (2009-08-11 23:44:16 +0000)
I don't want to bump an old topic, but I think it is appropriate because today I wrote a new Square-1 scrambler. It can be found at [url:381sb69q]http://mzrg.com/miniSites/scramblers/new%20sq1.htm[/url:381sb69q]. If you look at the code, it should be much less opaque than Jaap's code, and shorter as well - I used a different way of storing the pieces and moves which is much easier to deal with from a coding standpoint. Although I believe this is a better scrambler (from the standpoint of wanting to have an equal distribution of all possible scrambles), the scrambles will be a bit different from those of the old scrambler for a few reasons: - I don't understand what Jaap did with the axes, but my approach was, for each time I wanted an (x,y) move, to randomly choose one out of the set of every possibility which did not prevent a / move from being made (also not counting moves which would bring the total over 40 moves ftm). The net result of this was that there are much fewer (0,y) and (x,0) type moves than in scrambles from Jaap's program. - I had to remove the restriction of automatically putting a / after each (x,y) move in order to keep each scramble to 40 moves. I really do think it is an improvement to include the /, as it's easier to follow and as no (0,0) moves are necessary. I really hope that this scrambler, or a variation of it, can become the new official scrambler. Since the code is much easier to read and less complex, it should be significantly easier to understand, and thus easier to maintain in the future if we want to make changes in the way this puzzle is scrambled.