Proposal: web-based random state scrambles for 3x3

[brunson]

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]

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]

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]

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

 

[FatBoyXPC]

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]

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]

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]

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.

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]

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

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

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

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]

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]

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.

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.

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.

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]

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]

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.

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]

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]

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]

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

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.

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]

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.

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]

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]

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]

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.