2010(?): Optimal Scrambles and Discarding Scrambles
qqwref (2009-02-04 00:51:08 +0000)
I don't want to stall the 2009 regulations with this idea. Because this is not really much of a rule change (it does not change what happens during a competition), I don't even think it is necessary that it be included in a yearly revision of the regulations - I think it would be reasonable to change this at pretty much any time.
My idea is twofold:
(1) Use a random-state, optimal scrambler for 2x2, Pyraminx, and Square-1. Also, optimize the way Clock is scrambled to save time for the scramblers.
(2) Discard scrambles which are too easy (for a specific definition of too easy).
(1) To elaborate, optimal solvers exist for 2x2 (there's another topic on this), Pyraminx (see [url=http://geocities.com/jaapsch/puzzles/pyraminx.htm:31eqenp0]Jaap's page[/url:31eqenp0]), and Square-1 (also see [url=http://geocities.com/jaapsch/puzzles/square1.htm:31eqenp0]Jaap[/url:31eqenp0]). Thus, it would be practical to make a random-state, optimal scrambler for each one. Since it takes less time to execute an optimal scramble than to execute the longer scrambles we currently use, it would save time, and since it would be a true random state scrambler (assuming the random number generator is acceptable), it would also provide 'better' scrambles than the current ones.
As for Clock, I realize that in a sense the scrambler we use already is optimal. However, the usage of pegs is not, and in my experience it can waste a lot of time for inexperienced scramblers. I think we should (a) change the order of the moves to save time in scrambling (see my [url=http://mzrg.com/miniSites/scramblers/megascrambler.html?scramble=clke:31eqenp0]Clock scrambler[/url:31eqenp0] for this), and (b) switch to horizontal scrambles rather than vertical ones (again see my scrambler). I think all of these changes would make the Clock scrambles easier to read and more intuitive for people who don't practice it.
(2) Now about discarding scrambles. In an earlier topic I mentioned the unofficial criterion for "lucky", where something is lucky if it is skipped under 20% of the time, and proposed that we discard optimal scrambles which are short enough that a scramble of their length or shorter occurs under 20% of the time. This means I propose to discard:
- 2x2x2 scrambles of 7 or fewer moves (maximum is 11).
- 3x3x3 scrambles of 16 or fewer moves (maximum is 20).
- Pyraminx scrambles of 6 or fewer moves not counting tips (maximum is 11), and Pyraminx scrambles with 1 or fewer turned tips (maximum is 4).
- Square-1 scrambles with 9 or fewer twist moves (maximum is 13).
- Clock scrambles where 3 or more of the 14 possible moves are 0-turns.
This provides an objective justification for knowing when a scramble is too easy, and it also allows us to remove scrambles that are obviously too short (such as the 4- and 5-move 2x2 scrambles that have been popping up recently). When a scramble is that short, you end up with multiple people in the competition getting times that they could never get on a nonlucky solve - that is, it's not just individual people being lucky anymore, it's actually an unfair advantage to anyone attending the competition. Apparently, cheating has occurred with such easy scrambles, too - I have heard that in some cases with very easy scrambles, competitors who had already gone were observed to be showing the scramble to those who hadn't gone up yet. I think we need to eliminate easy scrambles, and just discarding solved cases (or nothing) isn't enough.
Some people might criticize this method and say that it does not prevent some "easy" scrambles, or that a longer scramble is not always harder. That's not the point of this - the point is to prevent scrambles that are objectively significantly easier than average. Just because you know a one-look solution to a scramble (for example the superflip on 3x3, or the Y-perm on 2x2) does not make it easy, and just because it skips a step on your method does not make it easy either. The point of this idea is not to prevent scrambles that anyone could possibly find easy, but rather to prevent scrambles that are so short that the chance of skipping a good portion of the puzzle is increased.
blade740 (2009-02-04 06:57:37 +0000)
I agree with everything except for one: Square-1.
How would random-state scrambling work? Shape-wise, that is. Do you weight every shape equally? This would SIGNIFICANTLY change the game. As the scrambler is now, you are much more likely to get an easy cubeshape than a harder one. I agree, it needs a change, but it should be discussed how to weight the shapes before we decide officially.
Lucas (2009-02-04 07:39:57 +0000)
[quote="blade740":subyoh8i]I agree with everything except for one: Square-1.
How would random-state scrambling work? Shape-wise, that is. Do you weight every shape equally? This would SIGNIFICANTLY change the game. As the scrambler is now, you are much more likely to get an easy cubeshape than a harder one. I agree, it needs a change, but it should be discussed how to weight the shapes before we decide officially.[/quote:subyoh8i]
We have data for the Markov distribution. All we need is a random-state solver configured to the correct probabilities.
StefanPochmann (2009-02-04 09:40:04 +0000)
[quote="qqwref":2p99gz6l]- Clock scrambles where 3 or more of the 14 possible moves are 0-turns.[/quote:2p99gz6l]
I don't understand.
qqwref (2009-02-04 19:14:44 +0000)
[quote="blade740":3u4bdg55]How would random-state scrambling work? Shape-wise, that is. Do you weight every shape equally? This would SIGNIFICANTLY change the game. As the scrambler is now, you are much more likely to get an easy cubeshape than a harder one. I agree, it needs a change, but it should be discussed how to weight the shapes before we decide officially.[/quote:3u4bdg55]
As Lucas pointed out, he did an analysis which showed the probability of each shape after you do a theoretically infinite number of turns. As it turned out the bias was not towards cubeshapes that are easy or hard, but towards ones which have the highest number of U/D slice positions which allow a / turn. Anyway there are two reasonable ways of doing this, which according to Lucas's analysis seem to be equivalent:
- Jaap says there are "11,958,666,854,400 twistable positions". Choose one uniformly at random and optimally solve it.
- Randomly choose a cubeshape according to the weightings Lucas found. Then randomly permute the corners and edges separately within that shape, and choose a random E-orientation.
[quote="StefanPochmann":3u4bdg55][quote="qqwref":3u4bdg55]- Clock scrambles where 3 or more of the 14 possible moves are 0-turns.[/quote:3u4bdg55]
I don't understand.[/quote:3u4bdg55]
The current Clock scrambler uses 14 random moves, each an integer from -5 to +6. If some of them are 0, the scramble is in a way easier because it has been scrambled with fewer moves than normal (and each move has a specific effect, so it's not just like doing a 24-move random 3x3 scramble instead of 25). For instance the moves in one of the configurations where only two adjacent pegs are up will affect whether any of the edge clocks start out the same as the center one, so if they are 0 then we will allow the solver to skip a step. Since it is obvious that easy enough scrambles exist that times of half one's average are possible, and since Clock is already solved optimally (relative to the 14 moves Jaap chose), I think it makes sense to discard scrambles which are too easy.
StefanPochmann (2009-02-04 22:30:00 +0000)
Ah, ok. You really meant the scramble, not the state of the puzzle after applying the scramble. My bad.
I understand the reasoning for the UUdd moves, but for the UUUd moves it makes less sense to me, and even less for the UUUU and dddd moves. Especially for the latter, I think zero-moves only matter if you solve the same route as the scrambler backwards.
Speaking of that, at least the edge clocks could be solved the same way as the scrambler backwards, so if luck in this route is artificially limited, then by intentionally choosing a different route, I can increase my luck probabilities. Not much, I admit, but I still dislike that the specific implementation of the scrambler influences different routes differently.
qqwref (2009-02-05 02:09:38 +0000)
[quote="StefanPochmann":xw7bz58o]Ah, ok. You really meant the scramble, not the state of the puzzle after applying the scramble. My bad.
I understand the reasoning for the UUdd moves, but for the UUUd moves it makes less sense to me, and even less for the UUUU and dddd moves. Especially for the latter, I think zero-moves only matter if you solve the same route as the scrambler backwards.
Speaking of that, at least the edge clocks could be solved the same way as the scrambler backwards, so if luck in this route is artificially limited, then by intentionally choosing a different route, I can increase my luck probabilities. Not much, I admit, but I still dislike that the specific implementation of the scrambler influences different routes differently.[/quote:xw7bz58o]
Yeah... it's annoying that the scrambler does not follow anything resembling a method. It would be really nice if we could choose a random clock scramble and figure out the optimal solution to it, using all possible moves, not just a specific arbitrary set of 14. Then we could chart God's Algorithm and really figure out when scrambles are too easy.
qqwref (2009-02-05 10:27:08 +0000)
Lucas made a random-state scrambler for Pyraminx
One thing Lucas didn't point out in his [url=http://www.worldcubeassociation.org/forum/viewtopic.php?f=4&t=547:263ahy6x]thread[/url:263ahy6x] is that he also did a little analysis of the length of the scrambles, and the average length turns out to be about 14.7 moves including tips. This will save time over the 25-move scramble, and it is also more equally distributed than the traditional scramble (i.e. assuming the algorithms in the scrambler are all correct every position has a precisely equal probability), assuming the PRNG works properly.
Note that every once in a while this scrambler will produce very short scrambles (I even had a 5-move one of which two were tip moves), so if we plan to use something like this I will of course vote to discard any scrambles that are 6 or fewer non-tip turns, or which turn one or fewer tips.
StefanPochmann (2009-02-05 12:45:42 +0000)
I just realized another benefit of optimal scrambles that I hadn't realized before (though it's kinda obvious, so maybe you're all aware of it already): Fewer moves means fewer opportunities to make a mistake. Especially beneficial for square-1, I guess.