• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

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

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
- 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.
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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.

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

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).
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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.

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.

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.

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.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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

Premium Member
Joined
Aug 12, 2010
Messages
2,203
Location
Aberdeen, Scotland
YouTube
Visit Channel
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.
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Looks great!

Test in Chrome 15.0.874.120 m (on Windows XP):
Code:
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):
Code:
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):
Code:
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

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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.

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. :)

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

Administrator
Staff member
Joined
Jun 7, 2007
Messages
11,305
Location
Indianapolis
WCA
2007HUGH01
SS Competition Results
YouTube
Visit Channel
Mine in Firefox 8.0, Windows 7 64-bit:
Code:
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.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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.
 

MaeLSTRoM

Member
Joined
Jan 7, 2011
Messages
1,862
Location
UK
WCA
2011WALL02
YouTube
Visit Channel
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

Member
Joined
Feb 9, 2009
Messages
1,910
WCA
2008ANDE02
YouTube
Visit Channel
OS: Windows 7, 64 bit
Browser: Google Chrome: 15.0.874.121 m


First Run (13+14.5)
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)
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)
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)
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)
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]
 
Last edited:
Top