Which 3x3x3 positions require at least 20 moves to solve?

[Stefan]

Okay, I understand the basic idea of this. It is optimized for storage but will require much more lookups and processing to match a scramble with it's optimal solution. Could you write out the data (in table form and bitform) for something simple like a 3*3*1 as an example?

Mmh, 3*3*1... good idea and tempting. I should really study for an exam, but I might do this anyway.

Now that I think of it... while we end up with only three possibilities for each entry ("0", "1" or "2"), how do we handle it while building the table? Cause there we have a fourth possibility: "unknown".

 

[Renslay]

Now that I think of it... while we end up with only three possibilities for each entry ("0", "1" or "2"), how do we handle it while building the table? Cause there we have a fourth possibility: "unknown".

I used it.
Once I tried to build the table actually as a binary table with two entries: 00 represented zero, 01 represented one, 10 represented two and 11 represented unknown; so first the unfilled table was full of 11-s.
(Turned out it was really slow in Matlab, I don't know why; but maybe I did something wrong in the coding. Will try again.)

 

[Stefan]

Yeah but then two bits is optimal (when assuming a uniform distribution of the values 0 to 3) and most of our talk about how to not waste parts of bits is moot

 

[Renslay]

Yeah but then two bits is optimal (when assuming a uniform distribution of the values 0 to 3) and most of our talk about how to not waste parts of bits is moot

I guess you're talking about the overall memory usage during the process. Then I don't think the previous talks were moot. Yes, maybe me need N*2 bits to calculate the whole table, but you can modify the resulted table further after you have it, and store it with less memory (while still usable with direct look-ups). Actually this is what I'm planning with the "5 state in 1 byte" storage version. I calculate the distance table in a regular way, then modify the result.

 

[Stefan]

Sure, you can shrink it at the end, but since you obviously have enough memory to store it without shrinking, shrinking doesn't really "help".

 

[Renslay]

Yes. Sure, you can shrink it at the end, but since you obviously have enough memory to store it without shrinking, shrinking doesn't really "help".

Unless you calculate the table on one machine, then use it on an other one which has less memory.

 

[Stefan]

Yeah ok. Now I'm slightly happier again

Btw, since you already have your 2x2x2 table: Can you compress it (zip or 7-zip or so) and tell the compressed size? (Might help to store each value in a whole byte rather than a quarter of a byte, though I'm not sure about that)

 

[whauk]

The first digit (0) represents the first state, which is the solved state.
The second digit (1) represents the second state, which actually has the optimal solution U R' U R' F' R2 U2 F U F' (10f*)
The third digit (1) represents the third state, which actually has the optimal solution U F' U R' U' F2 R2 U R F (10f*)
etc.
The 99-th digit (2) represents the 99-th state, which actually has the optimal solution R F' R' F' U' R U (7f*)
etc.
The 3674160-th digit (1) represents the 3674160-th state, which actually has the solution U F2 U2 R2 U F' U2 R U F2 (10f*)

which rule did you use for ordering the cube states?

 

[Renslay]

which rule did you use for ordering the cube states?

The cube is represented with a permutation of 7 elements and the orientation of 6 elements.
So, the identical cube is this:
1 2 3 4 5 6 7
0 0 0 0 0 0
The order of the elements: UBL,UBR,UFR,UFL,DBR,DFR,DFL (DBL is fixed / always solved). A corner is oriented, if the top/down sticker is actually looking at top/down. 1 is CW, 2 is CCW. Note that the orientation of the 7. corner is uniquely determined by the other 6 (the sum of the seven orientation-numbers must be 0 modulo 3).

So let's see that state when everything is okay, only UBL (1.) and UFR (3.) swapped:
3 2 1 4 5 6 7
0 0 0 0 0 0

Or another one, where everything os solved, but UBR (2.) rotated CW and UFR (3.) rotated CCW:
1 2 3 4 5 6 7
0 1 2 0 0 0

If we apply a U move, that permutes elements from 1 to 4, and leaves the orientation:
4 1 2 3 5 6 7
0 0 0 0 0 0

A more complicated example: after R U, you have this:
4 1 3 6 2 5 7
0 0 1 2 2 2
Look at the 4. column (6, and under it a 2). It means that at the forth position (UFL place) is the 6. corner (DFR), an it is rotated counter-clockwise.

So we need to encode this information into a single number. The oriantiton is very easy: just handle it as a number in base 3. So
0 0 0 0 0 0 = 0
1 0 0 0 0 0 = 1
2 0 0 0 0 0 = 2
0 1 0 0 0 0 = 3
...
1 1 1 1 1 1 = 301
...
2 2 2 2 2 2 = 728

As for the permutation, the number represents a permutation is the ordinal number in a lexicographical ordering. So:
1 2 3 4 5 6 7 = 0
1 2 3 4 5 7 6 = 1
1 2 3 4 6 5 7 = 2
1 2 3 4 6 7 5 = 3
...
7 6 5 4 3 2 1 = 5039

There are algorithms how to calculate this directly. (See more: permutation ranking)

So, for every state, we can generate 2 unique numbers. How can we merge it into a singe number? Easy:
final number = permutation_number * number_of_orientation numbers + orientation_number,
and we know that the number_of_orientation numbers = 3^7 = 729
So:
final number = permutation_number*729 + orientation number
This is a similar trick when you want to get the n-th element of a 2 dimensional matrix: i-th row (i = 0, ..., h-1), j-th column (j = 0, ..., w-1), then the n-th element is i*w + j (or j*h + i, depends on we want the rows first or the columns first).

This goes from 0 to N-1 (N = number of states on a 2x2), so if we want the numbering from 1 to N, we just have to add 1.

The inverse is just as easy (for a given number what is the cube state).

EDIT:

So, the 1. element in the table is the solved:
1 2 3 4 5 6 7
0 0 0 0 0 0
(perm number is 0, orientation is 0)

What could be the second element? The perm number is 0 and the orientation is 1:
1 2 3 4 5 6 7
1 0 0 0 0 0
That means the 7-th cubie has a CCW orientation. So overall, UBL is rotated CW, DFL is rotated CCW, and indeed, its solution is U R' U R' F' R2 U2 F U F'.

And the very last element in the table is:
7 6 5 4 3 2 1
2 2 2 2 2 2

 

[cuBerBruce]

i think i caught up with everything in this thread now. one more thing is unclear though: we divide by 96 because of rotation symmetry (factor 24), mirroring (factor 2), and inverting (factor 2), right? however there are positions that have more than one of these symmetries themselves (superflip as example for everything). so we counted that we removed them multiple times from the list which means that in fact the list still has to be longer. therefore the final bits per state number should be a little higher?!

Yes, the exact size of the table would be slightly larger than |G|/96, where |G| represents the size of the cube group.

The exact size would be:

450541810590509978
rather than
450541700775936000

(The value was determined by Mike Godfrey and Herbert Kociemba in 2005.)

I note that there is also the issue of converting a cube position into an index from 0 to 450541810590509978-1. Additional storage for additional lookup table(s) will probably be needed for that conversion. Often, a sym-coordinate is used to make such additional lookup tables smaller at a cost of a small increase in the size of the main table (the range of index values).

Huffman coding also adds complexity to the lookup algorithm. If we simply always used 8 bits to store 5 elements, we can easily calculate the position of the byte we need to read and how to extract the right value from it (to extract the value for an arbitrary index). If the elements of the table are variable in size, on the other hand, it makes it difficult to find the precise location of an arbitrary element of the table. Huffman coding works better for a serial stream than a random-access table. We can argue we're not concerned about lookup time here, or we can use some tricks/tradeoffs to come close to the ideal size while reducing the lookup time to a more reasonable value.

 

[Stefan]

Huffman coding also adds complexity to the lookup algorithm. If we simply always used 8 bits to store 5 elements, we can easily calculate the position of the byte we need to read and how to extract the right value from it (to extract the value for an arbitrary index). If the elements of the table are variable in size, on the other hand, it makes it difficult to find the precise location of an arbitrary element of the table.

For Huffman and arithmetic coding, I was thinking of adding a shortcut table, like pointers into the stream at every 1000th position. This would add a little storage overhead to allow decently fast random access. A quick google search for "random access" and "huffman" or "arithmetic coding" also found many papers (I didn't check them much, though).

 

[Renslay]

Yeah ok. Now I'm slightly happier again

Btw, since you already have your 2x2x2 table: Can you compress it (zip or 7-zip or so) and tell the compressed size? (Might help to store each value in a whole byte rather than a quarter of a byte, though I'm not sure about that)

So, here are some storage data info about the table.

According to Matlab's "whos" function, if the table as a variable
containing 0,1,2 as double: 29393280 bytes ( 8 bytes per state)
containing 0,1,2 as int8: 3674160 bytes ( 1 byte per state)
containing 00,01,10 as two logical (binary) in a row: 7348320 bytes ( 2 bytes per state - jepp, Matlab store a logical variable on one byte. What a waste...)

Write out the int8 table into a .txt (without spaces, so it is just a N digit number in a single row):
Size: 3674160 bytes (1 byte per digit)
Size on disk: 3678208 bytes (1.001 byte per digit)

Save int8/double data as .mat (Matlab's storage format for workspace variables - the result is some kind of a binary code, I don't know how it works)
Size: 901256 bytes (0.245 byte per state or 1.962 bit per state)
Size on disk: 905216 bytes (0.246 byte per state or 1.971 bit per state)
(The size of the double and the int8 table is the same; the logical table was higher)

After the compression:

I tried 2 different zip: one is the standard Windows 7 (right click on file, send to compressed folder). The second one is the 7z. It has tons of options, I left everything default.

Actually, the .mat cannot be compressed further, so I suspect that it is already a zip-like compression itself. Win's zip saved just a few bytes, 7z even increased its size with 7 kilobytes.

The .txt:
Win's zip size: 890302 bytes (0.242 byte per state or 1.939 bit per state)
size on disk: 892928 bytes (0.243 byte per state or 1.944 bit per state)

7z size: 739049 bytes (0.201 byte per state or 1.609 bit per state)
Size on disk: 741376 bytes (0.202 byte per state or 1.614 bit per state)

 

[Stefan]

Thanks. I'm not terribly surprised the .mat wasn't compressed further, though it's own almost 1.962 bits per state is a bit weird. Better than two, so some compression is going on, but not much better than two, so the compression sucks?

The "size on disk" values are rather irrelevant, that's just always a little more because of the file system (working in blocks of 4096 bytes, so even a file with just 1 byte content costs you 4096 bytes of disk space).

The .txt:

7z size: 739049 bytes (0.201 byte per state or 1.609 bit per state)
Size on disk: 741376 bytes (0.202 byte per state or 1.614 bit per state)

Sweet. Not quite as good as it could be with just Huffman or arithmetic coding and I was hoping it might actually be better than those because of possible patterns, but still far below 2 bits.

Here are what pure Huffman and arithmetic coding should achieve:

probability for mod-3-distance 0 is 0.527523570013282
probability for mod-3-distance 1 is 0.23221416595902192
probability for mod-3-distance 2 is 0.24026226402769613
[COLOR="#FF0000"]arithmetic: 1.4701906119602757 bits per state
huffman:    1.4724764299867181 bits per state[/COLOR]


Python code:

import math
 
# numbers from http://www.jaapsch.net/puzzles/cube2.htm
s = "1 9 54 321 1,847 9,992 50,136 227,536 870,072 1,887,748 623,800 2,644"
nums = map(int, s.replace(',', '').split())
 
freqs = [0] * 3
d = 0
for s in nums:
    freqs[d % 3] += s
    print(d, s)
    d += 1
print(sum(freqs), freqs)
 
arithmetic = huffman = 0
for i in range(3):
    prob = freqs[i] / sum(freqs)
    print('probability for mod-3-distance', i, 'is', prob)
    arithmetic += -math.log(prob, 2) * prob
    huffman += (1 + (freqs[i] < max(freqs))) * prob
print('arithmetic:', arithmetic, 'bits per state')
print('huffman:   ', huffman, 'bits per state')

Code on ideone in case someone wants to play with it (like use it for other puzzles) and doesn't have Python.

 

[Stefan]

The 7z-file contains some meta-data (like the original file name) as well, though. What's the size of the actual compressed data inside the 7z-file? 7zip should tell you that you open it. I expect it to be only about 100 bytes less than the 739049, but I don't know what you did to it

 

[Renslay]

The 7z-file contains some meta-data (like the original file name) as well, though. What's the size of the actual compressed data inside the 7z-file? 7zip should tell you that you open it. I expect it to be only about 100 bytes less than the 739049, but I don't know what you did to it

Found it: 738936
The difference is 113. You guessed well.

 

[Renslay]

Rewrote the solution/distance table generation. Now it requres less than 11 minutes instead of the first 40 minutes version and the second 25-30 minutes version.

The major change is the forward-backward filling of the table (see this post), which sped up the end of the filling. I used the naive filling algorithm instead of the queue-using BFS, which is much slower in the beginning: filling the table from distance 0 to distance 6 the naive method requires 5 seconds, while BFS requres 19 seconds.

The minor (but probably more powerful) change was rewriting the "NumberToState" function; now it uses pre-calculated tables (e.g., a list of all possible permutations of 7 elements in lexicographical order) instead of using an actual algorithm (such as the Permutation Unranking). Unfortunatly, I cannot use any similar tricks for the inverse StateToNumber function.

So now I'm running out of ideas how to speed up the generation... Maybe this helps further:
For every state (with known distance), I store the movement what lead to that state form the previous state. So, for example, if the current state's number is 132 with d = 4 distance, and it's U2 neighbour is 4333 with an unknown distance, then obviously table(4333) = 5 and I save lastMovement(4333) = U2 (actually, U is enough).
So next time when I check the neighbours of 4333 (now with d = 5), I only check 6 neighbours instead of 9 (I won't check U, U' and U2 neighbours). Because it's impossible that:
S has a distance 4, and
S + U* has a distance 5, and
S + U* + U* has a distance 6.

This can reduce the searching space, therefore saving time (with the price of the increasing memory usage during the calculation).

Any opinion?

 

[rokicki]

For the 2x2, the space is small enough where there's really no need to ever leave symcoords
even when scanning the table; you just make a table of symcoords for the orientation
moves and another for the permutation moves, and with these you can rip through your
table extremely quickly. It's possible blocking the algorithm can improve the performance
even more but it's probably not necessary.

In general you probably want to fill the first n levels (maybe through 6?) using iterated
depth-first search (much faster than table scans), then a level or two of scans forward,
and finally a level or two of scans backwards. For the 2x2, you should easily be able to
get the full table generation done in a few seconds.

In the scans, avoid division by arranging the loops correctly, and put the larger table
(permutation in this case) in the outer loop for cache effects. So you want something
like this (for a forward scan):

for (int cp=0; cp<CORNER_PERMS; cp++) {
   for (int mv=0; mv<NMOVES; mv++) {
      int srcn = cp * CORNER_ORIENTATIONS ;
      int dstbase = cp_move[cp][mv] * CORNER_ORIENTATIONS ;
      for (int co=0; co<CORNER_ORIENTATIONS; co++, srcn++) {
         if (table[srcn] == SEEK_VALUE) {
            int dstn = dstbase + co_move[co][mv] ;
            if (table[dstn] == UNSEEN)
               table[dstn] = SET_VALUE ;
         }
      }
   }
}

You can also hard-code the ultimate distance, prefill your table with this value, and skip
the final scan.

 

[Renslay]

For the 2x2, the space is small enough where there's really no need to ever leave symcoords
even when scanning the table; you just make a table of symcoords for the orientation
moves and another for the permutation moves, and with these you can rip through your
table extremely quickly. It's possible blocking the algorithm can improve the performance
even more but it's probably not necessary.

In general you probably want to fill the first n levels (maybe through 6?) using iterated
depth-first search (much faster than table scans), then a level or two of scans forward,
and finally a level or two of scans backwards. For the 2x2, you should easily be able to
get the full table generation done in a few seconds.

In the scans, avoid division by arranging the loops correctly, and put the larger table
(permutation in this case) in the outer loop for cache effects. So you want something
like this (for a forward scan):

for (int cp=0; cp<CORNER_PERMS; cp++) {
   for (int mv=0; mv<NMOVES; mv++) {
      int srcn = cp * CORNER_ORIENTATIONS ;
      int dstbase = cp_move[cp][mv] * CORNER_ORIENTATIONS ;
      for (int co=0; co<CORNER_ORIENTATIONS; co++, srcn++) {
         if (table[srcn] == SEEK_VALUE) {
            int dstn = dstbase + co_move[co][mv] ;
            if (table[dstn] == UNSEEN)
               table[dstn] = SET_VALUE ;
         }
      }
   }
}

You can also hard-code the ultimate distance, prefill your table with this value, and skip
the final scan.

In a few seconds? (Even in Matlab? It is much slower than C, especially when it comes to iterations.)

I'm not familiar with symcoords (although I read about them in Kociemba's page about the Two Phase Algorithm), they seems a bit complicated for me.

By iterated depth search, you mean iterative deepening depth-first search (IDDFS), right? I can try that. Actually, I implemented Kociemba's Two Phase algorithm in Matlab maybe a year ago (based on his Mathematica code).

As for your code, I have a few questions. Is it true, that:
CORNER_PERMS = 7!
CORNER_ORIENTATIONS = 3^6
cp_move[cp][mv] is a number represents a permutation, which is the cp's permutation with an applied mv move (for example: if cp = 2 -> 1234576 + U = 2341576 -> 119, then cp_move[2] = 119)
co_move[co][mv] is the same with the orientations
SEEK_VALUE is the distance (from the solution), which is increasing during the forward scan
UNSEEN means we don't know it's distance yet,
SET_VALUE is current distance + 1

Is this technically the full code for a forward scan? For example,

for SEEK_VALUE = 0..10
[insert your code here]
endfor

will fill the table completely? (Of course this is just the "only forward" algorithm).

It seems a completely different strategy than mine.

Which is (for a completely forward scan):

for d = 0:10
    % For every state in the table
    for i = 1:ROWNUM
        % If the current state's distance equals to the current distance d
        if optimalTable(i) == d
            % Check its neighbours
            for r = 1:9
                newState = State2Number( Rotate( Number2State(i),r ) );
                if optimalTable(newState) == UNKNOWN
                    optimalTable(newState) = d+1;
                end
            end
        end
    end
end

Where State2Number(state) = 729*PermutationRankOfState + OrientationRankOfState,
and Number2State is the inverse (which actually uses pre-generated tables: all the possible permutations and orientations are listed lexicographically).

EDIT:
Boy, I should use move tables. I don't know why I didn't think about them earlier. :fp

Also, I don't want to hard-code too many things. The speed is not the ultimate goal; I also want to keep the code clean and understandable.

GRAND EDIT:

Aaaw, I think I understand it!

I rewrote your code to Matlab-like and add a little comment; but if I get it wright, it should be:

% for every possible permutation-number
for cp = 0:factorial(7)-1
    % for every movements we'll check the mv-neighbours
    for mv = 0:8 % U,U2,Ui,R,...,Fi
        srcn = cp * power(3,6); % source cube-number(base)
        dstbase = cp_move(cp,mv) * power(3,6); % mv-neighbour cube-number(base)
        
        % for every possible orientation-number
        for co = 0:power(3,6)-1
            % if our cubestate has a d distance
            if table(srcn) == d
                % calculate its mv-neighbour
                dstn = dstnbase + co_move(co,mv);
                % if neighbour's distance is unknown, then it is d+1
                if table(dstn) == -1
                    table(dstn) = d+1;
                end
            end
            srcn = srcn + 1; % next source cube-number
        end
    end
end

Re-arrange the cycles... Genious.

 

[Renslay]

o.O
I rewrote the code based on your suggestion. With a pure forward filling (no iterative depth search, no backward filling, just run the code from d = 0 to d = 10 and fill the table with d+1 values).

The runtime was 6.7 SECONDS.

What kind of sorcery is this?

(Okay, I understand the code, so I know why it works, but still my mind is blown. )

 

[AvGalen]

I am amazed how this topic changed from pure noob to pure genius. I can only imagine that learypost has either abandoned this topic or is now the quickest learning cube-mathematician in the world