• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Computer solving: a new two-phase algorithm?

Looks like half turn subgroup, but limited to only <=8 moves.

I like to think of it as a finish in 8 moves (reason) on a 6-color cube solved as a 3-color cube :-).

Hmmm, http://forum.cubeman.org/?q=node/view/519 gives different numbers for >= 5 moves.

<U, D, R, L, F, B> vs <U2, D2, R2, L2, F2, B2>. See distance distribution in Phase 2 of Half-turn reduction -> Solved in my previous post (notice 13 vs 15 moves).

8 moves is quite deliberate here.

Yes, that´s because Feather´s algorithm goes like this: Any 3-color solutions that arise from the nodes being generated are then looked up in the DistP2 array (which is 3-color reduced = 4M configurations) and if it is 8 moves or less (of which there are 117K configurations) then a solution is generated.

I think the only correct number is 15 for phase 2.

I believe I covered that above.
 
Now I got it. bcube's table in phase 2 of Feather's Algorithm refers to the 3-color-cube cut to depth 8. @bcube: So for phase 1 you essentially ask what is the maximum number of moves to get from an arbitrary state to a 3-color-cube state which is not more than 8 moves away from solved. I see no way that this can be answered.
 
Yes, that´s because Feather´s algorithm goes like this: Any 3-color solutions that arise from the nodes being generated are then looked up in the DistP2 array (which is 3-color reduced = 4M configurations) and if it is 8 moves or less (of which there are 117K configurations) then a solution is generated.
In a two phase algorithm you always cut the phase 2 length to some suitable length. If you take 7, 8 or 9 is not really relevant.
 
bcube's table in phase 2 of Feather's Algorithm refers to the 3-color-cube cut to depth 8. @bcube: So for phase 1 you essentially ask what is the maximum number of moves to get from an arbitrary state to a 3-color-cube state which is not more than 8 moves away from solved.

Have you considered that the 6-color cube is already being solved as the 3-color cube in phase 1 of Feather´s algorithm?

I am essentially asking what is the maximum number of moves to get from an arbitrary configuration to any of those 117,265 configurations in phase 2 (while already knowing it is 20 or less). Since I don´t see an obvious way why this should be impossible to calculate, can you explain in more detail why do you think so?
 
I deleted my previous answer because the argument was wrong. I will try again. In a two phase algorithm in the first phase you handle with cosets of a subgroup while in the second phase you solve the position in this subgroup. If the target of phase 1 is not a full subgroup but something like "all positions of the subgroup which <= 8 moves from solved, the whole concepts of cosets breaks and at least I do not see a way how to handle this in a reasonable way. The distance distribution for phase 1 will start with depth 0: 117,265 or not? And for depth 1 you have to apply all 18 moves to all the 177,265 positions and count the new created positions etc. You must continue with depth 2... until you produced finally all possible Rubik's cube configurations. This cannot be done in a reasonable time.
 
The distance distribution for phase 1 will start with depth 0: 117,265 or not? And for depth 1 you have to apply all 18 moves to all the 177,265 positions and count the new created positions etc.

I am sorry, I am not following you on this.

Here is an idea for lowering that maximum length from 20 to 19: if a solver using Feather´s algorithm was able to solve all configurations requiring 20 moves to solve without going above depth 19 in phase 1, then it would prove that 19 is the maximum length (or rather the upper bound) for phase 1. However, all configurations requiring 20 moves to solve are not known yet.
 
I have no doubt that there is a good chance that 19 moves (or even less) would suffice to reach this set of 177,265 positions from every cube position. But to show this you will have to work backwards and show that you can generate all 4.3*10^19 cube positions by applying moves to these 177,265 positions. And even if you generate 10^9 new positions/s it will take more than 1300 years before you are finished. Ok, you may be able to reduce the number by the 48 symmetries but still it takes too long.
 
Last edited:
Here is an idea for lowering that maximum length from 20 to 19: if a solver using Feather´s algorithm was able to solve all configurations requiring 20 moves to solve without going above depth 19 in phase 1, then it would prove that 19 is the maximum length (or rather the upper bound) for phase 1. However, all configurations requiring 20 moves to solve are not known yet.

1,130,184 scrambles for all 102,764,490 currently known distance-20 positions from http://cube20.org/distance20s/ have been tested using Feather´s Solver 2.

params: use_dist4=1&stl=60&conc=18&batch=1&stoplen=30

total runtime: 1202.09000 s for average of 1130184/1202.09000 = 940.18251 solves/second (on ryzen 7)

24f was longest, there were 344 of them, 344 / 1130184 = 0.00030 = 0.030%

depth 16 was max in phase 1, there were 860 of them, 860 / 1130184 = 0.00076 = 0.076%
Code:
  70384 (20f)

 234863 (21f)

 530542 (22f)

 294051 (23f)

    344 (24f)
Code:
   1059 [12+8](20f)

   7520 [13+7](20f)

    184 [13+8](20f)

  29298 [13+8](21f)

  35842 [14+6](20f)

    806 [14+7](20f)

 125688 [14+7](21f)

   3256 [14+8](20f)

   3563 [14+8](21f)

 375936 [14+8](22f)

  19387 [15+5](20f)

    455 [15+6](20f)

  68410 [15+6](21f)

   1832 [15+7](20f)

   1733 [15+7](21f)

 150131 [15+7](22f)

   6062 [15+8](21f)

   4293 [15+8](22f)

 293869 [15+8](23f)

     38 [16+4](20f)

      1 [16+5](20f)

     91 [16+5](21f)

      4 [16+6](20f)

      5 [16+6](21f)

    162 [16+6](22f)

     13 [16+7](21f)

      4 [16+7](22f)

    179 [16+7](23f)

     16 [16+8](22f)

      3 [16+8](23f)

    344 [16+8](24f)
Scrambles were run in a batch of 100k each as Chrome can't handle 200k.
 
Empirical data is no proof. That there was never found a position that needs 21 moves did not proof God's number is 20 for example. You have to check all cases and this is practically not possible for Feather's algorithm with this phase 2 subset of 177,265 positions.

And btw. if you run phase 1 long enough every position will be solved in 20 moves. So what do you actually want to show with the provided data?
 
Last edited:
In a two phase algorithm you always cut the phase 2 length to some suitable length. If you take 7, 8 or 9 is not really relevant.
I think in this context the choice of 8 actually makes a subtle difference. From what I remember, there are no <=8 movers that can turn an HTR case into a fake HTR case (feel free to disprove that, if I remember incorrectly. In that case nvm this response). That would imply that all cases of feathers phase 2 are actually HTR states with depth <=8.

Hence you could check the HTR states of depth 16 for any 8 movers and if you find one, then thats a lower bound, if I am understanding this correctly.
 
Empirical data is no proof. That there was never found a position that needs 21 moves did not proof God's number is 20 for example. You have to check all cases and this is practically not possible for Feather's algorithm with this phase 2 subset of 177,265 positions.

I wasn´t actually trying to prove anything :).

I was implying that all 1f* - 19f* positions can be solved in 19 moves in phase 1 of Feather´s algorithm (similarly to phase 1 of Kociemba´s algorithm). To lower the upper bound for phase 1 of Feather´s algorithm from 20 to 19 I would need to test all 20f* positions to see if they can be all solved without going above depth 19 in phase 1. Since not all 20f* positions are known, I was at least sharing the (hopefully interesting) data from all 20f* currently known positions - just about 1/5 of all 20f* positions.

That would imply that all cases of feathers phase 2 are actually HTR states with depth <=8.

All 117,265 configurations can be solved using only half-twists.
 
Last edited:
I was implying that all 1f* - 19f* positions can be solved in 19 moves in phase 1 of Feather´s algorithm
Ît is unclear for me what you mean by this. Since in phase 1 all moves are allowed without any restrictions obviously you solve all 19f* positions in 19 moves in phase 1. And if for 20f* positions the last move is in phase 1 (any turn) or in phase 2 (180° turn) seems completely irrelevant for me.
 
Ît is unclear for me what you mean by this. Since in phase 1 all moves are allowed without any restrictions obviously you solve all 19f* positions in 19 moves in phase 1. And if for 20f* positions the last move is in phase 1 (any turn) or in phase 2 (180° turn) seems completely irrelevant for me.

Both phases of Feather´s algorithm are not move-restricted unlike in Thistlethwaite-like algorithms. Last move in phase 2 can be a quarter-twist as can be seen in this [13+6] (19f*) example:


Hence you could check the HTR states of depth 16 for any 8 movers and if you find one, then thats a lower bound, if I am understanding this correctly.

Even though it is unclear to me what you are trying to say, every HTR configuration can be solved in 13 moves (if moves are not restricted) as shown in this post.
 
Even though it is unclear to me what you are trying to say, every HTR configuration can be solved in 13 moves (if moves are not restricted) as shown in this post.
You were searching for a bound on the first phase of feathers method.

You know that all the states in the second phase are HTR states (Not the converse). Consider all cases that are 16 moves away from HTR. Those will also be at least 16 moves away from feathers phase 2, so if you find such a state that actually ends up in feathers phase 2, then you know that 16 has to be a lower bound. This obvlsy just helps, if the list of 16 movers is already known and can be utilized.
 
Both phases of Feather´s algorithm are not move-restricted unlike in Thistlethwaite-like algorithms. Last move in phase 2 can be a quarter-twist as can be seen in this [13+6] (19f*) example:
You are right, I did not see this correctly. But it gets increasingly unclear for me what this all has to do with the original question: How many moves does it take at most to reach this subset of 177,265 positions. I tried to point out that this cannot be answered in acceptable computation time and I must now also add that the question is anyway not that interesting that it would justify such an effort. It would have been eventually interesting to answer to get an upper bound for God's number but since this is known it is quite irrelevant now.
What would be more interesting for me is how far you will have to go out in phase 1 to get an overall solution with <=20 moves. For my standard two-phase algorithm we know from the God's number proof that there exist exceptional positions which need 18 moves in phase 1 to get a 20 move solution.
 
Last edited:
But it gets increasingly unclear for me what this all has to do with the original question: How many moves does it take at most to reach this subset of 177,265 positions.

From a theoretical standpoint I find it interesting to know (or to compare with Kociemba´s algorithm) what is an upper bound for God´s number using Feather´s algorithm. Knowing the maximum length for phase 1 of Feather´s algorithm is a step 1 in this 2-step process.

It would have been eventually interesting to answer to get an upper bound for God's number

This is exactly what I meant by "In Kociemba´s algorithm, phase 1 needs at most 12 moves and phase 2 needs at most 18 moves. It has been proven that the 30 and 29 moves cases can be avoided, so it is guaranteed every cube configuration can be solved in at most 28 moves. Can anyone do the same analysis for Feather´s algorithm, please?"

You know that all the states in the second phase are HTR states (Not the converse). Consider all cases that are 16 moves away from HTR. Those will also be at least 16 moves away from feathers phase 2, so if you find such a state that actually ends up in feathers phase 2, then you know that 16 has to be a lower bound.

Got it this time, thank you for clarification.
 
This obvlsy just helps, if the list of 16 movers is already known and can be utilized.

Unfortunately, it has been many years since 2007 when Gene Cooperman and Daniel Kunkle have generated such set. Professor Cooperman haven´t worked with Rubik´s cube in many years, I am currently waiting for an answer from Daniel to see if he can offer help.

In my tests, Superflip needs at least 14 moves in phase 1 and the "hardest position" from cube20.org needs at least 16 moves in phase 1. So I am calling 16 an lower bound.
 
So I am calling 16 an lower bound.

Nice. There are about 1.5*10^18 different cube maneuvers of length <=16. I hope you have enough patience to wait until anyone shows that eventually these maneuvers applied to the phase 2 set generate the whole cube space.
 
Do we have any known candidate(s) which would need at least 17f in phase 1? I feel like Tom Rokicki in his hunt for a distance-21 position :-).

For my standard two-phase algorithm we know from the God's number proof that there exist exceptional positions which need 18 moves in phase 1 to get a 20 move solution.

What are they? Have you tested them in Solver 2?
 
Back
Top