# Square-1 WCA-Style Markov Random State Scrambler in Javascript



## Lucas Garron (Nov 17, 2011)

- Hacking the old scrambler.
- Graphics cleaned up with Raphael.js (long overdue).
- Square-1 solver source written in CoffeeScript. (EDIT: No longer.)
- Using code ported from PPT. Walter really deserves the credit.
- Still not JS-optimized.
- The Javascript updates are hard to display in real-time, and I can't think of a way around it without some sort of continuations.

Go!


In case anyone tries it, would you mind posting benchmarks (without alerts, of course)?

Me:
- Google Chrome 15, OSX Lion
- Initialization is about 2.5s consistently
- Scramble generation is about <1s for most scrambles, but up to 5s for longer scrambles.


----------



## qqwref (Nov 17, 2011)

It basically crashed Firefox, so no benchmarks here. But of course, Firefox does perform extremely badly on any long js script.

Seems alright on Chrome although it takes longer than you say. The graphics don't look all that great but they do seem to not have the pixels outside of lines that the other one had. I don't understand what the code is doing (it's pretty ugly and clearly not written by hand) or why you had to throw together a few different Cool New Programming Languages to do it, but I'm definitely impressed that a javascript random-state scrambler exists. Hopefully with time the speed and code readability will increase.


----------



## Lucas Garron (Nov 17, 2011)

qqwref said:


> Seems alright on Chrome although it takes longer than you say.


How long, exactly? I'm going to try a few simple optimizations, but I don't know what the limiting capabilities fo Javascript arrays are.



qqwref said:


> The graphics don't look all that great but they do seem to not have the pixels outside of lines that the other one had.


The graphics look pretty okay for me. The main point is that this wasn't too hard to do, but it renders a lot better, and it's semantically better. The exported PDFs were so bad they occasionally crash my PDF reader.
(The current WCA scrambler uses an older, hackier drawing library.)



qqwref said:


> I don't understand what the code is doing (it's pretty ugly and clearly not written by hand) or why you had to throw together a few different Cool New Programming Languages to do it, but I'm definitely impressed that a javascript random-state scrambler exists. Hopefully with time the speed and code readability will increase.


Coffeescript is basically a thin syntactic layer over Javascript that compiles into "relatively" readable Javascipt (some cases like this scrambler become a bit messier, though). It makes it much easier to write Javascript without having to deal with all the little idiosyncrasies. sq1.coffee is pretty readable, I think.
For one, this made it a lot easier to port from Java. I wouldn't have any objections if anyone wanted to convert it to pure Javascript, I just thought Coffeescript would be better to use for a first pass (plus, I kind of wanted to learn it).


----------



## qqwref (Nov 17, 2011)

Lucas Garron said:


> How long, exactly?


Ten seconds or so. But it takes that much every time, I can't do the <1 second scramble generation that you mentioned.



Lucas Garron said:


> The graphics look pretty okay for me. The main point is that this wasn't too hard to do, but it renders a lot better, and it's semantically better.


Fair enough. But yeah, the lines are a little iffy looking, not a big deal though.



Lucas Garron said:


> Coffeescript is basically a thin syntactic layer over Javascript that compiles into "relatively" readable Javascipt (some cases like this scrambler become a bit messier, though). It makes it much easier to write Javascript without having to deal with all the little idiosyncrasies. sq1.coffee is pretty readable, I think.


It looks kinda okay in the coffee version, I guess, although it looks like the language has a lot of small details that are very important. The "compiled" Javascript is pretty damn awkward, though, and does a lot of really unnatural-looking stuff.



Lucas Garron said:


> For one, this made it a lot easier to port from Java. I wouldn't have any objections if anyone wanted to convert it to pure Javascript, I just thought Coffeescript would be better to use for a first pass (plus, I kind of wanted to learn it).


Fair enough, I suppose. I've always thought JS had a pretty similar feel to C/Java but I guess that's kind of subjective. Coffeescript reminds me a bit of Python.


----------



## cubeflip (Nov 17, 2011)

works great for me! I want to get back into square-1 so this could be helpful. Scrambling SQ-1 is annoying; I keep giving myself similar scrambles, so there are some cube-shape cases I never get to practice.


----------



## Lucas Garron (Nov 17, 2011)

Lucas Garron said:


> For one, this made it a lot easier to port from Java. I wouldn't have any objections if anyone wanted to convert it to pure Javascript, I just thought Coffeescript would be better to use for a first pass (plus, I kind of wanted to learn it).



The for loops were bothering me, and I couldn't find a way to get around them in Coffeescript, so I just reduced the Javascript source. I'm down to 2.5 seconds for initialization, with <1s for most scrambles, but a large SD.


----------



## MaeLSTRoM (Nov 17, 2011)

Can't get it to work on IE9/Firefox (using Win7)
Just to check, what order do you press the buttons in?


----------



## Lucas Garron (Nov 17, 2011)

MaeLSTRoM said:


> Can't get it to work on IE9/Firefox (using Win7)
> Just to check, what order do you press the buttons in?


Just press "Go!". You can try enabling the alerts first, if you want to see the progress in more detail (working on that).

Try Chrome, just to see if you can get it to work. Firefox is really bad with slow scripts, and Chrome's Javascript is way faster than other browsers for me.


----------



## Godmil (Nov 17, 2011)

Windows 7, Firefox 9.0 

was going to do an average, but you seem to have updated the page while I'm doing it and it nolonger works.
here was the times I got:
Initiate scrambles
3.273 0.247
3.201 0.481

Tried loading up in some version of IE, but it just hangs after saying it's generating scrambles.


----------



## Stefan (Nov 17, 2011)

Looks great!

Test in Chrome 15.0.874.120 m (on Windows XP):

```
14. Done initializing Square-1 Solver. [603ms split, 3732ms total]
Generated scramble #1. [17335ms split, 17336ms total]
Generated scramble #2. [1448ms split, 18784ms total]
Generated scramble #3. [146ms split, 18930ms total]
Generated scramble #4. [7713ms split, 26643ms total]
Generated scramble #5. [56ms split, 26699ms total]
```

Test in Opera 11.52 (on Windows XP):

```
14. Done initializing Square-1 Solver. [1319ms split, 12476ms total]
Generated scramble #1. [40332ms split, 40332ms total]
Generated scramble #2. [3574ms split, 43906ms total]
Generated scramble #3. [216ms split, 44122ms total]
Generated scramble #4. [18286ms split, 62408ms total]
Generated scramble #5. [49ms split, 62457ms total]
```
But only the images for the fifth scramble showed up, for the first four I only see "Created with Raphaël 2.0.0". I tested it again and it happened again. The images for the first four scrambles *were* shown temporarily, when they were the last scramble so far. Like when the first three scrambles had been computed, only the images of the third scramble were shown, and when the fourth scramble appeared, the images of the third scramble turned into that text.

Test in Firefox 8.0 (on Windows XP):

```
14. Done initializing Square-1 Solver. [523ms split, 10418ms total]
Generated scramble #1. [101807ms split, 101808ms total]
Generated scramble #2. [7560ms split, 109368ms total]
Generated scramble #3. [638ms split, 110006ms total]
Generated scramble #4. [40058ms split, 150064ms total]
Generated scramble #5. [238ms split, 150302ms total]
```

Test in Internet Explorer 8.0.6001.18702IC (on Windows XP):
It switches to say "Generating Square-1 Scrambles..." but then it doesn't seem to do anything anymore.

The first scramble always took very long. Is something not fully initialized when you start it?


----------



## Lucas Garron (Nov 17, 2011)

Stefan said:


> But only the images for the fifth scramble showed up, for the first four I only see "Created with Raphaël 2.0.0".


Confirmed over here. I don't remember seeing issues in Opera before, but I should look into it.



Stefan said:


> Test in Internet Explorer 8.0.6001.18702IC (on Windows XP):
> It switches to say "Generating Square-1 Scrambles..." but then it doesn't seem to do anything anymore.


A while ago I decided that I don't care about Internet Explorer one bit anymore. (Especially since I can't test on it as easily). If anyone can tell me what's wrong / how to fix it, I might look into it. I also take pull requests. 



Stefan said:


> The first scramble always took very long. Is something not fully initialized when you start it?


No idea. I don't recall this being an issue in earlier testing, but now it shows up consistently. It's odd because it takes even longer than initialization.
My first guess was that the Javascript interpreter needs to "warm up" to something (e.g. data structures) used in the search, but I hope that's not the case, because I can't fix that.


----------



## Mike Hughey (Nov 17, 2011)

Mine in Firefox 8.0, Windows 7 64-bit:

```
14. Done initializing Square-1 Solver. [374ms split, 6849ms total]
Generated scramble #1. [56866ms split, 56867ms total]
Generated scramble #2. [4108ms split, 60975ms total]
Generated scramble #3. [359ms split, 61334ms total]
Generated scramble #4. [25425ms split, 86759ms total]
Generated scramble #5. [64ms split, 86823ms total]
```

I really hope we can go to something like this soon; I've always hated the old square-1 scramblers. And shorter scrambles is an added bonus - it should cut down on competition time!

I'm very tempted to switch to this for the weekly competition. Not this week, but maybe soon.


----------



## @uguste (Nov 17, 2011)

Clément showed us a optimal square-1 scrambler at last Montpellier Open (in May) which looked like this one...


----------



## Lucas Garron (Nov 18, 2011)

@uguste said:


> Clément showed us a optimal square-1 scrambler at last Montpellier Open (in May) which looked like this one...


I hear he ported Jaap's solver to tnoodle.

1) Did it *actually* look like this and run client-side in a browser?
2) There must be some reason the WCA isn't using it yet, because we're obviously still using bad scrambles.


----------



## Lucas Garron (Nov 23, 2011)

Walter's given his permission, so I've submitted this to the WCA board.


----------



## MaeLSTRoM (Nov 24, 2011)

Finally got the scrambler to initialize in IE 9.
Here's the time codes up to that point:

1. Initializing Square-1 Solver. [7ms split, 7ms total]
2. Generating shape tables. [14ms split, 21ms total]
3. Shape Table Depth: 10/20 [14933ms split, 14954ms total]
4. Shape Table Depth: 12/20 [43906ms split, 58860ms total]
5. Shape Table Depth: 15/20 [80146ms split, 139006ms total]
6. Generating move tables. [6667ms split, 145673ms total]
7. Corner permutation move table... [206ms split, 145879ms total]
8. Corner combination move table... [14197ms split, 160076ms total]
9. Edges permutation move table... [47ms split, 160123ms total]
10. Length: 8 [6ms split, 160129ms total]
11. Edges combination move table... [14654ms split, 174783ms total]
12. Generating prune tables. [45ms split, 174828ms total]
13. Corners distance prune table... [2ms split, 174830ms total]
14. Edges distance prune table... [6554ms split, 181384ms total]
15. Done initializing Square-1 Solver. [134901ms split, 316285ms total]

Using Markov Random-State scrambles.
Generating 5 scrambles. [1ms split, 1ms total]

So yeah, 5 minutes to load a scrambler :/


----------



## Carrot (Nov 24, 2011)

OS: Windows 7, 64 bit
Browser: Google Chrome: 15.0.874.121 m


First Run (13+14.5)


Spoiler



1. Initializing Square-1 Solver. [11ms split, 11ms total]
2. Generating shape tables. [9ms split, 20ms total]
3. Shape Table Depth: 10/20 [581ms split, 601ms total]
4. Shape Table Depth: 12/20 [1534ms split, 2135ms total]
5. Shape Table Depth: 15/20 [2725ms split, 4860ms total]
6. Generating move tables. [229ms split, 5089ms total]
7. Corner permutation move table... [14ms split, 5103ms total]
8. Corner combination move table... [743ms split, 5846ms total]
9. Edges permutation move table... [19ms split, 5865ms total]
10. Length: 8 [15ms split, 5880ms total]
11. Edges combination move table... [773ms split, 6653ms total]
12. Generating prune tables. [22ms split, 6675ms total]
13. Corners distance prune table... [16ms split, 6691ms total]
14. Edges distance prune table... [314ms split, 7005ms total]
15. Done initializing Square-1 Solver. [6088ms split, 13093ms total]

Using Markov Random-State scrambles.
Generating 5 scrambles. [2ms split, 2ms total]
Generated scramble #1. [1687ms split, 1689ms total]
Generated scramble #2. [307ms split, 1996ms total]
Generated scramble #3. [482ms split, 2478ms total]
Generated scramble #4. [80ms split, 2558ms total]
Generated scramble #5. [11924ms split, 14482ms total]


Second Run (7.5)


Spoiler



Using Markov Random-State scrambles.
Generating 5 scrambles. [0ms split, 0ms total]
Generated scramble #1. [564ms split, 564ms total]
Generated scramble #2. [128ms split, 692ms total]
Generated scramble #3. [4094ms split, 4786ms total]
Generated scramble #4. [189ms split, 4975ms total]
Generated scramble #5. [2518ms split, 7493ms total]


Third Run (10.5)


Spoiler



Using Markov Random-State scrambles.
Generating 5 scrambles. [0ms split, 0ms total]
Generated scramble #1. [3839ms split, 3839ms total]
Generated scramble #2. [5858ms split, 9697ms total]
Generated scramble #3. [365ms split, 10062ms total]
Generated scramble #4. [303ms split, 10365ms total]
Generated scramble #5. [67ms split, 10432ms total]


Fourth Run (1:11)


Spoiler



Using Markov Random-State scrambles.
Generating 5 scrambles. [0ms split, 0ms total]
Generated scramble #1. [2539ms split, 2539ms total]
Generated scramble #2. [638ms split, 3177ms total]
Generated scramble #3. [66883ms split, 70060ms total]
Generated scramble #4. [333ms split, 70393ms total]
Generated scramble #5. [783ms split, 71176ms total]


Fifth Run (6)


Spoiler



Using Markov Random-State scrambles.
Generating 5 scrambles. [0ms split, 0ms total]
Generated scramble #1. [2835ms split, 2835ms total]
Generated scramble #2. [185ms split, 3020ms total]
Generated scramble #3. [2096ms split, 5116ms total]
Generated scramble #4. [153ms split, 5269ms total]
Generated scramble #5. [825ms split, 6094ms total]


----------



## Michael Womack (Nov 27, 2011)

How long do I have to whate until you make a super square-1 scrambler?


----------



## MaeLSTRoM (Nov 27, 2011)

Michael Womack said:


> How long do I have to whate until you make a super square-1 scrambler?


 
Just do 2 individual scrambles, one on inner layers, one on outer.


----------



## Michael Womack (Nov 27, 2011)

MaeLSTRoM said:


> Just do 2 individual scrambles, one on inner layers, one on outer.


 
Ok thanks for that tip.


----------



## Stefan (Nov 28, 2011)

Do you have statistics for how long the scrambles are? In both the <R>-metric and the <R,U,D>-metric. I counted a few and they seem to be shorter than the WCA's 40 <R,U,D> moves but longer (in both metrics) than optimal would be. If it's significantly shorter than the WCA's 40, you could mention that as an advantage in the WCA thread - faster to scramble and fewer opportunities to screw up.


----------



## Mike Hughey (Dec 9, 2011)

I was wondering, is this essentially the same scrambler that is at http://www.cubing.net/sq1/? Apparently the one at www.cubing.net is now the official scrambler, since competitions have been told to start using that this weekend.

I'm about to post the weekly competition, and I wanted to switch to the new official one, to try it out.

The code at first looks quite different, but both of them have Lucas's name on them - is the one at www.cubing.net a "cleaned-up" version? I didn't really read through the code to see if they were fundamentally the same or not (I'm lazy).

I also noticed that the scrambler at www.cubing.net has a tendency not to generate slashes at the end. In an admittedly small sampling, I noticed that only 8 of the first 40 scrambles I tried ended in slashes. I can see how optimized scrambles might work out that way, but I was just wondering - do you think that result is expected?

As for the length, it looked like the average length was several slice moves shorter than the old generated scrambles. However, it also looked like there were fewer 0s in the scrambles, so I'm not sure it's actually much easier to scramble.

Edit: I just actually tried a few of the scrambles. I didn't realize that it starts off solving the cubic version, then moves away from square at the end. So it's kind of like one of my BLD solves in reverse - cool! That actually makes it much easier to scramble - the puzzle stays cubic until the last 7 or fewer moves or so. So if you mess up early, you'll know you did, and it will be relatively easy to solve and try again since you don't have to get to square (unless you mess up at the end). This seems a lot nicer than the old scrambler, actually.


----------



## Lucas Garron (Dec 9, 2011)

Mike Hughey said:


> I was wondering, is this essentially the same scrambler that is at http://www.cubing.net/sq1/? Apparently the one at www.cubing.net is now the official scrambler, since competitions have been told to start using that this weekend.
> 
> I'm about to post the weekly competition, and I wanted to switch to the new official one, to try it out.
> 
> The code at first looks quite different, but both of them have Lucas's name on them - is the one at www.cubing.net a "cleaned-up" version? I didn't really read through the code to see if they were fundamentally the same or not (I'm lazy)


Yes. The Square-1 scrambler at http://www.cubing.net/sq1/? is Mark 2 with everything but Square-1 hidden.
I wrote the scrambler in this post first, then incorporated into a general scrambler, which became Mark 2. Since then, the code has been cleaned up a little more (and the Square-1 code is also faster).

Since it's temporary, I was going to leave it to the WCA to announce if it wanted.
(Basically, I poked Tyson and said "We really need to switch to a random-state Square-1 scrambler", and he sent out an email making this one temporarily the official one.)



Mike Hughey said:


> I also noticed that the scrambler at www.cubing.net has a tendency not to generate slashes at the end. In an admittedly small sampling, I noticed that only 8 of the first 40 scrambles I tried ended in slashes. I can see how optimized scrambles might work out that way, but I was just wondering - do you think that result is expected?


It depends on the solver. Apart from sampling a bunch of scrambles, I have no idea what the distribution of final moves will be.

Also note that this scrambler does not follow official Square-1 scrambling notation. I'm going to push to have the notation reverted to include slashes for 2012, because it's 1) not much longer, 2) not as confusing to novice scramblers, 3) clear about the final move.



Mike Hughey said:


> As for the length, it looked like the average length was several slice moves shorter than the old generated scrambles. However, it also looked like there were fewer 0s in the scrambles, so I'm not sure it's actually much easier to scramble.


Yeah, I think it's a bit shorter, which is good - faster and fewer chances for errors. Hopefully having fewer 0s doesn't mean more errors, though.
One thing to consider is that random-turn Square-1 scrambler would have to be significantly longer to be sufficiently random.



Mike Hughey said:


> Edit: I just actually tried a few of the scrambles. I didn't realize that it starts off solving the cubic version, then moves away from square at the end. So it's kind of like one of my BLD solves in reverse - cool! That actually makes it much easier to scramble - the puzzle stays cubic until the last 7 or fewer moves or so. So if you mess up early, you'll know you did, and it will be relatively easy to solve and try again since you don't have to get to square (unless you mess up at the end). This seems a lot nicer than the old scrambler, actually.


Yeah, it's a solver! It solves into cube shape with the correct parity, and then searches within cube shape. (The scramble is the reverse solution of a randomly generated state.) The middle slice is actually given a random orientation via a hack; adding it toe the solver made the solver significantly slower, but the middle slice parity of an algorithm can be changed by doing something like replacing a (x, 0) move with (x, 0) (6, 0) / (6, 0) / (6, 0) / = (x + 6, 0) /(6, 0) /(6, 0) /. This is even more efficient if there's a (6, 0) in the scramble.

As for staying in cube shape longer, that's a good point! I'll try to make sure to write this down somewhere, since this seems like it could be a very useful property.


----------



## Lucas Garron (Jan 8, 2012)

Just an update: This official WCA scrambler for Square-1 is now based on this. It's available at http://www.worldcubeassociation.org/regulations/scrambles/sq1/

Delegates were instructed to start using http://www.cubing.net/sq1/ last month, but Ron made a revision to the regulations today.

While I'm excited that the WCA is finally mandating a random-state scrambler, I hope this will only get better. In particular, I'm sure it's possible to write a scrambler that always produces significantly at a rate of faster than one per second.


----------



## Michael Womack (Jan 9, 2012)

hey Lucas are you going to make a Square-2 scrambler or is there already one out there that I can use?


----------



## Lucas Garron (Jan 10, 2012)

Michael Womack said:


> hey Lucas are you going to make a Square-2 scrambler or is there already one out there that I can use?


It's not a priority, even if it's not as hard as Square-1. For now, it would probably be fine to adapt qq's megascramble.


----------



## Michael Womack (Jan 10, 2012)

Lucas Garron said:


> It's not a priority, even if it's not as hard as Square-1. For now, it would probably be fine to adapt qq's megascramble.


 
ok thanks Lucas


----------

