WCA Scramble Algorithm

[Cride5]

I've noticed this phenomenon with edge orientation cases in ZZ. Using a sequence of random moves to scramble usually results in a bias towards a lower number of bad (misoriented) edges. Although 4 and 8 bad edges should be equally probable, I seem to get more 4-edge than 8-edge cases (similarly for 2 and 10 edge cases).

You're right. From my 3x3 scramble analyzer:

scramble length: 25
  probability for  0 flipped edges: 0.00134544044252748545
  probability for  2 flipped edges: 0.03673557940805194881
  probability for  4 flipped edges: 0.25615535099536977496
  probability for  6 flipped edges: 0.44489037738355416974
  probability for  8 flipped edges: 0.23149165891662189241
  probability for 10 flipped edges: 0.02895679378114915976
  probability for 12 flipped edges: 0.00042479907272556887
  state 2047 is least probable with 0.00042479907272556887
  state    0 is most  probable with 0.00134544044252748545

Cheers for confirming the stats, I'm not going mad after all

For the 3x3, it chooses a random position and then finds a fast way to create that position using the advanced Kociemba algorithm. (This is really hard to program, so I suggest just using 25 random moves.)

After a bit of searching, I'm quite sure there are no online WCA-style 3x3 scramblers. The only thing which seems to come close is using Johannes's Cube Solver to scramble then solve and applying the solution's inverse. The only problem is its hard to tell if the scrambler actually chooses a random state or whether it applies a random sequence of moves.

If I can find the time, I might try implementing a scrambler in Javascript which randomly generates a cube state, ensuring its orientation and permutations are compliant with the laws of the cube. A basic implementation of the Kociemba algorithm will then generate an efficient solution and provide its inverse for the scramble. Is this something that folk would find useful?

 

[rokicki]

> Could be because the built-in PRNG sucks or because the sample is too small. Or maybe I made a mistake.

I suspect your code is not taking into account sequences that leave the group and re-enter it later; that might account for the difference.

By the way, the quick analysis I posted was indeed assuming independent moves; my longer analysis handles both independent moves (which are fairly common in some cube "scramblers", as well as being interesting from a theoretical perspective) and the "restrict subsequent moves" in various ways.

I have exact numbers for the entire Kociemba group (this required many gigabytes of RAM and hundreds of gigabytes of disk space) for various twist combinations. It's a lot of data to crunch through.

 

[rokicki]

That sounds like an excellent challenge: who can write a JavaScript WCA scrambler that (however it wants to) generates reasonably short scrambles for random cube positions? The program has to start from scratch (no loading pruning tables from disk). This is similar to my cube solving contest a few years ago, but different because we want shorter lengths than those algorithms would generate.

Kociemba's algorithm is super fast, but generating the pruning tables take a while; what's the best balance between precalculating and solving?

 

[mrCage]

That sounds like an excellent challenge: who can write a JavaScript WCA scrambler that (however it wants to) generates reasonably short scrambles for random cube positions? The program has to start from scratch (no loading pruning tables from disk). This is similar to my cube solving contest a few years ago, but different because we want shorter lengths than those algorithms would generate.

Kociemba's algorithm is super fast, but generating the pruning tables take a while; what's the best balance between precalculating and solving?

What is reasonably short in this respect? A typical Roux/Heise solve would take about 40 turns (htm). I guess the best bet would be to port the two-phase algorithm to JavaScript. And why cannot pruning tables be used with JavaScript?

Seriously, i dont think random state scrambling will have any great impact. It mostly only complicates matters. What's wrong with the occasional lucky solve? What matters is fairness!!

Per

PS! There are great practical implications with random state scrambling. It cannot be elegantly used for most "larger" puzzles like 4x4x4, 5x5x5, etc. The scrambles would be rather longish. So why being so picky about 3x3x3 scrambling?

What is the current state of 4x4x4 god's algorithm search? There are some solvers generating decently short scrambles, but they do not claim at all be opimal or even near optimal. The idea is yet again nested subgroups, not humanlike solving.

Per

 

[Stefan]

What is reasonably short in this respect?

Well, he said the solutions of his cube solver contest aren't good enough, and the winners used Thistlethwaite which averages 31.3 moves.

I guess the best bet would be to port the two-phase algorithm to JavaScript.

I suspect Thistlethwaite searching alternatives like Kociemba does might be better.

And why cannot pruning tables be used with JavaScript?

He didn't say that.

So why being so picky about 3x3x3 scrambling?

What? We aren't. Random state scrambling is ideal and the simple rule is that we want to use it whenever possible. Remember we don't just do it for 3x3x3 but also already for 2x2x2, clock and pyraminx:
http://www.worldcubeassociation.org/regulations/#scrambling

 

[AvGalen]

...and for pyraminx the provided scramble isn't optimal (not even close). I didn't know that clock-scrambles were randomstates. Are you sure?

I do suspect that generating and using the "Kociemba 2 step alg pruning tables" wouldn't be possible in yesteryears browsers. IE (even 8) already gives problems (timeouts) with the 2x2x2 pruning tables. All other (presentdays) major browsers seem to handle javascript increasingly fast but I have never seen a browser handle such huge javascript.

I wrote a web-interface for Cube Explorer a couple of years ago. I had Cube Explorer running as a service on my webserver and its webinterface was used for solving the provided state. I am sure that implenting that would be the simplest solution, but it would require a server were Cube Explorer was actually running.

 

[Cride5]

Seriously, i dont think random state scrambling will have any great impact. It mostly only complicates matters. What's wrong with the occasional lucky solve? What matters is fairness!!

Going by the statistics here I don't really trust a sequence of 25 random moves to scramble my cube properly. Of course, I could simply add more random moves, but that will get tedious. The nice thing about implementing a random state scrambler is that the scramble moves you're applying are efficient at scrambling the cube. Its not just a sequence of 25 random moves, but a sequence of 25 (or so) moves to bring the cube to a truly random state.

I do suspect that generating and using the "Kociemba 2 step alg pruning tables" wouldn't be possible in yesteryears browsers. IE (even 8) already gives problems (timeouts) with the 2x2x2 pruning tables. All other (presentdays) major browsers seem to handle javascript increasingly fast but I have never seen a browser handle such huge javascript.

I wrote a web-interface for Cube Explorer a couple of years ago. I had Cube Explorer running as a service on my webserver and its webinterface was used for solving the provided state. I am sure that implenting that would be the simplest solution, but it would require a server were Cube Explorer was actually running.

I'm pretty sure that's how Johannes's online solver works as well. I've had a wee look through his Javascript and solve requests are being passed to cgi scripts on the server-side.

This could be the best (or only) way to do it, but the fandamental problem is scalability. Imagine a popular site like cubetimer.com handling thousands of solve requests in order to generate nice scrambles for its users. I doubt their service providers would be happy

Anyway, I think I'm going to have a look at possible client-side options. If Javascript doesn't work then it may have to be an applet.

 

[Stefan]

...and for pyraminx the provided scramble isn't optimal (not even close).

Right. Would be desirable to not have scrambles more than 12 moves plus tip moves.

I didn't know that clock-scrambles were randomstates. Are you sure?

Pretty sure. Well, not in the sense that we first pick a random state and then compute a generating scramble for it, but in the sense that the scrambles we generate result in a uniform distribution.

 

[AvGalen]

...and for pyraminx the provided scramble isn't optimal (not even close).

Right. Would be desirable to not have scrambles more than 12 moves plus tip moves.

I didn't know that clock-scrambles were randomstates. Are you sure?

Pretty sure. Well, not in the sense that we first pick a random state and then compute a generating scramble for it, but in the sense that the scrambles we generate result in a uniform distribution.

For Pyraminx I love to play "beat the scramble" so I like the longer scrambles

For Clock I have had this feeling for quite some time that the scrambles aren't actually that good and certainly aren't "random state". Do you know of a study about this or do I have to do this research myself?

 

[Stefan]

For Clock I have had this feeling for quite some time that the scrambles aren't actually that good and certainly aren't "random state". Do you know of a study about this or do I have to do this research myself?

I just checked it (probably have before). I'm sure now. A proof is actually quite easy, at least if you know how to solve the clock. I can give my proof, but I'm sure you can do it as well and I'd like to see (how) you do it.

 

[mrCage]

Hi

I see a possible future clash between the wca preferred scrambling notation and optimality. A random state optimal scrambler would (probably) use all notation tokens on larger cubes, not solely outer block notation. There are a few puzzles where random state scrambling is easy and feasible. So by all means go ahead and scramble like that. Noone has yet convinced me what is the gain in doing so. KISS

Per

 

[AvGalen]

For Clock I have had this feeling for quite some time that the scrambles aren't actually that good and certainly aren't "random state". Do you know of a study about this or do I have to do this research myself?

I just checked it (probably have before). I'm sure now. A proof is actually quite easy, at least if you know how to solve the clock. I can give my proof, but I'm sure you can do it as well and I'd like to see (how) you do it.

I am actually not quite sure that clock scrambles are indeed random state. I will look into this on sunday. I am especially worried about the quality of the scrambles when there are 0's in it. I hope that on Sunday I will realise that I shouldn't worry.

And Per: You should realise that for blind and FMC it is unfair if chances of 8 misoriented edges are smaller than 4 misoriented edges. For speed, this might also be an advantage if you use methods like EOLine. I am not saying this is a big problem, but if we have the capabilities to avoid it without big downsides...why not?

 

[qqwref]

The way the clock scramble should work is that it generates 14 random numbers (from -5 to 6 inclusive) and then does a specific set of 14 linearly independent moves with those amounts. That is, as there are 14 clocks, we should be able to solve every position by doing each of those moves once, and similarly we can scramble to any position by doing each of those moves once. As long as the function we use to generate the 14 numbers is truly random, the scrambles also will be.

 

[Cride5]

Looks like the simple idea of implementing Kociemba in Javascript wasn't to be. As I suspected, Javascript with its very loose type system made it difficult to store the lookup tables efficiently. The program consumed far too much memory to be usable. Looks like its back to the drawing board...

In the mean time, I've posted up a simple random state scramble generator as a Java applet if anyone's interested.

I'd still like to get an efficient solver (25 moves or less) working in Javascript, something with a much leaner memory footprint. Currently very short on time, so I'll put it on the back burner for now

 

[mrCage]

And Per: You should realise that for blind and FMC it is unfair if chances of 8 misoriented edges are smaller than 4 misoriented edges. For speed, this might also be an advantage if you use methods like EOLine. I am not saying this is a big problem, but if we have the capabilities to avoid it without big downsides...why not?

Have i misunderstood the concept of fairness?! As long as all competitors get the same scramble(s) it would be fair, right ???

Seriously, explain to me what is wrong with the occasional easy/lucky scramble as long as everyone get that same scramble??

Per

 

[Lucas Garron]

And Per: You should realise that for blind and FMC it is unfair if chances of 8 misoriented edges are smaller than 4 misoriented edges. For speed, this might also be an advantage if you use methods like EOLine. I am not saying this is a big problem, but if we have the capabilities to avoid it without big downsides...why not?

Have i misunderstood the concept of fairness?! As long as all competitors get the same scramble(s) it would be fair, right ???

Seriously, explain to me what is wrong with the occasional easy/lucky scramble as long as everyone get that same scramble??

Per

It's not fair because the solves enter a database where solves are compared with people's who didn't get a chance at the same scrambles. "Fair" at the competition, not fair worldwide.

Also, it's unfair because it changes the nature of the event. The idea is to assess the ability to solve any cube in few moves. With an uneven scramble distribution, we're giving competitors a chance to prepare to perform better in this event than their ability to solve arbitrary cubes.

 

[qqwref]

It's not fair because the solves enter a database where solves are compared with people's who didn't get a chance at the same scrambles. "Fair" at the competition, not fair worldwide.

This is the same reason that I have advocated removing scrambles that give a position which is too close to solved. Even if everyone in a competition has the opportunity to solve an incredibly easy scramble, not everyone in the world will, and so it's not fair to everyone who wasn't at that competition. For some events this is no problem at all, but for short events such as 2x2 and pyraminx it is a huge deal. I don't want to have to compete with someone who averages 8-9 seconds on 2x2 but got a 2-second solve because the scramble was 4 or 5 moves; unless I was world-class at 2x2, there's no way I could beat a time like that without also being lucky.

 

[mrCage]

And Per: You should realise that for blind and FMC it is unfair if chances of 8 misoriented edges are smaller than 4 misoriented edges. For speed, this might also be an advantage if you use methods like EOLine. I am not saying this is a big problem, but if we have the capabilities to avoid it without big downsides...why not?

Have i misunderstood the concept of fairness?! As long as all competitors get the same scramble(s) it would be fair, right ???

Seriously, explain to me what is wrong with the occasional easy/lucky scramble as long as everyone get that same scramble??

Per

It's not fair because the solves enter a database where solves are compared with people's who didn't get a chance at the same scrambles. "Fair" at the competition, not fair worldwide.

Also, it's unfair because it changes the nature of the event. The idea is to assess the ability to solve any cube in few moves. With an uneven scramble distribution, we're giving competitors a chance to prepare to perform better in this event than their ability to solve arbitrary cubes.

That is taking fairness a bit far ... Then one could say cubing contests are by nature unfair (unless online ... ) Would you also include method independence in your perfect fairness definition?

Per

 

[AvGalen]

...Would you also include method independence in your perfect fairness definition?

Per

Yes, that is exactly what this is about. If the number of oriented edges should be 6 on average, but it is 10 on average (these numbers are exagerated) then you could optimise training by learning all 2-flip algs but only 1 or 2 6 flip algs.

If a truly random puzzle state is generated first and then a scramble is calculated for it that would be the fairest way

 

[qqwref]

If a truly random puzzle state is generated first

Ah, Arnaud, didn't you know, that's the hardest part ;-)