What are the limitations to making a random state 5x5/Mega scrambler?

[OtaMota]

Do you think it could be possible in the near future to make one?

 

[fes_77]

whats even the difference between random state and random move?

 

[An Animating Cuber]

whats even the difference between random state and random move?

Random state is making sure the actual state of the puzzle you receive is randomized, random move is just a sequence of randomized moves, for bigger puzzles there is pretty much no distinction.

 

[DGCubes]

Technically all you need to make a random state scrambler is to have a way to solve the puzzle - then the scrambling program can generate a random state, solve that state, and invert the solution to give you a random state scramble. I'm sure 5x5 solving programs exist and aren't that hard to make (e.g. use commutators to solve the whole thing) but the same goes for 6x6, 7x7, 8x8, or as high up as you want to go. The problem is that these solving programs aren't move-efficient; nobody wants to do hundreds or thousands of moves for every scramble, so we opt for random move scrambles instead.

We still don't know God's number for any NxN bigger than 3x3, so I'm not sure how efficient a 5x5 solving program could get, and whether that movecount is low enough to implement without making everyone upset that they have to do longer scrambles. I'm sure someone more familiar with the state of the art can chime in here!

 

[Hazel]

Technically all you need to make a random state scrambler is to have a way to solve the puzzle - then the scrambling program can generate a random state, solve that state, and invert the solution to give you a random state scramble. I'm sure 5x5 solving programs exist and aren't that hard to make (e.g. use commutators to solve the whole thing) but the same goes for 6x6, 7x7, 8x8, or as high up as you want to go. The problem is that these solving programs aren't move-efficient; nobody wants to do hundreds or thousands of moves for every scramble, so we opt for random move scrambles instead.

We still don't know God's number for any NxN bigger than 3x3, so I'm not sure how efficient a 5x5 solving program could get, and whether that movecount is low enough to implement without making everyone upset that they have to do longer scrambles. I'm sure someone more familiar with the state of the art can chime in here!

The upper bound for 5x5 God's Number is known to be 130 (see this thread), though the actual number is expected to be decently less than that, somewhere in the vicinity of 75. We're still a long way's off of finding that true number, though, as there haven't been any developments since 2018.

 

[Mike Hughey]

Actually I believe the programs that exist can get to pretty optimal scrambles, but the current computation speeds are such that it takes forever to generate a solution of a reasonable number of moves. Already the WCA 4x4x4 random state scramble generator takes quite a while; extending to larger puzzles means exorbitantly long scramble generation times.

 

[xyzzy]

for bigger puzzles there is pretty much no distinction.

This is probably not true.

On big puzzles, there's what I call the "small subgroup problem". You could end up having a scramble sequence that never uses some of the moves (e.g. a 5×5×5 scramble seq that is all wide moves or all outer-layer moves), causing the puzzle permutations to lie in a small subgroup, and the probability of this happening with our current naïve random-move scramblers is way too high compared to proper random-state scramblers. (See e.g. this calculation I did on the probability of 3-movers on big cubes.)

Even if the scramble sequence isn't purely with the restricted generators, it could still sometimes have very few of the other generators, leading to poor mixing. This is noticeable on e.g. 40-random-move 4×4×4 scrambles (default in qqTimer), which have a lot more free centre bars. It's very rare for a scramble sequence to never have Uw or Uw', but much less rare for the scramble sequence to have only 1 or 2 of them.

(Tom Rokicki had already noticed that this also significantly affects 3×3×3 if you consider the DR subgroup ⟨U, D, L2, R2, F2, B2⟩, although at the time that didn't have much relevance to human solving methods. It is relevant for FMC now, though, for obvious reasons.)

Granted, the small subgroup problem is probably not a big deal in practice. You need all the stars to line up right, and it's basically converting extremely rare situations to "merely" very rare situations.

I have a half-assed proposal for a new 5×5×5 scramble format that avoids the small subgroup problem that naïve random-move has, while also mixing up the centres better, though I don't know if it suffers from its own type of small subgroup problem.

However, when it comes to megaminx scrambles, the R++ D++ scramble format that is currently used by the WCA does have noticeable statistical flaws: it's a lot more likely for an edge to be solved than to be flipped, and there are around 32% too many free corner-edge pairs on average. (Incidentally, with the standard colour scheme, the white-yellow (U-BL) and white-green (U-F) edges are the ones most likely to be solved.) I've been working on a replacement for this, which I expect will make me a pariah among megaminxers because nobody wants to hear the inconvenient truth and switch to a "worse" scramble format that mixes much better.

(please contact me if you're interested in the details; I'll release it to the public eventually, but not yet)

The upper bound for 5x5 God's Number is known to be 130 (see this thread), though the actual number is expected to be decently less than that, somewhere in the vicinity of 75. We're still a long way's off of finding that true number, though, as there haven't been any developments since 2018.

The upper bound is extremely pessimistic. It's basically adding up all the worst possible cases together, some of which are very rare. (And most of them are avoidable by choosing different solutions in previous steps.)

Practically, reduction can be done in around 50-60 moves on average, so a full solve would take 70-80 moves.

 

[Christopher Mowla]

If by "random state", you might have possibly meant to have nxnxn scramblers which create a center scramble (for cage, BLD), like this, or an edge scramble like this (for reduction), to save us time with practicing a certain big cube sub-step, here are instructions on how conjugates can be used. (The scrambles can be as long/short as you want with virtually no extra generation time than regular (full) scrambles.)

(Obviously the exact same idea should be able to be applied to the nxnxn minx.)

(See e.g. this calculation I did on the probability of 2-movers on big cubes.)

As I explained in this post, you can use Herbert Kociemba's generating function to quickly get the 100764 3 move scrambles/algs for the 7x7x7. (Or just as easily, the number of m move scrambles for the nxnxn. This is in OBTM, but of course, that's the move metric that WCA scrambles are counted in anyway.)

 

[finger go brr]

if there was a random state megaminx scramble, the notation would probably have to have symbols for each face being turned, which would be super prone to misscrambles.

5x5 would probably need 80-100 moves to solve semi-optimally, which would also prone to misscrambles. when was the last time you did every move in a 7x7 scramble perfectly?

 

[xyzzy]

As I explained in this post, you can use Herbert Kociemba's generating function to quickly get the 100764 3 move scrambles/algs for the 7x7x7.

You're right! Some of the numbers in my older post are wrong because I forgot to account for commuting moves. The orders of magnitude involved are still roughly the same, though, so the qualitative result (that small subgroups have greatly boosted probability) isn't affected. (I'll get around to fixing it eventually. There's another handwave approximation with a similar(?) amount of error as well, which shouldn't be too hard to fix.)

Edit: wait, no, turns out I had already fixed this particular mistake.

when was the last time you did every move in a 7x7 scramble perfectly?

Yesterday, when I did the forum weekly comp. I'm pretty sure my scramble accuracy is ~90% for 80-move 6×6×6 scrambles and >80% for 100-move 7×7×7 scrambles.

It's even easier to scramble 5 correctly than 6/7 (for the same number of moves) since there's much less risk of accidentally turning the wrong number of layers. I've done small sessions with random-state scrambles before; the only hard part is that you need a not-terrible computer to generate the scrambles at all (as well as being able to figure out the software, I guess – I wrote my own code for this, so I knew how to use it, but I can't say the same for anyone else or even for myself now, many years since I last used the code for anything). It's otherwise not substantially easier/harder to accurately execute the scramble sequences compared to normal random-move scrambles.