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

[Stefan]

the number becomes significantly smaller if you try to get as many zeros as possible to the first digits of the number.

I very much doubt you can get any significant number of zeros this way (with a reasonable numbering of the states, i.e. you can't give the solved state the number 0 and its 18 neighbour states the numbers 1 to 18 etc or something silly like that).

(log2(3^(4.4*10^19)))/(3^(4.3*10^19))=0.477121 bits per cube state

Please check your calculation. It's massively wrong. First of all I don't understand why you divide by 3^(4.3*10^19) instead of by 4.3*10^19, and if you do the latter, you should get the already discussed log[sub]2[/sub](3)≈1.585, not 0.477121. And simply intuitively, why/how would a number expressed in a lower base ever become shorter?

 

[Stefan]

(please don't merge, my two posts are long and deal with separate issues/people)

Remember in all of this: the most obvious "optimization" is to store the distances for equivalence classes mod M+inv, so the "base" number is log(3)/log(2)/96 or 0.01651 bits per "state"---to start with.

I do remember (I mentioned symmetry earlier). But do you think the distance distribution changes significantly when you reduce by symmetry? (I really don't know, and you certainly know much better about this stuff than me)

I guess it's rather obvious by now: the further improvement I was thinking of was to not ignore the fact that the mod-3-distances distribution is not at all uniform. Thanks to 18 and 17 moves being very dominant, we have about these probabilities:

probability for mod-3-distance 0 is 0.6657235237807297
probability for mod-3-distance 1 is 0.05951019617882638
probability for mod-3-distance 2 is 0.27476628004044384

Now you can use arithmetic coding or Huffman (encoding 0 as one bit and 1 and 2 as two bits each):

arithmetic: 1.1451205786459624 bits per state
huffman: 1.3342764762192703 bits per state

With symmetry, I'd expect all of this to still work about the same, so dividing by 96 I get:

arithmetic: 0.011928339360895442 bits per state
huffman: 0.013898713293950732 bits per state

Spoiler: Python 3 program to calculate this stuff, numbers from cube20.org

import math
s = '''0	1
1	18
2	243
3	3,240
4	43,239
5	574,908
6	7,618,438
7	100,803,036
8	1,332,343,288
9	17,596,479,795
10	232,248,063,316
11	3,063,288,809,012
12	40,374,425,656,248
13	531,653,418,284,628
14	6,989,320,578,825,358
15	91,365,146,187,124,313
16	about 1,100,000,000,000,000,000
17	about 12,000,000,000,000,000,000
18	about 29,000,000,000,000,000,000
19	about 1,500,000,000,000,000,000
20	about 300,000,000'''
nums = s.replace(',', '').replace('about', '').split()

freqs = [0] * 3
while nums:
    s = int(nums.pop())
    d = int(nums.pop())
    freqs[d % 3] += s
    print(d, s)
print(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.log2(prob) * prob
    huffman += (1 + (freqs[i] < max(freqs))) * prob
print('arithmetic:', arithmetic, 'bits per state')
print('huffman:   ', huffman, 'bits per state')

 

[Dapianokid]

I very much doubt you can get any significant number of zeros this way (with a reasonable numbering of the states, i.e. you can't give the solved state the number 0 and its 18 neighbour states the numbers 1 to 18 etc or something silly like that).



Please check your calculation. It's massively wrong. First of all I don't understand why you divide by 3^(4.3*10^19) instead of by 4.3*10^19, and if you do the latter, you should get the already discussed log[sub]2[/sub](3)≈1.585, not 0.477121. And simply intuitively, why/how would a number expressed in a lower base ever become shorter?

I may not know exactly what I'm talking about as a whole, but I agree with Stefan in this case. I'm pretty sure that no number represented in binary is ever going to be any smaller when you take the digital representation of it and plug it into a higher base. 11 in binary is 3, but in decimal, it's eleven. 11 > 3

And that arithmetic is off. Don't mess with mathz, friend.

Trying to make the number smaller by arranging the "0" digits of the number is completely impractical, if not impossible. That's like saying that my hard drive stores more because it has a 1 bit at the start than yours which doesn't (hypothetically). It'd mean storing the system in a completely different way from numerical order, and that's suggesting it wouldn't be random and that you could find a formula to tell you which states satisfy n(mod3)=0... And that's also suggesting that you know how the states are arranged.

Could it be smaller by indexing only paths that lead to known states that are only, say, 5 moves away from solved? Or would that defeat the purpose or go against the concept?

 

[Stefan]

Could it be smaller by indexing only paths that lead to known states that are only, say, 5 moves away from solved? Or would that defeat the purpose or go against the concept?

I'm not exactly sure what you mean with indexing paths (we're indexing states), but I'm guessing the answer is it would.

How would you use that table? Remember the idea is to have a way to pretty much just look up a solution to a state, not doing any more serious cube space searching.

 

[Renslay]

I just wrote an optimal solver for the 2x2x2 in Matlab (HTM, but very easy to rewrite it for QTM as well).
2 bits / state, for a start. But I want to do the "5 state in 1 byte" trick.
It was fun to write, although the runtime of the table generation is a bit disappointing. 25-30 minutes! I know Matlab is not the fastest, but I expected somewhere around 5 minutes... Heck, even my 3x3x3 TwoPhase table generations (Kociemba's algorithm, also inMatlab) are faster than that.
For the record, I used BFS algorithm for filling up the table. Even the queue of the next-to-check states is just a fixed sized vector with "pointers" to the queue's actual beginning and end. Is there a better algorithm, or should I try to optimize the code a bit better? The naive "check every state with distance d in the table, check their neighbours, increase d" strategy took 40 minutes.

EDIT: By the way Stefan, nice trick with the distance probabilities. I guessed that the distance table (mod 3) is close to uniformly random, but actually, it is very far from that indeed. :fp

 

[Stefan]

I think I've seen people mentioning switching from forward to backward searching at some point (stop the BFS, start backwards from the remaining few undiscovered states or something like that), but I don't know how much it helps here.

Might also help to post your code here (and I'd be curious about it as well (not that I know Matlab much)).

 

[whauk]

I very much doubt you can get any significant number of zeros this way (with a reasonable numbering of the states, i.e. you can't give the solved state the number 0 and its 18 neighbour states the numbers 1 to 18 etc or something silly like that).

i already said this idea of optimising might not be important at all.

Please check your calculation. It's massively wrong. First of all I don't understand why you divide by 3^(4.3*10^19) instead of by 4.3*10^19, and if you do the latter, you should get the already discussed log[sub]2[/sub](3)≈1.585, not 0.477121. And simply intuitively, why/how would a number expressed in a lower base ever become shorter?

just mispasted something. it is correct now. (the result also according to wolframalpha)
can you please explain why you want to compare the length of numbers in different bases whereas i compare the length of "the number" in base 2 with the number of cube states?

Trying to make the number smaller by arranging the "0" digits of the number is completely impractical, if not impossible. That's like saying that my hard drive stores more because it has a 1 bit at the start than yours which doesn't (hypothetically). It'd mean storing the system in a completely different way from numerical order, and that's suggesting it wouldn't be random and that you could find a formula to tell you which states satisfy n(mod3)=0... And that's also suggesting that you know how the states are arranged.

well first of all if you want to store a number between 0 and 2^n-1 you know that you have to reserve n bits for it. but if you know that the first m digits (n>m of course) of that number are zeros you know that it is actually between 0 and 2^(n-m)-1 and therefore n-m bits will suffice. => less storage volume required.

i also suggested to only apply some inner automorphisms on the cube group and hope for some large quantitiy of zeros at the beginning. not that i want to arrange every zero to the start of the number. (i am not sure whether you meant that. at least it sounds like that).

 

[Renslay]

I think I've seen people mentioning switching from forward to backward searching at some point (stop the BFS, start backwards from the remaining few undiscovered states or something like that), but I don't know how much it helps here.

Might also help to post your code here (and I'd be curious about it as well (not that I know Matlab much)).

Yes, I remember that backward strategy mentioning somewhere. It can speed up the search when the table is already filled half. I just can't find the exact description of it...
It's something like:
0) Fill nearly half the table with BFS / naive algorithm starting with the solved state (distance 0).
1) pick up a state with unknown distance; let's note its distance as T.
2) for every neighbour, if the neighbour's distance is unknown, then its distance is T-1.
3) continue searching through neighbours: T-2, T-3, etc.
3) if we met a state with a known distance, T is calculable. E.g., a state with distance T-3 has a neighbour with distance 4, then T = 8.
4) Go back to 1) until the whole table is filled.

Or I remember it completely wrong? (That's why I didn't implement it.)

I will upload the source to somewhere (or should I write just the main algorithm here?), but first I want put some comment in it. Makes the code nicer.
(Don't worry, Matlab is very C-like, I found it much easier to read than Mathematica for example.)

 

[Stefan]

the result also according to wolframalpha

Well, wolframalpha is obviously very wrong there. Come on, look at that! I know you know how to simplify that expression properly.

can you please explain why you want to compare the length of numbers in different bases whereas i compare the length of "the number" in base 2 with the number of cube states?

Well, your number has 43 quintillion "digits" in base 3, and with log[sub]2[/sub](3[sup]43 quintillion[/sup]) you're computing the length of that number's base 2 representation. Or to put it in other words: In base 3 the states average 1.0 digits, and in base 2 you expect them to average less? It's like you have a certain amount of water in 3 liter buckets and then you pour it all into 2 liter buckets and expect to need fewer 2 liter buckets than you needed 3 liter buckets.

And the reason I brought this up is because this should have right away told you that there's something wrong with wolframalpha.

i also suggested to only apply some inner automorphisms on the cube group and hope for some large quantitiy of zeros at the beginning. not that i want to arrange every zero to the start of the number. (i am not sure whether you meant that. at least it sounds like that).

I know what you suggested. That's why I said I "doubt you can get any significant number of zeros this way" (and since "this way" isn't necessarily very clear and since we obviously *can* introduce a large quantity of starting zeros or other very compressible tables when we use silly numberings, I had to distinguish them from yours).

 

[Stefan]

Or I remember it completely wrong? (That's why I didn't implement it.)

It starts getting weird in step 2, because the neighbour might have distance T or T+1 instead of T-1, no?

But I barely remember it being mentioned, I'd have to think about how to actually do it

 

[Renslay]

It starts getting weird in step 2, because the neighbour might have distance T or T+1 instead of T-1, no?

But I barely remember it being mentioned, I'd have to think about how to actually do it

Hm, right, that does not make sense... What if we start from a known furthest state (T = 11)?
All its neighbours is T = 10 (cannot be 11 nor 9), then their neighbours (T = 9 if not visited yet, because cannot be 10 or 11, since it's not visited), etc. And forget about the other steps in my description.
So:
Start forward DFS/naive with solved state (d = 0). Fill half the table.
Start backward DFS/naive with a hardest state (d=11). Just like the forward case, only with decreasing distances. Finish the table.

EDIT:
Nah, still not good :fp. I just discovered that a neighbour of a T = 11 can be also T = 11. Example:
R U' R2 U' F' R' U F2 R U' F (11f*)
its neighbour:
R U' R2 U' F' R' U F2 R U' F U (12f)
which equals to:
R2 U R' F U F2 R' U F U2 F' (11f*)

I guess it's only work if the hardest (furthest) case is unique.

 

[Stefan]

I guess it could be like this:

1) BFS until all distance-8 states are discovered. (edit: fixed from "distance-9")
2) Check all remaining states. If they're neighbors of a distance 8 state, mark them as distance 9.
3) Check all still remaining states. If they're neighbors of a distance 9 state, mark them as distance 10.
4) Go on like that until no states are left (or since we already know that 11 is maximum, just mark the rest as distance 11).

So actually still forward, but from the perspective of the remaining states rather than from the perspective of the already discovered states.

 

[Renslay]

I guess it could be like this:

1) BFS until all distance-9 states are discovered.
2) Check all remaining states. If they're neighbors of a distance 8 state, mark them as distance 9.
3) Check all still remaining states. If they're neighbors of a distance 9 state, mark them as distance 10.
4) Go on like that until no states are left (or since we already know that 11 is maximum, just mark the rest as distance 11).

So actually still forward, but from the perspective of the remaining states rather than from the perspective of the already discovered states.

Not sure if that can speed up much, since getting to a finished distance-9 usually requires the most time (83% of the table is finished). But I can give it a try. My guess is it shorts down a few minutes - but it wouldn't be the first time I'm wrong.

EDIT: I don't understand step 1 + 2: if all distance-9 discovered, how can be a remaining state with a distance-8 neighbour (being a distance-9 itself)?

 

[rokicki]

No, the distance distribution is almost exactly the same when symmetry and inverse symmetry is taken into account.
This is easy to see; symmetrical and antisymmetrical positions taken together account for a vanishingly small number
of positions.

I wasn't thinking Huffman coding at all (although I do know about it); I was thinking more along the lines of storing
all four positions related by turns of the up face together. The distances of these four are closely related, and
together probably take much less space. You can combine up and down face turns as well to store 16 related
positions together and get even more compression. But this makes the mod M+inv stuff messy. I don't know
how messy, though.

And then I started thinking of storing only distances of the even positions, but quickly ran off into the weeds.

I'll bet there are some cool tricks you could play in this space to get very good compression while still being
able to find a solution with only a small number of, say, memory lookups. After all, a cache line of 64 bytes
holds a lot of bits.

 

[whauk]

Well, wolframalpha is obviously very wrong there. Come on, look at that! I know you know how to simplify that expression properly.

well who expects a formula with terrifyingly *huge* numbers to drastically simplify just like that...? shame on that habit of spamming everything into wolframalpha

Well, your number has 43 quintillion "digits" in base 3, and with log[sub]2[/sub](3[sup]43 quintillion[/sup]) you're computing the length of that number's base 2 representation. Or to put it in other words: In base 3 the states average 1.0 digits, and in base 2 you expect them to average less?

yup seeing it now. thanks.

I know what you suggested. That's why I said I "doubt you can get any significant number of zeros this way" (and since "this way" isn't necessarily very clear and since we obviously *can* introduce a large quantity of starting zeros or other very compressible tables when we use silly numberings, I had to distinguish them from yours).

this paragraph was still directed at dapianokid who, i think, did not quite understand my idea. i agree with you that it will probably not lead to any significant difference.

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

 

[Stefan]

EDIT: I don't understand step 1 + 2: if all distance-9 discovered, how can be a remaining state with a distance-8 neighbour (being a distance-9 itself)?

Ah crap, I inserted that step 2 because I wanted to show that kind of step twice, and forgot to adapt step 1. Fixed, thanks.

 

[Renslay]

Ah crap, I inserted that step 2 because I wanted to show that kind of step twice, and forgot to adapt step 1. Fixed, thanks.

Okay, now it seems reliable. I give it a shot tomorrow. :tu
Strange, but the naive table filling seemed faster in the beginning, and the queue-based BFS was faster in the end... So I'll try the naive 2-way table filling.

 

[Stefan]

shame on that habit of spamming everything into wolframalpha

Exactly what I thought . Right after your first post I had actually checked with wolframalpha myself and had seen its mistake, but I wanted to give you another chance to notice it yourself. Didn't quite work, but third time was a charm, and now I'm sure you won't blindly trust it as much anymore . I'm actually a little shocked to see that mistake, btw, it's like wolframalpha wasn't smart enough to do that simple simplification itself and I would've expected it to be.

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

As Tom just pointed out when he ninja'd you, they're rare. Also, we don't know how it affects the distribution. It could make it *more* uneven, maybe making the final bits per state number a little *lower*? Edit: Nah, while that could decrease it, I guess the *increase* due to dividing by less than 96 is stronger.

 

[AvGalen]

I get the feeling you don't know what we're doing. We're already kinda using zero bytes to encode the entire state.

Explanation for those who don't know what we're talking about: Instead of storing states along with their solutions, we're storing *neither*.

We encode a state by turning it into a number from 0 to n-1, where n is the number of possible states (about 43 quintillion for 3x3 if we ignore symmetry). Now instead of *storing* that number, we just *use* it as a pointer into a large list, one list entry for each state. And such an entry is not a solution, not even just a move, but only the distance to the solved state modulo 3. So if a state can optimally be solved in 17 moves, we store "2" for it. Then to find a solution for a state, we compare its mod3dist to those of its neighbour states to determine a move that gets us closer to solved, and repeat until we're at solved.

Since each such mod3dist value is 0, 1 or 2, we can encode it in two bits. But since two bits also allow the value 3 and we're never using it, we can do better. For example we can combine five consecutive values into a number from 0 to 3[SUP]5[/SUP]-1=242, which is less than 2[SUP]8[/SUP]-1=255 so we can store the values for five states in eight bits (one byte), averaging 8/5=1.6 bits per state. Now here we're never using the numbers 243 to 255 that eight bits also allow, so we're still wasting storage opportunity. This then is where arithmetic coding comes in, which kinda really uses *fractions* of bits and we don't have any such waste anymore.

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?

 

[Renslay]

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?

I have a 2x2x2 solver in Matlab, written yesterday. Here is the table which contains all the information for optimally solving it:
0 1 1 1 0 1 1 1 0 1 1 1 0 2 2 1 1 2 1 1 1 1 2 1 0 2 2 1 2 1 0 2 0 1 1 2 2 2 2 2 1 0 1 0 1 1 2 2 0 0 0 2 1 0 1 1 2 1 2 1 0 0 2 1 2 2 2 0 1 0 0 0 2 2 2 1 1 0 2 0 1 1 1 1 0 2 2 1 1 2 1 1 2 2 0 0 1 2 2 1 (...) 2 0 1
(Yes, actual table).
The number of the digits is 3674160 ( = 7!*3^6)
Each digit represent a certain state's optimal distance from the solution modulo 3.
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*)

How to use the table? For a given scrambled state, I can say its state number. So here is the actual example:
Scramble: R2 F2 R2 F2 U2 F R.
It's state number is 2368996, and the 2368996-th number in the table is 2.
Now I'm looking for a neighbour which has the table number 1, because that's mean that this neighbour is 1 step closer to the solution. This requires 9 searches in the table. This neighbour will be the R' neigbour: state number 2514142, table number 1.
Now I'm looking for further, the next neighbour, which has a table number 0. It would be the F' neighbour (2461105-th state).
The next neighbour should has a table number 2. Continue this searching, I get:
State numbers:
2368996, 2514142, 2461105, 221617, 86752, 1 (note that 1 is the solve state!)
Table numbers:
2 1 0 2 1 0 (this is what we expected / searched: a decresing series of distance numbers in the table modulo 3, until the solved state reached)
Neighbours's path through the states:
R' F' U2 R2 F2
And this is our optimal solution.

Yes, this method needs more than one search in the table. But what is the worst case? The worst case is to search for all the neighbours during the path, and the original scrambled state is the furthest: 11*9 (furthest distance * number of neighbours) = 99 searches.
But if one search is negligible (in runtime), it's a fraction of a fraction of a second, then 99 searches (worst case!) still can be considered as an immediate search. For a 3x3x3, it would be 20*18 = 360 searches; which is still small.