Proposal: web-based random state scrambles for 3x3

[FatBoyXPC]

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]

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]

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.

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]

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.

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]

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.

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

 

[JBCM627]

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]

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.

But that would limit your ability to do something like F B (which should be legal).

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

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]

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]

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]

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]

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

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/

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.

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]

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]

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]

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]

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

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.

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]

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.

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.

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.

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]

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]

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

I get the following distribution:

moves   n=1      n=2      n=3      n=4      n=5      n=6      n=8   totals   n >= 2

 0        0        0        0        0        0        0        1        1        1
 1        0        0        0        9        0        0        0        9        9
 2        0       54        0        0        0        0        0       54       54
 3       48      186        0       87        0        0        0      321      273
 4      264      956      528       99        0        0        0     1847     1583
 5     1092     6302     1944      654        0        0        0     9992     8900
 6     7092    35976     6408      660        0        0        0    50136    43044
 7    44904   151900    26592     3948      192        0        0   227536   182632
 8   186864   577424    99688     5328      768        0        0   870072   683208
 9   451728  1235424   186288    13524      784        0        0  1887748  1436020
10   151512   401360    62496     7932      384      116        0   623800   472288
11      240     1776      328      276        0       24        0     2644     2404
     ------  -------   ------    -----      ---      ---        -  -------  -------
     843744  2411358   384272    32517     2128      140        1  3674160  2830416

     8.8199   8.7447   8.6894   8.6794   8.6391  10.1714   0.0000   8.7556   8.7364

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]

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]

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.

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.