8 billion scrambles?

[Kenneth]

I's 43,252,003,274,489,856,000 diffrent scrambles, right? We use a scramble genarator to randomly select one of them. But will we get any of them? I'm not so sure.

The function the scramble generator uses to create random numbers is intiated using a seed and that is most likely a 32 bit integer = about 8 billon diffrent seeds. Each seed will create a diffrent sequence of random numbers each creating a diffrent scramble. Then it does not matter if the choosen lengt of the scramble is 25 or 250 turns, it will still be the same number of sequences/scrambles. The seed can be given as a specific number always giving the same scramble or as normaly it is taken from the system timer to get a "random" seed, but it's still "only" 8 billion diffrent ones. Not only the seed used but also the random function it self most like works in long integers so that's the resolution we got (it may be something else on some implementations but normaly It's a 32 bit int (correct me if I'm wrong about this). If we use a diffrent scramble generator, then we will again have 8 bilion possible scrambles but maybe 8 billion diffrent ones depending of how the code in the specific generator uses the random number taken from the random sequence. The same code can act diffrently on diffrent platforms depending on how the random function in the OS works but the resolution probably will still be 32 bit.

Or?

 

[KConny]

I don't know how all the scrambler works, but I saw code for one. First it picks a random face, then a random turn, like ' or 2. Picks a diffrent face, and also checks so that turns like U D U won't show up, and again a turn and it does this 25 times. Since the cube is always solvable in sub25 moves all cases are reachable. Or so I think.

 

[blgentry]

Kenneth,

You seem to be implying that a computer based scramble generator is simply generating one random number and using that to index into a list of 43 quadrillion cube states. I think it's quite unlikely that someone has written a scramble generator in that way.

Again, as the above poster said, the code that I've read does a call to the random number generator for each move in the scramble sequence at least twice: Once for the face to turn and once for the direction. Logic should also be employed such that you don't undo the work done by a previous face turn. The code I read was quite ingenious in preventing that from happening.

You bring up an interesting question about generating really, really big random numbers though: The system supplied routine has a relatively small ceiling compared to the number of configurations of the cube.

I just flipped through the chapter on random numbers in "Numerical Recipes In C" looking for guidance. The best I could find is taking random numbers from a pool of cryptographically generated data. I believe PGP and other public key systems use a (relatively) large pool of random data for generating those incredibly large keys they work with (2048 bits for example).

I read an article on how it was done many years ago, and frankly it was over my head. I find it really interesting though, that all of the generators that go to this level of complexity now include an outside source of random data: PGP gets it from the user typing random keystrokes on the keyboard and measuring the timing between the keys. TrueCrypt gets it from the user moving the mouse around in random patterns. Ok, this is WAY off topic now, so I'll stop.

Brian.

 

[badmephisto]

KConny thats not what Kenneth is talking about. He is questioning the process by which computers generate random scrambles, and is basically arguing that some scrambles are impossible to generate using conventional methods that current computers use.

You may actually have a pretty good point, I never thought of that. I'll have to think about that one

 

[Lucas Garron]

Note that the old scrambler also suffered from this.
Mathematica, an expensive commercial math program, better have reliably random numbers with a huge seed; they explain some of the methods for 6.0 here.

We could always use http://www.random.org/ for competitions.

 

[Sebastien]

as for example an "one slice turned" scramble, which is surely one existing scramble is quite uninteresting and lets say lucky i don't think that its really necessary to get every possible scramble by a scramble generator.

 

[cuBerBruce]

I've mentioned this issue before (on the yahoo forum, at least). Typical pseudorandom number generators (PRNGs) appear to have an internal state represented by an integer ("seed") of around 31 to 48 bits. Even a 48-bit seed would not be enough for generating all states of the 3x3x3 puzzle, as 43 quintillion is a 66-bit number.

I don't consider this a major issue, since a scramble generating function can still generate billions of positions, and it is not easy to predict which positions could be generated by a given scramble generating function and which ones would never get generated, without actually calling the scramble generating function with the PRNG in each possible seed state. But I would like to see a high quality PRNG eventually being used for generating WCA competion scrambles. (Or an "actual" random number generator as mentioned at the site Lucas linked to).

 

[Kenneth]

No, it's not a big deal, no way anyone will learn to recognise 8 billion scrambles

 

[brunson]

I's 43,252,003,274,489,856,000 diffrent scrambles, right? We use a scramble genarator to randomly select one of them. But will we get any of them? I'm not so sure.

Edit: After replying to bundat below, I realized that I didn't properly read the original posting. The OP was talking about the limited number of seeds available, but seeding before every random sequence generated would be silly. Anyway, I'll leave the rest of my post here, but predicate that now it's just a discussion of a point that isn't actually on topic.

If we were had every possible position of the cube precalculated and numbered 1 through 43,252,003,274,489,856,000 and then used a random number generator to pick one of them, then, no you wouldn't get all of them, because it only selects from the first 2^32 scrambles, because your proposed PRNG only generates numbers from 0 to 2^32 - 1.

However, that's not how it works. We're generating moves that result in a scramble, not picking from a list of scrambles. If I have a random number generator that generates integers from 0 to 9, I can still generate random numbers larger than 9 simply by concatenating a sequence of random digits together. i.e. if I want a number between 1 and a billion, then I just generate 6 random digits and stick them together so it forms a 6 digit number and that number will be from 0 to 999,999. In fact I can generate an arbitrarily large number using random 1's and 0's by interpreting that string of digits as a binary number.

In the case of the cube we're generating 25 random face turns. We don't even need a random number from zero to a billion, we just need a random number from 1 to 6 to pick a face, then another number from 1 to 3 to pick a +1 +2 or +3 rotation. Add some logic to prevent picking the same face twice and some more to avoid simple sets of moves than cancel each other out and you have a scramble generator.

Here's one I wrote in python:

def randomtwist():
    from random import choice, random

    axes = 'xyz'
    faces = { 'x': ( 'L', 'R' ), 
              'y': ( 'U', 'D' ), 
              'z': ( 'F', 'B' ) }
    directions = ( "", "'", "2" )
    
    axis = ""
    last = ""

    while True:
        while axis == last:
            axis, direction = choice( axes ), choice( directions )
            face = choice( faces[axis] )
    
        last = axis
        yield face + direction

def scramble( count=25 ):
    from random import randint

    for twist in randomtwist():
        seq.append( twist )
        if len( seq ) > count: break

    return " ".join( seq )

I'm not using anywhere near the full range of the random number generator, I'm selecting from a list of 3, then a list of 2, then a list of 3, so essentially I'm generating a random number from 1 to 18. But I certainly generate more than 18 different cube positions.

Does that make sense?

Now, given that it has been proven that any scramble can be solved in 24 moves (and I think that has been reduced to 23), will a random selection of 25 face turns result in covering the entire set of 43 quadrillion possible states? That is debatable. Given a set of face turns, the first will take you away from the solved state, and any of the 15 possible next face turns (excluding turns of the same face) will take you further away from the solved state, and that continues for some number of turns. However, you can quickly reach a state where another turn will actually bring you closer to a solved state than you were at or keep you the same distance from solved.

In fact, if we say for the sake of argument that the maximum length of "God's algorithm" is N, then if your cube is in a state where N is the minimum number of turns that is required to solve it, then any face turn you make is more likely to bring you closer to solved than leave you N turns from solved. In any sufficiently scrambled state (i.e. min number of face turns to solve is n) there will exist a partitioning of the set of face turns such that one subset will make the cube more scrambled (min face turns to solve = n+1), one subset will leave the cube in the same "scrambledness" (min face turns to solve remains n) or will actually bring the cube closer to being solved (turns to solve = n-1). And it easy easy to see that in any state other than solved, the number of face turns that brings the cube closer to being solved is at least 1.

So, lets say we generate a random scramble of M face turns and define N to be the maximum length of an optimal solution to any given cube state. If M < N, then we *definitely* cannot generate every possible cube state. If M = N, then it would be possible to reach every possible state, but only if you never generated a face turn that either brought you closer to solved or kept you the same distance from solved. For M > N we have to revert to statistics and probability.

Imagine all 43 quadrillion states of the cube laid out as nodes on a connected graph with solved in the center, and the nodes of the graph are organized into concentric circles numbered outward from the center from 1 to N such that all if a cube's state node lies on a circle O (for "Order of the scramble), then O is the length of the optimal solution to that state. Finally, each state node on the graph is connected to 18 other nodes with each of the 18 connections corresponding to each of the 18 possible face turns of the cube.

Starting at the center and choosing a random face turn and following the corresponding connection will take you to a different node on the graph. Repeating that operation at the new node will take you to another node, with a 1 in 18 chance of taking you back to solved. If you imagine generating a list of random moves and following that list of moves through the graph, then it become very analogous to a problem statisticians call a "random walk" with restricted states and a maximum distance from the starting point. I can't imagine I'm the first one to imagine this, I bet it's called a "constrained random walk", maybe I'll google it.

A good statistician may be able to tell you the optimal M > N so that you are reasonably sure to get near maximal scrambledness, but I am not that statistician. I imagine the interconnectedness of the graph is such that for some values of O you are more likely to move towards solved than away (O = N being the obvious example) and, for some values of O you are more likely to move away from solved (at 0 = 1 only 1 in 18 face turns brings you back to solved). I envision there is a band of circles that have a certain stability in that their interconnectedness such that, once you get within that band, you are most likely to remain there, no matter how many moves you make. If you get too close to solved the connections between nodes are more likely to move you toward scrambled and as you move too far away from solved, you're more likely to move randomly back closer to it.

But, none of you were arguing that, you seemed stuck on the whole "we're only generating 8 billion possible positions because that's the range of our PRNG", which is a patently invalid argument.

 

[Stefan]

brunson, you're funny. Admittedly I didn't read further than your first two paragraphs, as those are already very wrong. I suggest you learn how PRNGs work, especially what the "seed" is.

 

[blgentry]

I'll just add one little thing to Brunson's coverage of this topic:

Again, picking face turns at random and *not* generating some huge number, you can see that 25 random cube face turns must yield all combinations of the cube, due to the number of states these 25 turns can produce.

The math:

On our first turn, we can pick from 6 faces, and we can pick to turn that face one quarter, 2 quarters, or 3 quarters. 6 x 3 = 18 choices for our first turn.

For our second move through our last move, it is useful to restrict the choice of faces to only those that are not on the same axis we just turned on. I.E, if I just turned on the U face, I am not allowed to now turn on either U or D, only R, L, F, and B. So the math becomes: 4 faces to choose from, and the same 3 directions, equaling 12 choices for the 2nd, 3rd, .... 25th turns.

So 24 of our turns has 12 choices: 12^24
One of our turns has 18 choices: 18

Total: 18 x 12^24 = 1.43094... x 10^27

That's 14 with 26 zeros behind it, or 1400000000000000000000000000 .

The 43 quintillion number only has 18 zeros behind it, or 19 if you express it as 4.3 x 10^19 .

So the "space" of a 25 move scramble is over 1 million TIMES larger than the entire space of possible cube configurations. Note: This is not 1 million more combinations. It's one million *TIMES* more combinations. I think this math speaks for itself.

Brian.

 

[brunson]

brunson, you're funny. Admittedly I didn't read further than your first two paragraphs, as those are already very wrong. I suggest you learn how PRNGs work, especially what the "seed" is.

Stefan, I assure you that I know what a PRNG is. If you think something in my first two paragraphs is incorrect, I'd invite you to tell me what and why.

BTW, I read up to page iii of your thesis and concluded it was written in German. Where's the flaw in that?

 

[bundat]

From what I can recall, if you use a certain number as the seed, the random number function will generate the same sequence of random numbers everytime. Always the same sequence.
(because IIRC a PRNG is just a crazy formula that just takes the previous number and generates the next one, the very first one being the seed(?))

I made the following program quickly:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <conio.h>

int main(){
	int i,seed;
	clrscr();

	seed = time(NULL);
	srand(seed);
	for (i=0;i<20;i++)
		printf("%i: %i\n",i,rand());

	getch();
	return 0;
}

And yes, it seemed pretty random.
However, replace the line

seed = time(NULL);

with

seed=50;

And after running it 20 times from different places (from the IDE, in the console, after closing and reopening the command prompt, after restarting, in pure DOS mode, even in DOSBox), the result was always the same:

Depending on the seed function (which can usually only accept a 32-bit integer as the seed), it only has 2^32 possible SEQUENCES it can generate. So if the scramble size is fixed (at 25?), then yes, it ACTS as if the seed is an index into a list of all possible scrambles, even though it isn't programmed that way.
Because a certain seed will ALWAYS generate the same scramble.

Even if the program was designed for a 64-bit processor, and the language/compiler's seed function accepts a 64-bit integer as the seed, it still generates only 2^64 possible sequences (18,446,744,073,709,551,616), barely touching half of all possible scrambles (not even considering overlapping 25-move algos that generate the same end state, sorta like no-do algos like R U R' U' x6).

Not that it matters though, even if the seed function only accepted 16-bit seeds, thus only generating 65536 possible scramble sequences, it's still more than enough that no one (human) will notice anyway.

 

[brunson]

If you were to seed the random number generator before you generated every scramble, then you would limit yourself to the 2^32 25 move sequences that are at the beginning of each seeded sequence. However, that would be bad practice.

What you're more interested in is the periodicity of the PRNG. Python, for example, uses the Mersenne Twister, which has a periodicity of 2^19937 − 1, which is a 5339 digit number.

 

[brunson]

I guess I better understand what the original poster was asking about. If you use a 32 bit it as the seed for your PRNG, then you would be stuck at the beginning of one of 2^32 different pseudo random sequences, but that would be a very naive implementation. But that only determines the starting point, as you use up numbers in the PRNG you generate more than 2^32 random sequences. If you generate more than one scramble per seed, say 100, then you'll most likely generate slightly fewer than 2^32 * 10 unique scrambles (with the possibility of a few collisions).

There are many simple ways to increase the entropy of your starting point into the pseudo random sequence. When I need that kind of unpredictability I usually generate a 32 bit hash of the string representing the time of day and use that as my seed, then I use /dev/random to generate large number of values to "waste" from the beginning of the sequence. There are also many cryptographically secure algorithms available (the Mersenne Twister is not cryptographically secure).

/dev/random on linux uses environmental inputs to generate entropy for truly random numbers, but can easily be exhausted. /dev/urandom provides a pseudo random implementation which will not be exhausted but uses additional input from the environment to remain cryptographically secure random numbers.

So, I guess the real answer is: It depends on how naive the program is and how many scrambles you generate at a time before re-seeding the PRNG.

 

[cuBerBruce]

I agree pretty much with what bundat said, and this is more or less a further explanation. A PRNG as I said before has a fixed number of internal states. Call that number S. It doesn't matter if your scramble generator somehow uses the PRNG to get a number from 0 to N-1 (where N is the number of possible states of the puzzle), or if your scramble program picks a set of 25 (or some similar number depending upon the puzzle) moves, applying them in sequence.

Let's say you have a function called GetScramble() that uses a PRNG somehow to get a scramble. In fact, let's say GetScramble() gets 25 pseudorandom numbers from the PRNG, and maps those numbers to cube moves by some scheme, and returns that sequence of moves. If the internal state is one particular state out of the S possible states, the call to GetScramble() will result in the PRNG to cycle through 25 of its S internal states. So the next call the PRNG will have some different internal state, and cycle through another 25 of its S internal states and GetScramble() will generate (generally speaking) a different set of 25 moves. Do this over and over and over and eventually the PRNG will be in the same state that it had prior to the first call to GetScramble(). Now if GetScramble() is called again, it gets the same sequence of 25 pseudorandom numbers it did when GetScramble() was called that first time, because the PRNG just cyclically goes through all of its states. So GetScramble() returns the same sequence of 25 moves that it returned on that first call.

So the number of different scrambles you get will be at most the number of internal states of the PRNG. If GetScramble() calls the PRNG a fixed number of times each time it is called, and that number is relatively prime to S, then it will take S calls to GetScramble() to get back to the same internal state (assuming no reseeding of the PRNG). Assuming S is a power of 2, then any odd number would achieve this.

Another thing, the seed function for a PRNG may not always let you completely specify the internal state (the real seed, so to speak). Sometimes the number passed to the seed function may be extended or converted to a higher precision number internally. So let's say the seed function lets you specify a 32-bit number. That doesn't necessarily mean there are only 2^32 internal states. It might be more. Also the precision of the value returned by a PRNG is often less than the precision of the internal seed. You need to make sure you don't try to use more precision than the PRNG returns to you. It might use a 31 bit internal seed, but only return 15-bit values, for example.

I haven't used Python language myself. It's interesting that it uses a high quality PRNG, apparently. I know that the standard library pseudorandom number generator function from my MS Visual C++ compiler is not a Mersenne twister.

Generally, reseeding of the PRNG is not recommended (only seeding it initially). bundat only talked about using the seed function again (with the same parameter) to show how putting the PRNG into the same state causes you to get identical results. By putting the PRNG back to the same state, you get repeatable results.

 

[blgentry]

This is all sort of interesting, but it's become completely academic.

No one is going to use the same seed for all scrambles. No one is going to generate millions of scrambles from one single seed value. The size of the seed has no relation to the number of states that a 25 move scramble can create, when created with good random input.

So there's really no point to this whatever. Simply seeding a scrambler with time of day, date, etc, and not calling it hundreds or millions of times in a row with the same seed will result in very random scrambles over a space larger than the space of the cube.

IMHO: Case closed.

Brian.

 

[brunson]

cuBerBruce, that's a very good explanation of what's going on in the PRNG, which is essentially a state machine with a large number of states, the better the algorithm, the larger the number of states. Given any starting point, the sequence is always the same, which I now realize was the point of Kenneth's original post. In your description I'm interpreting your "S" as being what I called the periodicity of the algorithm.

One thing I don't know is whether the seed will put simply put you at some known state in S or if the seed generates an entirely different state machine, which also has S states.

Any pseudo random number generator is going to suffer from this repeatability problem. There are true random number generators, but they usually require some environmental input to accumulate "entropy" and that entropy can be easily depleted. For example Hot Bits from Fourmilab uses a detector to monitor the decay of a sample of radioactive isotope to measure random intervals of time and convert those into sequences of random numbers. However, those sources are limited to the number of observations that are used to generate their entropy and can be exhausted if queried too quickly.

I think there are several implementations that combine a TRNG and a PRNG to provide a cryptographically secure RNGs. /dev/urandom in Linux provides one of those implementations and I've written a Python module (all of 30 lines of C) that replaces the Mersenne Twister (MT) implementation of PRNG with one that reads from /dev/urandom.

I also started a pure python implementation of CMWC (complementary multiply with carry), but never finished it. CMWC can have a period 10^33000 times longer than MT, but is much less complicated to implement. The idea was to look at the performance in pure python and see what I'd need to speed up in C to make it a reasonable replacement for MT.

But, enough rambling. In python it's pretty simple to seed the PRNG with an environmental, like timestamp, and use jumpahead(n) with n being a sufficiently large number derived from /dev/random to get a starting place that would avoid the problems Kenneth originally pointed out.

 

[Stefan]

Stefan, I assure you that I know what a PRNG is. If you think something in my first two paragraphs is incorrect, I'd invite you to tell me what and why.

Bah, you cheated. Prepended a new paragraph so now it's paragraphs two and three.

The context you were responding in was the common poor PRNGs, I think the original message made that quite clear. Java for example is used for several popular scrambler programs and it has a 48 bit internal state. Python is indeed much better, but that's unusual and I think even your example program didn't seed it properly but used the current time as seed, which is very poor and nullifies the advantage of the huge internal state.

(I confess I didn't know about Python's PRNG until now, and I was obviously too quick suggesting to learn about seeds, should've said "internal state" instead.)

But mainly I meant the part where you also said you can generate arbitrarily large randomness simply by using the generator several times and concatenating the results. That works with real random generators, but not with pseudo ones.

BTW, I read up to page iii of your thesis and concluded it was written in German. Where's the flaw in that?

Actually I had skimmed the rest of your post. If you do the same with my thesis, you see it's English. The German paragraph had to be in there, legal stuff saying I didn't plagiarize. Well, I assume you weren't serious. If you were, should I point the issue out somewhere?

Oh and I did read the rest now (last night I didn't have much time until my tram home). Nothing in there about the number of internal states of the PRNG or something else rectifying the wrong impression you gave in the first paragraphs. Reading your later messages made me believe you do know what you're talking about, but just didn't talk about it quite properly, and somewhat ignored the context and the reality of our scramblers (note I don't mean to be mean (this time really not), just trying to explain what happened, i.e., misunderstandings).

 

[brunson]

Stefan, I assure you that I know what a PRNG is. If you think something in my first two paragraphs is incorrect, I'd invite you to tell me what and why.

Bah, you cheated. Prepended a new paragraph so now it's paragraphs two and three.

Yes, after bundat's posting I realized I'd skimmed over the real point of Kenneth's posting and wasn't replying to what he was talking about. I figured taking the whole post down would really be cheating, I was offbase in my reply and I'm willing to own up to that without trying to sweep it under the rug.

BTW, I read up to page iii of your thesis and concluded it was written in German. Where's the flaw in that?

Actually I had skimmed the rest of your post. If you do the same with my thesis, you see it's English. The German paragraph had to be in there, legal stuff saying I didn't plagiarize. Well, I assume you weren't serious. If you were, should I point the issue out somewhere?

No, I was just being facetious (really kind of trying to be a ****). I thought of it because I seem to remember someone almost making that mistake when you originally posted it.

Oh and I did read the rest now (last night I didn't have much time until my tram home). Nothing in there about the number of internal states of the PRNG or something else rectifying the wrong impression you gave in the first paragraphs. Reading your later messages made me believe you do know what you're talking about, but just didn't talk about it quite properly, and somewhat ignored the context and the reality of our scramblers (note I don't mean to be mean (this time really not), just trying to explain what happened, i.e., misunderstandings).

Definitely misunderstandings, I should have read the OP more closely to begin with. To my defense, I'm not the only one that misunderstood it, blgentry and I actually discussed it off forum before either of us replied and we both had the same misinterpretation.

By the way, I read your entire thesis last night. It was very interesting, your application sounds very cool, especially the way you handle description of goals, even allowing for concurrent goals. Even more interesting to me was the history of computational analysis of the cube. I'd read bits about it here and there, but having it all in a nice, concise, chronological bundle for one reading was excellent. I think I'm going to have to play with ACube a bit more now that I've read your description of what it is capable of.

It's kind of funny, if it hadn't been for this misunderstanding I may have never gotten around to reading your thesis, even though I'd been intending to for weeks. It turned out to be quite enjoyable and definitely educational.