# Positions vs Possible Scrambles



## whatshisbucket (Jan 19, 2018)

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?


----------



## Douf (Jan 19, 2018)

I'm very curious to see what someone who is half decent at math will say about your question!


----------



## AlphaSheep (Jan 19, 2018)

whatshisbucket said:


> I know (or at least am pretty sure) for these puzzles the scrambles are random state:
> 3x3
> 2x2
> Pyraminx
> ...


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 (Jan 19, 2018)

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 (Jan 19, 2018)

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.


----------



## Dancing Jules (Jan 19, 2018)

whatshisbucket said:


> And that due to the fact that the current scramble generators for megaminx have only 2 options for each move


There's also the U/U' at the end of a line.


----------



## AlphaSheep (Jan 19, 2018)

Dancing Jules said:


> There's also the U/U' at the end of a line.


Not many people notice this, but only the D++/D-- and R++/R-- are random. The direction of the U/U' is always in the same direction as the D++/D-- before it.


----------



## jaap (Jan 20, 2018)

xyzzy said:


> 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 (Mar 9, 2018)

jaap said:


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


----------



## Thom S. (Mar 9, 2018)

xyzzy said:


> 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 (Mar 9, 2018)

Thom S. said:


> 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 (Mar 9, 2018)

SciTech said:


> 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 (Mar 14, 2018)

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


----------



## casi (Apr 13, 2018)

Will the generators generate really easy scrambles?


----------



## xyzzy (Apr 13, 2018)

casi said:


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


----------

