• 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 40,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!

Positions vs Possible Scrambles

Joined
Oct 17, 2017
Messages
194
Location
Here
WCA
2018OLSE04
Due to the impossibility with current computational power of having random state scrambles for many puzzles, and the inconvenience of having scrambles long enough to produce a good random state, some puzzles use scramble generators that couldn't possibly generate every position of the puzzle. I noticed this when I picked up Megaminx recently, and I am curious how the different scramble generators compare in the portion of possible positions can actually be generated as scrambles.
I know (or at least am pretty sure) for these puzzles the scrambles are random state:
3x3
2x2
Pyraminx
Skewb
Square-1
Clock?

And that due to the fact that the current scramble generators for megaminx have only 2 options for each move, there are at most 2^70=1.18*10^21 possible scrambles out of the 1.01*10^68 possible positions (this is an astonishingly tiny fraction of the possible positions).

But since I don't do larger NxN puzzles, I don't know how those scramble generators work. Could anyone shed some light on the number of possible scrambles that they can generate?
 
Last edited:

AlphaSheep

Member
Joined
Nov 11, 2014
Messages
1,083
Location
Gauteng, South Africa
WCA
2014GRAY03
I know (or at least am pretty sure) for these puzzles the scrambles are random state:
3x3
2x2
Pyraminx
Skewb
Square-1
Clock?
Can confirm that WCA competitions do indeed use random state state scrambles for clock, and also for 4x4.

Megaminx scrambles don't produce all possible states, but it can be shown that there's no meaningful bias in the states it does produce, so from a fairness perspective, it doesn't matter.

We don't know God's number for 5x5 and larger, but we do have lower bounds. These are where the number of states that can be reached in a number of moves exceeds the number of possible states for that cube. These lower bounds are 49 moves for 5x5, 72 moves for 6x6 and 95 moves for 7x7, but the actual God's numbers for these puzzles are likely several moves higher than these numbers. What that means is that, for all we know, scrambles for the cubes may be able to reach all possible states, but we don't actually know because solving these puzzles optimally would take far too long. What we can say is that it's quite probable that we are able to reach at least the vast majority of possible states on these puzzles with current scramble lengths, but we can't be certain of that either.
 

Mike Hughey

Administrator
Staff member
Joined
Jun 7, 2007
Messages
11,304
Location
Indianapolis
WCA
2007HUGH01
SS Competition Results
YouTube
Visit Channel
It should be mentioned here that, when Stefan Pochmann suggested the new megaminx scramble approach a number of years ago, he went through a very detailed analysis of the possibilities to verify the things AlphaSheep mentions above. He pointed out what a large percentage of the possible states were not reachable, and then demonstrated the lack of bias. So all of this was carefully considered before this scramble format was adopted.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
We actually can have random-state scrambles for larger big cubes (all you need is some code to solve a cube, and that code exists), but the problem then becomes one of move count: 5×5×5 might need ~80 moves (still reasonable), 6×6×6 ~150 moves (nope), 7×7×7 ~300 moves (nope).

Keep in mind that longer scramble sequences also implies a higher chance of misscrambling; if misscrambling is going to happen anyway, you're not getting a "perfect" random-state scramble out of this and so you might as well stick to random moves. (Unless scrambling robots become a thing… Probably not practical+cheap, though.)

Also, re: number of possible megaminx scrambles being much fewer than the state space, see this post by Lucas Garron.
 

jaap

Member
Joined
Sep 22, 2009
Messages
32
Location
Netherlands
WCA
2003SCHE01
YouTube
Visit Channel
We actually can have random-state scrambles for larger big cubes

There is another problem that is rarely mentioned, and which can happen even with random-state scramblers for the 4x4x4, namely the quality of the Random Number Generator. Many browsers for example use the xorshift128+ generator in their javascript, and as the name implies, it uses 128 bits of internal state. This means that no more than 2^128 possible different outcomes are possible, or about 3e38. So fewer than one out of 22 million possible 4x4x4 states could ever be generated (with a javascript scrambler using the default RNG). RNGs that use only 64 or 32 bits of state are of course very much worse in this respect.

So not only is the practical length of a scramble a limiting factor in the fraction of puzzle states that can be output by a scrambler, the choice of RNG is too. I really don't think this is a problem however, as this subset of puzzle states that the scrambler is limited to is unlikely to exhibit any usable bias to the human solver. (See Lucas Garron's post that was linked to before)
 

SciTech

Member
Joined
Oct 21, 2017
Messages
7
There is another problem that is rarely mentioned, and which can happen even with random-state scramblers for the 4x4x4, namely the quality of the Random Number Generator. Many browsers for example use the xorshift128+ generator in their javascript, and as the name implies, it uses 128 bits of internal state. This means that no more than 2^128 possible different outcomes are possible, or about 3e38. So fewer than one out of 22 million possible 4x4x4 states could ever be generated (with a javascript scrambler using the default RNG). RNGs that use only 64 or 32 bits of state are of course very much worse in this respect.

This would apply if you used only one random number, but why would you do that? For example, take a random permutation of a pack of cards, with 52! possibilities. It's easy to generate a sequence such that every ordering has an equal probability, despite the huge size of 52!, because multiple random numbers are used to produce the random permutation. Same with cubes: generating the permutations (and orientations and bit switch for parity...) of each exchangeable set of cubies I can't see that there would be any issue for any sized cube, even for generators of small period.

Edit:
Actually, I now disagree with my comment above. Using xorshift128+ with a fixed seed, multiple random numbers will not help, so I now see the problem.
 
Last edited by a moderator:

Thom S.

Member
Joined
Sep 26, 2017
Messages
1,292
We actually can have random-state scrambles for larger big cubes (all you need is some code to solve a cube, and that code exists)

I'm interested in that code because all 4x4 solvers I know of have large problems with center prunning and speed
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
I'm interested in that code because all 4x4 solvers I know of have large problems with center prunning and speed
For 444? Chen Shuang's solver is pretty fast and it's used in TNoodle and csTimer (among others).

For 555 I'm pretty sure my solver is the best one that exists so far (~85 moves OBTM; can get as low as 75 OBTM if you let it run for hours), but it does, like you'd expect, have problems with pruning and speed. For 666 and up, I believe @dwalton76's solver has the lowest move count and is reasonably fast, but the move counts are still way too high to be used for generating useful random-state scramble sequences.
 

SciTech

Member
Joined
Oct 21, 2017
Messages
7
Actually, I now disagree with my comment above. Using xorshift128+ with a fixed seed, multiple random numbers will not help, so I now see the problem.

Now I've looked into this I was definitely wrong. Probably the most informative discussion is the subsection on Psuedorandom generators in the wikipedia entry for the Fisher-Yates Shuffle.
 

dwalton76

Member
Joined
Jan 2, 2017
Messages
71
YouTube
Visit Channel
Current averages for my solver:
  • 3x3x3 average solution is 20 moves
  • 4x4x4 average solution is 59 moves
  • 5x5x5 average solution is 105 moves
  • 6x6x6 average solution is 192 moves
  • 7x7x7 average solution is 270 moves
  • 8x8x8 average solution is 408 moves
  • 9x9x9 average solution is 556 moves
  • 10x10x10 average solution is 768 moves
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
Will the generators generate really easy scrambles?
Define "really easy" first, and then the question should answer itself.

Hint: most scramble generators don't do any filtering, except possibly to match the WCA limits (2 moves for most puzzles, 4 moves for 222, etc.).
 
Top