# 2x2 scrambler programming project suggestion



## Stefan (Nov 28, 2008)

As mentioned in a WCA thread I believe it's possible and fairly easy to create non-canceling 11-moves scrambles for all states of the 2x2. This would allow fast scrambling while preventing giving a clue about short solutions. Anyone capable and interested in verifying/implementing this? I myself dont' have the time right now.

Holding let's say DBL fixed and only scrambling in <U,R,F> leads to 3,674,160 possible states (7! * 3^6), easily allowing brute force.

I'd suggest to first check that it's indeed possible. For that I'd have a field reachable[M] which tells whether state S is reachable in exactly M moves. Init with reachable[solved][0]=true, fill progressively, check that reachable[11] is true for all states S.

This is a one-time research so it doesn't need to be efficient or runnable on all computers. Not like the scramble program for use in competitions. For that, here's a more efficient but still easy approach:

Compute all pairs <state,lastTurnedAxis> reachable from the solved cube in exactly six moves. That's at most 69,984 pairs (9*6^5). This should still be efficient enough even with trivial brute force, and needs to be done just once per program start (or could be precomputed once and stored for reloading). Then for a cube state you want to generate, backwards-compute all pairs <state,firstTurnedAxis> that can reach the desired state in exactly five moves. For each of those, look up a matching pair six moves from solved and ending in a different axis then the finisher-path starts with. The scramble is then the concatenation of the starter path and the finisher path (these paths need to be in some way reconstructable for this, of course, but that's a minore issue and what's best depends on the actual overall implementation).

I don't have time to do it, can anyone else here? The above ideas are just how I would do it without thinking much, it can certainly be done other ways as well, and possibly better. Maybe this could also become the official WCA scrambler, though I think it's also an interesting and rewarding project by itself and it would certainly be very useful for unofficial practice.


----------



## Kenneth (Nov 28, 2008)

Create a precalculated look up table having all possible solutions, it will make some megs but not 'that' much. Then you can find the correct solution in no time at all.

EDIT: when thinking about it, you don't need to "find"a solution for a random state to create a scramble, just pick one of the solutions directly from the table by random instead.


----------



## Stefan (Nov 28, 2008)

I think your 'not that much' is still 'too much'. Ok, Cube Explorer uses even larger lookup tables, but the 2x2 is so easy that this would be unnecessary wasteful overkill. Plus where's the fun in lookup tables doing the whole job? I'm envisioning a slim javascript scrambler here. Maybe I'll do a quick-and-dirty proof-of-concept in perl.


----------



## Herbert Kociemba (Nov 29, 2008)

Actually Cube Explorer already has implemented a table reachable[M] not only for the 2X2 but for the corners of the 3x3 which is 8!*3^7 possibilites and hence 24 times as much as the number of possibilites of the 2x2 cube. Because of reduction by 16 symmetries, this table uses about 1.5 MB and is generated on the fly when starting cube explorer. It is used if you solve incomplete cubes where all corners are defined.
So if there is some interest for a 2x2 scrambler which gives optimal generators (or 11 move generators), it would be easy to implement it.


----------



## TomZ (Nov 30, 2008)

I have ripped up Jaap's 2x2 simulator and modded it into a optimal 2x2 scrambler. To prevent 4 move scrambles from appearing, it has a 9 move lower boundary.

The scrambler: http://zandenonline.nl/22scrambler/
Source: http://zandenonline.nl/22scrambler/source.zip

It's written in JavaScript, so it is portable. Currently it randomizes the cube by doing 100 random moves - is this random enough?

[original post: http://www.worldcubeassociation.org/forum/viewtopic.php?f=4&t=485&start=20]


----------



## Lucas Garron (Nov 30, 2008)

TomZ said:


> I have ripped up Jaap's 2x2 simulator and modded it into a optimal 2x2 scrambler. To prevent 4 move scrambles from appearing, it has a 9 move lower boundary.


This is not what Stefan asked for, and not even an implementation of his goal.
Your scrambler should either always give 11 moves, or you might as well make it optimal.
Also, you don't use the standard color scheme.



TomZ said:


> It's written in JavaScript, so it is portable. Currently it randomizes the cube by doing 100 random moves - is this random enough?


No, that's just silly. You should use a randomly generated state (not a shortened "sufficiently long" scramble).


----------



## TomZ (Nov 30, 2008)

I have never claimed to have done exactly what Stefan proposed. I have simply read over the discussion, and I've made what I think the scrambler should be like.

Since the better part of 2x2 scrambles can be solved in nine moves or less, I thought that would be 'the best' lower boundary. If in the discussion it is decided later on that another number would make a better boundary - it is as simple as changing a single number in the source code.

The colour scheme matches that of an ES 4x4 (with the exception of purple) or a Rubik's 3x3. Since most cubes use this scheme I also used this colour scheme. I know that official rubik's 2x2's have a different layout, but there aren't many people using it.

As for the scrambles, you are right. The 100 move thing was an act of lazyness. I guess completely random positions should be fairly easy to implement.


----------



## Lucas Garron (Nov 30, 2008)

TomZ said:


> I have never claimed to have done exactly what Stefan proposed. I have simply read over the discussion, and I've made what I think the scrambler should be like.


Ah, that's not what I thought you'd meant to do.



TomZ said:


> Since the better part of 2x2 scrambles can be solved in nine moves or less, I thought that would be 'the best' lower boundary. If in the discussion it is decided later on that another number would make a better boundary - it is as simple as changing a single number in the source code.


Could you upload a separate version with lower bound 0?
And can you also upload one with lower bound 11, to see if it works?



TomZ said:


> The colour scheme matches that of an ES 4x4 (with the exception of purple) or a Rubik's 3x3. Since most cubes use this scheme I also used this colour scheme. I know that official rubik's 2x2's have a different layout, but there aren't many people using it.


Seems to be working now. When I used it earlier, I saw gray stickers.



TomZ said:


> As for the scrambles, you are right. The 100 move thing was an act of lazyness. I guess completely random positions should be fairly easy to implement.



(Be careful about the PRNG!)


----------



## TomZ (Nov 30, 2008)

11 moves minimum: http://zandenonline.nl/22scrambler/11moves/
0 move minimum: http://zandenonline.nl/22scrambler/optimal/

What's PRNG anyway?


----------



## Stefan (Dec 7, 2008)

(sorry for the absence)

Looks good, especially the 11 moves version. Is it guaranteed to always find a generator with 11 moves? Or are there cases that can't be done in exactly 11? Maybe Herbert can answer this one...

Since Cube Explorer is already used for competitions, that might be a nice option, too.

Btw, here's a link to the WCA thread about this (of which this thread here is a spin-off):
http://www.worldcubeassociation.org/forum/viewtopic.php?f=4&t=485



TomZ said:


> What's PRNG anyway?


http://tinyurl.com/5gp47u


----------



## TomZ (Dec 7, 2008)

I am not sure on the 11 move limit. I think if a scramble can be generated in N moves, it must also be generatable in N+M moves.

There would be (3*3)*(2*3)^10 different 11 move scrambles, which means that if the scrambles were distributed evenly, each scramble would have about 150 generators.

Of course this isn't a proof, but there is an easy workaround: set the upper bound to 20, so that if no 11 move generator exists, it will find a generator with more moves. That would take care of the problem. And as it quits searching once a generator is found, it wouldn't present a 12 move generator if a 11 move could be found.

This one begins the search at 11 moves, and ends at 20: http://zandenonline.nl/22scrambler/20upper/

That's a very nice just****ingoogleitwebsite. Damn, I thought PRNG was just some kind of insider's joke.


----------



## rjohnson_8ball (Dec 7, 2008)

@Stephan, First time I have seen that site letmegooglethatforyou.com. It will come in handy.


----------



## Stefan (Dec 7, 2008)

The 2x2x1 has a three moves diameter but only half of all states can be reached in exactly three moves. No idea about the 2x2, though, just proving it's not the case for all puzzles.

About PRNG: There once was a TopCoder competition where input cases were supposed to be generated randomly and they used the Random class which produced significant patterns that really shouldn't have been there, screwing the competition results a lot. SecureRandom would've been better. No idea about JavaScript, but the issue is worth researching if you rely on randomness.

And yeah that googling site is great, I've used it a few times already.


----------



## brunson (Dec 7, 2008)

StefanPochmann said:


> About PRNG: There once was a TopCoder competition where input cases were supposed to be generated randomly and they used the Random class which produced significant patterns that really shouldn't have been there, screwing the competition results a lot. SecureRandom would've been better. No idea about JavaScript, but the issue is worth researching if you rely on randomness.


I posted an implementation of CMWC4096 (google it) in Python here:
http://www.speedsolving.com/forum/showpost.php?p=53481&postcount=23

It should be pretty easy to adapt to any other language. The original was implemented in C using bit shifts (very efficient), I ported those using mods, (fast, but not as efficient), but I don't know what is the most efficient way to do that in JS. I also use /dev/urandom to get my pool of seeds, I'm not sure how to do that portably, but I don't really care about programming in anything except Unix.


----------



## Herbert Kociemba (Dec 9, 2008)

Here is the distribution of the 2x2x2

```
0                    1              
  1                    9       
  2                   54          
  3                  321   
  4                1,847    
  5                9,992      
  6               50,136   
  7              227,536      
  8              870,072        
  9            1,887,748           
 10              623,800             
 11                2,644
```
So 11 moves suffice in all cases. I have two more questions concerning an implementation of a scrambler in Cube Explorer. For a random scrambler, is it a good suggenstion to exclude all cases with depth <8 or depth<7 for example ?
The 2x2x2 has no centers. Is there nevertheless any WCA-rule, where for example the position of a certain corner is in the scramble?


----------



## hr.mohr (Dec 9, 2008)

The standard way to scramble is to have white up and green front.


----------



## Stefan (Dec 9, 2008)

Herbert Kociemba said:


> So 11 moves suffice in all cases.


But can you also tell whether every case can be solved not in "at most" but in "exactly" 11 moves? Because the idea is to always have the same scramble length so that there are no short scrambles hinting at a short solution.



Herbert Kociemba said:


> For a random scrambler, is it a good suggenstion to exclude all cases with depth <8 or depth<7 for example ?


This has been discussed a few times (most currently in this current WCA thread), but no, we don't exclude any cases. I hope we'll change that to exclude anything that "counts as solved" (which would mean up to one turn away from solved) in order to prevent confusion, but currently even that would be allowed.



Herbert Kociemba said:


> Is there nevertheless any WCA-rule, where for example the position of a certain corner is in the scramble?


The rule is indeed U=white and F=green. And the official scrambler turns only <U,R,F>, leaving the DBL corner fixed (that's not explicitly in the rules, but I recommend adopting it). Have a look:
http://www.worldcubeassociation.org...e.htm?size=2&num=5&len=25&col=yobwrg&multi=on


----------



## cuBerBruce (Dec 10, 2008)

StefanPochmann said:


> Herbert Kociemba said:
> 
> 
> > So 11 moves suffice in all cases.
> ...



I assumed this also meant exactly 11 moves with no trivial redundancies in the scramble, so no consecutive turns of the same layer. (Conventional scramble programs avoided such redundancies.) With less than 4 million total positions, it wouldn't be hard to use a brute force check of all possible positions to verify this. If consecutive turns of the same layer were allowed, you could trivially convert a single turn such a R into two turns such as R' R2, as necessary in order to get the length up to 11.


----------



## Stefan (Dec 10, 2008)

Yes, of course without such redundancies.


----------



## qqwref (Dec 10, 2008)

I can't add anything to this topic other than saying I can't think of any way to non-constructively prove that every state has an 11-move generator, but here are some for all positions of distance 1 or less up to symmetry:
identity: R2 U R U R' U' R' U' R' U R'
U: R2 U2 R U2 R2 U F2 U2 F' U2 F2
U': R2 U2 R U2 R2 U F2 U2 F' U2 F2
R2: R2 U R U R' U' R' U' R' U R
 Good luck guys, this is a really cool idea.


----------



## Kenneth (Dec 14, 2008)

TomZ said:


> I am not sure on the 11 move limit. I think if a scramble can be generated in N moves, it must also be generatable in N+M moves.



With exeptions, if you have a mix of quarter and half turns that is true, better to look at quarter turns, a scramble that is a uneven number of QTM must always have a uneven number. Take Niklas as an example, R' U L U' R U L' U' it is 8 QTM and optimal, all other algs that solves this case must have 8, 10, 12... QTM, newer 9, 11, 13...


Hey, look at that, it's my post #1,000


----------



## qqwref (Dec 14, 2008)

That's obvious though Kenneth, and nobody generates scrambles in QTM...

Anyway I think that the assertion that "if a position can be solved in N moves HTM it can also be solved in N+M moves HTM" is not necessarily true. For example there is no way to solve the scramble U with two non-canceling moves. So unfortunately I think the assertion is not true in general and thus we might have to prove it somehow else.

Here is an interesting approach: suppose we have a scramble of k<11 moves, call it A B ... N. Then what we are actually looking for is a non-canceling 11+k move identity which starts with N' ... B' A'. That is - any 2x2 scramble can be solved in exactly 11 moves if and only if there is an 11+k move identity starting with every possible k-move scramble. So, if we could somehow find a way to list every 2x2 identity of 11+k moves, we could quite easily check to make sure that every possibility of the first k moves is accounted for. (Probabilistically speaking this is very likely, but we have to be sure...)


----------



## Kenneth (Dec 14, 2008)

qqwref said:


> That's obvious though Kenneth, and nobody generates scrambles in QTM...



To you it is but not to anybody, you are not the only one who reads this forum


----------



## qqwref (Dec 14, 2008)

You're right, maybe I'm overestimating the knowledge of theory on this forum. But still, I would expect all the people who are talking about math and theory (like Stefan, Bruce, you, Kociemba, TomZ, etc) to be well aware of that fact


----------



## Kenneth (Dec 14, 2008)

Yes, true. But some that don't may like to learn, that's why I always try to explain as much as possible (sometimes it may look like I try to show off but I'm actually the mentor type, I like to see people learn things).


----------



## AvGalen (Dec 24, 2008)

Interesting discussion, but why this fascination with exactly 11?

Scramblers are not supposed to solve those same scrambles.
Scramblers are not supposed to talk to competitors.
So what would be the problem if a scramble would be 10 moves (or 12?)

I would worry more about an 11 move scramble that has a 2 move solution.


----------



## Stefan (Dec 24, 2008)

10 or 12? The blasphemy! Curse you Arnaud!

Having all scrambles the same length would be just *beautiful*. I agree 10 or 12 wouldn't really make a difference in practice, but... it wouldn't be beautiful. Something deep inside of me would cry and howl in pain. If it's possible to make it perfect, then I want it perfect.

The 2 move solution scramble and whether it's good is a different issue altogether. But compared to optimal length scrambles I'd prefer the 11 moves scrambles particularly for scrambles with short solutions. Two moves are probably trivial to spot anyway, but four aren't. And then it would be bad to see the scramblers picking up the cubes and putting them back after four moves. That would *tell* people that there's a short solution. And that's exactly what the idea discussed here tries to prevent.


----------



## AvGalen (Dec 24, 2008)

StefanPochmann said:


> 10 or 12? The blasphemy! Curse you Arnaud!
> 
> Having all scrambles the same length would be just *beautiful*. I agree 10 or 12 wouldn't really make a difference in practice, but... it wouldn't be beautiful. Something deep inside of me would cry and howl in pain. If it's possible to make it perfect, then I want it perfect.
> 
> The 2 move solution scramble and whether it's good is a different issue altogether. But compared to optimal length scrambles I'd prefer the 11 moves scrambles particularly for scrambles with short solutions. Two moves are probably trivial to spot anyway, but four aren't. And then it would be bad to see the scramblers picking up the cubes and putting them back after four moves. That would *tell* people that there's a short solution. And that's exactly what the idea discussed here tries to prevent.



Oh, so the idea is to have beautiful scrambles. And beautiful means 11 moves always. Not 25 moves always and not an optimal scramble always. No, even if there is a 7 move scramble you want it transformed to an 11 move so you don't cry and howl in pain 

.................................................................OK, let's have someone else do it


----------



## Stefan (Dec 24, 2008)

Don't obsess over the number 11. That's just because some cases require 11 moves, so a smaller number wouldn't always suffice. The real objective is not the number 11. The real objective is (A) having short scrambles so scrambling is fast and (B) not letting the scramble length give clues about the possible solution length. Having all scrambles the same length achieves (B) the best possible way, having them have 11 moves achieves (A) the best possible way (assuming all cases can indeed be generated in exactly 11 moves, which is still not clear).


----------



## Stefan (Dec 24, 2008)

AvGalen said:


> Scramblers are not supposed to solve those same scrambles.



Oh and this is actually wrong. As already mentioned in my initial post in this thread, this is not just intended for WCA competitions but also for private unofficial practice where we *do* scramble for ourselves.


----------



## qqwref (Dec 24, 2008)

Can't we just switch to, say, 15 random moves for the time being? Even if we can't get optimal scrambles, 25 is way excessive.

If you don't like that, we could always just use 3x3 scrambles for official 2x2. It's faster to do 19 moves than 25 anyway...


----------



## Stefan (Dec 24, 2008)

Well, Tomz' scrambler and Ron's latest reply in the WCA thread (http://www.worldcubeassociation.org/forum/viewtopic.php?p=2954#p2954) look promising.


----------



## AvGalen (Dec 25, 2008)

StefanPochmann said:


> Don't obsess over the number 11. That's just because some cases require 11 moves, so a smaller number wouldn't always suffice. The real objective is not the number 11. The real objective is (A) having short scrambles so scrambling is fast and (B) not letting the scramble length give clues about the possible solution length. Having all scrambles the same length achieves (B) the best possible way, having them have 11 moves achieves (A) the best possible way (assuming all cases can indeed be generated in exactly 11 moves, which is still not clear).



You know me well enough to know I understand where the 11 comes from. And you warning me about not obsessing about the number 11 sounds really weird after you said


> I agree 10 or 12 wouldn't really make a difference in practice, but... it wouldn't be beautiful. Something deep inside of me would cry and howl in pain. If it's possible to make it perfect, then I want it perfect.



I like perfection, but I love simplicity. Simply providing a 15, 20 or even 25 moves scramble gives very random scrambles (some hard, some easy), is short enough for me and long enough for competitors that are looking at the scramblers.

I have some other requirements for good scrambles. If they are very short (like 11) I would just memo them while scrambling and might end up solving using the inverse scramble. (this has happened on clock-scrambles). I don't like those repetitive 45 FMC scrambles, but they prevent "inverse solving"


----------

