Random Scramble Generation

[Cheese11]

Hello everyone! I'm a computer science student taking a software engineering class, and my group has decided on making a speed solving timer, for android. One of our features needs to be a random scramble generator for at least 3x3x3 (This timer is not going to be released). Are there any resources out there on the algorithms that go into random scramble generation that will help me implement my own?

 

[shadowslice e]

I would have a look at kociemba's work and also tnoodle.

Make a random state and solve that rather than using random move generator.

 

[Cubetastic5]

If you want to make your own program, it is very easy! I don't know what language you are going to use, but I will try to explain. For 3x3, make an array of all the 18 WCA Notations, and then generate a random number between 0 and 18, and call it from the array. Now, you need to prevent stuff like R R', L L2, F B' F', etc. So, store the last two moves, and if they cancel each other out, then generate a new random number.

 

[DGCubes]

If you want to make your own program, it is very easy! I don't know what language you are going to use, but I will try to explain. For 3x3, make an array of all the 18 WCA Notations, and then generate a random number between 0 and 18, and call it from the array. Now, you need to prevent stuff like R R', L L2, F B' F', etc. So, store the last two moves, and if they cancel each other out, then generate a new random number.

This would generate a random-move scramble as opposed to a random-state scramble. I'm not sure how good OP's timer program has to be, but random-state scrambles are always better if at all possible. Like @shadowslice e explained above, these work by picking one of the 43 quintillion states at random and solving it (so some cube-solving program would be required).

 

[Cheese11]

This would generate a random-move scramble as opposed to a random-state scramble. I'm not sure how good OP's timer program has to be, but random-state scrambles are always better if at all possible. Like @shadowslice e explained above, these work by picking one of the 43 quintillion states at random and solving it (so some cube-solving program would be required).

Essentially it doesn't have to be too perfect. I'll be presenting it to a prof who has limited knowledge of speedcubing, and I'm working with a group of people that are completely clueless to it. While the random state generator seems to be the way to go, I might have to just do a very simple random move generator due to time constraints, as well as space constraints. Not having an internet connection is pretty important to our vision for this application, so having an entire cube solver onboard might be a little crazy, bearing in mind I have no idea what those run yeah.

If you want to make your own program, it is very easy! I don't know what language you are going to use, but I will try to explain. For 3x3, make an array of all the 18 WCA Notations, and then generate a random number between 0 and 18, and call it from the array. Now, you need to prevent stuff like R R', L L2, F B' F', etc. So, store the last two moves, and if they cancel each other out, then generate a new random number.

Thank you. This is probably the way that we'll go. And it's a Java android app, not that it really matters. An array is an array no matter the language

 

[theawesomecuber]

Hello everyone! I'm a computer science student taking a software engineering class, and my group has decided on making a speed solving timer, for android. One of our features needs to be a random scramble generator for at least 3x3x3 (This timer is not going to be released). Are there any resources out there on the algorithms that go into random scramble generation that will help me implement my own?

https://github.com/thewca/tnoodle/tree/master/tnoodle-android

I haven't played around much with tnoodle since I don't like app development, but thrawst's recommendation in his US Nats seminar on making a cube timer is tnoodle for android apps.

I know your class won't be able to tell the difference, but if you want to make a timer worth anything, use tnoodle.

 

[Cubetastic5]

Thank you. This is probably the way that we'll go. And it's a Java android app, not that it really matters. An array is an array no matter the language

Thanks a lot! In languages like python, an array is called a list... Also, can you give me your email id or something? I would like to contact you.

 

[xyzzy]

Not having an internet connection is pretty important to our vision for this application, so having an entire cube solver onboard might be a little crazy, bearing in mind I have no idea what those run yeah.

Like mentioned above, there's TNoodle (and alternatives like jsss), but you could also write your own solver in maybe 500-1000 lines of code (Jaap's Puzzle Page is a good resource).

It's not absolutely essential for writing a timer that isn't going to be used "seriously", though, and a simple random-move approach works just fine for that. (For "serious" timers, random-state scrambles are considered a necessity nowadays, as they can be generated pretty quickly, you don't even need to write your own code to generate them, and they avoid statistical irregularities from insufficiently long random-move scrambles.)

 

[vidcapper]

If you want to make your own program, it is very easy! I don't know what language you are going to use, but I will try to explain. For 3x3, make an array of all the 18 WCA Notations, and then generate a random number between 0 and 18, and call it from the array. Now, you need to prevent stuff like R R', L L2, F B' F', etc. So, store the last two moves, and if they cancel each other out, then generate a new random number.

That's the approach I've used to create an Excel scramble generator, based on a random password generator I already set up.

 

[ProStar]

That's the approach I've used to create an Excel scramble generator, based on a random password generator I already set up.

1.) The last post to this thread was a year ago, please don't bump threads without a very good reason
2.) What you made was a Random Move Generator, which just presents random moves and doesn't have an equal probability for a given state to show up(that would be Random State)

 

[vidcapper]

1. Apologies, I *did* look for a more recent thread, without success.

2. I don't understand the difference between 'random move' and 'random state'? Surely with 43 quintillion possible positions it effectively makes no difference, especially on longer scrambles?

 

[I'm A Cuber]

1. Apologies, I *did* look for a more recent thread, without success.

2. I don't understand the difference between 'random move' and 'random state'? Surely with 43 quintillion possible positions it effectively makes no difference, especially on longer scrambles?

Some eo configurations come up more often than others with random moves. This isn’t especially important on 3x3, but on cubes like square-1 it makes parity way less likely

 

[ProStar]

1. Apologies, I *did* look for a more recent thread, without success.

2. I don't understand the difference between 'random move' and 'random state'? Surely with 43 quintillion possible positions it effectively makes no difference, especially on longer scrambles?

Technically they mean the same thing, but as far as cubing goes:

Random Move: Just a string of random moves
Random State: An equal probability for each state to show up

For random move certain ZZ orientations are favored and human noticeable patterns appear. For puzzles like Squan, parity almost never happens

 

[kubesolver]

I don't understand the difference between 'random move' and 'random state'?

That's a good start to learn about the difference.

Surely with 43 quintillion possible positions it effectively makes no difference, especially on longer scrambles?

The problem is that for a scramble to be long enough to be random enough you might need to generate much longer scrambles.

And even then you might not get random scramble.

As an analogy imagine that you want to select a random location in the Russia.

Consider approach 1 which is to randonly select one position, and the second approach being that you start from Moscow and do a big number of steps each step in the random direction.
- Do you think with big number of steps enough you will have equal chance to reach any position?
- How much more random steps you need to even have a chance to reach some distant locations, let alone with big probability?

 

[xyzzy]

The problem is that for a scramble to be long enough to be random enough you might need to generate much longer scrambles.

And even then you might not get random scramble.

As an analogy imagine that you want to select a random location in the Russia.

Consider approach 1 which is to randonly select one position, and the second approach being that you start from Moscow and do a big number of steps each step in the random direction.
- Do you think with big number of steps enough you will have equal chance to reach any position?
- How much more random steps you need to even have a chance to reach some distant locations, let alone with big probability?

The interesting thing here is that while in general there's a difference between the notion of a uniform distribution (equal probability everywhere) and the notion of a stationary distribution (for a random walk; the limit distribution "after many time steps"), as far as cubing is concerned, they're pretty much the same thing.

The WCA regulations state the scrambling requirements in terms of uniform distributions (4b3: "equal probability for each state"), but there is good reason to prefer to use the stationary distribution instead of the uniform distribution if these happen to differ: the stationary distribution is what you get in the limit if you scramble with random moves forever. Why should the scramble distribution be uniform if doing random moves doesn't tend to a uniform distribution?

(Counterintuitively, even what's considered a basic move will change the distribution. For example, with 15 puzzle, (independent) random multi-tile moves lead to the uniform distribution over the 16!/2 scrambles, but random single-tile moves don't! The latter distribution biases the free space towards being one of the middle four cells (1/12 each) and against being one of the four corner cells (1/24 each).)

 

[I'm A Cuber]

The interesting thing here is that while in general there's a difference between the notion of a uniform distribution (equal probability everywhere) and the notion of a stationary distribution (for a random walk; the limit distribution "after many time steps"), as far as cubing is concerned, they're pretty much the same thing.

The WCA regulations state the scrambling requirements in terms of uniform distributions (4b3: "equal probability for each state"), but there is good reason to prefer to use the stationary distribution instead of the uniform distribution if these happen to differ: the stationary distribution is what you get in the limit if you scramble with random moves forever. Why should the scramble distribution be uniform if doing random moves doesn't tend to a uniform distribution?

(Counterintuitively, even what's considered a basic move will change the distribution. For example, with 15 puzzle, (independent) random multi-tile moves lead to the uniform distribution over the 16!/2 scrambles, but random single-tile moves don't! The latter distribution biases the free space towards being one of the middle four cells (1/12 each) and against being one of the four corner cells (1/24 each).)

Wuuuutttt???????

 

[kubesolver]

Why should the scramble distribution be uniform if doing random moves doesn't tend to a uniform distribution?

I think that's a very good question probably worth a discussion.

Depending on what are the actual goals of competitive speedcubing the best distribution might be either:
- uniform
- stationary (I learned this term from you here)
- difficult (so always starting from theoretically most difficult position)

I see good arguments for all of them. Given that speedcuging doesn't come from any real-life activity and is not meant to be a test of any real-life ability it's probably hard to come up with an objective argument for any of them.

 

[aoaaceai]

I would suggest using WCA's library for scrambling if you are using Java.
click here for the library

 

[kubesolver]

I would suggest using WCA's library for scrambling if you are using Java.
click here for the library

I suggest using the right tool from the job and stay clean of this library in android app.

The WCA scrambles is a great tool for generating tournament scrambles, but not so good for a timer app mostly because it's relatively slow and computationaly intensive.
For the phone app you want something like https://github.com/cs0x7f/min2phase which is fast and lightweight.