Proposal: web-based random state scrambles for 3x3

[FatBoyXPC]

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]

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]

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

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]

Why is this ridiculous?

 

[brunson]

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]

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]

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 assume you mean this?
http://stefan-pochmann.info/spocc/other_stuff/tools/scramble3x3/sourcecode.txt

Yes I was talking about the link you gave for the scrambler you made.

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.

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]

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]

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]

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]

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.

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.

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.

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]

BOY DO YOU SUCK!

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

 

[Stefan]

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]

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]

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.

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]

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]

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?

Damn I need sleep.

 

[JBCM627]

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]

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

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

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

 

[JBCM627]

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

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

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

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.