Cachan, officialy beating the scramble for Square1

[OlliF]

Starting with (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3), I get:

6,7,8,9,8,7,8,9,8,9

Details:

Spoiler

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3):
3,0/0,3/0,10/3,6/2,0/0,3/6,6 [6|15]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3):
3,9/0,9/3,9/1,9/0,9/2,0/3,0/ [7|17]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4):
/3,11/3,6/3,9/1,9/3,6/0,2/6,9/6,6 [8|23]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5):
5,7/1,0/3,5/3,3/0,8/1,7/0,9/0,3/11,8/6,4 [9|25]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1):
0,3/0,8/1,6/3,3/2,0/4,4/0,3/9,0/5,3 [8|21]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1) (0,3):
0,8/1,6/3,3/2,0/4,4/0,3/9,0/5,3 [7|19]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1) (0,3) (4,2):
/2,0/3,10/3,3/3,1/2,2/1,10/6,3/11,9 [8|23]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1) (0,3) (4,2) (6,4):
2,4/1,10/3,3/0,10/3,9/5,8/1,4/5,11/10,1/5,6 [9|28]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1) (0,3) (4,2) (6,4) (0,2):
3,6/0,9/3,0/3,6/0,7/3,6/2,9/0,3/3,6 [8|22]

Optimal solution for (3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1) (0,3) (4,2) (6,4) (0,2) (-4,4)
2,10/2,10/4,2/2,10/2,10/2,1/3,3/0,5/9,0/3,1 [9|27]

Edit: I note that I used the -w option so that it guaranteed the minimal number of twists, rather than the optimal solution in turn metric.

@STEFAN: Any conclusions to these results?

 

[OlliF]

This. Fortunately, the problem of random Square-1 scrambles has been solved. Unfortunately, there is still no official scrambler for it.

This. Fortunately, the problem of random Square-1 scrambles has been solved. Unfortunately, there is still no official scrambler for it.

@LUCAS: Currently I'm writing a Square-1-Explorer with the Square-1-Optimizer/Solving-Algos of Jaap Sheerphuis as solver. It's more a graphical user interface than working on solver-problems.

Could you give me some information where I can find more about the solved problem of random Square-1 scrambles, please?

Thanks a lot.

Oliver

 

[Stefan]

@STEFAN: Any conclusions to these results?

Not really, as I'm not really a Square-1 expert. But I can ask more questions now

I find it interesting that it starts with 6, so it already lost a move (or two? not even sure how to count) in the first few moves. And then it does stay around 8 and never gets to 10 and 11, the most common distances. Now I'm wondering how inherent that is in our current scrambler. Do we have statistics about the quality of the scrambles it generates, at least a distance distribution and the distance it produces on average?

 

[OlliF]

Not really, as I'm not really a Square-1 expert. But I can ask more questions now

I find it interesting that it starts with 6, so it already lost a move (or two? not even sure how to count) in the first few moves. And then it does stay around 8 and never gets to 10 and 11, the most common distances. Now I'm wondering how inherent that is in our current scrambler. Do we have statistics about the quality of the scrambles it generates, at least a distance distribution and the distance it produces on average?

Last week I modified the Square-1-optimiser of Jaap Sherphuis to produce scrambles and let them solve. I transcripted the scramble algorithm of the official WCA-scrambler "scramble_square1_2010.htm" excatly 1:1 from javascript to c++. With this stuff I produced a little statistic:
n=10.000 scrambles, variable: scramble length s, option -w used for optimal twist solution
s=40:
Twists = 3 # = 2
Twists = 4 # = 1
Twists = 5 # = 6
Twists = 6 # =23
Twists = 7 # =91
Twists = 8 #=403
Twists= 9 #=1365
Twists=10 #=3808
Twists=11 #=3375
Twists=12 #= 922
Twists=13 # = 4
avg.: #=10,2645

s=50:
Twists = 3 # = 0
Twists = 4 # = 0
Twists = 5 # = 0
Twists = 6 # =4
Twists = 7 # =32
Twists = 8 #=219
Twists= 9 #=1088
Twists=10 #=3749
Twists=11 #=3778
Twists=12 #=1130
Twists=13 # = 0
avg.: #=10,4400

s=60:
Twists = 3 # = 0
Twists = 4 # = 0
Twists = 5 # = 0
Twists = 6 # = 0
Twists = 7 # =14
Twists = 8 #=170
Twists= 9 #=977
Twists=10 #=3643
Twists=11 #=4003
Twists=12 #=1192
Twists=13 # = 1
avg.: #=10,5031

s=80:
Twists = 3 # = 0
Twists = 4 # = 0
Twists = 5 # = 0
Twists = 6 # = 3
Twists = 7 # =15
Twists = 8 #=127
Twists= 9 #=891
Twists=10 #=3579
Twists=11 #=4091
Twists=12 #=1293
Twists=13 # = 1
avg.: #=10,5478

My conclusions: the distance distribution getting significant smaller with increasing scramble-length, getting more like the most common distance distribution. But: a scramle length of 60 and more is in my opinion not useful for competitions.

Oliver

 

[Stefan]

Thanks for those statistics, I'm preparing some more myself now. But why did you transcribe the scrambler to C++? I'm using the original Square-1 scrambler, just without the drawings because they were very slow and memory-intensive.

 

[Lucas Garron]

Could you give me some information where I can find more about the solved problem of random Square-1 scrambles, please?

Here's some, especially this post. The conclusion: Place pieces randomly, try again if it's not a valid state where you can do a / immediately. (Alternatively, generate a random shape with the proper distribution, then random permutations of corners and edges.)

 

[oranjules]

How could be a scrambled square 1 impossible ? With the parity, every permutation is possible, and since there is no state not allowing you to do R...

 

[Lucas Garron]

How could be a scrambled square 1 impossible ? With the parity, every permutation is possible, and since there is no state not allowing you to do R...

You try placing 7 edges and then a few corners to fill up the top.

Valid state here also means you can do a / without AUF and ADF. Did you read the link?
(But yes, will edit above to clarify?)

 

[Stefan]

Some more statistics...

First I checked the twist metric (counting R turns), comparing 10000 WCA scrambles to Jaap's God's table.

"Looks" is for number of turns as shown by the WCA scrambler
"Needs" is for number of turns needed to solve the WCA scrambles (solving twist-optimally)
"Should" is for the number of turns it should need (from God's table)

Turns Looks  Needs    Should      Is/Should
-------------------------------------------
  0      -      -      0.000000023        -
  1      -      -      0.0000015          -
  2      -      1      0.000026    37804.98
  3      -      -      0.00039            -
  4      -      -      0.0054             -
  5      -      4      0.071          56.40
  6      -     18      0.89           20.17
  7      -     90     10.37            8.68
  8      -    401    102.3             3.92
  9      -   1401    772.5             1.81
 10      -   3793   3429.8             1.11
 11      -   3374   4213.5             0.80
 12      -    917   1467.0             0.63
 13      -      1      3.61            0.28
 14     15      -      -                  -
 15    408      -      -                  -
 16   1763      -      -                  -
 17   3030      -      -                  -
 18   3147      -      -                  -
 19   1428      -      -                  -
 20    204      -      -                  -
 21      4      -      -                  -
 22      1      -      -                  -
---------------------------------
Avg  17.40  10.26  10.61

Then I checked the move metric counting R, U and D turns, comparing 10000 WCA scrambles to 10000 random scrambles generated by Jaap's solver.

"Looks" is for number of turns as shown by the WCA scrambler
"Needs" is for number of turns needed to solve the WCA scrambles (solving turn-optimally)
"Should" is for the number of turns it should need (from the 10000 random scrambles)

Turns Looks  Needs  Should  Is/Should
---------------------------------
  0      -      -      -        -
  1      -      -      -        -
  2      -      -      -        -
  3      -      -      -        -
  4      -      -      -        -
  5      -      -      -        -
  6      -      -      -        -
  7      -      1      -        ?
  8      -      -      -        -
  9      -      -      -        -
 10      -      -      -        -
 11      -      -      -        -
 12      -      2      -        ?
 13      -      1      -        ?
 14      -      4      -        ?
 15      -     10      -        ?
 16      -     19      2     9.50
 17      -     25      4     6.25
 18      -     62      4    15.50
 19      -    102     18     5.67
 20      -    207     53     3.91
 21      -    346    130     2.66
 22      -    714    324     2.20
 23      -   1104    752     1.47
 24      -   1921   1568     1.23
 25      -   2451   2638     0.93
 26      -   2021   2790     0.72
 27      -    901   1467     0.61
 28      -    107    241     0.44
 29      -      2      9     0.22
 30      -      -      -        -
 31      -      -      -        -
 32      -      -      -        -
 33      -      -      -        -
 34      -      -      -        -
 35      -      -      -        -
 36      -      -      -        -
 37      -      -      -        -
 38      -      -      -        -
 39      -      -      -        -
 40  10000      -      -        -
---------------------------------
Avg     40  24.38  25.15

Evaluation:

While the averages are at least somewhat close to what they should be, there's a significantly too high number of short scrambles. The one really short scramble (2 twists or 7 turns) really shouldn't have happened, and there shouldn't be so many other short scrambles (see the "Is/Should" ratios).

A random state scrambler would provide scrambles of significantly higher quality. Computing optimal-length scrambles would also save a lot of moves, making scrambling faster and less error-prone. At least Prisma Puzzle Timer already offers random state scrambles (though I don't know how it picks them and how optimal the scramble-lengths are).

 

[Dene]

I wish I had noticed this thread before I put an effort into thinking about a square-1 scrambler myself completely by coincidence. This was my idea, which seems to have been thought up of before, but because I already typed it up I may as well post it.

First, the sq1 must be broken down into 4 sections. These sections are based on the slices. The sections are UL, UR, DL, DR. That is, U layer-left slice, U layers-right slice etc. Each of these sections can fit exactly 6 points (edge = 1 point, corner = 2 points).

To scramble the puzzle, the scramble programme would take out all of the pieces from the U and D layer and randomly create four groups of 6 points. The idea that I had in mind for picking how to place the pieces is fairly simple and maybe it's a bad idea but whatever. I was thinking just assign all 16 pieces on the puzzle (that is, 8 edges and 8 corners) a number from 1 to 16. The simplest way would be to take the puzzle in its solved state and assign those numbers in a clockwise direction starting from whichever piece on the U and D layers. Those numbers can just be permanent, as they're arbitrary. Starting with group 1, a random number generator chooses numbers from 1 to 16 until 6 points are chosen. If the issue arises of having 5 points chosen at some point, and an edge needs to be picked, the random number generator just continues until it chooses an edge. Then it moves onto group 2, and just keeps going until it's done.

The pieces in each group would then be randomly ordered from 1 to 6. Again a random number generator could be used to do this. I don’t know the easiest way to programme it, but I see two obvious options: 1) the pieces retain their original number from 1-16, and the random generator is restricted to choosing numbers only from the pieces in the group. For example, suppose group one had pieces numbered 7, 8, 11, and 14, the random number generator would be restricted to choose only from those numbers. OR option 2) the pieces in the group are re-numbered from 1-? (depending on how many pieces are in the group) and the random number generator picks from that subset.

Then each group would be randomly assigned to one of the four sections on the puzzle. Then the pieces would be placed back into the puzzle in their assigned section in the order that is arbitrarily assigned (clockwise is easy enough)

A simpler idea that I guess would also work would be to put all of the pieces into an order from 1 to 24, then placing them into the puzzle that way, but then I realised it would have a problem with the slice which is why I changed to thinking of four groups of 6 points. Either way should get the job done.

So that was the idea I came up with. I highly doubt it's original. There must be some problems with it... Lucas?


Thanks to Stefan for his help.

 

[Stefan]

At least Prisma Puzzle Timer already offers random state scrambles

I forgot: Jaap's program (from his page) also does:

C:\sq1opt>sq1optim.exe -r5 -g -v0 -n
-3,-4/4,-2/0,2/-3,0/-3,4/0,-1/0,-3/0,-3/-2,5/0,-3  [9|23]

1,0/0,-1/-3,0/0,-2/0,-1/3,4/-4,0/-2,0/0,6/0,5/0,2/-4,0/  [12|25]

-2,0/3,-3/5,0/3,0/0,-4/-3,0/1,0/0,2/0,4/-4,5/6,0/-5,0  [11|25]

1,0/-1,2/3,0/0,-3/3,0/0,4/3,3/-5,4/0,4/0,-2/-2,0/-2,0  [11|26]

-5,0/3,0/5,0/0,3/-3,0/2,0/1,0/0,-4/1,3/4,-5/0,-4/3,0  [11|25]

C:\sq1opt>

I don't know how it picks the random state and it's a DOS/Windows program, the latter being the reason I only thought of Prisma. But we're already using Cube Explorer which is also a Windows program. Looking forward to Oliver's GUI.

 

[Stefan]

I don't know how [Jaap's program] picks the random state

Was easy enough to find and understand:

   void random(){
      middle = (rand()&1)!=0?-1:1;
      do{
         //mix array
         int tmp[16];
         for( int i=0;i<16; i++) tmp[i]=i;
         for( int i=0;i<16; i++){
            int j=rand()%(16-i);
            int k=tmp[i];tmp[i]=tmp[i+j];tmp[i+j]=k;
         }
         //store
         for(int i=0, j=0;i<16;i++){
            pos[j++]=tmp[i];
            if( tmp[i]<8 ) pos[j++]=tmp[i];
         }
         // test twistable
      }while( pos[5]==pos[6] || pos[11]==pos[12] || pos[17]==pos[18] );
   }

It shuffles the 16 pieces and then tries to put them in that order into the puzzle along a certain path. If they don't fit without obstructing the half-puzzle twist, it starts over. I'd say that's theoretically perfect, just the standard "rand" function is rather weak. But with a better random number generator and output, this seems to be ready to use for WCA...

 

[Michael Womack]

(3,0) (-3,6) (0,1) (0,3) (3,0) (0,3) (0,5) (0,3) (0,3) (6,4) (6,5) (5,1) (0,3) (4,2) (6,4) (0,2) (-4,4) (0,0)

This was scramble 3 of group 2 in round 1. Good luck finding a solution that is (way) shorter than the scramble

lol with that scramble i got 54.82 a sub 1 solve

 

[Lucas Garron]

So that was the idea I came up with. I highly doubt it's original. There must be some problems with it... Lucas?

It's a really bad idea. See my links earlier in this thread.

 

[Dene]

Yea I tried reading them. I couldn't understand them

 

[Lucas Garron]

Some more statistics...First I checked the twist metric (counting R turns), comparing 10000 WCA scrambles to Jaap's God's table.

Then I checked the move metric counting R, U and D turns, comparing 10000 WCA scrambles to 10000 random scrambles generated by Jaap's solver.

Stefan, I'm about to submit this scrambler to the WCA. Would you mind re-running your simulation with more moves (e.g. WCA scrambles with 50, 60, 70 turns)?
I've kept the old scramble for backwards-compatibility, and set them to 60 moves for now. It would be nice to get a number that is reasonably safe in case the WCA board would prefer availability of the old scrambler for backup.

 

[OlliF]

Hi to all and first of all: a happy new Year 2012!

I've reached a step in programming the Square-1 Explorer that is able to show a first demo version. As written above the SQ1Explorer is a Windows-GUI to Jaap Scherphuis SQ1optimiser.
Under the following link is a ZIP-file containing the SQ1Explorer.exe, an HTML-Template and a Javascript-file used by the HTML-files, that could be generated with SQ1Explorer.
Here is the zipped SQ1Explorer
Please feel free to check all files by your actual virus scanner before running it on your windows system! It should give no errors. If not, please give me a short note.

Notes: The program is in development. Actually there is no help, the keyboard-control is not implemented, some long-term-functions aren't threaded,...
The random-function is the one of Jaaps' SQ1optimiser (the rand of the C-library).
Please give me your feedback to errors, to additional ideas of the user interface, to additional funciotnality a.s.o. Thanks!

In case of a former WCA-scrambler, I think it is easy to implement a well known random-function (maybe it is still available as c-/c++-library) and use the idea of Lucas for generating a random-state square-1 scramble (see posted links above).

What do you think?

Oliver

 

[Lucas Garron]

Hi to all and first of all: a happy new Year 2012!

I've reached a step in programming the Square-1 Explorer that is able to show a first demo version. As written above the SQ1Explorer is a Windows-GUI to Jaap Scherphuis SQ1optimiser.

I like how it looks just like Cube Explorer. Cute.

I'm not sure if you intended to try to make this an official scrambler, but:
- The current official Square-1 scrambler is temporarily http://www.cubing.net/sq1/ . Not sure if you knew.
- For official scramblers, we're looking for unified scramblers. (See the submitted WRC proposal.) Considering that Mark 2 and tnoodle handle all official puzzles (random-state except on big cubes) and run on all major operating systems, I think it's unlikely that a stand-alone program like this would be accepted as an official scrambler.

But still, nice work, I like it. It seems to have a lot of nice features, and the solver is fast.

(By the way, is it possible to draw the puzzle anti-aliased? I have this preference for everything to be minimally pretty anytime it might as well be.)

 

[aronpm]

Looks good so far.

When I first opened it the background of the Move Editor panel was black, until I pressed one of the buttons. The other panels had a normal white background.

Also it would be a nice feature to have a right-click menu for the scrambles on the left, like in Cube Explorer, to have options to copy the scramble/generator to the clipboard and delete the cube.

 

[OlliF]

Looks good so far.

When I first opened it the background of the Move Editor panel was black, until I pressed one of the buttons. The other panels had a normal white background.

Thanks for the hint. This behavior is knew for me and I don't know why at that moment...

Also it would be a nice feature to have a right-click menu for the scrambles on the left, like in Cube Explorer, to have options to copy the scramble/generator to the clipboard and delete the cube.

I haven't yet implemented right-click features...
But: All Positionstrings and Solves/Generates can be copied by selecting with the mouse and copied with ctrl-c / ctrl-v for former use, e.g. to put it in the "Enter maneuver / Positionstring"-field.
To delete single cube please mark it at the box on the left side and use the menu item "Delete selected cubes". More functionality will come with a right-click-popup-menu...