# Proposal: web-based random state scrambles for 3x3



## Cride5 (May 13, 2010)

In partnership with other developers I've put together an open-source browser-based random-state scrambler for 3x3 which I would like to propose as an official scrambler for WCA competitions.

The main post on the WCA forum is here:
http://www.worldcubeassociation.org/forum/viewtopic.php?f=4&t=871

A demo of the scrambler application is here:
http://cube.crider.co.uk/wca_scrambler/scramble_cube_333.htm

... note: please wait for initial download of ~2.6MB jar file. Requires Sun Java plugin.

Because many of you aren't registered on the WCA forums I'd just like to gauge general opinion on this here. Does it (in principle) sound like a good idea?


----------



## qqwref (May 13, 2010)

Yep, sounds like a very good idea. It's far more convenient to have a web application generate all the scrambles than to be forced to use CubeExplorer for (only) 3x3 ones.

It's surprisingly quick to generate single scrambles too, once the jar file is downloaded. If only it didn't require an extra ~2MB I'd want to put it into qqTimer...


----------



## masterofthebass (May 13, 2010)

In the web application, the images do not work for me in Safari or Chrome on OS X, although it does work in Firefox


----------



## Cride5 (May 13, 2010)

masterofthebass said:


> In the web application, the images do not work for me in Safari or Chrome on OS X, although it does work in Firefox



Interesting, do they work on this?
http://www.worldcubeassociation.org/regulations/scrambles/scramble_cube.htm?size=3&num=5&len=25

... I've found that scaling a page causes the cube images not to render properly in firefox. The behaviour should be the same on the WCA scrambler as the demo version, since the code which generates the cube images is the same.


----------



## Toad (May 13, 2010)

masterofthebass said:


> In the web application, the images do not work for me in Safari or Chrome on OS X, although it does work in Firefox



Doesn't work for me in safari too. Haven't tried any other browsers.


----------



## Cride5 (May 13, 2010)

randomtoad said:


> masterofthebass said:
> 
> 
> > In the web application, the images do not work for me in Safari or Chrome on OS X, although it does work in Firefox
> ...



Do you have any more info? Is the applet failing to load, or are cube images not rendering? 

If the applet is failing to load, do you have the 'Sun' java plug-in installed?


----------



## masterofthebass (May 13, 2010)

Cride5 said:


> randomtoad said:
> 
> 
> > masterofthebass said:
> ...



The official scrambler image works. It probably is the applet failing to load, although I am able to get scrambles. Java on Macs is horrible because apple decided to develop it themselves, instead of having Sun do it, so there is no 'Sun' plugin, but I have the latest apple one.

edit:
here's a picture.


----------



## Cride5 (May 13, 2010)

Ah, cheers for the screenshot ... that tells me what it can/can not be. The applet is only responsible for providing the scramble string, which seems to be working perfect. The problem appears to be within the JavaScript.

Does Safari have any kind of JavaScript error console (similar to the one on Firefox)? I'm going to look closer at the image generator code to see if I can find the issue, but if there are any kind of error messages coming from the script they would be very helpful, cheers..


----------



## Stefan (May 13, 2010)

After 3 minutes, I gave up waiting for something to appear (it was still loading).


----------



## Bryan (May 13, 2010)

Can you post a .zip that people can download and run locally?


----------



## PatrickJameson (May 13, 2010)

Works fine for me on Win7 Chrome and Firefox. It takes about 1-2 seconds to load for both.


----------



## Cride5 (May 13, 2010)

StefanPochmann said:


> After 3 minutes, I gave up waiting for something to appear (it was still loading).


And you're on a reasonably fast connection?
What platform/browser/Java plugin are you using?
While you were waiting for it to load was your CPU running at 100%?



Bryan said:


> Can you post a .zip that people can download and run locally?


Yup, sure here it is:
http://dl.dropbox.com/u/4352576/wca_scrambler.zip


----------



## Cride5 (May 13, 2010)

masterofthebass said:


> In the web application, the images do not work for me in Safari or Chrome on OS X, although it does work in Firefox



OK, I've tracked down the problem, and it appears that Safari isn't interpreting the String.length property correctly. Either that, or the object returned by the applet isn't being classified as a String.

I've updated the code to attempt to force string type, so it may just fix it. Any Safari users want to test it? Cheers..


----------



## Toad (May 13, 2010)

Cride5 said:


> masterofthebass said:
> 
> 
> > In the web application, the images do not work for me in Safari or Chrome on OS X, although it does work in Firefox
> ...



Works perfectly now for me


----------



## Kenneth (May 13, 2010)

Cride5 said:


> StefanPochmann said:
> 
> 
> > After 3 minutes, I gave up waiting for something to appear (it was still loading).
> ...



Was up here after about a minute and I got 10 megabit downstream.


BTW, can you make it show the lengt of the scrambles? like : R U R U (4f)


----------



## Cride5 (May 13, 2010)

randomtoad said:


> Cride5 said:
> 
> 
> > masterofthebass said:
> ...



Great news, thanks for testing it for me 



Kenneth said:


> BTW, can you make it show the lengt of the scrambles? like : R U R U (4f)



Done.


----------



## Stefan (May 13, 2010)

Cride5 said:


> StefanPochmann said:
> 
> 
> > After 3 minutes, I gave up waiting for something to appear (it was still loading).
> ...



Yes.
WinXP / Opera 10.53 / Sun Java 6.20
No idea.

But I just tried again and it worked, took about 15 seconds. Right after the first attempt my computer was also messed up, the (alt-tab didn't show me the programs, couldn't open the network status window). Don't know what caused what. I rebooted afterwards. Will let you know if I experience problems again, but right now it works fine.


----------



## brunson (May 13, 2010)

Not to be picky, but if it's a Java app, then it's not really web based, is it? Sorry, I just hate Java apps. 

Or is it just the cube viewer that's Java? I could write something to render the images server side.


----------



## StachuK1992 (May 13, 2010)

PatrickJameson said:


> Works fine for me on Win7 Chrome and Firefox. It takes about 1-2 seconds to load for both.


This exactly.


----------



## Cride5 (May 13, 2010)

brunson said:


> Not to be picky, but if it's a Java app, then it's not really web based, is it? Sorry, I just hate Java apps.
> 
> Or is it just the cube viewer that's Java? I could write something to render the images server side.



The Java component of the application is the scramble generator. Its job is simply to provide scramble string on request. Everything else (including image generation) is done by JavaScript.


----------



## FatBoyXPC (May 13, 2010)

I'm curious to why this needs java at all? People have written plenty of image scripts for the cube (web based, non java), and there are also plenty of scramblers out there using javascript (I think that's how cubetimer does it?) to generate the scramble. I'm certain you could do all this with php just as easily, and avoid the 2.6mb jar file. Granted the page would have to reload for the new scramble but you could fix that with frames, or just as it reloads keep the content and as it refreshes it puts the content back.

Edit: I posted this prior to your response to brunson 

Why have java generate the scramble when you can do it with anything else that's completely web-based and doesn't need the client to download a file?


----------



## brunson (May 13, 2010)

It's mainly a matter of distribution of compute cycles. Pushing the java to the browser means the server doesn't have to do the computation of the solve. The generation of the initial random position is not computationally intensive, but the solve of the position to get the scramble would be quite a bit more (I think). A few dozen people hitting the server at the same time for scrambles could really put a load on the backend.

Who's up for porting Kociemba's solver to Javascript. 

Edit: The solve doesn't have to be optimal, maybe that could take some load off a server side implementation. Or we could bribe Tom Rokiki to use his contacts and let us run the solvers on Sony's render farm. jk


----------



## Cride5 (May 13, 2010)

brunson said:


> Who's up for porting Kociemba's solver to Javascript. ;-)



Yup, I tried that a while ago. JavaScript just isn't cut out for the two-phase algorithm. The lookup tables are too big.


----------



## FatBoyXPC (May 13, 2010)

So are you saying the load is due to the fact we have images of what the scrambled cube will look like, correct? The server doesn't have to quite compute a solve here, it's only shifting colors as moves are performed. That is quite different than a "solve."


----------



## Stefan (May 13, 2010)

brunson said:


> It's mainly a matter of distribution of compute cycles.



Mmh, I think the real reason is that the WCA scramblers need to work in emergency cases, like the competition organizer forgot the scrambles and there's no internet at the venue. At least that's the reason I remember for the javascript scramblers.

Edit: OMG, fatboyxpc is so full of fail.


----------



## Toad (May 13, 2010)

fatboyxpc said:


> So are you saying the load is due to the fact we have images of what the scrambled cube will look like, correct? The server doesn't have to quite compute a solve here, it's only shifting colors as moves are performed. That is quite different than a "solve."



Do you understand what it means by "random state scrambles"?

(Not insulting, just asking.)


----------



## Bryan (May 13, 2010)

fatboyxpc said:


> Why have java generate the scramble when you can do it with anything else that's completely web-based and doesn't need the client to download a file?



Because you're then dependent on a web connection.


----------



## FatBoyXPC (May 13, 2010)

Stefan: Elaborate where I failed. It's not really a fail when I thought it was clear I do not understand why it has to be Java based, and he mentioned computation cycles. If it is about that, please explain why I failed.

Randomtoad: Apparently I don't, please explain.

Bryan: You're also dependent on the web connection to navigate to his webpage. Yes it might run after that, but if you don't have a connection first, what good is it?


----------



## brunson (May 13, 2010)

There's no need to be mean.

The 3x3 scrambler doesn't randomly generate moves to apply to the cube to get to a random state, it randomly generates a state, then computes the moves to get to that state. Essentially, you can think of it as disassembling a cube, then randomly reassembling it just making sure that it's still solvable. 

You then calculate the solution to that state using that solver and reverse it to get the scramble. The images are created in the Javascript on the browser.

Does that make sense?


----------



## Dene (May 13, 2010)

StefanPochmann said:


> Edit: OMG, fatboyxpc is so full of fail.



Oh come on you only said that for the Pochmann Magic 8-ball


----------



## Bryan (May 13, 2010)

fatboyxpc said:


> Bryan: You're also dependent on the web connection to navigate to his webpage. Yes it might run after that, but if you don't have a connection first, what good is it?



You can save a webpage to your computer. As long as the webserver itself isn't doing any processing (like PHP), then it works locally.


----------



## FatBoyXPC (May 13, 2010)

Brunson yeah I just looked it up after I got out of the shower. The only problem with that is there are some rules you have to follow, because everybody should agree that you cannot just reassemble a cube however you like (and this is stated in the wiki as well). Certainly I understand your definition (as well as the definitions off the wiki) are quite basic, but I still don't see why this yields any advantage over a scramble generator and a random state scramble generator. The wiki states this method is used to provide no bias toward easy solutions, but I still don't see how it's any better for this method as opposed to making 20 random moves.

Edit: Bryan I understand you can do that, but you can also save any other scramble generator and run everything locally. You can also do the same with PHP files if you are so inclined to install a PHP server on your computer. And if the purpose is to save it to your computer, why not just use cube explorer? He stated this is based off Kociemba's code anyway.


----------



## brunson (May 13, 2010)

fatboyxpc said:


> Brunson yeah I just looked it up after I got out of the shower. The only problem with that is there are some rules you have to follow, because everybody should agree that you cannot just reassemble a cube however you like (and this is stated in the wiki as well).


Which is why I said, "... making sure that it's still solvable".


fatboyxpc said:


> Certainly I understand your definition (as well as the definitions off the wiki) are quite basic, but I still don't see why this yields any advantage over a scramble generator and a random state scramble generator. The wiki states this method is used to provide no bias toward easy solutions, but I still don't see how it's any better for this method as opposed to making 20 random moves.


Because of the connectedness of the graph of states of the cube, any random series of moves will tend away from solved but also away from maximum distance from solved. Just as a Random Walk will result in a Gaussian distribution of position around the starting point, random movement through the cube state graph would reach a semi-stable equilibrium at some distance from solved. i.e. You would probably never reach solved again and you would probably never reach a 20 move scramble.

Random position generation gives equal weight to all states of the cube.

This has been discussed a few times in the Theory area.


----------



## Stefan (May 13, 2010)

brunson said:


> random movement through the cube state graph would reach a semi-stable equilibrium *at some distance from solved*. i.e. You would *probably never reach solved again* and you would probably never reach a 20 move scramble.



Somehow that sounds like the solved state is less likely to be reached than those at that some distance...



fatboyxpc said:


> You can also do the same with PHP files if you are so inclined to *install a PHP server on your computer*.


Right, cause that's about as easy as installing Java.



fatboyxpc said:


> And if the purpose is to save it to your computer, why not just use cube explorer?


Have you tried Cube Explorer on a non-Windows computer?


----------



## qqwref (May 13, 2010)

Sure, you probably COULD do it in Javascript. But Javascript is slow and Java is fast, and Javascript isn't good at dealing with integers and large tables. I am not sure it is possible to make a pure-JS implementation of Kociemba's algorithm that is both reasonably fast and reasonably efficient.



brunson said:


> Just as a Random Walk will result in a Gaussian distribution of position around the starting point, random movement through the cube state graph would reach a semi-stable equilibrium at some distance from solved. i.e. You would probably never reach solved again and you would probably never reach a 20 move scramble.



I disagree. From experience it seems like, if you do enough random moves, you can get every position to have an arbitrarily close probability to the probability in a uniform random distribution.


----------



## Samania (May 13, 2010)

im on firefox. and its been a while and has said loading.


----------



## Stefan (May 14, 2010)

qqwref said:


> Sure, you probably COULD do it in Javascript. But Javascript is slow and Java is fast, and Javascript isn't good at dealing with integers and large tables. I am not sure it is possible to make a pure-JS implementation of Kociemba's algorithm that is both reasonably fast and reasonably efficient.


Can anyone here judge ActionScript's aptitude for this? I'm about to learn it (for something else) and I've seen some benchmarks where it was fairly fast, e.g.:
http://oddhammer.com/actionscriptperformance/set4/ (old)
http://www.insideria.com/2009/03/java-collections-for-flex.html (newer)

Also, doesn't have to be a 2-phase algorithm. Thistlethwaite just taking the first solution averages 31.3 moves, which could be improved by trying more solutions like Cube Explorer does (it's been on my dream-todo-list for a while).


----------



## Joël (May 14, 2010)

qqwref said:


> I disagree. From experience it seems like, if you do enough random moves, you can get every position to have an arbitrarily close probability to the probability in a uniform random distribution.



I vaguely recall that they switched to the (pseudo?) random state scramber because it was shown the old scrambler was biased... And that some edge orientation states had another frequency of occurrence than you would expect with a random state scrambler. This could be relevant when ppl start to be extremely good with zz..

This does bring up some interesting questions about the 'random states' being generated now, since technically they aren't random. 

I've thought about this a while ago: Given a certain scramble/cube state, would it be possible for anyone who reverse-engineers cube explorer, and the pseudo random number generator being used to predict the next scramble (using a computer)?


----------



## JBCM627 (May 14, 2010)

Works great for me, and only took a few seconds to download... 2.5MB isn't that bad. I generally like to stay away from Java applets on principle, but this seems to work well.


StefanPochmann said:


> Can anyone here judge ActionScript's aptitude for this? I'm about to learn it (for something else) and I've seen some benchmarks where it was fairly fast


That would be great 
I've only seen one person on here write anything using it: http://www.speedsolving.com/forum/showthread.php?t=19658


It would be nice to see those green arrows (or something similar) where you can look for a shorter generator if it exists... I usually hit those once or twice when generating scrambles to get them below 20 moves.


----------



## Johannes91 (May 14, 2010)

If requiring internet connection is ok, then yeah it'd be much better to put a scramble generator on some server and make a small web page for it. Load shouldn't be a problem because you could make it generate scrambles 24/7 and put them to a queue. When the queue is almost empty you'd start accepting less optimal solutions to make generation faster.

But the whole point of this is that it works offline and doesn't need anything fancy, just a web browser with java.


I always thought, based on intuition, that if you start from the solved state and make some random moves, the solved state would be the most likely position you'd end at and positions very far away would be the least likely (this of course doesn't hold if you make only like 5 moves and avoid cancellations, but that's a special case). What brunson described sounds completely different and I don't really understand it and what the problem with that scenario would be, could someone who knows the math behind this try to explain it in layman terms?


----------



## brunson (May 14, 2010)

I could be wrong about it, but this is how I think about it. It could be tested if we had a perfect solver and a tremendous amount of time.

But imagine it this way: Say you are at a position with an optimal solution of 16 moves. If you make one turn at random, are you likely to be closer or further away from solved? Repeat that exercise indefinitely and I think you're probably find you migrate around the positions with solutions of about 14 to 17 moves. Maybe it's more the case of there just being so many more positions that are 16 moves away from solved than there are solved positions.

Though, upon reflection, you may be able to make the case that any given position is as arbitrary as the solved state. I could very well be wrong about the whole thing.

Edit: Actually, I think my comparison to the Random Walk could show that I'm wrong about it. Consider moving through the graph as a constrained random walk where you travel a fixed distance in each iteration, but are constrained to making turns in increments of 10 degrees. Your distance from the starting point should still be Gaussian. I will have to think more about it on my drive home.


----------



## Stefan (May 14, 2010)

brunson said:


> you may be able to make the case that any given position is as arbitrary as the solved state.



Yep, that's what I thought. You can say the same things about any other state (if you're 16 moves away, you're more likely to move further away than get closer), the solved state is nothing special (except that you started your walk there). At least for 3x3x3 and the like. I believe it's not true for Square-1.


----------



## Cride5 (May 14, 2010)

OK, so I finally managed to get it working with chrome on Linux, and I'm hoping the fix will make it work on chrome on Mac too, but this still needs to be tested. The problem was that browser was trying to request scrambles before the applet had properly loaded, even though the applet is 'technically' supposed to be rendered first. The problem was fixed by implementing a small delay in generating the scrambles on first load. During this delay 'Loading...' is displayed on the page. Subsequent scramble requests are done internally, so there shouldn't be any further delays. 

So the app has now been tested to work on:
Ubuntu/Firefox
Ubuntu/Chrome
Ubuntu/Opera ... although there is quite a delay (~30sec to 1min)
Windows XP/IE6
Windows XP/Firefox
Windows XP/Chrome

I'm not sure what is causing the delay in opera. I suspect it has something to do with the JVM being slow, because testing the applet in isolation is also desperately slow. Any Opera wizards out there to shed light on this?

I'm hoping it now works on all browsers, but if you find any problems with it, please let me know.

If you find it doesn't work, the applet can be tested in isolation by visiting:
http://cube.crider.co.uk/wca_scrambler/testapplet.html

I've also packaged up new off-line version for running in a connectionless environment. Get it at:
http://cube.crider.co.uk/wca_scrambler/offline_version.zip

.. and just as a reminder, the source code for the applet is available at:
http://cube.crider.co.uk/wca_scrambler/JCubeExplorer_src.zip

Thank you all for your help in testing it and reporting problems.


----------



## masterofthebass (May 14, 2010)

o lawd, i just realized chrome for mac doesn't support java yet. That's why it didn't work


----------



## FatBoyXPC (May 14, 2010)

Joel brings up the point I didn't make very clear about these "random states." They aren't quite random. They are just as random as these scramblers. I personally feel that these random scramblers would be more random because you can write it all randomly and not force specific orientations in the midst of your random state generation.

Granted I haven't written a scrambler, but keep thinking about if I should, it'd be a decent learning experience.

Stefan: No I haven't tried using cube explorer in a non-windows PC, but I also know that if it was that difficult to use I could either A) Install a virtual PC w/Windows onto whatever OS/distro I have and call it a day, or B) possibly use Wine if we're talking Linux. Also installing PHP as an alternative to java? I see your point, but WAMP installations are quite user friendly, and let us also not forget that PHP has an interpreter for a command line interface. I'm only suggesting alternatives, and installing WAMP is about as user friendly as a typical installwizard on windows, which would be similar to installing java. Don't forget that to have the java plugin for your browser, it must be downloaded and installed (commonly done by manufacturers these days for users who buy pre-built machines, but still my point exists). Also stefan, do you really think there won't be a single person there with a windows computer at the event?


----------



## Cride5 (May 14, 2010)

fatboyxpc said:


> JNo I haven't tried using cube explorer in a non-windows PC



The other problem with cube explorer is that it's not open source, while the Java implementation of it is.


----------



## Stefan (May 14, 2010)

Cride5 said:


> Ubuntu/Opera ... although there is quite a delay (~30sec to 1min)
> 
> I'm not sure what is causing the delay in opera.



On Windows, it's working fine for me now. I visited the page once again, this time I guess it was from cache, it was done in a second.


----------



## FatBoyXPC (May 14, 2010)

Cride5 said:


> fatboyxpc said:
> 
> 
> > JNo I haven't tried using cube explorer in a non-windows PC
> ...



Why does it need to be open source? I understand the benefits from it, but why is it necessary? Please don't take this as me saying your project is worthless, I think it's wonderful, I just don't understand all the reasons behind all this.


----------



## qqwref (May 14, 2010)

Joël said:


> qqwref said:
> 
> 
> > I disagree. From experience it seems like, if you do enough random moves, you can get every position to have an arbitrarily close probability to the probability in a uniform random distribution.
> ...


Sure, but all this proves is that 25 moves is not enough. We've seen this before anyway.



Joël said:


> I've thought about this a while ago: Given a certain scramble/cube state, would it be possible for anyone who reverse-engineers cube explorer, and the pseudo random number generator being used to predict the next scramble (using a computer)?


As I recall the way it's currently done is to take a bunch of random numbers and look at them mod a bunch of smaller numbers to get CO, CP, EO, EP separately. Since the Mersenne Twister has a huge number of states, you'd need a very large number of consecutive scrambles to do this, and it wouldn't be easy at all (you'd have to check all possible generated numbers with the correct modulo value).



brunson said:


> If you make one turn at random, are you likely to be closer or further away from solved? Repeat that exercise indefinitely and I think you're probably find you migrate around the positions with solutions of about 14 to 17 moves. Maybe it's more the case of there just being so many more positions that are 16 moves away from solved than there are solved positions.


This (that there are many more positions with 16f*) is the entire reason. The same distribution would pop up if you uniformly randomly chose a position because that's just how the graph is.

I think the "Gaussian" property only applies to a one-dimensional random walk, anyway, but I'm not sure.


----------



## Joël (May 14, 2010)

qqwref said:


> As I recall the way it's currently done is to take a bunch of random numbers and look at them mod a bunch of smaller numbers to get CO, CP, EO, EP separately. Since the Mersenne Twister has a huge number of states, you'd need a very large number of consecutive scrambles to do this, and it wouldn't be easy at all (you'd have to check all possible generated numbers with the correct modulo value).



Ah.. A period of 2^219937-1... I see. Didn't know that. I guess the WCA doesn't have much to worry about.


----------



## Cride5 (May 14, 2010)

Joël said:


> Ah.. A period of 2^219937-1... I see. Didn't know that. I guess the WCA doesn't have much to worry about.



Yup, 2^19937 - 1 is a ridiculously huge number. It dwarfs the number of possible cube states, and is even orders of magnitude more than the number of atoms in the observable universe.




fatboyxpc said:


> Cride5 said:
> 
> 
> > fatboyxpc said:
> ...



Because if it weren't, I could build a weakness into the scramble generator, which only I knew how to exploit. Open source means that anyone can look at the source to ensure it does exactly as its supposed to.


----------



## jfly (May 14, 2010)

Cride5 said:


> The problem was that browser was trying to request scrambles before the applet had properly loaded, even though the applet is 'technically' supposed to be rendered first. The problem was fixed by implementing a small delay in generating the scrambles on first load.



Yeah, I've had this problem before too. It's really freaking annoying. Rather than adding a delay, I chose to make the applet call a javascript function on startup. Now that I'm thinking about it, add a parameter called callback and pass it the name of the javascript function you want to be called when the applet loads. In my opinion, this seems like the best way of dealing with issues like this, rather than adding a random delay or polling.


----------



## Cride5 (May 14, 2010)

j-fly said:


> Cride5 said:
> 
> 
> > The problem was that browser was trying to request scrambles before the applet had properly loaded, even though the applet is 'technically' supposed to be rendered first. The problem was fixed by implementing a small delay in generating the scrambles on first load.
> ...



Yea tell me about it  I was a bit reluctant to use JSObject though because I'd read about flaky browser support, and I've personally experienced problems with it. For example, this crashes my browser :/
http://www.raditha.com/java/mayscript.php


----------



## JBCM627 (May 14, 2010)

Cride5 said:


> For example, this crashes my browser :/
> http://www.raditha.com/java/mayscript.php


Well, it just plain doesn't work:
Uncaught TypeError: Cannot set property 'value' of undefined
document.forms[0].txt1 is undefined
Looks more like a bad attempt to access an element rather than it not properly calling a javascript function.


----------



## FatBoyXPC (May 14, 2010)

Cride: I understand that part of why it's open source, but they currently use cube explorer, which is not open source.

I still don't understand why a random state generator is any different than using a random scramble.


----------



## Bryan (May 14, 2010)

fatboyxpc said:


> A) Install a virtual PC w/Windows onto whatever OS/distro I have and call it a day


Yeah, you may not have a Windows license to install



fatboyxpc said:


> I see your point, but WAMP installations are quite user friendly, and let us also not forget that PHP has an interpreter for a command line interface.


Congratulations. You know acronyms. But it's a security risk to open up ports on your system. With Java, you're not doing that. Just because you know what PHP is, doesn't mean that everything should use it.



fatboyxpc said:


> Also stefan, do you really think there won't be a single person there with a windows computer at the event?


At my competitions, I'm usually the only person with a laptop. Some parents may have one, but I doubt they're going to install an application for me. Plus, you don't want o just use a random person's laptop to generate scrambles.


----------



## Cride5 (May 14, 2010)

fatboyxpc said:


> Cride: I understand that part of why it's open source, but they currently use cube explorer, which is not open source.


.. and that is a problem which this is trying to address.



fatboyxpc said:


> I still don't understand why a random state generator is any different than using a random scramble.



OK, so If I were to scramble your cube with 5 moves, would that be adequate? ... what about 6-moves, or 7 .. 8 etc. How many moves is enough to properly 'scramble' a cube. Well it turns out that 25 isn't enough. As a ZZ-user I get easier EO cases with 25-move scrambles because there is a bias towards cube states with less than the average number of disoriented edges. This is unacceptable for competition because it may give users of particular methods an unfair advantage. So how many moves is enough? Well possibly 40, maybe if you're really paranoid lets make it 100. Theoretically, there will always be a slight bias towards EO cases with less than the average number of bad edges unless you make an infinite number of moves. For practical purposes we can probably assume that something like 50 would reduce the bias sufficiently for competition.

... orrr, you could just use a random-state scrambler, applying 20 or so moves to jump directly to one of the 4.3*10^19 states, with an equal probability of landing at each one.

I'm not going to explain the detail behind how they work because this has been done before see:
http://www.speedsolving.com/wiki/index.php/Random_State_Scramble
http://www.speedsolving.com/forum/showthread.php?t=12969
http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/34652

... if you still don't understand after reading that material, then can you explain specifically what you don't understand and I'll do my best to explain it.


----------



## FatBoyXPC (May 14, 2010)

Then you can use ReactOS or Linspre(aka Lindows) to install cube explorer on, it's supposed to work with all windows apps (how well it does I do not know, haven't thoroughly tested it, but it's a nice concept at least). Anybody can find a some sort of free copy of a windows install anyway, whether it be cracked, student copy, etc. 

I'm not saying everything should use it, I'm just providing an alternative, that right now seems logical. I could also argue to use C++ but the logic here is that it is a web-based scramble generator.

You're the only person with a laptop at competitions? Well then this site Cride has provided now is out of the question if by chance nobody else on staff has a working laptop.

Cride, how can you say that if you only do a 25 move scramble it gives an EO bias? That doesn't seem logical when you can clearly get to one of those many permutations with a less than 25 move scramble? I shall go read those now, and if that question isn't answered, I'll leave it here.


----------



## blade740 (May 14, 2010)

Linux/Chrome/Java 1.6.0_18-b07

Works perfectly. 

@fatboyxpc: the point is that Java is the most widely-installed platform that the kociemba algorithm is feasible on (besides possibly flash, which was discussed). Sure, you could use wine/PHP/assembly/brain****/pen&paper, but that's making things more difficult than they need to be. The whole idea is to make the scrambler run on as many machines as possible.


----------



## qqwref (May 14, 2010)

fatboyxpc said:


> Cride, how can you say that if you only do a 25 move scramble it gives an EO bias? That doesn't seem logical when you can clearly get to one of those many permutations with a less than 25 move scramble? I shall go read those now, and if that question isn't answered, I'll leave it here.



You're doing 25 *random* moves, and the randomness of the moves themselves is what is important. Each position can be solved in 25 or fewer moves, but that doesn't mean each position has the same number of 25-move solutions, so some positions will be more likely to come up than others.


----------



## FatBoyXPC (May 14, 2010)

I understand the whole concept about it being widely available and what not. The debate evolved into something different.

After reading through some of those posts, I have a question for you, Stefan. You provided your PHP script in a text file for making the scrambles (and putting them into a pdf file). I noticed that you didn't force an adjacent face to move if you have already done F2/B2. Meaning if by chance the rand() picked F2 then B2 then F again, it is equivalent to doing F' B2, which cuts your scramble a move short. I realize that may not practically happen a lot (if at all) but the point is that it is theoretically possible. I'd like to see you output say 1 million scrambles then write another script that checks for this issue.

Even though 1million is a large sample size to run all of the numbers on, for these test that have been run against scramblers vs random state generators, the mere fact is 1 million is hardly a sample size compared to the 43 quintillion possibilities. I guess if we were to compare the result of 1 million scrambles, to 100 million scrambles, and they were nearly identical, that might hold some weight. I would still rather compare to say 1 quintillion scrambles from a scrambler to see what happens. We could also check to see if after say 100 million scrambles we start getting duplicate scrambles, and that would invalidate the results.

qqwref: I understand that with the state generators, when it solves the cube in 25 moves or less that it's the importance of each turn that makes the difference, not just a random move. I believe though that if you were to make 43 quintillion scrambles from some of these scramblers, and the random number generators were legit, that the results wouldn't be biased like this. I could be wrong but I need to understand why before I go and accept a different answer.


----------



## Lars Petrus (May 14, 2010)

fatboyxpc said:


> I have a question for you, Stefan. You provided your PHP script in a text file for making the scrambles (and putting them into a pdf file). I noticed that you didn't force an adjacent face to move if you have already done F2/B2. Meaning if by chance the rand() picked F2 then B2 then F again, it is equivalent to doing F' B2, which cuts your scramble a move short.




I found a simple way to deal with this. When you generate moves, don't allow the opposite side to follow F, U or R. Together with not allowing repetition of a side, it's all you need.


----------



## JBCM627 (May 14, 2010)

Lars Petrus said:


> fatboyxpc said:
> 
> 
> > I have a question for you, Stefan. You provided your PHP script in a text file for making the scrambles (and putting them into a pdf file). I noticed that you didn't force an adjacent face to move if you have already done F2/B2. Meaning if by chance the rand() picked F2 then B2 then F again, it is equivalent to doing F' B2, which cuts your scramble a move short.
> ...


But that would limit your ability to do something like F B (which should be legal). You could just generate moves on one axis, then switch to another axis and generate moves on it (see source code).


----------



## FatBoyXPC (May 14, 2010)

Lars Petrus said:


> fatboyxpc said:
> 
> 
> > I have a question for you, Stefan. You provided your PHP script in a text file for making the scrambles (and putting them into a pdf file). I noticed that you didn't force an adjacent face to move if you have already done F2/B2. Meaning if by chance the rand() picked F2 then B2 then F again, it is equivalent to doing F' B2, which cuts your scramble a move short.
> ...



Are you saying the opposites of F, U, and R? Or are you saying to not let the opposite side I just turned follow F? You've confused me


----------



## Lucas Garron (May 14, 2010)

Lars Petrus said:


> fatboyxpc said:
> 
> 
> > I have a question for you, Stefan. You provided your PHP script in a text file for making the scrambles (and putting them into a pdf file). I noticed that you didn't force an adjacent face to move if you have already done F2/B2. Meaning if by chance the rand() picked F2 then B2 then F again, it is equivalent to doing F' B2, which cuts your scramble a move short.
> ...


That, uh, skews the distribution a bit, don't it?


----------



## JBCM627 (May 14, 2010)

Lucas Garron said:


> That, uh, skews the distribution a bit, don't it?


Does mixing occur more quickly for an arbitrary size cube when using (non-canceling / backtracking) moves defined by Lars's metric, HTM, QTM, STM, or ATM (Axis), and counting the number of moves using HTM?


----------



## Lars Petrus (May 14, 2010)

JBCM627 said:


> Lars Petrus said:
> 
> 
> > I found a simple way to deal with this. When you generate moves, don't allow the opposite side to follow F, U or R. Together with not allowing repetition of a side, it's all you need.
> ...




It allows B F, which is the same thing. But B F B can't happen.



Lucas Garron said:


> That, uh, skews the distribution a bit, don't it?




Maybe. I haven't analyzed that. You'd have to be precise about compared to what it skews which distribution.

I use it to avoid trivial duplicates when generating all possible sequences. I just want B2 F, not F B2 or B F2 B F'. It works for that purpose.

The programming benefit is that you only have to keep the last move around, which is much simpler than keeping the last 2.


----------



## FatBoyXPC (May 14, 2010)

Lars, up until I tried to propose a situation I didn't understand that at all. But I said B F B F B F and then I realized oh wait...yeah. Understood now. Edit: Wait, what if the "opposite" side is F? Then couldn't B F B F B F work?


----------



## Portponky (May 14, 2010)

In response to cracking the randomness of the Mersenne Twister, the cycle length is not the important factor. The cycle length is important in that it must be larger than the cardinality of the cube group because otherwise it cannot generate every possible scramble. If the cycle length _is_ longer then it's possible that it _can_ generate every cube scramble, although that's not sufficient to say that it _does_. As noted, the Mersenne Twister's cycle length is far larger than the cube group.

Every time a random number generator makes a prediction it leaks a small amount of information about its internal state, probably just a fraction of a bit. Every subsequent random roll gives a little more information until you can rebuild the internal state of the random number generator. Mersenne is really weak in this way, but only from a computational perspective. According to wikipedia it leaks its entire state after 624 random numbers are generated.

However this is really meaningless from a practical point of view because if someone can translate a cube scramble back to a series of seed numbers and undo the Mersenne twister in their head and come up with the next scramble and then solve that in their head, well, they probably deserve to win anyway.


----------



## FatBoyXPC (May 14, 2010)

Portponky: I saw the part about how at 624 one can then predict all future numbers. Does this mean that it'll be in the same order or you can use an algorithm to get the numbers? Or is there a pattern to this? I'll read more about this PRNG tomorrow when I wake up.


----------



## Stefan (May 14, 2010)

fatboyxpc said:


> Stefan. You provided your PHP script in a text file for making the scrambles (and putting them into a pdf file). I noticed that you didn't force an adjacent face to move if you have already done F2/B2.



I assume you mean this?
http://stefan-pochmann.info/spocc/other_stuff/tools/scramble3x3/sourcecode.txt



fatboyxpc said:


> Cride, how can you say that if you only do a 25 move scramble it gives an EO bias?


Because it's 1) rather obvious and 2) has been computed and documented? If the links he gave you don't suffice, check out my scramble analyzer right above my scrambler:
http://stefan-pochmann.info/spocc/other_stuff/tools/



fatboyxpc said:


> Anybody can find a some sort of free copy of a windows install anyway, whether it be cracked, student copy, etc.



You're suggesting to the WCA competition orgainizers/delegates to install a cracked operating system... riiiiiiiight.



Portponky said:


> Mersenne is really weak in this way, but only from a computational perspective. According to wikipedia it leaks its entire state after 624 random numbers are generated.



We better not change from average-of-5 to average-of-*157* (or more) then, huh?


----------



## Stefan (May 14, 2010)

Joël said:


> Given a certain scramble/cube state, would it be possible for anyone who reverse-engineers cube explorer, and the pseudo random number generator being used to predict the next scramble (using a computer)?



Yes. Especially now that we have the source code. The problem is that while Mersenne Twister is very good once it's running, the scrambler starts it with System.currentTimeMillis() as seed. There are thus only 86.4 million possibilities per day. Encoding a scramble state in 9 bytes and its corresponding seed in 5, I could store all first scrambles and their seeds for a whole month in a 34 GB file. So I could prepare that before a competition, look at the first scramble of a round, look up its seed in my file, and use it to generate the next four scrambles.


----------



## Stefan (May 14, 2010)

blade740 said:


> Java is the most widely-installed platform that the kociemba algorithm is feasible on



Maybe. And if you insist on direct execution of a single executable on a single platform. WCA could offer different executables of the same program, compiled for different platforms.


----------



## Portponky (May 14, 2010)

StefanPochmann said:


> So I could prepare that before a competition, look at the first scramble of a round, look up its seed in my file, and use it to generate the next four scrambles.



You would then have to memorise believable move sequences to solve these cubes and be able to perform them faster than you can solve a cube anyway...

Even adding a tiny bit more randomness to the seed would make this impossible. Any hardware sampling (microphone, cpu temperature) would be a good source for something to XOR with the seed and make it random enough.


----------



## Stefan (May 14, 2010)

Portponky said:


> StefanPochmann said:
> 
> 
> > So I could prepare that before a competition, look at the first scramble of a round, look up its seed in my file, and use it to generate the next four scrambles.
> ...



Right, you could even have the computer search for a short/fast solution using your method/algs. It would be believable and easy to memorize because it would be your actual normal method, and it would be faster because you don't need to look ahead and because the solution is short/fast and because you can practice it a few times.



Portponky said:


> Even adding a tiny bit more randomness to the seed would make this impossible. Any hardware sampling (microphone) would be a good source for something to XOR with the seed and make it random enough.



Yep. So they should do that.


----------



## qqwref (May 14, 2010)

Portponky said:


> According to wikipedia it leaks its entire state after 624 random numbers are generated.
> 
> However this is really meaningless from a practical point of view...


It's even more meaningless than you think. Remember that we simply are not generating the entire cube-state from one number, but rather taking parts of it from parts of a bunch of different numbers, so you will never get anywhere near enough information from a cube to be sure of any of the random numbers used to generate it. You can't figure out one of the random numbers, let alone 624. To figure out the Twister's state, you'd need a LOT more than 624/4 cubes, and a lot of computation time too to check the various possibilities.



StefanPochmann said:


> Joël said:
> 
> 
> > Given a certain scramble/cube state, would it be possible for anyone who reverse-engineers cube explorer, and the pseudo random number generator being used to predict the next scramble (using a computer)?
> ...



This is much more doable as far as scramble predicting and is a good point. 86.4 million is not only much less than the number of cube possibilities (virtually guaranteeing that only one seed will generate the right cube) but also small enough that you could actually have a computer check all the possibilities in a reasonable time.

I suppose one fix would be to use four SEPARATE Mersenne Twister initializations, each generated with their own currentTimeMillis() seed when needed. So for the first cube you'd seed one, get CO from one, seed two, get CP from two, etc., and for the rest of the cubes you'd do the same without seeding. On an inconsistently timed OS (Windows) this should give enough variation in timing to completely destroy any such cubestate-cracking attempts.



StefanPochmann said:


> Right, you could even have the computer search for a short/fast solution using your method/algs. It would be believable and easy to memorize because it would be your actual normal method, and it would be faster because you don't need to look ahead and because the solution is short/fast and because you can practice it a few times.



I don't know how hard this would be to determine, but is it feasible to make a program that would take a list of your F2L, OLL, PLL algorithms - possibly more than one per case - and then try a bunch of near-optimal crosses to find the best (fewest moves) Fridrich solution? I would be interested to see how low a typical solve can go.


----------



## Escher (May 14, 2010)

qqwref said:


> I don't know how hard this would be to determine, but is it feasible to make a program that would take a list of your F2L, OLL, PLL algorithms - possibly more than one per case - and then try a bunch of near-optimal crosses to find the best (fewest moves) Fridrich solution? I would be interested to see how low a typical solve can go.



http://acesoftware.110mb.com/cube/cubeassistant/

Is a rough approximation of what you mean, I think.


----------



## reThinking the Cube (May 14, 2010)

Even if competitors can be prevented from getting prior access to the scrambles, just being random, does not by itself, ensure a good competition scramble anyway. Obviously, some random states are going to be WAY easier to solve than others. Not addressing this, will eventually create a situation where ALL the single records will belong to the cubers that were lucky enough to get the easiest random state scramble. You can already see this happening with the best times for 2x2x2 singles. So YES, I would love to have a web-based 3x3x3 scrambler that can generate random (to coin a phrase for the enjoyment of Lord Gottlieb) "Competition-Grade" scrambles based upon the following conditions:

1) NO corner should already be correctly positioned (relative to the center pieces on odd NxNXN cubes). 

2) Now using any corner as reference(ignoring centers), this corner, and only this corner, can be viewed as solved relative to all the other corners. This would be the equivalent of a 2x2x2,with 1 and only 1, correctly placed corner, no matter how you orient the cube. The n=1 column in the following table shows the distribution of these cases relative to all possible random. All those cases where n>1 need to be rejected, since there are more than 1 corners that are solved relative to each other.


Spoiler






cuBerBruce said:


> I get the following distribution:
> 
> ```
> moves   n=1      n=2      n=3      n=4      n=5      n=6      n=8   totals   n >= 2
> ...





3) Testing with all the corner pieces as the solved reference (ignoring centers), NO edge piece should be solved relative to the position of that corner. This will reject all cases that have prebuilt C/E pairs. Also testing so that NO edge piece is correctly placed relative to the position of the centers(i.e. no edge may already be solved). Optionally, edge pieces could also be tested relative to each other (ignoring centers) so that any 2 that could be correctly positioned with a single center slice move could also be rejected.

4) Using CubeX to test the solution length, and only keep those that can be solved within the range 15f>x>19f. The actual scramble should be generated with the same program.

Now this will produce a REAL scramble that has NOTHING already solved, and no cheap solution should even be possible. And it would be nice if these scrambles could be generated at the competition site, with a hardware reseeded rnd# just prior to the actual events. 

The total# of these possible "Competition-Grade" scrambles would end up to be a small% of all possible random positions, but still way more than would ever be needed. Some distribution studies would be required before implementing, but I would much prefer something like this, over the random state, but-not-always-so-scrambled state, scramblers, we have now.


----------



## aronpm (May 14, 2010)

reThinking the Cube said:


> 1) NO corner should already be correctly positioned (relative to the center pieces on odd NxNXN cubes).
> 
> 2) Now using any corner as reference(ignoring centers), this corner, and only this corner, can be viewed as solved relative to all the other corners. This would be the equivalent of a 2x2x2,with 1 and only 1, correctly placed corner, no matter how you orient the cube. The n=1 column in the following table shows the distribution of these cases relative to all possible random. All those cases where n>1 need to be rejected, since there are more than 1 corners that are solved relative to each other.
> 
> 3) Testing with all the corner pieces as the solved reference (ignoring centers), NO edge piece should be solved relative to the position of that corner. This will reject all cases that have prebuilt C/E pairs. Also testing so that NO edge piece is correctly placed relative to the position of the centers(i.e. no edge may already be solved). Optionally, edge pieces could also be tested relative to each other (ignoring centers) so that any 2 that could be correctly positioned with a single center slice move could also be rejected.



As someone who mainly does blindfolded solving, this is the dumbest thing I've ever ****ing heard.


----------



## Portponky (May 14, 2010)

qqwref said:


> It's even more meaningless than you think. Remember that we simply are not generating the entire cube-state from one number, but rather taking parts of it from parts of a bunch of different numbers, so you will never get anywhere near enough information from a cube to be sure of any of the random numbers used to generate it. You can't figure out one of the random numbers, let alone 624.



No matter how you use it, it's leaking information. If you're using it to pick a colour for each face then it's leaking 2.58 bits of information about the number used. So it's not impossible to work out where you are in the twister.

But like you said it's a completely meaningless weakness. The seed attack is much more reasonable.



reThinking the Cube said:


> Even if competitors can be prevented from getting prior access to the scrambles, just being random, does not by itself, ensure a good competition scramble anyway. Obviously, some random states are going to be WAY easier to solve than others.



This is irrelevent cause everyone gets the same set of scrambles, right? So everyone is on even ground. The point of the random state scrambler is it gives a much better distribution of random states.


----------



## joey (May 14, 2010)

Only people in the same group, in the same competition though.


----------



## Cride5 (May 14, 2010)

StefanPochmann said:


> Joël said:
> 
> 
> > Given a certain scramble/cube state, would it be possible for anyone who reverse-engineers cube explorer, and the pseudo random number generator being used to predict the next scramble (using a computer)?
> ...


This is a good point actually, and is quite a concern. If you were to know (for example) the hour in which the scrambles were being generated then that would only be 3.6 million cubes to check. It would be quite feasible to go to a competition with a database of scramble sequences. As soon as you have the first scramble in the sequence, then all subsequent scrambles can be worked out. NOTE: This is also a problem for the current random-moves generators used officially.

Anyway, Java implements a SecureRandom object which creates cryptographically secure random numbers. When setting the seed it uses hardware sampling to guarantee that there is an equal chance of entering every possible generator state on initialisation. For more information see:
http://www.javamex.com/tutorials/random_numbers/securerandom.shtml

Like the Mersenne Twister it also has a long enough period (2^160, ~10^48) to ensure all possible cube states are reachable. The problem, however is that the period isn't guaranteed. The 2^160 figure is for Sun's implementation of the SecureRandom class. The period may vary between JVMs, but I doubt it will be as low as 4.3 * 10^19.

So there are two options:
(1) Use only the SecureRandom generator
(2) Seed the Mersenne Twister with a number generated from SecureRandom


----------



## qqwref (May 14, 2010)

reThinking the Cube said:


> to coin a phrase for the enjoyment of Lord Gottlieb


Am I supposed to be insulted by this? Because it's closer to "mystified".



reThinking the Cube said:


> 1) NO corner should already be correctly positioned (relative to the center pieces on odd NxNXN cubes).
> 
> 2) Now using any corner as reference(ignoring centers), this corner, and only this corner, can be viewed as solved relative to all the other corners. [...]
> 
> 3) Testing with all the corner pieces as the solved reference (ignoring centers), NO edge piece should be solved relative to the position of that corner. This will reject all cases that have prebuilt C/E pairs. Also testing so that NO edge piece is correctly placed relative to the position of the centers(i.e. no edge may already be solved). Optionally, edge pieces could also be tested relative to each other (ignoring centers) so that any 2 that could be correctly positioned with a single center slice move could also be rejected.


This is ridiculous. There will be very few scrambles left after these tests, and those that ARE left will represent the most difficult (in some sense), not random ones. By generating random positions we are testing people on every type of scramble, not just ones that you think are difficult. Besides, these scrambles won't be equally difficult to every method like randomized ones will. I notice you include nothing about edge orientation, for instance, meaning ZZ solvers won't find these scrambles harder than normal. It is a fact that you cannot make scrambles hard for everyone.



reThinking the Cube said:


> 4) Using CubeX to test the solution length, and only keep those that can be solved within the range 15f>x>19f. The actual scramble should be generated with the same program.


Do you mean this? Because there's no way that will generate a solution less than 20f for a scrambled position. I'll assume you mean CubeExplorer or something analogous. Anyway the range of 16f to 18f is arbitrary and silly. There is nothing wrong with a 15f* cube (it's not easier, generate a few), and there is nothing wrong with a 19f* cube (it's not harder, generate a few). Maybe the difference would matter if people solved cubes optimally (fewest moves?) but they don't and it doesn't. If you don't believe me that optimality means very little about solve difficulty, I can provide a 16f* cube whose optimal solution is a Fridrich solution.



reThinking the Cube said:


> Now this will produce a REAL scramble that has NOTHING already solved, and no cheap solution should even be possible. And it would be nice if these scrambles could be generated at the competition site, with a hardware reseeded rnd# just prior to the actual events.
> 
> The total# of these possible "Competition-Grade" scrambles would end up to be a small% of all possible random positions, but still way more than would ever be needed. Some distribution studies would be required before implementing, but I would much prefer something like this, over the random state, but-not-always-so-scrambled state, scramblers, we have now.


It is always scrambled, just not always equally difficult. You seem to think it's better to make "real" scrambles, but did you think about how much people already know about the scrambles? If this policy were to be instituted, people would be aware that scrambles are setup in a specific way, and would modify their methods accordingly. People would practice these kinds of scrambles, get used to very slightly more difficult first steps and learn special tricks for them, and after a while cubers would be getting FASTER averages on your "competition-grade" scrambles than on random scrambles. Whenever scrambles have to satisfy a restrictive property, you are giving competitors a lot of information about their scrambles before they see them, and that gives people an advantage compared to knowing nothing about a completely random mix.


----------



## reThinking the Cube (May 14, 2010)

qqwref said:


> This is ridiculous. There will be very few scrambles left after these tests,



How many exactly is "very few"? Do you think you could solve those "very few" in your lifetime?



qqwref said:


> and those that ARE left will represent the most difficult (in some sense), not random ones. By generating random positions we are testing people on every type of scramble, not just ones that you think are difficult.



My opinion, is that a scramble should have as little as possible already in the solved state. I don't care about making the scrambles more difficult, or harder for anyone, but just want to reject those that are far too easy (random, but relatively unscrambled). 



qqwref said:


> and that gives people an advantage compared to knowing nothing about a completely random mix.



Which would give people the most advantage, the ones I propose, or one of these?



reThinking the Cube said:


> What was the official WCA scramble for these solves?
> 
> 1)	Erik Akkersdijk	0.96	Netherlands,	Geneva Open 2008
> [F' U' F' R2 F2 R U2 R' U F U R2 U F' U2 F2 R' U R F' R U2 R2 U' F] - Edward Lin
> ...


----------



## Cride5 (May 14, 2010)

Cride5 said:


> (2) Seed the Mersenne Twister with a number generated from SecureRandom



The scrambler applet has been updated to do this.


----------



## Stefan (May 14, 2010)

reThinking the Cube said:


> REAL scramble that has NOTHING already solved



Contradiction right there.

Please keep that annoying argument in your threads, don't contaminate this one.



Cride5 said:


> So there are two options:
> (1) Use only the SecureRandom generator
> (2) Seed the Mersenne Twister with a number generated from SecureRandom



I knew SecureRandom, but didn't know about its seeding. Quite cool. And it has the generateSeed() method for precisely your option 2:
http://java.sun.com/j2se/1.4.2/docs/api/java/security/SecureRandom.html#generateSeed(int)


----------



## qqwref (May 14, 2010)

reThinking the Cube said:


> qqwref said:
> 
> 
> > This is ridiculous. There will be very few scrambles left after these tests,
> ...


I don't know how many, but your conditions are quite restrictive, so I assume it's a very small fraction of the set of cube positions. Someone would need to compute this.



reThinking the Cube said:


> I don't care about making the scrambles more difficult, or harder for anyone, but just want to reject those that are far too easy (random, but relatively unscrambled).


But a huge proportion of the scrambles you are rejecting are NOT "far too easy" in any sense.



reThinking the Cube said:


> Which would give people the most advantage, the ones I propose, or one of these?
> [2x2 stuff...]


3x3 is not 2x2.


----------



## Cride5 (May 14, 2010)

StefanPochmann said:


> Cride5 said:
> 
> 
> > So there are two options:
> ...



Yup, It's pretty cool that this is provided in the standard Java library 
I've used the following code to seed the MTRandom generator:

```
byte[] seed = null;
	try{
		seed = SecureRandom.getInstance("SHA1PRNG").generateSeed(9);
	} catch(NoSuchAlgorithmException e) {
		seed = new SecureRandom().generateSeed(9);
	}

	return randomCube(new MTRandom(seed));
```
I chose a seed of 9 bytes (size 2^72), because it is the smallest sequence of bytes which is large enough to access all cube states. The code also prioritises the SHA1 pseudorandom generator, falling back to the system default if it isn't available.


----------



## Cride5 (May 14, 2010)

I'm still quite concerened about the other JavaScript scramblers we're using.

If I can find the time I might build a program to test/demonstrate the weakness. If it works, the program will take two parameters, a scramble generated from here:
http://www.worldcubeassociation.org...e.htm?size=4&num=5&len=40&col=yobwrg&multi=on
and time period in which the scramble was generated. It will then return the sequence of future scrambles. This should theoretically be possible.

I think it might be an idea to secure up these JavaScript generators. We can fix the limited state-size issue by simply including a Mersenne Twister library, such as the one here:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/java-script.html

But the most concerning weakness is a bit harder to fix. JavaScript currently provides no library for generating cryptographically secure random numbers. There's a good discussion about it here:
http://news.ycombinator.com/item?id=748430
and also here:
http://stackoverflow.com/questions/...pts-random-implementation-in-various-browsers

I think a feasible option though, might be just to capture mouse movements and combine that with the current time to generate the numbers. There's a demonstration of it here:
http://tim.dierks.org/2007/03/secure-in-browser-javascript-password.html
.. with a criticism here:
http://www.webappsec.org/lists/websecurity/archive/2008-01/msg00111.html

It may not be perfect, but it would certainly be a big improvement over the current situation!


----------



## brunson (May 14, 2010)

There are sources of true entropy available on the net. That would be a better source of a seed. Linux has a source of real entropy, but it's easily depleted. I used it as a seed in a pure python implementation of Marsaglia's CMWC4096. I posted the code here, but that was before pjk switched servers, so I think it's gone.

That was in response to a discussion we were having on the period of the Mersenne Twister being so much lower than the number of positions of the cube and whether it meant that we were only reaching 2^32 scrambles. CMWC4096 has a period of 2^131086, which is a bit of an overkill, especially considering it uses and array of up to 16 32 bit seeds (if I remember correctly).

I think the question boiled down to: is the MT implementation locked into a single cycle, where the seed just picks your starting position in the cycle. If I remember correctly, this stuff:


```
private final static int N = 624;
        private final static int M = 397;
        private final static int MAGIC[] = { 0x0, 0x9908b0df };
        private final static int MAGIC_FACTOR1 = 1812433253;
        private final static int MAGIC_FACTOR2 = 1664525;
        private final static int MAGIC_FACTOR3 = 1566083941;
        private final static int MAGIC_MASK1   = 0x9d2c5680;
        private final static int MAGIC_MASK2   = 0xefc60000;
        private final static int MAGIC_SEED    = 19650218;
        private final static long DEFAULT_SEED = 5489L;
```

can be changed to generate different cycles, but most implementations hard code them, just like the implementation in your source.


----------



## Portponky (May 14, 2010)

The period of MT is much bigger than the cube group size. There's nothing wrong with MT, it's a perfect random generator for our use. The only issue is it is probably quite easy to come up with a seed collision attack.

I don't think it's a good idea to change the coeficients it uses cause (a) it's open source anyway so that wouldn't prevent a seed attack, and (b) other numbers may be significantly worse.


----------



## JBCM627 (May 14, 2010)

qq has mentioned this before, but:
http://www.random.org/
This means you'll need an internet connection to generate scrambles, but if you don't have an internet connection, a number of these could still be stored in advance.


----------



## Cride5 (May 14, 2010)

JBCM627 said:


> qq has mentioned this before, but:
> http://www.random.org/
> This means you'll need an internet connection to generate scrambles, but if you don't have an internet connection, a number of these could still be stored in advance.



Lol ninja'd ... yea I was going to suggest the JavaScript scrambler could make calls to something like:
http://www.random.org/integers/?num=1&min=0&max=100&col=1&base=10&format=plain&rnd=new

... random.org does impose quota limits, but because only one seed is needed per page load this shouldn't be a problem. The only problem with this (as JBCM pointed out), is that it needs a connection.


----------



## Herbert Kociemba (May 14, 2010)

Cride5 said:


> Yup, It's pretty cool that this is provided in the standard Java library
> I've used the following code to seed the MTRandom generator:
> 
> ```
> ...



I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).


----------



## Stefan (May 14, 2010)

Cride5 said:


> ... random.org does impose quota limits, but because only one seed is needed per page load this shouldn't be a problem. The only problem with this (as JBCM pointed out), is that *it needs a connection*.



If you're using it online, you do have a connection, and if you're using it offline, you did have a connection when you downloaded it. So we could implant a proper random seed at download (using let's say php instead of static html files). You and I downloading the same scrambler would get different seeds. Then when it's run, additionally use the system time to randomize further (don't want the downloaded scrambler generate the same scrambles over and over again).

Also, security restrictions could play a role. I'm not sure Javascript is allowed to connect to a server other than the one it came from. So asking random.org might not work because of that.


----------



## JBCM627 (May 14, 2010)

Herbert Kociemba said:


> I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).


I can't find much on it other than this article:


> When adding entropy to a system, it is best to collect a lot of entropy and seed all at once, instead of seeding a little bit at a time. We will illustrate why by example. Suppose you seed a generator with one bit of entropy. An attacker has only one bit to guess, which can be done accurately after two outputs. If the attacker completely compromises the state after two outputs, and we then add another bit of entropy, he can once again guess the state easily.
> If we add one bit 128 times, there is still very little security overall if the generator state is compromised. However, if you add 128 bits of entropy to the generator all at once, an attack should essentially be infeasible.





StefanPochmann said:


> I'm not sure Javascript is allowed to connect to a server other than the one it came from. So asking random.org might not work because of that.


That is a good point... generally you can't httprequest data from another domain.


----------



## Lars Petrus (May 14, 2010)

StefanPochmann said:


> Cride5 said:
> 
> 
> > ... random.org does impose quota limits, but because only one seed is needed per page load this shouldn't be a problem. The only problem with this (as JBCM pointed out), is that *it needs a connection*.
> ...




A simpler approach is to have the user enter a string that's used as a part of the seed.

If we can trust the organizer to keep it secret, this is safe.

If we can't trust the organizer, there is no way to make this safe anyway.


----------



## Cride5 (May 14, 2010)

Herbert Kociemba said:


> I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).



Doh! What a stupid mistake :fp ...I wasn't intending on re-seeding it every time. In the process of fixing now. Thanks for pointing that out ... that really is a big facepalm for me!


----------



## Portponky (May 14, 2010)

Lars Petrus said:


> A simpler approach is to have the user enter a string that's used as a part of the seed.



This is the best solution by far.


----------



## Cride5 (May 14, 2010)

Cride5 said:


> Herbert Kociemba said:
> 
> 
> > I would prefer to seed the random generator only once for example when the program is starting. Reseeding after a few calls/ for every new cube is not recommended as far as I know (but I must admit I cannot explain why).
> ...



OK this has been fixed and updated in the demo system. I would encourage folks to check the source to make sure there aren't any more silly errors like that. 



Portponky said:


> Lars Petrus said:
> 
> 
> > A simpler approach is to have the user enter a string that's used as a part of the seed.
> ...



Yup, I would agree with this. I think seeding a JavaScript implementation of MT with the current system time, and a user input value (generated from random.org if possible) is probably the best security we could hope for.


----------



## FatBoyXPC (May 14, 2010)

Stefan: Yes I was talking about the link you gave for the scrambler you made. You also did not take into account the fact that you sampled an incredibly small size compared to the amount of possibilities. One could also argue that you can only generate so many scrambles with 25 moves. I'm not real big on math but I think it might be 25! for the amount of scrambles? Yes/no? If so, that number is larger than the amount of possible scrambled positions.

About this Mersenne Twister, is this the RNG that's used in C? There are plenty of other RNGs out there, and we could easily make our own. You could take your system time and hash it with another new piece of information repetitively. That could easily prevent this whole "figuring out the scramble."


----------



## brunson (May 14, 2010)

Portponky said:


> The period of MT is much bigger than the cube group size. There's nothing wrong with MT, it's a perfect random generator for our use. The only issue is it is probably quite easy to come up with a seed collision attack.


You're right, I was looking at the distribution, and not the period.

WRT Kociemba's comment, I was definitely recommending only generating the seed from a true entropy source. Internet if it's available, /dev/random if available on your platform, something lame like uptime if that's the only thing you have.

In the mean time, I found my CMWC4096 posting. http://www.speedsolving.com/forum/showthread.php?p=53481#post53481

Edit: Buggy code. I'm usually pretty careful about making sure code works before posting it, but I fixed it.


----------



## Cride5 (May 14, 2010)

fatboyxpc said:


> About this Mersenne Twister, is this the RNG that's used in C? There are plenty of other RNGs out there, and we could easily make our own. You could take your system time and hash it with another new piece of information repetitively. That could easily prevent this whole "figuring out the scramble."





StefanPochmann said:


> Edit: OMG, fatboyxpc is so full of fail.



I don't normally like to make comments like this, but I think in this case it is warranted. Please do some research into the things you are talking about, because the suggestions you are making are quite ridiculous.


----------



## FatBoyXPC (May 14, 2010)

Why is this ridiculous?


----------



## brunson (May 14, 2010)

I believe the standard C rand() family of functions uses Linear Congruent Generators (LCG) http://en.wikipedia.org/wiki/Linear_congruential_generator

MT is far more sophisticated, usually only criticized because it's hackish and overly complicated in its implementation. It is also not considered to be cryptographically secure. Thinking we could write our own PRNG is a bit naive. We could probably come up with a reasonable effort, but I certainly don't have the skillz to prove its efficiency or randomness.

@fatboyxpc: Try reading this for an introduction to the complexities of PRNGs http://en.wikipedia.org/wiki/Pseudorandom_number_generator


----------



## qqwref (May 14, 2010)

fatboyxpc said:


> One could also argue that you can only generate so many scrambles with 25 moves. I'm not real big on math but I think it might be 25! for the amount of scrambles? Yes/no? If so, that number is larger than the amount of possible scrambled positions.


No, you're not real big on math at all. It makes no sense to suggest 25!. (For reference, the number of 25-move scrambles is roughly 18 * (15)^24, but because sequences like B F B aren't allowed the true number is lower than this.) The number IS larger than the amount of scrambled positions, which is obvious if you know that it's been proved that every position can be solved in strictly fewer than 25 moves. But even though each position has on average some 7 billion 25-move solutions, positions will not have the same number of 25-move solutions, and since each possible scramble has an equal chance of being generated (if you use random moves) this means that different positions will not have the same probabilities of coming up.


----------



## Stefan (May 14, 2010)

fatboyxpc said:


> StefanPochmann said:
> 
> 
> > fatboyxpc said:
> ...


Learn to read code properly before making up false accusations. That scrambler of course *DOES* prevent such trivial cancellations. The code is very short and easy to read, it's even documented. Boy do you suck.



fatboyxpc said:


> You also did not take into account the fact that you sampled an *incredibly small size compared to the amount of possibilities*. One could also argue that you can only generate so many scrambles with 25 moves.


I assume you're now talking about my analysis? WTF? I clearly state in the description that I analyzed *ALL* scrambles with 25 moves. BOY DO YOU SUCK! Even at reading PLAIN ENGLISH, not just my code.


----------



## FatBoyXPC (May 14, 2010)

qqwref how are you getting this number? Now the way you've expressed this is probability of how it ends up after the scrambles, I was under the impression before it was a fault of the PRNG.


----------



## qqwref (May 14, 2010)

fatboyxpc said:


> qqwref how are you getting this number?



18 possibilities for the first move (6 faces * 3 angles) and 15 possibilities for each move after that (5 faces * 3 angles). This number is a bit of an overestimate, though - it gives 3.03 x 10^29 when the real number is closer to 1.35 x 10^29. It's still of the right order of magnitude, and so good enough for casual talk.


----------



## brunson (May 14, 2010)

brunson said:


> Edit: Actually, I think my comparison to the Random Walk could show that I'm wrong about it. Consider moving through the graph as a constrained random walk where you travel a fixed distance in each iteration, but are constrained to making turns in increments of 10 degrees. Your distance from the starting point should still be Gaussian. I will have to think more about it on my drive home.


Relevant: http://en.wikipedia.org/wiki/Random_walk#Random_walk_on_graphs

I think I've effectively proved myself wrong.


----------



## Lars Petrus (May 14, 2010)

Cride5 said:


> OK this has been fixed and updated in the demo system. I would encourage folks to check the source to make sure there aren't any more silly errors like that.
> 
> 
> 
> ...



You can also use the second time stamp from when the user responds to further mix things up. That's may be enough in itself.

I suspect getting the string from random.org is overkill, but it wouldn't hurt of course.


----------



## Escher (May 14, 2010)

StefanPochmann said:


> BOY DO YOU SUCK!



[off-topic]
Another quote for the magic 8-ball?
[/off-topic]


----------



## Stefan (May 14, 2010)

qqwref said:


> 18 possibilities for the first move (6 faces * 3 angles) and 15 possibilities for each move after that (5 faces * 3 angles). This number is a bit of an overestimate, though - it gives 3.03 x 10^29 when *the real number is closer to 1.35 x 10^29*. It's still of the right order of magnitude, and so good enough for casual talk.



Closer to that, yes, but 2.0133 * 10^28 is even closer. How did you compute your number? I used this:

$P[0] = 1;
$P[1] = 6*3*$P[0];
$P[2] = 6*2*$P[1] + 9*3*$P[0];
for $i (3..25) {
$P[$i] = 6*2*$P[$i-1] + 9*2*$P[$i-2];
}


```
Moves        New states         Total states
 0                    1                    1
 1                   18                   19
 2                  243                  262
 3                3,240                3,502
 4               43,254               46,756
 5              577,368              624,124
 6            7,706,988            8,331,112
 7       1.0288 * 10^08       1.1121 * 10^08
 8       1.3732 * 10^09       1.4845 * 10^09
 9       1.8331 * 10^10       1.9815 * 10^10
10       2.4469 * 10^11       2.6450 * 10^11
11       3.2662 * 10^12       3.5307 * 10^12
12       4.3599 * 10^13       4.7129 * 10^13
13       5.8198 * 10^14       6.2911 * 10^14
14       7.7685 * 10^15       8.3976 * 10^15
15       1.0370 * 10^17       1.1209 * 10^17
16       1.3842 * 10^18       1.4963 * 10^18
17       1.8477 * 10^19       1.9973 * 10^19
18       2.4664 * 10^20       2.6661 * 10^20
19       3.2923 * 10^21       3.5589 * 10^21
20       4.3947 * 10^22       4.7505 * 10^22
21       5.8662 * 10^23       6.3413 * 10^23
22       7.8305 * 10^24       8.4646 * 10^24
23       1.0452 * 10^26       1.1299 * 10^26
24       1.3952 * 10^27       1.5082 * 10^27
25       1.8624 * 10^28       2.0133 * 10^28
```


----------



## qqwref (May 15, 2010)

I started with
\( a_1 = 18 \)
\( b_1 = 0 \)
\( a_n = 12 * a_{n-1} + 12 * b_{n-1} \)
\( b_n = 3 * a_{n-1} \)
The 'a' sequence is the number of scrambles ending in one axis-turn and 'b' is the number of scrambles ending in two axis-turns (such as F B or B F). So the key number here is a_n + b_n and I found a formula that gives that in closed form. Looking at n=2 I think the difference is that I looked at F B and B F as different (they are different scrambles) but you looked at them as the same (they give the same position). My way is perhaps better for the problem since F B and B F are both as likely to show up as any other legal two moves.

I suppose I could get the same results as your calculation by halving b_n after every step (i.e. b_n = 3/2 a_{n-1}).

EDIT: Also, I'm looking at the number of scrambles of EXACTLY 25 moves, since that is what scramblers generate. I don't understand why you are looking at the cumulative sum.


----------



## Stefan (May 15, 2010)

qqwref said:


> I don't understand why you are looking at the cumulative sum.


Mistake . Right, I should've said 1.8624 * 10^28 and not shown the right column.



qqwref said:


> My way is perhaps better for the problem since F B and B F are both as likely to show up as any other legal two moves.


Right, I think he asked about the number of scramble algorithms (what you did, thanks for explaining), I computed the number of states reachable by them.


----------



## Tim Reynolds (May 15, 2010)

StefanPochmann said:


> Right, I think he asked about the number of scramble algorithms (what you did, thanks for explaining), I computed the number of states reachable by them.



Wouldn't "the number of states reachable by them" be at most 4.3*10^19?


----------



## Stefan (May 15, 2010)

Tim Reynolds said:


> StefanPochmann said:
> 
> 
> > Right, I think he asked about the number of scramble algorithms (what you did, thanks for explaining), I computed the number of states reachable by them.
> ...



Damn I need sleep.


----------



## JBCM627 (May 16, 2010)

So I was thinking about this some last night, and was wondering... why do rngs have periods at all? Has nobody ever tried to create a number generator based on a chaotic physical system, eg an attractor or multi-body problem?

A chaotic generator certainly shouldn't be that computationally slow, although I have no idea how it would compare to other prngs, so perhaps relatively it might. I'd think a chaotic one would be perfect for the purposes of generating cube states when you need true random numbers instead of pseudo-random,and you only need a few numbers. So you would really be limited by the number of possible initial seeds, and you'd only ever need one seed. Even then, truncation errors that crop up may vary across machines, so different seeds might even result in random numbers after a point.

I can't find much literature on this...


----------



## Stefan (May 16, 2010)

What exactly do you mean with "chaotic", how would you do that?



JBCM627 said:


> Even then, truncation errors that crop up may vary across machines


If your computer has a bug, yes. Computations are standardized.


----------



## JBCM627 (May 16, 2010)

StefanPochmann said:


> JBCM627 said:
> 
> 
> > Even then, truncation errors that crop up may vary across machines
> ...


So working precision never changes across machines? Never mind that part then.



StefanPochmann said:


> What exactly do you mean with "chaotic", how would you do that?


As in, take a double-pendulum, given some initial conditions. The motion of the system can't be analytically determined. In the future, you would have no way of determining where the pendulum had been without infinite precision, and you have no way of telling how the pendulum will behave without infinite precision. You can use some parameter, say the number of times the second pendulum reaches a certain height per second, to determine the "random" part. I don't know for sure that you could calculate an expectation value for this, but assuming you could, you could then normalize the distribution of numbers you received accordingly.

Basically, instead of using something like [chaotic] mouse movements, just simulate a small chaotic system.


----------



## Stefan (May 16, 2010)

Yeah yeah yeah. It doesn't matter *what* you compute, some physics simulation or artificial number playing or whatever. *Is it deterministic or not?* If it's deterministic and has limited memory, eventually it must cycle. Only if you have infinite memory or a nondeterministic source, you can evade cycling.


----------



## Stefan (May 16, 2010)

JBCM627 said:


> So working precision never changes across machines?


It really shouldn't. Unless you're talking about hardware with the express purpose of being nondeterministic (I've read about some cryptography chips, they might do something like that). Other than that, standards are in place because you *want* your program to run properly on all computers, so you don't want different computers to behave differently. This for example is the main standard for floating point calculations, I think:
http://en.wikipedia.org/wiki/IEEE_754-2008



JBCM627 said:


> As in, take a double-pendulum, given some initial conditions.


If your pendulum is a real physical object, then you can probably get true randomness from it. If you just deterministically simulate it on the computer, then you're no better than other PRNGs, just different, and quite possibly worse.


----------



## JBCM627 (May 16, 2010)

StefanPochmann said:


> If it's deterministic and has limited memory, eventually it must cycle.


Pi should never cycle, and you can find the nth digit using a recursive formula. I think that is a sufficient counterpoint, unless I missed something.

Edit: Ah, I think I did... x_n blows up in terms of memory usage.


----------



## JBCM627 (May 16, 2010)

StefanPochmann said:


> JBCM627 said:
> 
> 
> > As in, take a double-pendulum, given some initial conditions.
> ...


Alright, I agree... Although I'd be interested to see what the period would be for what I suggested.


----------



## Stefan (May 16, 2010)

JBCM627 said:


> Edit: Ah, I think I did... x_n blows up in terms of memory usage.



That's somewhat the problem, yes. The state of this generator is the pair of n and x_n. And with the formula, you can get from state (n-1, x_n-1) to state (n, x_n). It's less important how "large" each state is (it's an encoding issue anyway), what matters is that with finite memory, you can only encode and distinguish a finite number of states. If your computer has 1 TB memory, it only has 2^(2^43) different possible states. A huge number, but still finite. So in your sequence of (n, x_n) states for the Pi computation, eventually you'll run out of new states your computer can possibly be in, you'll be in a previous state again, and revisit the states you visited from there the first time. Welcome to the cycle.


----------



## Stefan (May 16, 2010)

JBCM627 said:


> Although I'd be interested to see what the period would be for what I suggested.



You'd need to define it properly first. And I suspect it'll be less random than "normal" PRNGs, and less memory efficient, too. You can get longer periods simply by using more memory. Mersenne Twister for example has a period of length (*2^19937*)-1 using only *19968 bits* for its state. I think that's quite efficient, and that's because it was intentionally *made* that way. I doubt some physical simulation would use the memory nearly as efficiently.


----------



## JBCM627 (May 16, 2010)

StefanPochmann said:


> JBCM627 said:
> 
> 
> > Although I'd be interested to see what the period would be for what I suggested.
> ...


Yeah, I see your point.

A double-pendulum would require information about 2 distinct angles for a state, and the rate of change of those angles, so 4 pieces of information, although this can technically be reduced to 3. anyway, trivial example of an unreachable state (assuming you don't start with it): the pendulum dangling straight down (angular velocity of both arms are 0, and angles don't change).

A naive implementation of a double-pendulum simulation would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably be almost perfectly efficient.


----------



## Stefan (May 16, 2010)

Another problem of such a simulation is that it might be very hard to analyze how good it is. How do you determine the period length, for example? You can't just test it and count. Well you can if it's short, but then it's no good anyway. The systematic way PRNGs like Mersenne Twister are created makes the analysis possible. In that sense, "chaotic" is actually *bad*.



JBCM627 said:


> A naive implementation of a double-pendulum would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably *compress this to make it almost perfectly efficient*.



Nah, probably not. Remember you're trying to create randomness. Good randomness doesn't compress well. And bad randomness is, well, bad.


----------



## JBCM627 (May 16, 2010)

StefanPochmann said:


> JBCM627 said:
> 
> 
> > A naive implementation of a double-pendulum would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably *compress this to make it almost perfectly efficient*.
> ...


By this, I meant taking 4 parameters to 3. A double-pendulum also only has 2 degrees of freedom, so I think you can compress it to 2. But without creating a simple implementation, I'm not sure how efficient this would be.

I guess I should look into exactly how MT works more.


----------



## Stefan (May 16, 2010)

JBCM627 said:


> StefanPochmann said:
> 
> 
> > JBCM627 said:
> ...


I think we're talking about different things here.

Imagine each of your parameters is a 6656-bits floating point value. Then with 3 such parameters you use the same amount of state memory as Mersenne Twister. Now... if your simulation's periods are longer than MT's (2^19937)-1 period, it's more memory-efficient, if they're shorter, it's less memory-efficient. Relating the period length to the amount of memory used to represent the state, I mean. And I suspect yours would have differently long periods including quite short ones. And again, probably hard to analyze.

This is worth reading: http://en.wikipedia.org/wiki/PRNG#Periodicity
Period of (2^n)−1 using n bits apparently gets achieved by some PRNGs, and that's almost perfect (only a single state going to waste). You're not going to achieve that with a side product of a physics simulation that by itself doesn't care about maximizing the period length.


----------



## Stefan (May 16, 2010)

StefanPochmann said:


> Period of (2^n)−1 using n bits apparently gets achieved by some PRNGs, and that's almost perfect (only a single state going to waste). You're not going to achieve that with a side product of a physics simulation that by itself doesn't care about maximizing the period length.



In order to be that efficient, your pendulum, once started, would have to go through every single state it could possibly be in (except one state, standing still).


----------



## qqwref (May 16, 2010)

StefanPochmann said:


> This is worth reading: http://en.wikipedia.org/wiki/PRNG#Periodicity
> Period of (2^n)−1 using n bits apparently gets achieved by some PRNGs, and that's almost perfect (only a single state going to waste).


I'd say that IS perfect, actually. You don't really want a period of exactly 2^n because then there could very well be a clear pattern every 2^k outputs (for k < n). But if the period is (2^n)-1 you can choose n such that this number has very few nontrivial factors (if any at all!). For instance, as you know, (2^19937)-1, the cycle length of the Mersenne Twister, is a Mersenne prime, so the PRNG itself is a lot stronger and looks more chaotic.


----------



## Stefan (May 16, 2010)

qqwref said:


> You don't really want a period of exactly 2^n because then there could very well be a clear pattern every 2^k outputs (for k < n).


Could be, but doesn't have to be, so I don't see how that makes me want to waste a state. And MT could also have a clear pattern every 2^k outputs virtually all the time (except once, somewhere in its long period where we're very unlikely to ever be).


----------

