• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Random Scramble Generation

Cheese11

Member
Joined
Jul 18, 2011
Messages
1,060
Location
Winnipeg, Manitoba, Canada
WCA
2011KULC01
YouTube
Visit Channel
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?
 

Cubetastic5

Member
Joined
May 5, 2016
Messages
47
Location
India
YouTube
Visit Channel
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

Member
Joined
Feb 14, 2014
Messages
1,710
Location
Over there
WCA
2013GOOD01
YouTube
Visit Channel
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

Member
Joined
Jul 18, 2011
Messages
1,060
Location
Winnipeg, Manitoba, Canada
WCA
2011KULC01
YouTube
Visit Channel
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 :p
 
Last edited by a moderator:
Joined
May 27, 2015
Messages
64
WCA
2012BRAS01
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

Member
Joined
May 5, 2016
Messages
47
Location
India
YouTube
Visit Channel
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 :p
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

Member
Joined
Dec 24, 2015
Messages
1,896
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

Member
Joined
May 22, 2020
Messages
27
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

Member
Joined
Oct 27, 2019
Messages
4,044
Location
An uncolonized sector of the planet Mars
WCA
2020MAHO01
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

Member
Joined
May 22, 2020
Messages
27
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

Member
Joined
Jan 28, 2020
Messages
319
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

Member
Joined
Oct 27, 2019
Messages
4,044
Location
An uncolonized sector of the planet Mars
WCA
2020MAHO01
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

Premium Member
Joined
Nov 15, 2019
Messages
187
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

Member
Joined
Dec 24, 2015
Messages
1,896
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

Member
Joined
Jan 28, 2020
Messages
319
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

Premium Member
Joined
Nov 15, 2019
Messages
187
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.
 

kubesolver

Premium Member
Joined
Nov 15, 2019
Messages
187
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.
 
Top