Proposal: web-based random state scrambles for 3x3

[FatBoyXPC]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Edit: OMG, fatboyxpc is so full of fail.

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

 

[Bryan]

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]

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]

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

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]

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

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.

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]

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.

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]

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

 

[Stefan]

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]

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]

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.

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]

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?