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

Multi-stage random scrambling(4x4x4, etc.)

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Okay, this just hit me:

I have a great idea for WCA scramblers. though I'm not sure how effective an implementation will be.
Unlike what has been assumed, we do not seek to generate a random state and then solve it. That's just a convenient way to do it for 3x3x3.
However, we are actually only interested in generating a random state.

The key:
We can randomize different factors of the scramble separately: Orbits, orientations, etc.

The other important thing:
In scrambling such a factor, all other factors may be disregard.


I'm using "factor" to stand for any aspect of a puzzle that in a sense contributes a number to the total number of of factors in the number of states. That's mostly permutations and orientations, but you can, for example, split permutation into even permutation + parity.

This is big.

Consider 3x3x3: We can scramble orientation randomly, and then permutation. This will give us a random state.
We can scramble orientation randomly, ignoring permutation, then scramble permutation randomly, and still get a random state.
Even better! We can scramble orientation randomly, ignoring permutation, then scramble permutation randomly, ignoring orientation and STILL get a random state.

This is easy to prove
You can take this simple proof: Noise+anything=noise (assuming that the "anything" is not constructed to cancel the noise).
I believe Huffman proved that no information can be communicated in binary over a channel that switches each bit with 50% chance (noise). Here, the noise cancels order/non-order/anything as likely as not, so you can't even prevent the noise (unless you know exactly what the noise is going to be, in which case it's not noise)
If you record noise, and combine it with silence, you get noise.
If you record noise, and combine it with order, you get noise.
If you record noise, and combine it with noise, you get noise.
Note: This is complete noise, not something like background noise that weak and possibly non-random.

Mathematically:
Consider the permutation of an orbit. If you randomly permute (apply a random element of the set of possible permutations, with equal weight to each) it with an algorithm, it is in a random state.
Now let's say you added some moves before. The cube sill still in a random state at the end. Whatever the previous moves were, they placed it in a certain arbitrary state, but the random permutation now randomly placed it into one of the possible states.
It is an an elementary result of number theory that if you compose an arbitrary permutation R with any permutation P to get Q, any different values of P will give you a different value of Q. Thus, if R is a random permutation, Q is a random element of of the set of potential permutations (all of them, in fact). Applying P is an isomorphism on that set, so you still get Q as random element of that same set!
Even better! It does not matter if P is done before or after Q, or if there are multiple such permutations P(i) that get thrown onto both sides of Q. They can even be random each, as long as their randomness is independent of Q (i.e. not made to cancel the specific random element Q).
If you wanna go really formal, ask qqwref and Stefan.

I'm sure people will try to argue against this. Let's try:
Suppose that you scramble edges while ignoring corners. Suppose also that all the algs use to do this happen either to leave corners unaffected, or, say, switch each corner with its opposite (you can substitute a lot of things, like "misorient all corners"). Doesn't this weird distribution bias the final scramble?
It does not, I assure you. Try this on a deck of cards. If you change the order in some way and the shuffle, it'll be randomly ordered. Now let's say that after shuffling, you do something, anything that could easily have been chosen independent of the shuffle (and perhaps determined before the shuffle), like cutting the deck after the 8th card. The deck will still be in a random order.
(Note: It will not be in a random order if you, say, cut after the first jack, or move the final ace to the top. But all we have to avoid is something biased like that.)





So, the procedure for a multi-stage random-state scrambler is simple: Apply a set of algorithms, each of which randomizes a factor, until all factors have been accounted for.

The different factors can be any groups in any order, and with all the choices, there should be some best (shortest-output) ones.
The process is analogous to a solver, but more generous at each step, so I hope that it will allow us to get significantly short scrambles. I know of (and have used) an optimal 4x4x4 solver for 77 STM, and current WCA scrambles are 40 outer-block-turn moves. If this turns out to give quick scrambles under 50 twists, this may be worth pursuing for improvement.
If the output has a large standard deviation, we might also be able to generate a few too many, and pick the few shortest ones (though this probably messes with randomness, so I will not recommend it unless someone has a good reason to show that this is negligible).

As an example, for 4x4x4 the simplest scheme might be: x-centers, wings, then corners
5x5x5 might be: p-centers, x-centers, midges, wings, corners.
Pyraminx: Edges, centers (trivial), tips (trivial)
...

You can easily condense these, and the order can be switched: 5x5x5 could also be: centers, midges+corners (i.e. 3x3x3, which may even be done with double-layer turns), wings.
It might also be worth trying to reduce steps, or use a flexible program, if output is promisingly short and fast.
Also note that if you do edges, corners, and x-centers (I'll just include them, in case of supercubes) separately, you may introduce parity to one, any, or all of them.

IMPORTANT NOTE:
Centers are indistinguishable on big cubes. However, having one orbit of centers randomly arranged before permuting it -as if each side were originally a solid color- is inappropriate. By the design of this system, we don't know which centers to treat the same, so we have to randomly permute all 24 pieces, not 6 sets of 4.
This is best resolved by scrambling centers first. The first set of centers will not have this problem. We can also design our algs not to scramble certain other orbits of centers, which may then treated as 6 sets of 4. Experimentation will show the shortest schemes for each cube, if there is a significant difference.

Also, note that on cubes we cannot automatically turns slice turns into block turns, or else we could turn outer turns as multi-layer by the same token, and would thus be able to fairly scramble a 5x5x5 with double-layer turns, which is simply absurd. I have a feeling that making only slice turns into block turns might have a negligible effect on the fairness (I've said "negligible" before - with this I mean allowing the distribution of scrambles to skew microscopically in exchange for much easier, faster scrambling), but I don't have any good reason at all.
I propose and suggest that any work on this should be in outer-block half-turn metric, representing the way most cubes are scramblable (hey, this word is not in the dictionary!). It doesn't matter if some people's cubes can do slice turns, block turns are safer and easier. It also continues the current style of scrambling, and allows us to compare scrambling time easily by comparing the number of moves.


So, this is my idea. I hope that some programmers and mathematicians pick this up (I also want to see what kind of bounds we get on this), and really hope that this turns out useful and practical enough for the WCA to use and/or consider for future puzzles.

It might not turn out so necessary or useful, but we won't see until we try. I think 4x4x4 may be worth it, but if we don't save any moves we'd have to investigate the distributions of the current scrambler to see if it's worth it.

I've posted this here and not on the WCA forum because it's an idea and will require at least a few months of research/development, and I think this would be the best place to discuss it and reach appropriate, interested cubers (I might also post something about this on the Yahoo group). In particular, I'd like to hear Stefan's ad Chris H's ideas and comments on this.

-Lucas Garron

EDIT: Please don't reply to this with a short, useless comment (whether positive or negative). This is a very serious idea, and a clogged thread would not help at all.
 
Last edited:

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
Could you please explain how you think this would lead to more random AND shorter scrambles?

I always thought that a perfect scrambler should be able to generate every position of the puzzle (including the solved state and the one(s) that would require the maximum amount of moves). That means a scrambler needs to perform at least the amount of moves that god's algorithm would require.

By splitting the scrambler into several factor/phase scramblers the amount of moves a perfect scrambler would need becomes larger (or at least equal). If you look at Kociemba's 2-phase solver (which I am pretty sure you have) you can see that it would require 18+12 moves to be able to reach all states (noise+order, order+noise). By combining the 2 stages much shorter solves (and thus scrambles) are reached.

I understand this topic is about scramblers (not solvers) and big cubes (not 3x3x3), but I think my points are equally valid. I don't think a 4x4x4 3-factor scramble of 40 moves would be better than the current random 40 moves scrambles.

P.S. without any prove I would like to say that I think these are the formula's for god's algorithm:
odd cubes: (n-1)*10 (1x1x1 becomes 0, 3x3x3 becomes 20, 5x5x5 becomes 40, etc)
even cubes: (n-1)*10 +1 (so 2x2x2 becomes 11, 4x4x4 becomes 31, 6x6x6 becomes 51, etc)
 

Johannes91

Member
Joined
Mar 28, 2006
Messages
1,341
By splitting the scrambler into several factor/phase scramblers the amount of moves a perfect scrambler would need becomes larger (or at least equal).
Yes, but the solving times should go down a lot. Solving 3x3x3 optimally is already quite a challenge, puzzles significantly more complex than it are just out of reach (for now, at least).

If you look at Kociemba's 2-phase solver (which I am pretty sure you have) you can see that it would require 18+12 moves to be able to reach all states
That's just the worst case, and unless the implementation is very dumb (which is certainly not the case in Cube Explorer), in real life the move count is a lot lower. The 2-phase algorithm will actually find optimal solutions if you wait for long enough (unless some optimizations have been made that break this).

But I don't see what Kociemba's algorithm has to do with this topic.

I don't think a 4x4x4 3-factor scramble of 40 moves would be better than the current random 40 moves scrambles.
So even if it was possible to get to a random position in 40 moves, you think it wouldn't be any better than using 40 random moves?! Doesn't make any sense to me. Using a random position is the better way, only potential problem is that it might require more moves than what currently is used (personally, tough, I think that fair scrambling is more important than saving a minute or two). But the scrambles certainly would be better.

P.S. without any prove I would like to say that I think these are the formula's for god's algorithm:
odd cubes: (n-1)*10 (1x1x1 becomes 0, 3x3x3 becomes 20, 5x5x5 becomes 40, etc)
even cubes: (n-1)*10 +1 (so 2x2x2 becomes 11, 4x4x4 becomes 31, 6x6x6 becomes 51, etc)
Without any proof I would like to say that those grow waaaay too slowly. The number for 4x4x4 sounds too low already (IMHO), and it gets just more absurd for larger n.
 
Last edited:

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
Maybe I got confused by this sentence
I think 4x4x4 may be worth it, but if we don't save any moves we'd have to investigate the distributions of the current scrambler to see if it's worth it.
. I thought the purpose of this topic was to come up with a way of scrambling that:

1) requires less moves compared to what we do right now
2) gives distributions for factors/phases that are according to their mathematic probability
2b) allows for all possible positions to occur (implied by 2))
3) accomplishes the above by breaking up the scramble into several sub-scrambles

2b) implies that all scrambles should be >= gods algorithm for the entire puzzle
3) implies that all sub-scrambles should be >= gods algorithm

The 2-phase algorithm I gave was to prove that using sub-scrambles requires a lot more moves than gods algorithm (Lucas allows for noise, but not for a structured optimization approach like Cube Explorer uses)
(also, the 2-phase algorithm will no longer find all optimal solutions
In the current implementation the Two-Phase-Algorithm does not look for some solutions that are optimal overall, those that must cross into and back out of phase 2. This increases the speed considerably. Use the Optimal Solver, if you want to prove some maneuver to be optimal.
)

About the 4x4x4 example: I can prove that the current approaches for sub-scrambles would require > 40 moves (about 65/70 in 5/6 steps if I remember correctly). If 65 in 5 steps is possible, 40 in 1 step seems extremely likely to me (actually 31 also seems extremely likely to me). This is why I think 40 random moves will give a better scramble than 40 sub-scramble moves.

I agree that it would be best to have a randomly generated cube-position and generate an optimal scramble for it. However I don't think this will be possible for a long time. I think a scramble of 40 random moves is good enough. Fair scrambling to me means everybody gets the same scrambles. Most competitions have 2 scramblers, 4 (or more) timers and competitors that take about 3 minutes to solve a 4x4x4 (on average, including inspection, writing down times and other overhead). That means that a scrambler needs to scramble at least 1 cube every 1:30 or else the competitors have to wait. Using an extra minute or two just isn't a realistic option. There is a reason megaminx is only mean of 3 and that there are cut-off times for some puzzles.

Finally, about my formula for god's algorithm:
If you look at the amount of possibilities that a 4x4x4 has compared to 3x3x3 you might think it would require a lot more moves to solve it optimally.
But if you look at the amount of possible moves on a 4x4x4 compared to a 3x3x3 you might think differently.

Hopefully someone can make a list like this:
Dimension of cube, nr of unique positions, minimum number of moves needed before all unique positions could be reached
 
Joined
Apr 29, 2006
Messages
1,802
Hopefully someone can make a list like this:
Dimension of cube, nr of unique positions, minimum number of moves needed before all unique positions could be reached

That last one sounds kind of familiar... ;)
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
I thought the purpose of this topic was to come up with a way of scrambling that:

1) requires less moves compared to what we do right now
2) gives distributions for factors/phases that are according to their mathematic probability
2b) allows for all possible positions to occur (implied by 2))
3) accomplishes the above by breaking up the scramble into several sub-scrambles
2, 2b, and 3 are true.
1 is partially true. The hope is to reduce scrambling time. ;)
However, if the result is a program with output of comparable length (since it will vary, this means a mean not much higher than the alternate standard).

2b) implies that all scrambles should be >= gods algorithm for the entire puzzle
3) implies that all sub-scrambles should be >= gods algorithm
2b) is FALSE. ;)
3) Yes, but the sub-scrambles will likely be so small that they're practically optimal.

Remember that we are using a random position to generate a random scramble, not that random position.

Consider 3x3x3 as an example: M2UM2U2M2UM2E (H-perm+E)
Optimal solutions to this (HTM, as for scrambling) are 10 moves, like "R2 F2 B2 L2 D' R2 F2 B2 L2 D (10f*)"
Now let's generate a 2-stage scramble "solution" it by solving corners and edges:
Corners: U' D
Edges: U D

My first example was for corners:
F + U R2 F U2 R' F2 (CO+CP) vs. U R' F R U' F2 R U' R' U (I will call this CA, to mean "corners: all" and signify that the corners are getting fully scrambled/permuted[&oriented] in their orbit.)

The stage-based scramble can be significantly shorter, and the first one even move-cancels down to one move (move-cancellations produced by shuffling around stages is fine -if you're careful about centers). These are contrived examples, but a good demonstration that the multi-stage scrambler can work off components of a random state and come up with a sub-optimal length random scramble (compared to the length of the solution length of that state).
(I think that that usage of "sub-optimal" qualifies qualifies some sort of award, it's that funny. :p )

I have tried several scrambles in CE, splitting into EA and CA, as well as EP, EO, CP, CO.
My first attempt was "D2 L' F' R2 U D2 B L2 (8f*) R2 L2 U B (4f*) U R B2 L' U (5f*) F U F' R' F (5f*)" (22 total).
I hit some 19-movers where the 2-phase solver slowed at 19, but couldn't find an example where I beat the optimal solution. Too bad you can't auto-run incomplete input.
I think this is a good sign. ;)
You could actually brute-force each step with relatively simple program, and I

Note that on average, indeed, stages must take no less moves than the average optimal length (which is slightly under the value for God's number, note). I don't think that we'll quite reach God's number for 4x4x4, but this is some good evidence to me that it could be close.
What are the best estimates for God's number and the average optimal solve length for 4x4x4?
(Let's say we generate some multi-stage scrambles for 4x4x4 by any means.
Will that give us an empirical upper bound (estimate) on the mean optimal solution length, with some confidence interval? We are getting sup-optimal solutions to random positions, but not technically solving randomly generated positions. Something is fishy, but I can't tell what.)

We, of course, can't choose the stages (like EO+EP+CO+CP vs. EA+CA) based on the random factor-states generated (though it's not technically bad to use different stages for different scrambles, which would nevertheless be useless), nor pick out only short scrambles (which will to some extent have less entropy and not be random).


The 2-phase algorithm I gave was to prove that using sub-scrambles requires a lot more moves than gods algorithm (Lucas allows for noise, but not for a structured optimization approach like Cube Explorer uses)
(also, the 2-phase algorithm will no longer find all optimal solutions
No, I just showed that to be false.
Also, the noise is the scrambling.

In the current implementation the Two-Phase-Algorithm does not look for some solutions that are optimal overall, those that must cross into and back out of phase 2. This increases the speed considerably. Use the Optimal Solver, if you want to prove some maneuver to be optimal.
I am doing sub-steps optimal right now.

I'll mention something cool below, an idea so dun it just might work.

About the 4x4x4 example: I can prove that the current approaches for sub-scrambles would require > 40 moves (about 65/70 in 5/6 steps if I remember correctly).
Are you sure, considering what I've mentioned?

This is why I think 40 random moves will give a better scramble than 40 sub-scramble moves.
Really? If the 40 sub-scramble moves generate a random state, how can you complain about that?
(The issue is that we probably won't reach 40, so it's a matter of coming close enough.)



I agree that it would be best to have a randomly generated cube-position and generate an optimal scramble for it.
That is not what the idea here is (the idea is to get closer to it). ;-)
But, really I agree.

However I don't think this will be possible for a long time. I think a scramble of 40 random moves is good enough. Fair scrambling to me means everybody gets the same scrambles.
Agreed. This is only viable i we get near 40. I think that if we get lucky enough to hit sub-45 (yeah, right!) average moves, the little bit extra might be worth the full randomness.




Now:
We can use the 2-phase CE stages with this idea to try to beat CE (probably in vain, but still for fun), generating random scrambles. CE attempts to get into G1 (U, D, F2, B2, L2, R2) and from it to solved with the least total moves. Instead, you can solve to G1, and then solve, without restricting yourself to G1! Note that G1 solves the factors of EO, CO, and sorting E.
We must do it piecewise greedy-style, first picking the shortest path to G1, then solving in G1 ignoring orientation, without returning to G1.
It reduces, really, to a 2-stage scramble, where the two stages randomly generated and solved are (EO, CO, and placing 4 random edges into the E-ring) and (EP and CP, with E-ring edges already in E).
Upon further consideration, orientation+permutation seems better (no E-ring restrictions for permutation), but it seems quaint to utilize CE's chosen phase-definition (since 2-phase seems the way to go on 3x3x3).


The most efficient 2-phase split of factors for 3x3x3 is actually
{ {{2, 27}, {7, 2}} , {{3, 14}, {5, 3}, {11, 1}} }
(6576668672*6576582375)

I'd also like to see if can find something correspoinding to this, as it seems it should provie shortest solutions (but if Kociemba didn't choose it, is it actually a bad idea?)


It's a bit of consideration before 4x4x4, but I was mainly trying to sho AvG that the stages/steps can beat "optimal" if done independently, ignoring each other (but not on average, and it remains to be seen by how much so). If anyone has a good reason for the gross inefficiency of this (which, from 3x3x3, it seems, there isn't), do tell me. :)

Anyhow, I hope to try some 4x4x4 stuff soon...

(Or should I tackle Pyraminx first, which is actually really easy [except Clement is apparently on it]?)
(Or how about 2x2x2, where CO+CP is easy to brute-force, and will give nearly optimal scrambles?)
 

clement

Member
Joined
Sep 19, 2007
Messages
74
WCA
2004GALL02
Hi Lucas

This is a very good idea ! Why didn't I think of that !

But if you take for example the Kociemba 2 phase algorithm, solving the second step with allowing all moves would be actually a bit slower I think, because you would find solution with 2, 3 moves less, but the search tree would be bigger.

Anyway, I definitively a good idea to tackle big cubes scrambling (remember we will shortly scramble 6x6 and 7x7)

It would be good to try to get cancelation moves between phases also.

For the 2x2 and the pyraminx, the number of positions are 3,674,160 and 933,120. So pre-computation of the optimal solution works here ! (the memory taken is 2 bits times the number of positions).
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I would have to say the argument is flawed.

Let's consider the case of 3x3x3 orientation and permutation, for instance. So we pick a set A of 9656672256000 maneuvers to permute the cubies (not necessarily preserving orientation) and a set B of 4478976 maneuvers to orient the cubies (not necessaritly preserving permutation). Then we generate two pseudorandom numbers, one in the range 0..9656672255999 and one in the range 0..4478975 to select an element a from A, and b from B. We than apply a*b to the solved cube. (Apply a to the solved cube, then apply b to the result.) If we carefully choose the sets A and B, we may in fact be able to generate all positions of the cube group. However, if we just try to choose A and B to use shortest possible sequences, it is very likely some of the possible products a*b would yield duplicate positions. This would mean that some positions would be reached at all by such a product (given some specific sets A and B). There are just enough elements in A and B to possibly generate each cube group element once. Any duplicates mean some others will not be produced.

Yes, if we look at all results a*b for a in A and b in B, it may look like a random distribution of cubie permutations, and it may also look like a random distribution of orientations. But if you do a cross-correlation of permutation and orientation, you may find some combinations with double (or more) the anticipated probability, and some that don't occur at all.

I'm not saying this idea isn't valid at all, but I think that you have to be careful that you generate combinations of the "factors" with equal probability. And that probably means not using optimal sequences for each "factor."

By the way, all cubie permutations except 1 (out of 9656672256000 positions) can be reached in 13 face turns or less. (So the worst case is 14.) The average distance is 11.7326. For the typical orientation conventions used in BLD cubing, I calculate the worst case for orientation is 9 face turns, with the average distance being 7.1691.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
cuBerBruce:
Could you give me two sets of algs,
  • one for each of the 12 EPLL cases, and
  • one for each of the 8 EOLL cases,
such that randomly doing EP+EO will not give an even distribution of all EPLL states?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
cuBerBruce:
Could you give me two sets of algs,
  • one for each of the 12 EPLL cases, and
  • one for each of the 8 EOLL cases,
such that randomly doing EP+EO will not give an even distribution of all EPLL states?

Well, as an example, I used ACube to generate some algs for the orientation cases. I generated algs that preserve F2L and corners, but not necessarily the permutation of LL edges. For permuting edges, I just picked the 11 PLL algs that preserve corners and edge orientation (8 U-Perm, 2 Z-Perm, and H-Perm), plus the zero-length alg for the 12th case. (Only the even-permutations were used.)

For solving, you would use algs that takes mis-oriented edges and correctly orients them. For scrambling, you would tend to be doing the reverse - starting with oriented edges and mis-orienting some of them. If the algs also permute, you need to decide if you want to mis-orient cubies (based on where cubies start out) or mis-orient cubicles (based on where cubies end up). If you have a prior step that affects the orientation of the cubies, then both the starting orientation pattern and how the alg permutes the cubies whose orientation is flipped affects the ending orientation pattern.

That said, I picked "orientation" algs that orient a set of cubies based upon their starting position.

cubies to
flip . . . . . alg
------------------
  • none: 0-length alg
  • UF/UR: F' D2 B2 L' B2 D2 F2 R' F' (permuted to UL/UF)
  • UR/UB: R' D2 L2 F' L2 D2 R2 B' R' (permuted to UF/UR)
  • UB/UL: B' D2 F2 R' F2 D2 B2 L' B' (permuted to UR/UB)
  • UL/UF: L' D2 R2 B' R2 D2 L2 F' L' (permuted to UB/UL)
  • UF/UB: F U F' L R' D F' D' L' R (permuted to UL/UF)
  • UR/UL: R U R' F B' D R' D' F' B (permuted to UF/UR)
  • UF/UR/UB/UL: F2 L R' D2 F L2 R2 B' D2 L R' B2 (permuted to UL/UB/UR/UF)

Applying permutation algs first, then orientation algs, (using GAP) I get 72 unique positions instead of all 96. For example: 0-length permutation alg combined with UF/UR orientation alg, and B2 U' R L' B2 R' L U' B2 (a U-Permutation) combined with the UF/UB orientation alg produce the same configuration.
 
Last edited:

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
cuBerBruce: You're solving random EO, and solving random EP.
Right now, selecting a random EO of yours will not even possibly flip opposite edges...
Can you generate them (i.e. invert, WLOG for you only EO algs) instead, and still exhibit two identical generated states/a non-generatable state?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
My fifth and sixth orientation algs did flip two edges that were opposite, opposite at the start that is. Those edges just don't end up opposite. Yes, if I use the inverses of those algs, I do generate all 96 cases. Or if I replace those two algs with ones that swap opposite edges while flipping one of the pairs, I also generated all 96 cases. So you may be right that if you use cubicle-based EO, and you choose "orientation" algs that leave the flipped cubies in eight different patterns (assuming all oriented to start with), and you apply a non-orienting permutation alg first, then maybe it does work. Doing the orientation alg first, then the permutation alg, however, does not generate all 96 cases using those same sets.

I also note that none of my "permutation" algs had any effect on orientation. If I had used F R F2 D2 B2 L B2 D2 F in place of the equivalent U-permutation (F2 U'L R' F2 L' R U' F2), then that permutation alg combined with the first (non-trivial) orientation alg (F' D2 B2 L' B2 D2 F2 R' F') produces the identity,
as does the case of identity*identity. So that also would result in not producing all 96 cases. Since these two algs are inverses, it wouldn't matter which is done first, you get the identity either way.

In your original post you talked about applying a random permutation R and another random permutation P to get a third permutation Q. As any group is isomorphic to a permutation group, this applies to the ELL group (taking this to mean the group of even-permutation positions of the edges of the last layer).

So if we randomly pick one ELL group position from all the positions that have some desired permutation effect, and then randomly pick a 2nd ELL group position from all the ELL positions that have some desired orientation effect, then we will get a random ELL position as a result of composing the two positions. (This is rather silly, since we could just randomly pick a single ELL element instead of two.) But in my example, I wasn't picking random ELL positions. I picked certain positions with somewhat convenient sequences. So the result was we didn't get necessarily get a uniform distribution of ELL positions. With careful selection of representative positions for permutation and orientation, we can get a uniform distribution, such as by selecting permutation sequences that don't affect orientation, and orientation sequences that don't permute the cubies. But other possibilities exist, too.
 
Last edited:

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Hmm, I wanted to give a good response here, then lost it...

Well, thanks for at least disagreeing and giving some nice evidence.
At least someone knowledgeable is making sure I'm not doing something stupid. ;)

This already shows how careful we have to be... orientation & permutation and centers need to be handled correctly.
Even though we can ignore the distinction (practically) for permutation -since we get the same effect of a random state, as the inverse of a random permutation is a random permutation- we have to make sure to generate factors in order to obtain a random state...

I won't have time to try much soon, but if I do, I'll post here again... :)
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
I know I'm late, but here's my minimal counter-example. Imagine a very simple puzzle, it only has two edges. Permutation is free, they can be swapped. Orientation has parity, you can only flip both or none.

Permutation subscrambles = { doNothing, swapAndFlipBoth }
Orientation subscrambles = { doNothing, swapAndFlipBoth }

The puzzle has four states, combining the subscrambles reaches only two.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
I know I'm late, but here's my minimal counter-example. Imagine a very simple puzzle, it only has two edges. Permutation is free, they can be swapped. Orientation has parity, you can only flip both or none.

Permutation subscrambles = { doNothing, swapAndFlipBoth }
Orientation subscrambles = { doNothing, swapAndFlipBoth }

The puzzle has four states, combining the subscrambles reaches only two.
Gah, I couldn't come up with this myself? :(
Orientation is somewhat nasty, though...

But do you agree that if we only stay within permutations (combining permutation and orientation), we're always fine?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
No. Imagine a puzzle with two corners and two edges. No orientation, but corners can be swapped and edges can be swapped.

Corners subscrambles = { doNothing, swapCornersAndSwapEdges }
Edges subscrambles = { doNothing, swapCornersAndSwapEdges }

For a larger example using a real puzzle, take the (super) 4x4 and its edges and centers. Define a bijection between edges and centers. Now to scramble the edges, apply one of the possible 24! permutations on the edges, and also apply the same permutation on the centers. Repeat for centers. You can only get 24! outcomes but there should be 24!^2.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
My two small counter-examples were of course isomorphic. Here's the abstract short presentation:

Puzzle with two factors, each with two states. To randomize one factor, keep its state or change it, and do the same with the other factor.
 
Top