Non-explicit random state scrambles

[kubesolver]

I was thinking about ways to improve performance of random scramble generation for higher order puzzle.

I have noticed that on 3x3 you can get a random state by generating random state (from uniform distribution) of corners and separately random state of edges, solving them separately and applying both sequences. The final state will have neither corners nor edges from the generated states but will come from a uniform distribution.

Searching through the forums I found that the average number of moves for such a scramble would be 9+12 so on par with fast two phase solvers.

Now this approach could be used to generate random state scramble for 4x4x4 or 5x5x5 by concatenation of solutions to random state of each separate type of cubie to get random state scramble using very little computational power.

E.g. on 5x5x5 there are 5 type of pieces. If they can be randomly independently scrambled in 10 moves on average we would end up with 50 moves random state scrambles which feels like an improvement over current official scrambling.


Before I dwell in the math - is anyone aware if this approach has already been used/ considered/ evaluated?
@xyzzy

 

[xyzzy]

(@Lucas Garron might also have some input here.)

There are important caveats to the "scramble individual piece types" method. We'll focus on 3×3×3 first.

Method A:
1. generate random state C, find an optimal corner solution S_C (~9 moves)
2. generate random state E, find an optimal edge solution S_E (~12 moves)
3. return invert(S_C) + invert(S_E)

Method B:
1. generate corner-only random state C, find an optimal solution S_C (~17 moves)
2. generate edge-only random state E, find an optimal solution S_E (~17 moves)
3. return invert(S_C) + invert(S_E) + (an extra U move if random()<0.5)
(The random quarter turn is needed so that both even-parity and odd-parity scrambles are possible.)

With both of these methods, the resulting distributions of the corner pieces alone, or of the edge pieces alone, are uniform, as desired. (Let X and Y be independent random variables taking on values within a finite group. Then if X is uniformly distributed, so are XY and YX. It doesn't matter whether Y is uniform.)

However, while method B also has the joint distribution being uniform, method A does not. It's (very slightly) biased towards states where the same moves can be used to solve the corners and edges. (For simplicity, assume the optimal solution is deterministically chosen. There may be multiple optimal solutions and a nondeterministic solver (e.g. with multithreaded search) might not always pick the same one; adjusting the argument to account for this is left as an exercise for the reader.)

There are \( 3^7\times8! \) possible choices of S_C and \( 2^{11}\times12! \) possible choices of S_E. The product of these is twice the number of legal cube states, because you can biject the product to the set of cube states where the corners and edges are individually legal; this set includes the truly legal states, but also unsolvable states where the corner parity and edge parity are different (a la PLL parity). Consequently, method A produces a uniform distribution of resulting scrambles if and only if every legal cube state can be decomposed as invert(S_C)+invert(S_E) in exactly two ways.

If C is any one-move state (18 choices), and E is the inverse of C, then S_C must be one move long (said move will differ between all 18 choices), and S_C and S_E will be inverses of each other, so invert(S_C)+invert(S_E) is a no-op. This means that there are at least 18 ways to decompose the solved state in the form S_C+S_E. Therefore method A cannot produce a uniform distribution.

In practice, the bias doesn't seem to be noticeable, although I haven't studied this in depth so take it with a grain of salt.

Method B can, theoretically, be used to generate uniform random-state scrambles, but at ~34 moves long, you might as well just use the Kociemba algorithm instead.

---

As I understand it, the old pyraminx scramble generators did do something like method B above, although it later switched to a standard IDA* solver for the full puzzle. (Lucas probably knows more about it.)

---

For 4×4×4 I think Chen Shuang's solver works reasonably well already.

For 5×5×5 I once proposed a scrambling method that guarantees uniform marginal distributions on the midges and corners: do a 3×3×3 random-state scramble with wide moves, then 40-ish random moves afterwards. This method also results in the x-centre and t-centre marginal distributions being closer to uniform compared to normal random-move, although (iirc) there is more bias towards t-midge and x-wing pairs in the scramble compared to normal random-move.

random state of each separate type of cubie

This isn't very straightforward for big cubes because of how large the state spaces are. For the centre pieces, there are \( 24!/4!^6\approx3\times10^{15} \) states (per orbit). Fast optimal solving is not feasible, so you have to do it in two (or more) phases. For wings, there are \( 24!\approx6\times10^{23} \) states (per orbit), which would realistically need three (or more) phases.

 

[kubesolver]

You're right and have a good point. The combination is not uniform distribution. That's a bit unfortunate.

Regarding the approach to bigger cubes.
The approach could still work in delivering good short scrambles in no time.

For the steps which can't be easily solved online we could mine and whitelist e.g. few thousand wing scrambling sequences and use randomly one of them.