# God's Second Number?



## elrog (Jul 3, 2014)

I posted this post a while back in this thread. It is the last post on page 7 if you have 10 posts per page.


elrog said:


> I would like to clarify something in your post. You said that X moves have the same chance to give a random state, but some states are more likely to occur than others due to symmetries. On a supercube, every state has equal probability. I think what you were meaning though is that X moves and Y moves both have the same chance to come up with the same state.
> 
> Lets say you start at any particular random state on the cube. If you apply exactly 20 moves to the cube, there may be cases that are still unreachable. Take a state that is 19 moves optimally from the state you started at. That state is only reachable if it is solvable in 20 moves as well as the optimal 19 moves. I am fairly certain that there are 19 move optimal solutions that cannot be solved in exactly 20 moves because there are also 5 move solutions which cannot be solved in 6 moves.
> 
> ...



I thought about this a little more and realized something. If any position of the cube can be reached in exactly 35 (this is just an example) moves (HTM because that's how God's Number was found), then you can reach any position starting at any position, and any position can be reached with any number of moves above 35 moves because you can just apply any number of moves to the starting state and apply a different set of 35 moves.

After realizing this, I was wondering just what that number may be. To get an idea I took a look at the superflip (a well known position that requires 20 moves optimally HTM). An optimal solution for the superflip is U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2. Because of the symmetry of this position, any move you make makes the position closer to solved.

If you do a single move to the superflip position, you make a 19 move solution possible, but there is also a 20 move position possible as well because you can cancel at the beginning or end of the superflip alg because it has a 90 degree turn on one end and a 180 degree turn on the other. Doing any two moves on adjacent sides also can cancel out to give a 20 move solution. If you do any two moves on opposite sides, you will not be able to cancel both of them out and no 20 move solution is possible.

This would verify that 21 moves is the lower bound as long as there is no other optimal solution for the superflip that is not an inverse or mirror of the given algorithm (I don't think there is). Going by this logic, I could go further but I would likely run into other 20 move optimal positions.


----------



## Robert-Y (Jul 3, 2014)

Are you asking what is the maximum distance between any two states of the Rubik's Cube in HTM?

It's rather unclear to me what you asking for (if anything)... :S


----------



## 10461394944000 (Jul 3, 2014)

Robert-Y said:


> Are you asking what is the maximum distance between any two states of the Rubik's Cube in HTM?
> 
> It's rather unclear to me what you asking for (if anything)... :S



i wasnt sure if hes asking for that (which is 20) or the smallest N where every state has at least 1 solution of length N (i wouldnt be surprised if that is also 20)


----------



## elrog (Jul 3, 2014)

10461394944000 said:


> the smallest N where every state has at least 1 solution of length N



That is what I am looking for in HTM. I think it is over 20 by a little bit. If it was 20, you are saying every 19 move strong position is also solvable in exactly 20 moves. It is obvious that you cannot solve every 5 move strong position in 6 moves exactly.

Edit:
I have found multiple 20 move solutions to the superflip, so I don't think it is a good candidate for extended searches.

I have moved on to checking this scramble: F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2

I have found 21 and 22 move solutions to this scramble, but no other 20 move solutions yet. If I can confirm there are no other 20 move solutions, I can make 21 a lower bound.


----------



## mark49152 (Jul 3, 2014)

elrog said:


> I have found 21 and 22 move solutions to this scramble, but no other 20 move solutions yet. If I can confirm there are no other 20 move solutions, I can make 21 a lower bound.


Why?


----------



## porkynator (Jul 3, 2014)

Let's say you have an N-moves solution for a scramble. Let's suppose its last move is U.
You want an (N+1)-moves solution? Change the last move to U2 U'. You want an (N+2)-moves solution? Add R2 R2 at the end. And so on.
Conclusion: you can solve every position in exactly N moves for each N >= 20.


----------



## elrog (Jul 3, 2014)

.. I never dreamed I would have to specify that I don't want to do multiple turns of the same layer in a row...

@ mark - If there is only one 20 move solution, it will be possible to slightly change the scramble to a new one so that the new solution (which includes the old solution with a slight change) is longer. There will undoubtedly be a completely unique shorter solution to the new scramble too because God's number is 20. If there are many 20 move solution to a case, you will have to change the scramble so much (to make a new, longer solution for each old solution) that you will end up introducing a completely unique 20 move scramble.

I hope that made sense.


----------



## qqwref (Jul 3, 2014)

I don't think that makes sense, no. You will have to formalize it or find a 19f* position which has no 20-move solutions. If what you're saying is true it should be easy to find 

I think for this problem it is definitely important to specify what you mean by move sequence. The distinction does not matter for God's Algorithm since it is not affected by suboptimal versions of move sequences. I assume you are talking about a canonical move sequence (what we used in scramblers), i.e. a move sequence which cannot be shortened by repeated application of the operations (a) combine two adjacent turns of the same face, and (b) swap two adjacent turns on the same axis.

If every position does turn out to have a 20 move solution, I propose a second question: what is the largest N for which there is an Nf* position with no (N+1)-move canonical solution?


----------



## mark49152 (Jul 3, 2014)

@elrog: Sorry, I don't follow your logic at all, even after re-reading several times. It's a very interesting question though.

If a 20f* position really has only one optimal solution, that means that 17 of its adjacent positions are also 20f* (the other one would be 19f* of course). Statistically that seems very, very unlikely. I wonder if it would be meaningful to predict the probability from the distribution tables for optimal solutions? My intuition makes me suspect that 20f* positions are mostly little individual islands in a sea of <=19f* positions.

As qqwref said, I think that to prove that 20 isn't the answer, you have to find a position with no 20f solution. I'm not sure why that position would have to be 19f* but let's assume it is. You'd effectively have to prove that it has no 19f* neighbours, and none of its 18f* neighbours have 19f solutions. And so on. I have no idea how that could be done but it sounds difficult and impractical.

Alternatively you could prove that for a certain N, any N-move canonical sequence can be replaced with an (N+1)-move canonical sequence. Obviously the lower the N the easier the search or proof, but if you could prove it for any N<=19 then you're done and 20 is your answer. I have no idea how hard that would be. Perhaps it could be simplified by reducing the subgroup, e.g. applying to non-canonical sequence of quarter turns?


----------



## qqwref (Jul 3, 2014)

I ran some CubeExplorer while at work and luckily came up with this position: B' R D' B2 L' F2 U' B2 D' F L B2 R D2 L' (15f*). There are 17f solutions (at least three of them) but no 16f solutions.

Note that this does not by itself prove anything about God's Second Number


----------



## mark49152 (Jul 3, 2014)

qqwref said:


> I ran some CubeExplorer while at work and luckily came up with this position: B' R D' B2 L' F2 U' B2 D' F L B2 R D2 L' (15f*). There are 17f solutions (at least three of them) but no 16f solutions.
> 
> Note that this does not by itself prove anything about God's Second Number


Oh well, that kills my second idea . I wonder if that property can be determined by analysis of a sequence? For example, would a sequence have to have certain characteristics in order to not be replaceable in whole or part by a different sequence one move longer?


----------



## elrog (Jul 3, 2014)

I know that I have to find a position with no 20 move solution in HTM to prove that this number is not 20. What I described is just how I plan on finding one after my cube explorer search finishes. I have set it up with the "hardest" case and 1 piece greyed out so it will show all solutions. It as at 17 moves after over 12 hours. I will have to wait until it gets to 21 to have the information I want.

I have been looking through 20 move positions that I found here.

So far, comparing the seemingly harder scrambles to the easier ones, the harder scrambles seem to be lower move counts in QTM. Is there any position which takes 20 moves both HTM and QTM?


----------



## qqwref (Jul 3, 2014)

elrog said:


> I know that I have to find a position with no 20 move solution in HTM to prove that this number is not 20. What I described is just how I plan on finding one after my cube explorer search finishes. I have set it up with the "hardest" case and 1 piece greyed out so it will show all solutions. It as at 17 moves after over 12 hours. I will have to wait until it gets to 21 to have the information I want.


Bad news, each extra move takes something like 15 times as long. You can expect to wait months or years to get up to 21. Maybe try the Huge Optimal Solver or ACube instead?



elrog said:


> So far, comparing the seemingly harder scrambles to the easier ones, the harder scrambles seem to be lower move counts in QTM. Is there any position which takes 20 moves both HTM and QTM?


I don't think people know much about QTM (not even a good guess at God's Number). I know of a 20h/26q but not a 20h/20q, although I'm sure there is one.


----------



## elrog (Jul 4, 2014)

I thought our good guess at Gods number was 26 for QTM and 18 for STM.


----------



## cuBerBruce (Jul 4, 2014)

elrog said:


> Is there any position which takes 20 moves both HTM and QTM?



Superfliptwist. Source: http://www.cflmath.com/~reid/Rubik/h_symmetric.html
U R F' B U' D' F U' D F L F' L' U R D F U R L (20q*, 20f*)

There is also this post that gives some positions that are the same distance in both FTM and QTM.
http://cubezzz.dyndns.org/drupal/?q=node/view/174

EDIT: And by the way, God's number in QTM has been narrowed down to either 26 or 27, although it's almost certain to be 26.


----------



## qqwref (Jul 4, 2014)

When you say narrowed down, you mean you are sure there are no 28q* positions? How do we know this?


----------



## cuBerBruce (Jul 4, 2014)

qqwref said:


> When you say narrowed down, you mean you are sure there are no 28q* positions? How do we know this?



Yes, that's the claim. http://cubezzz.dyndns.org/drupal/?q=node/view/533

And perhaps 27 will be ruled out by the end of the summer.


----------



## 10461394944000 (Jul 5, 2014)

cuBerBruce said:


> Yes, that's the claim. http://cubezzz.dyndns.org/drupal/?q=node/view/533
> 
> And perhaps 27 will be ruled out by the end of the summer.



do you know any positions that are both 20f* and 26q*?


----------



## EMI (Jul 5, 2014)

cuBerBruce said:


> Superfliptwist. Source: http://www.cflmath.com/~reid/Rubik/h_symmetric.html
> U R F' B U' D' F U' D F L F' L' U R D F U R L (20q*, 20f*)



Thanks for the list, I always thought only "id", Superflip and both Supertwists were invariant. Cool!
Edit: huh? I thought x invariant meant x * y * x' = y here. Seems to be something different.


----------



## elrog (Jul 5, 2014)

Thank you Bruce.

I am currently not at home and won't be for a few days. I did leave cube explorer running when I left though. I was trying to see what all of the symmetry options did. I left it trying to find an identity with 6 colors selected. All I know is that about 8 hours in, it had no progress.

Does the number of colors mean there is at least that many colors on each side? So far it seems this way.


----------



## cuBerBruce (Jul 5, 2014)

10461394944000 said:


> do you know any positions that are both 20f* and 26q*?



That's an easy question. There is essentially only one known 26q* position (actually 3 symmetrically equivalent positions) and that position is indeed a 20f* position. I don't believe there is a *manuever* for it, however, that is both 26q* and 20f*.

Reid's site lists:

U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B' (26q*, 21f)
F U2 R L D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q) 

A 26q*/26f maneuver (for whatever that's worth) is: U F U F U' R D' F L D' F B' D' F D' L U F' U' F D' F U' F' R' D'



EMI said:


> Thanks for the list, I always thought only "id", Superflip and both Supertwists were invariant. Cool!
> Edit: huh? I thought x invariant meant x * y * x' = y here. Seems to be something different.



An element of the cube group (g) is invariant under a cube symmetry (m) if:

m' g m = g

Note that the cube symmetry group has 48 elements: 24 whole cube rotations (including the identity) and 24 refelections.

So, for example, we let g = U R F' B U' D' F U' D F L F' L' U R D F U R L and let m = x y; then

m' g m = y' x' U R F' B U' D' F U' D F L F' L' U R D F U R L x y

results in the same position as just applying:
U R F' B U' D' F U' D F L F' L' U R D F U R L = g

Hence, U R F' B U' D' F U' D F L F' L' U R D F U R L is invariant under the cube symmetry x y.


----------



## rokicki (Jul 8, 2014)

cuBerBruce said:


> I don't believe there is a *manuever* for it, however, that is both 26q* and 20f*.



This is fascinating! I tried to come up with a quick counterexample, generating a few hundred 20f* solutions
and a few hundred 26q* solutions, and could not come up with a solution that is both 20f* and 26q*.

I can't think of a reasonable explanation for this, and I know this position has just an incredible number of both
20f* and 26q* solutions.

So, can anyone either prove there is no such solution, or find a counterexample?

Is there a concise explanation for this?


----------



## cuBerBruce (Jul 9, 2014)

rokicki said:


> This is fascinating! I tried to come up with a quick counterexample, generating a few hundred 20f* solutions
> and a few hundred 26q* solutions, and could not come up with a solution that is both 20f* and 26q*.
> 
> I can't think of a reasonable explanation for this, and I know this position has just an incredible number of both
> ...



I stated my belief that there are no 20f*/26q* maneuvers based on:

1) Reid's page did not list a maneuver that was both 26q* and 20f* and I believe he would have if he had found one.
2) About 2 years ago, I believe I identified all symmetrically distinct canonical 26q* maneuvers for the known 26q* position. I counted 16738 such maneuvers. I checked these for how long they are in FTM, and found all of them to be at least 21 moves.

I've now generated the distribution of these maneuvers in terms of FTM length. That distribution is:


```
FTM length   count
    20           0
    21         380
    22         770
    23        1894
    24        3540
    25        5514
    26        4640
```

Possibly I could have missed some maneuvers in my original search. You're welcome to try to find an error in my data.


----------



## rokicki (Jul 9, 2014)

Wow. I decided to check it the other way around, finding all 20f*'s
and seeing where they showed up in the QTM metric.

Here are the results.

Every single 20f* solution to superflip-fourspot has exactly eight
double twists (and is therefore 28q).

There are something like 1600 of them. Every single one has
exactly eight half-twists. None with six, none with ten, none with
twelve.

There's got to be a logical explanation for this.


----------



## Stefan (Jul 9, 2014)

As I don't think I've seen a proof for the existence of God's Second Number, I'll try one (and an upper bound):

You can replace every F turn (other turns similarly) in a solution with
F U D R2 L2 U' D' B' U D R2 L2 U' D' F (15 moves)
or
F U2 R2 D2 L' B' L2 B L B R D2 R U2 L2 F (16 moves)
and this doesn't introduce cancellations. So if you have an optimal solution of length m and replace a move like this m times with 15 moves and 20-m times with 16 moves, you have a solution with m+14m+15(20-m)=300 moves and thus *all states are solvable in exactly 300 moves*. And since there is a natural number with this property, there also is a smallest one, which is God's Second Number.

(The zero-moves solution of the solved state doesn't have moves to replace, but there are identity algs with 10 moves you can start with.)



elrog said:


> Because of the symmetry of [the superflip] position, any move you make makes the position closer to solved.



I don't think the symmetry alone rules out that a quarter turn would get you closer to solved but a half turn wouldn't (or vice versa).



elrog said:


> If [from superflip] you do any two moves on opposite sides, [...] no 20 move solution is possible.



I must misunderstand, as for example
(U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2) (F2 B)
obviously has a 20 move solution. Please clarify.


----------



## Lucas Garron (Jul 9, 2014)

Stefan said:


> You can replace every F turn (other turns similarly) in a solution with



1. Very nice argument!
2. I think you also need to handle half-turns. I don't think your replacements allow us to expand R2 U2 into 300.

Perhaps use there?

F R U R' F' U2 L' U' L F U2 F (12h)
F R2 F2 R2 F2 R2 F2 R2 F2 R2 F2 R2 F' (13h)

EDIT: Never mind, we could simply replace the last F in each of your algs with F2.


----------



## Stefan (Jul 9, 2014)

Ah yeah, I don't know why I packed Do-F-without-turning-F algs between the F turns, I should have just packed identity algs between them. Here are shorter ones:

F2 U2 R2 L2 U2 D2 R2 L2 D2 F' (replaces F, adds 9 moves)
F2 U R2 L2 U2 D2 R2 L2 U D2 F' (replaces F, adds 10 moves)

If your optimal solution has fewer than 13 moves, first append 8-move-identities so you have a solution with m=13..20 moves. Then do m-13 replacements adding 9 moves and 20-m replacements adding 10 moves and you have m+9(m-13)+10(20-m)=83 moves.

Then again, 83 of course isn't really better than 300.


----------



## Stefan (Jul 9, 2014)

Um, we can also reduce the variation instantly by adding more moves:

F2 U2 R2 L2 U2 D2 R2 L2 D2 F' (replaces F, adds 9 moves)
F2 U R2 L2 U2 D2 R2 L2 U D2 F' (replaces F, adds 10 moves)
F2 *R* U2 R2 L2 U2 D2 R2 L2 D2 *R'* F' (replaces F, adds 11 moves)
F2 *R* U R2 L2 U2 D2 R2 L2 U D2 *R'* F' (replaces F, adds 12 moves)
F2 *U R* U2 R2 L2 U2 D2 R2 L2 D2 *R' U'* F' (replaces F, adds 13 moves)
F2 *U R* U R2 L2 U2 D2 R2 L2 U D2 *R' U'* F' (replaces F, adds 14 moves)
F2 *R U R* U2 R2 L2 U2 D2 R2 L2 D2 *R' U' R'* F' (replaces F, adds 15 moves)

So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves. Thus GSN is at most 28.


----------



## EMI (Jul 9, 2014)

cuBerBruce said:


> An element of the cube group (g) is invariant under a cube symmetry (m) if:
> 
> m' g m = g
> 
> ...



Ok thanks, I thought it was about turns.


----------



## Stefan (Jul 9, 2014)

Actually, since it's that easy to build identities for any number of moves from 8 and starting with any side, just take an optimal alg and append an appropriate identity to get to 28 moves. (And now it's so obvious that I'm sure someone must have said this before somewhere.)


----------



## cuBerBruce (Jul 9, 2014)

Stefan said:


> I don't think the symmetry alone rules out that a quarter turn would get you closer to solved but a half turn wouldn't (or vice versa).



Correct. For example, Pons Asinorum is also completely symmetrical but doing U from Pons Asinorum doesn't get you closer to solved in FTM. The statement would be correct for QTM. For FTM, it can be claimed that you at least can not get farther from solved with one turn (of course, this is for the stated symmetry condition).

Given that superflip is also in its own conjugacy class, any cyclic shift of a superflip maneuver is also a a superflip maneuver. Since a known optimal superflip maneuver contains both quarter turns and half turns, we can use this (along with the symmetry) to infer that any half turn or quarter turn from superflip gets us closer to solved.

I note that the Wiki page for superflip is making essentially the same false claim:


> Also, because the superflip is completely symmetrical but not solved, any move will bring it to a position that is easier to solve.


----------



## elrog (Jul 10, 2014)

Stefan said:


> I must misunderstand, as for example
> (U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2) (F2 B)
> obviously has a 20 move solution. Please clarify.



I was wrong in saying that no 20 move solution is possible. What I should have said is that if there is a 20 move solution it will be unrelated to the 20 move solution you started with. My thinking was that if you find a 20 move strong state that is isolated enough, you could do this and not run in to other 20 move solutions.

Nice job on establishing an upper bound.



rokicki said:


> Wow. I decided to check it the other way around, finding all 20f*'s
> and seeing where they showed up in the QTM metric.
> 
> Here are the results.
> ...



May I ask how you found every 20 move sequence and checked the similarities in all of them? I assume you know something of computer programming. It seems as if everyone is accomplishing things that I can't imagine trying to find usually through being skilled in programming.

Edit:
Going by Stefen's logic, I have come up with the following move sequence: B2 D2 U2 B2 F2 D2 U2. You can add F2 to the beginning and any F move you want to the end to replace an F move.

This would by a 9 move (so you add 8 moves) sequence with an F at the beginning and end, so that lowers the upper bound to 27.


----------



## qqwref (Jul 10, 2014)

elrog said:


> I have come up with the following move sequence: B2 D2 U2 B2 F2 D2 U2. You can add F2 to the beginning and any F move you want to the end to replace an F move.


I note that your sequence has a B2 right after the first F2. I was going to post saying that that could create cancellations (e.g. B2 F => B2 F2 B2 D2 ...) but I realized you could just put the B2 after the F move instead of before it. So we're still adding the right number of moves.

If we want to improve the bound to 27, though. 20-move sequences still need to have 7 moves added.
- If the 20f* sequence ends with F without a B move before it, replace it with F' B2 U2 D2 F2 B2 U2 D2.
- If the 20f* sequence ends with F2 without a B move before it, replace it with B U2 D2 F2 B2 U2 D2 B.
- If the 20f* sequence ends with B F, replace it with F' B U2 D2 F2 B2 U2 D2 B2. For B F', just treat it like F2 + B F.
- If the 20f* sequence ends with B F2, replace it with F R2 L2 F2 B2 R2 L2 F' B'.
- If the 20f* sequence ends with R B2 F2, replace it with R' U D' F2 L2 R2 F2 D U' R2.
- If the 20f* sequence ends with R2 B2 F2, replace it with R' B R' U' B2 L' B' L U F2.
(This should cover everything, up to symmetry and mirroring.)


----------



## rokicki (Jul 10, 2014)

elrog said:


> May I ask how you found every 20 move sequence and checked the similarities in all of them? I assume you know something of computer programming. It seems as if everyone is accomplishing things that I can't imagine trying to find usually through being skilled in programming.



I ran my optimal solver on the position and it found all the distance-20 solutions.

Initially I did something faster; I found all neighbors, eliminated symmetry-equivalent
positions reducing the count from 18 to 4, and then found all distance-19 solutions for
these positions. But later I just ran the optimal solver on the position directly and
asked it to find all solutions.


----------



## elrog (Jul 10, 2014)

Do you have a fast optimal solver? I would love to get a faster one but I was lucky my parents let me get the regular cube explorer.

@ qqwref - Stefen found a position that adds nine moves and said that makes the upper bound 28. So adding 7 moves makes the upper bound 27. By my logic, I came to the same conclusion.

Here's my thinking: For there to be a second god's number, there has to be a 19 move strong or lower position that cannot be solved in 20 moves exactly. If you can add 8 or more moves to any position and keep the same position, you can turn a position that proves there is a second god's number into a 27 move strong position or lower if it is less than 19 moves strong.

I am in the middle of lowering the upper bound down to 25.


----------



## qqwref (Jul 10, 2014)

elrog said:


> @ qqwref - Stefen found a position that adds nine moves and said that makes the upper bound 28. So adding 7 moves makes the upper bound 27. By my logic, I came to the same conclusion.


That's not quite valid, though. Stefan said: "So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves". But there is no 7-move identity to add, and your sequence adds 8 moves. So you missed the case of taking a 20-move algorithm and getting a 27-move algorithm. As for the paragraph you typed after the above quote, no idea what you're saying


----------



## elrog (Jul 10, 2014)

qqwref said:


> That's not quite valid, though. Stefan said: "So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves". But there is no 7-move identity to add, and your sequence adds 8 moves. So you missed the case of taking a 20-move algorithm and getting a 27-move algorithm. As for the paragraph you typed after the above quote, no idea what you're saying



I will try to explain myself better then. Lets pretend we find a position that is 19 moves strong and cannot be solved in 20 moves exactly. If we rotate the algorithm so that it ends it with an F move, we can replace the F at the end with a sequence that adds 8 moves. This would give us a 27 move sequence that solves the same cube state.

So for such a position to exist, there has to be a 27 move sequence for it making 27 the upper bound.

Stefen showed that we can add any number of moves above 8 in place of an F at the end. This would make the upper bound of 27 hold true for states that are 18 moves strong and cannot be solved in exactly 20 moves.


----------



## qqwref (Jul 10, 2014)

It sounds like you're just saying that if we have an 18- or 19-move sequence we can make it 27 moves. That's pretty clear. The thing I think you're glossing over is how to turn a 20-move sequence into a 27-move sequence. Remember, to have an upper bound, we need to be able to write all sequences as that number of moves, even 20f* ones.


----------



## rokicki (Jul 10, 2014)

elrog said:


> Do you have a fast optimal solver?



Yes; I believe I have the world's fastest
optimal solver.


----------



## Renslay (Jul 10, 2014)

rokicki said:


> Yes; I believe I have the world's fastest
> optimal solver.



Is it public?

I just run the HugeOptimalSolver of CubeExplorer 5.00s on three random cubes. All three of them were 18f*, and the runtimes were 0:50, 1:30 and 2:56. The superflip took 3:40 (it reached depth 18 much faster, I think because of the high level of symmetry.)


----------



## Stefan (Jul 10, 2014)

qqwref said:


> (This should cover everything, up to symmetry and mirroring.)



Ugly, but yeah I think you got them all 



elrog said:


> For there to be a second god's number, there has to be a 19 move strong or lower position that cannot be solved in 20 moves exactly.



I don't see why.

We already know that GSN exists, so you're claiming there is a position that cannot be solved in exactly 20. Was that proven somewhere?



elrog said:


> a position that proves there is a second god's number



This makes no sense to me. How could a single position prove that?


----------



## Tempus (Jul 10, 2014)

Stefan said:


> This makes no sense to me. How could a single position prove that?


I think he means a counterexample to disprove the notion that it's equal to 20, like the original.


----------



## elrog (Jul 10, 2014)

qqwref said:


> That's not quite valid, though. Stefan said: "So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves". But there is no 7-move identity to add, and your sequence adds 8 moves. So you missed the case of taking a 20-move algorithm and getting a 27-move algorithm. As for the paragraph you typed after the above quote, no idea what you're saying



If we are trying to find this number, and we know it is not a 20f* state if it does exist, why should we include 20f* states?

@ Stefen - of course there has to exist such a number, but if it is 20, I wouldn't call it a second number. A position could be a counterexample as Tempus said.

Edit: After some further thinking, I realize why 20f* states should be counted.

I have finished a proof for what I was thinking before would make the upper bound 25, but it actually only makes the upper bound 26.

If a sequence ends in U' R', you can replace the U' R' with F2 L F L' U' F2 R' F' unless the move before the U' R' is an F2. In that case, you can replace it with R2 F D R' D' R2 F' U'. This lets you replace the last 2 moves with an 8 move solution adding 6 moves. I have done this with every combination of 2 moves.

Shorter sequences have been given if there were any.



Spoiler: combinations



U' R' (2,2)
F2 L F L' U' F2 R' F' (8,10)
R2 F D R' D' R2 F' U' (8,10)

U2 R' (2,3)
D2 L2 R2 D2 U2 L2 R (7,13)
L' R B2 R' B2 L R' U2 (8,11)
B U B' R' U2 F' U' F (8,9)

U R' (2,2)
R' U2 F' L' U L U2 F (8,10)
B' R2 D' R' D B R2 U (8,10)

U' R2 (2,3)
D2 U L2 R2 D2 U2 L2 (7,13)
D' F2 U F2 D U' R2 U' (8,11)
R2 D' U F2 U' F2 D U' (8,11)

U2 R2 (2,4)
D2 L2 R2 D2 U2 L2 (6,12)
L2 B' F U2 R2 D2 B F' (8,12)
D2 L2 U L2 D2 U2 R2 U' (8,14)

U R2 (2,3)
D2 U' L2 R2 D2 U2 L2 (7,13)
B' R B R2 U F R' F' (8,9)
R' U F R2 D R D' F' (8,9)

U' R (2,2)
F R2 D R D' F' R2 U' (8,10)
D2 U L2 R2 D2 U2 L2 R' (8,14)

U2 R (2,3)
D2 L2 R2 D2 U2 L2 R' (7,13)
F' L' U L U2 F R U' (8,9)
D2 B2 F2 D2 U2 B2 F2 R (8,15)

U R (2,2)
D2 U' L2 R2 D2 U2 L2 R' (8,14)
R2 B' D' R D R2 B U (8,10)

L R (2,2)
L' B2 F2 L2 R2 B2 F2 R' (8,14)
B2 F2 L2 R2 B2 F2 L' R' (8,14)

L2 R (2,3)
B2 F2 L2 R2 B2 F2 R' (7,13)
D2 U2 L2 R2 D2 U2 R' (7,13)
R' B2 F2 L2 R2 B2 F2 (7,13)
R' D2 U2 L2 R2 D2 U2 (7,13)
R2 B2 F2 L2 R2 B2 F2 R (8,15)

L' R (2,2)
L B2 F2 L2 R2 B2 F2 R' (8,14)

L2 R2 (2,4)
B2 F2 L2 R2 B2 F2 (6,12)
D2 U2 L2 R2 D2 U2 (6,12)
R B2 F2 L2 R2 B2 F2 R' (8,14)

L' R2 (2,3)
L B2 F2 L2 R2 B2 F2 (7,13)
L D2 U2 L2 R2 D2 U2 (7,13)
B2 F2 L2 R2 B2 F2 L (7,13)
D2 U2 L2 R2 D2 U2 L (7,13)
L2 B2 F2 L2 R2 B2 F2 L' (8,15)

L' R' (2,2)
L B2 F2 L2 R2 B2 F2 R (8,14)


Edit 2:

To improve upon this, you would have to find 8 move solutions for every possible 3 move ending (or 9 move solutions for every 4 move ending and so on..). This started to seem like a lot of work and I didn't think it would yield any results until you got to higher movecounts. I did some preliminary testing just to see how far up I could push it. I found three move ending D F' U'. This 3 move ending takes 9 moves to solve optimally if you don't count the 3 move solution. From here I tried moves to see If I could come up with a 4 move ending that could not be solved in less than 10 moves optimally except for the 4 move solution. I found B D F' U'.

This continued up until I got the 9 move ending R' F' L U' R' B D F' U' which takes 15 moves optimally if you don't count the 9 move solution. I would go further, but it is beginning to take a longer amount of time for cube explorer to find solutions.

Edit 3:

B' R' F' L U' R' B D F U' requires 16 moves not counting the 10 move solution.


----------



## rokicki (Jul 10, 2014)

Renslay said:


> Is it public?
> 
> I just run the HugeOptimalSolver of CubeExplorer 5.00s on three
> random cubes. All three of them were 18f*, and the runtimes were
> ...



It's not public; I don't think there's interest.

For most optimal solving needs, CubeExplorer is the right way to
go. Like a bike, it gets you there easily, quickly, and with a
minimum of fuss.

My optimal solver is a freight train. It's made to solve
hundreds of thousands or millions of random positions as quickly
as possible. There is no UI (command-line only). It wants lots
of memory and lots of cores. It only supports two metrics (QTM
and HTM, not STM).

Even if you have lots of memory, generating or loading the
pruning table it wants can be slow; I typically use a 176GB
pruning table, which takes many minutes to load.

For pruning tables similar in size to what Cube Explorer uses, I
don't believe it is significantly faster than Cube Explorer.

Given all this, if anyone *really* has interest, I can document
it and put it out there. The pruning table sizes it supports
are:

20MB, 315MB, 472MB, 1.4GB, 2.5GB, 7.6GB, 22GB,
33GB, 60GB, 176GB, 550GB, 4.4TB.

Your choice. The larger the pruning table, the faster the
solution rate, but also the longer it takes to load and generate
the pruning table. On my 256GB 16-core box, I use the 176GB
size; on my 64GB 12-core box, I use the 33GB size. On my 16GB
2-core laptop, I use the 7.6GB size.

With a 176GB pruning table on the 16-core box I can solve random
positions in the half-turn metric at a rate of 33 per second. In
the quarter-turn metric it is even faster.

Now, back to the point of this thread. I solved a few hundred
thousand random positions and was able to find a length-20
canonical solution sequence for all. Then I tried all positions
with four degrees of symmetry or more, and for all of those was
able to find a length-20 canonical solution sequence. I am
running positions with three degrees of symmetry now and am
considering solving all positions with two degrees of symmetry
next.

Based on these results, I am moderately confident that every
position has a distance-20 canonical solution sequence (that is,
that God's Second Number is also 20.)


----------



## Renslay (Jul 10, 2014)

rokicki said:


> It's not public; I don't think there's interest.
> 
> For most optimal solving needs, CubeExplorer is the right way to
> go. Like a bike, it gets you there easily, quickly, and with a
> ...



Thank you. I think I'll stay with CubeExplorer then; but anyway, that solver sounds astonishing.


----------



## elrog (Jul 11, 2014)

I have pretty much gotten as far as I am going to following that sequence I posted in my last post (it became to time consuming for regular cube explorer). I decided I would go back and find Every 3 move position that takes at least 9 moves and follow them all up as far as I can.

To rule out some 3 move positions that do have other solutions lower than 9 moves, I went back to my 2 move combinations so I wouldn't try to branch off from 2 move positions with other solutions lower than 8 moves. That's was when I realized that all of the 2 move combination that had multiple solutions under 8 moves in length were the combinations that had half-turns in them.

This makes me want to think that there is at least some truth to what I said earlier about positions with fewer half-turns seeming harder.


----------



## qq280833822 (Jul 11, 2014)

Hi rokicki, I'm pretty interesting in your pruning table. Before guessing the coordinate you used to contribute the pruning table, I wonna confirm how you store the pruning table. Is it stored as 1.6 bits per entry(only store depth mod 3, as Kociemba's implementation)? Or 32 bits per entry(as mentioned in the source code of the proof of 20 moves)?


----------



## rokicki (Jul 11, 2014)

qq280833822 said:


> Hi rokicki, I'm pretty interesting in your pruning table. Before guessing the coordinate you used to contribute the pruning table, I wonna confirm how you store the pruning table. Is it stored as 1.6 bits per entry(only store depth mod 3, as Kociemba's implementation)? Or 32 bits per entry(as mentioned in the source code of the proof of 20 moves)?



It's two bits per entry. I don't store the value mod 3, though.
For each specific size of pruning table, I have a fixed BASE
value, and I store whether the pruning value is <BASE,
=BASE, =BASE+1, or >BASE+1 using those two bits.

In addition, for every 62 values, I have a single four-bit value
that holds the minimum *actual* value across those 62 values.
(This is in the same cache line as the 62 values.)

Essentially, then, I'm using 512/495 * 2 or 2.07 bits per entry.

So, you're going to guess the coordinates I use for all of my
12 different pruning tables? That would be impressive. Do you
want the exact sizes to help you in this quest?


----------



## qq280833822 (Jul 11, 2014)

Here's my guess of the coordinate of these pruning tables:
In each lines, the first number is the estimated file size of the table, the second number is the estimated number of entries of the table and then the possible coordinates. 

"495" is the UDSlice coordinate
"*16" is the edge orientation of 4 edges represented by the UDSlice coordinate.
"*256" is the edge orientation of 8 edges not represented by the UDSlice coordinate.
"*2048" is the edge orientation of all 12 edges.
"*2187" is the corner orientation of all 8 corners.
"*24" is the permutation of 4 edges represented by the UDSlice coordinate.
"*70" can be the "enhanced" UDSlice coordinate. Based on UDSlice, the position of 4 edges in U face or D face can be represented by 1..C(8,4)=70.
"*70" also can be the number to represent the position of 4 corners in U face or D face.
"/16" symmetry reduction. All combined coordinates listed follow can be reduced via the subgroup of the symmetry group generated by S_F2, S_U4 and S_LR2 with 16 elements.
As the symmetry reduction is not perfect because of some self-symmetry state and the imperfect implementation of symmetry reduction, the file size as well as the number of entries is underestimated.

20M
18,944,887	|	75,779,550 = 495 * 16 * 2187 * 70 / 16

315M
303,118,200	|	1,212,472,800 = 495 * 256 * 2187 * 70 / 16

472M
454,677,300	|	1,818,709,200 = 495 * 16 * 2187 * 70 * 24 / 16

1.4G
1,326,142,125	|	5,304,568,500 = 495 * 16 * 2187 * 70 * 70 / 16

2.5G
2,424,945,600	|	9,699,782,400 = 495 * 2048 * 2187 * 70 / 16

7.6G
7,274,836,800	|	29,099,347,200 = 495 * 256 * 2187 * 70 * 24 / 16

22G
21,218,274,000	|	84,873,096,000 = 495 * 256 * 2187 * 70 * 70 / 16

33G
31,827,411,000	|	127,309,644,000 = 495 * 16 * 2187 * 70 * 70 * 24 / 16

60G
58,198,694,400	|	232,794,777,600 = 495 * 2048 * 2187 * 70 * 24 / 16

176G
169,746,192,000	|	678,984,768,000 = 495 * 2048 * 2187 * 70 * 70 / 16

550G
509,238,576,000	|	2,036,954,304,000 = 495 * 256 * 2187 * 70 * 70 * 24 / 16

4.4T
4,073,908,608,000	|	16,295,634,432,000 = 495 * 2048 * 2187 * 70 * 70 * 24 / 16


----------



## rokicki (Jul 28, 2014)

Wow, that's pretty impressive that you were able to reverse engineer
the pruning tables just from the sizes.

Want to share exactly *how* you did such a reverse engineering?

Want to hazard a guess as to what these pruning tables all have in
common, that I use to gain more effectiveness?

-tom


----------



## rokicki (Aug 1, 2014)

So as to not leave anyone hanging:

All the pruning tables I use are with respect to subgroups that include U and D.

That is, the positions U, D, U2, D2, U3, and D3 are all at distance 0 in the
subgroups represented by the pruning table.

All also have sixteen degrees of symmetry.

This means for every node I can use six pruning table entries: three in the
three major axis orientations, and three more for the inverse position.

My search switches between forward and backward depending on which
pruning results are most restrictive (by branching factor).

So for instance if I have 12 moves to go, and a lookup in the primary
orientation forward says the position is at distance 12, I know the result
will not end in any twist of the up or down faces. Thus, I can search
from the *reverse* position and only consider moves of the other four
faces. If both the UD position and the LR position give a value of 12,
I know any solution must end in a move of only the F or B faces. This
is a generalization of the "if all three probes are 11, then the distance
must be 12" trick that Kociemba uses in his optimal solver.

Further, every recursion into a deeper node leaves one pruning value
unchanged, so I need do at most five probes of the table.

And of course I exploit the 16-way symmetry to get pretty deep tables in
a relatively compact space.

-tom


----------



## qq280833822 (Oct 24, 2014)

Hi rokicki, I have a question about your solver.
As you mentioned, once you turn a move, you will do 5 probes of the pruning table. And 3 of these probes are done through the inverse position. Does it mean that when you do a move 'X' on state 'S', you will calculate S * X and X^-1 * S^-1 simultaneously?
If yes, according to my knowledge, it's hard to calculate X^-1 * S^-1 at coordinate level. But if we do the move at cubie level, it will be 10x slower than at coordinate level. 
Would you mind sharing your implementation details about how to deal with this?

BTW, have you compared the performance between your implementation and kociemba's implementation when using the same pruning table?


----------



## rokicki (Oct 28, 2014)

qq280833822 said:


> Hi rokicki, I have a question about your solver.
> As you mentioned, once you turn a move, you will do 5 probes of the pruning table. And 3 of these probes are done through the inverse position. Does it mean that when you do a move 'X' on state 'S', you will calculate S * X and X^-1 * S^-1 simultaneously?
> If yes, according to my knowledge, it's hard to calculate X^-1 * S^-1 at coordinate level. But if we do the move at cubie level, it will be 10x slower than at coordinate level.
> Would you mind sharing your implementation details about how to deal with this?
> ...



Howdy!

Yes, I calculate XS and S'X' both. I don't use coordinates; I use cubie-level for almost all my programs including this one.

Coordinates work great when all the coordinates and their move tables fit in cache, but once they don't, you're actually
faster doing things at the cubie level, assuming your indexing is fast enough.

It would be interesting to compare my implementation to Kociemba's, but Kociemba's is for Windows and mine is in C.
I'd have to find a Windows machine and a C compiler for it and compile my programs for that (I've long since switched
to Linux and Macs). Maybe I'll do that.

I'd be happy to share the code, but it's not beautiful yet and there's no real UI.

-tom


----------



## qq280833822 (Oct 29, 2014)

Here's my knowledge about cache and move table:
The L3 cache of modern CPU (e.g. intel core i7 4770) is ~8M, which is large enough to store most of the move tables. Although the L1 and L2 cache miss rate may be very high, I don't think the average access time to the move table might exceed 50 clocks (http://stackoverflow.com/questions/4087280/approximate-cost-to-access-various-caches-and-main-memory). Especially, if we split the move table into several parts, the size of the move table will extremely decreased. For example, the size of CornerTwistMoveTable is only 2,187 * 18 * 2 = 78,732 Bytes, which is smaller than the size of L2 cache and the table can be accessed within 10 clock cycles on average.

But if the move is done at cubie-level, there will be more than 20 memory accesses (8 corner cubies+12 edge cubies), which will be about 80 clocks without calculating the overhead of indexing. 

However, when the performance bottleneck is not the move procedure (which might be the memory access to the pruning table), the benefit of doing moves at cubie level, e.g. search from the inverse simultaneously, will speedup the search. 

Can you release an alpha version who can solve a given state (no matter how to input the state)? Let's do some benchmark to verify the performance of doing move at cubie level. 

BTW, in my opinion, the searching time is proportional to the number of accessed nodes. And by pruning at the inverse state simultaneously, the number of accessed nodes can be reduced. However, once I implemented such solver, the number of accessed nodes is only reduced by about 50%. The result is reasonable because we have 3 pruning values already, and in most cases, max(x1, x2, x3) == max(x1_inv, x2_inv, x3_inv) according to the property of order statistic. If it's true, the inverse pruning won't show much improvement than the conventional solver. Have you done a statistics on the number of accessed nodes comparing to the solver who doesn't using the inverse state?


----------



## rokicki (Oct 29, 2014)

Source is at http://tomas.rokicki.com/nxopt.tar.gz

Most of it is the same source I used for the 20-move result.

Command line options are:

-t ## -- number of threads
- -- read stdin for positions

Input positions can be move sequences or they can be
positions as described at 

http://tomas.rokicki.com/cubecontest/

Here are some notes on a shootout vs Kociemba's solver.

Kociemba's huge optimal solver
E5-1620 3.6GHz
1.8GB pruning table
8 cores (4 physical, 4 logical)
Started 12:33 Friday, terminated 10:24 Monday, solved 16,665 cubes
13f*: 2
14f*: 3
15f*: 25
16f*: 427
17f*: 4510
18f*: 11135
19f*: 563
251,460 seconds
Rate of one cube per 15.089 seconds

Kociemba claims 7000 cubes/day on an i7-920, which is an average rate of 1 cube per 12.34 seconds. And the i7-920 is supposed to be only about 55% of the throughput of the E5-1620. Something is odd.

The distribution appears to be *highly* skewed but no easy way to get all the data

Node rate: 4.55M nodes/sec/core or 36.4M nodes/sec overall (very fast!)

Long term average: 549M nodes per solution

My 40 samples from Kociemba show 7.53s and 274M nodes

Mine, at 1.3GB: 227M nodes per solution; solution every 8.8s.

Here are some notes on the different options for my solver.
The "average1" is the average value in the pruning table with
one probe; the average6 is the average value returned with
6 probes (these are for random positions).

number size metric base average1 average6
11 19.7MB h 7 8.90627 9.84321
11 19.7MB q 9 9.88396 10.9947
21 315MB h 8 9.88681 10.8274
21 315MB q 10 11.0091 12.0452
12 472MB h 9 9.92374 10.9551
12 472MB q 10 11.492 12.5162
13 1.38GB h 9 10.2745 11.1472
13 1.38GB q 10 11.7077 12.6858
31 2.52GB h 9 10.6748 11.5986
31 2.52GB q 11 11.8365 12.9383
22 7.55GB h 9 10.9391 11.8728
22 7.55GB q 11 12.4016 13.3269
23 22.0GB h 10 11.3619 12.2277
23 22.0GB q 12 12.8229 13.9476
14 33.0GB h 10 11.4555 12.3198
14 33.0GB q 12 13.0704 14.0768
32 60.4GB h 10 11.79 12.7223
32 60.4GB q 12 13.3901 14.3404
33 176GB h 11 12.1112 13.0352
33 176GB q 12 13.8659 14.8389
24 547GB - - - -
34 4.37TB - - - -


----------



## qq280833822 (Oct 29, 2014)

Cool, kociemba's 1.8G table is equivalent to your 2.5G table. 
And it seems that doing moves at coordinate level is a little faster than at cubie level, while due to lack of inverse pruning, the number of accessed nodes is almost doubled.

WOW, I found a constant 9930


----------



## rokicki (Oct 29, 2014)

qq280833822 said:


> Cool, kociemba's 1.8G table is equivalent to your 2.5G table.
> And it seems that doing moves at coordinate level is a little faster than at cubie level, while due to lack of inverse pruning, the number of accessed nodes is almost doubled.



That might be reasonable, but I'll have to check; I don't remember
exactly what he uses. If it is equivalent I'm a bit surprised; I'm
using 2 bits per and I thought he was using 1.6 bits per, so
the ratio should be 1.25:1, but 2.5:1.8 is significantly greater
than that.

I would not be surprised if my optimal solver could be sped up
quite a bit.

The inverse helps more than just max(a,b,c) vs max(a', b', c');
let us say the number of allowed remaining moves is 10, and the
pruning values come out to be (10,9,9); (10, 10, 9). This
tells me that any move sequence cannot start with a twist of
the UD or FR faces, and it cannot end with a twist of the UD
faces. Because the start move is more constrained, I recurse
on the next (start) move; if the end move was more constrained,
I would recurse on the last (end) move. I think this helps
cut the nodes explored a fair bit.


----------



## qq280833822 (Oct 29, 2014)

It's due to your implementation of symmetry. The symmetry coordinate kociemba used is UDSliceFlip, 2048*495->64430, 1.69% redundancy. So the total number of the entries of his table is 64430 * 2187 * 70 = 9,863,588,700. The file size is 9,863,588,700 / 5 = 1,972,717,740 Bytes. 
While the symmetry coordinate you used is CornerCombinationTwist, 2187*70 -> 9930, 3.78% redundancy. The total number of the entries is 9930 * 495 * 2048 = 10,066,636,800. The file size is 9930 * 512 * 2048 / 4 = 2,603,089,920 Bytes (which is not 9930 * 495 * 2048 / 4 as you described below. Is that correct?)


----------



## rokicki (Oct 29, 2014)

qq280833822 said:


> It's due to your implementation of symmetry. The symmetry coordinate kociemba used is UDSliceFlip, 2048*495->64430, 1.69% redundancy. So the total number of the entries of his table is 64430 * 2187 * 70 = 9,863,588,700. The file size is 9,863,588,700 / 5 = 1,972,717,740 Bytes.
> While the symmetry coordinate you used is CornerCombinationTwist, 2187*70 -> 9930, 3.78% redundancy. The total number of the entries is 9930 * 495 * 2048 = 10,066,636,800. The file size is 9930 * 512 * 2048 / 4 = 2,603,089,920 Bytes (which is not 9930 * 495 * 2048 / 4 as you described below. Is that correct?)



I believe you are correct! The file size is different from my description because there are some other things going on with my files.
For instance, for the four "values" I might use ranges of 0-9, 10, 11, 12+, but every 62 entries or so I have a 4-bit field that
gives the minimum value over those 62 entries exactly (so whenever the two bits give me a range of 0-9, I use that larger
field instead which improves the accuracy of my table). This adds a factor of 512/495, which then matches your calculations.


----------

