# Optimal 3x3x3 solvers, Korf and Kociemba questions



## hatebreeder02 (Nov 12, 2015)

Hello
I have recently started to become really interested in optimal 3x3x3 solvers. Specially Korf´s and Kociemba algorithm. How fast are those on a normal computer ? pruning tables from depth 0 to 11 work pretty well, but it would still take a decent time to solve a cube which needs 18 or 19 moves, right ? And Kociemba division into 2 phases just doesnt work well all the time. (just imagine optimal solution to some particular scramble, where the last move is F....meaning that there would be no phase 2 in Kociemba algorithm, simply because during the optimal solution the cube would never be in the group which is the result of phase1).
With Korf´s algorithm, in the prunning tables we store the lower bound to solve some particular corner configuration (or edge, whatever..), wouldn´t it be faster to store the exact number of moves in which you can solve the corners ? (one table entry could for example have values 6,8,10 ... instead of 6 as a lower bound). I think this could eliminate some decent number of nodes in a search tree. Yes pruning tables would be larger, but not by a huge factor.

Also, has anyone ever tried to analyse and categorize cube scrambles by minimum number of moves required to solve them ? Lets take primitive example, if there are more than 4 misplaced corners on the cube, you can say certainly that it requires minimum of 2 moves to solve.......so i was thinking of something like this, but with much larger depths than 2.I know that it would be much more difficult than this. Both edge and corner positions and orientations must be watched. Perhaps if the edge is on the right place, but wrongly oriented it makes it hard to solve (superflip, eh..). I think you can get really creative here and think of many ways to do this. 
(btw i programmed both Korf and Kociemba, but didnt make the complete tables because it takes me a long time to do that, although i will do it sometimes in the future. If i can download the tables somewhere, please let me know )
Thank you so much for your answers, dear cubers


----------



## Herbert Kociemba (Nov 12, 2015)

My two phase algorithm was not designed to solve the cube optimally, only suboptimally with decent computational expense. With the increase of PC-performance it was possible to hold a complete phase 1 pruning table in memory and using this as the pruning table for an optimal solver, see http://cflmath.com/Rubik/optimal_solver.html


----------



## cuBerBruce (Nov 13, 2015)

hatebreeder02 said:


> With Korf´s algorithm, in the prunning tables we store the lower bound to solve some particular corner configuration (or edge, whatever..), wouldn´t it be faster to store the exact number of moves in which you can solve the corners



Wrong. The table *does* store the exact number of moves to solve the corners. The problem is that the maneuver that solves the corners will not generally also solve the edges. We have a lower bound as to how many moves are required to solve all the pieces.



hatebreeder02 said:


> (one table entry could for example have values 6,8,10 ... instead of 6 as a lower bound)



I do not understand how this is supposed to help. Let's say we know that with a particular corner configuration, it is known that the cube can be solved in somewhere from 10 to 18 moves. The fact the some of these positions require 18 moves requires us to know what corresponding edge configuration(s) we are required to have in order to know we are 18 moves from solved. Otherwise we haven't gained any useful information other than the fact that the current position is at least 10 moves from solved.

Perhaps we could have a small hash table containing positions that are maybe within 2 moves of the lower bound for a particular corner configuration. However, each entry in each hash table is still need to going to have to tell us the full edge state. So we need several bits for each hash entry just for the edge configuration, not to mention that we're talking about having a different hash table for each corner configuration. So we're going to need a lot more memory than what we need for a conventional corner pruning table (2 or 4 bits per corner configuration).

Another approach (and I have experimented with this myself) is to create a hash table of all positions that are within a certain distance from solved. Again, the hash table is going to need to store information about the position, not just the distance. So it is not nearly as efficient as a conventional pruning table, and we're going to be limited in the depth of the pruning we get.


----------



## hatebreeder02 (Nov 15, 2015)

Well, thats not exactly what i meant, perhaps i was not clear enough on that. I did not mean to include edge orientations into the data, although your idea of a hash table seems pretty good. Ill try to describe more exactly what i mean, and perhaps the idea is completely wrong, so be sure to correct me on that one. 
Lets have one corner configuration which is solvable in 8 moves. Is it solvable within 9 moves also ? or 10,11...and more ? (eliminating move sequences that can be shortened like R followed by R2...) I do not know much about the cube to answer this question. But if this particular corner configuration is not solvable within 9 moves, we still allow it to be searched when we have 8 as a lower bound, and thats basically my idea i was trying to present. In a lower bound scenario, we search 9 or 10 move solutions (because corners can be solved within 8 moves) but those solutions cannot happen since 9 move solution to the corners is not possible. Maybe, it is so that you can solve the corners with any number of moves greater than 8, in which case my idea is completely wrong (still not including solutions like R followed by R2). And maybe this happens way too rarely to have any impact on the speed of the algorithm, thereby just making tables larger for no reason. But if thats not the case i think you can eliminate decent number of nodes from the search tree.
Thank you so much for your reply !


----------



## Jakube (Nov 15, 2015)

If you can solve the corners in x moves, most of the time you could also solve them with x+1, or x+2, or ...

There are obviously some exceptions. For instance If the solution for the corners only take 1 move like U, you can't solve the corners in 2 moves. You also can't solve them with 3 or 4 moves. The next valid sequence that solves this case is R U D' F' D (5 moves). I think this is only possible though, if the optimal sequence is really short. If the optimal sequence is longer, lets say more than 5 moves, then you can always find solutions that are one or two moves longer. 

For instance I tried solving a random 6 move scramble in cube-exporer, and it found 2 6-move solutions, already 30 7-moves solutions, more than 100 8-move solutions, ... You can check them out here: http://postimg.org/image/ppda3pq9f/


----------



## Rune (Nov 15, 2015)

Why can´t you solve them in three moves?


----------



## rokicki (Feb 9, 2016)

hatebreeder02 said:


> pruning tables from depth 0 to 11 work pretty well, but it would still take a decent time to solve a cube which needs 18 or 19 moves, right ?



With modern computers and memory, you can do quite well. For instance, on a small server from several years ago with only 256GB RAM and 16 cores, I can optimally solve 33 random positions a second in the half-turn metric; this includes the expected distribution of distance-18 and distance-19 positions. Even on a laptop with only 8GB of RAM and 4 cores you can usually optimally solve a position in a few seconds.



hatebreeder02 said:


> And Kociemba division into 2 phases just doesnt work well all the time. (just imagine optimal solution to some particular scramble, where the last move is F....meaning that there would be no phase 2 in Kociemba algorithm, simply because during the optimal solution the cube would never be in the group which is the result of phase1).



You can apply Kociemba's algorithm to the three distinct axes of the cube, as well as to the inverse position, to help work around this issue.


----------



## unsolved (Feb 14, 2016)

rokicki said:


> For instance, on a small server from several years ago with only 256GB RAM and 16 cores in a few seconds.



I'm going to go out on a limb here and guess you meant 256 MB 



cuBerBruce said:


> Wrong. The table *does* store the exact number of moves to solve the corners. The problem is that the maneuver that solves the corners will not generally also solve the edges. We have a lower bound as to how many moves are required to solve all the pieces.



There needs to be a slight expounding on this: The corner pruning tables that most programs use do not consider the orientation of the corners with respect to the centers. So if you just make the move M, E, or S, the corner pruning database will say the corners are "solved" at the state corresponding to a distance of zero. I computed a pruning table that would list such a distance as "1" since I do consider the corner orientation with respect to the centers. For depths 0 through 7, the total count of arrangements differ, but sum to the same subtotal. Depths 8 through 11 have matching counts per depth.

I've applied corner pruning to the 5x5x5 with outstanding results. I owe Tom, Bruce, & Herbert a great deal. Without them paving the way I'd still be taking 24 hours to get to depths 9-10 on my 4x4x4 program. Yesterday I hit depth 18 on my 5x5x5


----------



## Herbert Kociemba (Feb 14, 2016)

unsolved said:


> There needs to be a slight expounding on this: The corner pruning tables that most programs use do not consider the orientation of the corners with respect to the centers. So if you just make the move M, E, or S, the corner pruning database will say the corners are "solved" at the state corresponding to a distance of zero. I computed a pruning table that would list such a distance as "1" since I do consider the corner orientation with respect to the centers. For depths 0 through 7, the total count of arrangements differ, but sum to the same subtotal. Depths 8 through 11 have matching counts per depth.



In case all corners are fully defined, the solver for incomplete cubes of cube explorer also uses a full corner pruning table. When you take a look into the cube explorer directory, you will find a file fullCornerX.prun, with X = F,Q or S depending on the metric. It takes about 1.4 MB. I think it would be better if you fix the centers and replace the M move by 2r 2l' for example. This is more natural for cubes with odd N. Then you need no special handling and the corner pruning table says solved only if the corners really are solved.

EDIT: Alternatively, if you want to fix the DLB corner, there are only 7 corners to permute and you get a corner-coordinate C from 0..7!*3^6-1. You then can combine this with a coordinate M from 0..24-1 which describes the position of the 6 centers, for example with CM = 24*C+M. CM then runs from 0 to 8!*3^7-1.


----------



## Pookie (Dec 2, 2017)

hatebreeder02 said:


> Hello
> I have recently started to become really interested in optimal 3x3x3 solvers. Specially Korf´s and Kociemba algorithm. How fast are those on a normal computer ? pruning tables from depth 0 to 11 work pretty well, but it would still take a decent time to solve a cube which needs 18 or 19 moves, right ? And Kociemba division into 2 phases just doesnt work well all the time. (just imagine optimal solution to some particular scramble, where the last move is F....meaning that there would be no phase 2 in Kociemba algorithm, simply because during the optimal solution the cube would never be in the group which is the result of phase1).
> With Korf´s algorithm, in the prunning tables we store the lower bound to solve some particular corner configuration (or edge, whatever..), wouldn´t it be faster to store the exact number of moves in which you can solve the corners ? (one table entry could for example have values 6,8,10 ... instead of 6 as a lower bound). I think this could eliminate some decent number of nodes in a search tree. Yes pruning tables would be larger, but not by a huge factor.
> 
> ...




Subset 1= _X_<4 (Build a face in 4 moves, at minimum missing one edge one corner.) - General *Generate pixel space
Subset 2= _Y_<4 (Orient opposite layer while f2l minus 1. Also 4 moves.) - Square one, to cage the item
Subset 3= a_Z_>2 b_Z_>6 ab_Z =_ +/- 1 =4 solve middle layer edge parity, if exists, while permute top bottom corners, if exists. - Obsessive patterns, "Order"
Subset 4= solve the cube using only HTM-- double moves. R2 L2 Etc. Max= 8 - "Rubricks cyoob?"

4>_n _= S1
4>_n _= S2
=0<_n_<6 = S3
8>_n_ = S4

While executing subset one, each step must have the other step in mind _almost_ similar to Heise method


----------



## xyzzy (Dec 2, 2017)

Pookie said:


> Subset 1= _X_<4 (Build a face in 4 moves, at minimum missing one edge one corner.) - General pixel space
> Subset 2= _Y_<4 (Orient opposite layer while f2l minus 1. Also 4 moves.) - Square one, to cage the item
> Subset 3= a_Z_>2 b_Z_>6 ab_Z =_ +/- 1 =4 solve middle layer edge parity, if exists, while permute top bottom corners, if exists. - Obsessive patterns, "Order"
> Subset 4= solve the cube using only HTM-- double moves. R2 L2 Etc. Max= 8 - "Rubricks cyoob?"
> ...


1. This literally makes no sense.
2. You replied to someone who hasn't logged in since 2015.


----------



## Pookie (Dec 4, 2017)

xyzzy said:


> 1. This literally makes no sense.
> 2. You replied to someone who hasn't logged in since 2015.



I would love to clarify, is there a specific part you are having trouble understanding?


----------



## xyzzy (Dec 4, 2017)

Pookie said:


> I would love to clarify, is there a specific part you are having trouble understanding?


Almost all of your post is incomprehensible, so no.

>Subset 1= _X_<4
I can't figure out what this is supposed to mean.

>Build a face in 4 moves, at minimum missing one edge one corner.
I don't see how this can be done in 4 moves every time.

>General pixel space
???

>Orient opposite layer while f2l minus 1. Also 4 moves.
No idea what "f2l minus 1" even means in this context. Also, don't see how this can be done in 4 moves.

>Subset 3= a_Z_>2 b_Z_>6 ab_Z =_ +/- 1 =4
????????????

>Subset 4= solve the cube using only HTM-- double moves. R2 L2 Etc. Max= 8
That's not what "HTM" means. Also requires more than 8 moves most of the time.

>"Rubricks cyoob?"
??????????????????????????

More importantly, how does any of this relate to optimal solving or Kociemba's algorithm?


----------



## Pookie (Dec 6, 2017)

xyzzy said:


> Almost all of your post is incomprehensible, so no.
> 
> >Subset 1= _X_<4
> I can't figure out what this is supposed to mean.
> ...



Best start for an FMC is block building technique. Try to build a 2x2x2 block then a 2x2x3 block. After the 2x2x2 block you have 3 sides to extend it to a 2x2x3. Explore all of them...[[ https://www.speedsolving.com/wiki/index.php/Fewest_Moves_techniques ]]

C F O P = 4 subsets 

Combining what we know about twisty puzzles and HTM, cubic twisty puzzles that allow slice moves have two states. 
Quarter turns
Half turns
~~~~~~~~~
An edge piece has 3 other "color commutators" given what we know the Western color scheme (also known as BOY: blue-orange-yellow)... [[ https://ruwix.com/the-rubiks-cube/japanese-western-color-schemes/ ]] and most all edge buffer commutator algs
Example of the above definition "color commutators" : The edge piece blue and yellow ---(imagining a cage 2x2x2 with the 3x3x3 corners and a NxNxN edge reduction puzzle)--- has 3 other pieces that can be in the final place on the core of the puzzle (see pattern 3 dots -- 2 spots -- [[ https://ruwix.com/the-rubiks-cube/rubiks-cube-patterns-algorithms/ ]] ) these "perfect world", or ideal, pieces are ;
Green and Yellow 
Blue and White
Green and White

In a more statistical humanized world, the color commutators/buffer pieces can also be the only 4 blue edges. This is not ideal because like all solving methods, the use of notation allows us to understand why a piece is TEMPORARILY out of place. 

Solving for God's number seems to better link up with Heise, Petrus, and ZZ. 

The most amount of Half turns I have seen a Optimal solver spit out tend to be close to 7. I can't reproduce 8 consistently nor have any screenshots of the solution. 

Usually 6 is optimal for 1 turn on each face. When solving the cube into a pattern, if you rush in without identifying how the pattern is constructed, you can run into parities when the cube has not been disassembled.


----------



## xyzzy (Dec 6, 2017)

The more you explain, the less sense you make. I could quote almost every sentence in your post again and follow them with a string of question marks, but that would be a waste of my time. (This is literally Time Cube-tier material.)


----------



## Pookie (Dec 6, 2017)

xyzzy said:


> The more you explain, the less sense you make. I could quote almost every sentence in your post again and follow them with a string of question marks, but that would be a waste of my time. (This is literally Time Cube-tier material.)



As long as half of my post is english, I don't care anymore man


----------



## AlphaSheep (Dec 6, 2017)

Pookie said:


> Subset 1= _X_<4 (Build a face in 4 moves, at minimum missing one edge one corner.) - General pixel space
> Subset 2= _Y_<4 (Orient opposite layer while f2l minus 1. Also 4 moves.) - Square one, to cage the item
> Subset 3= a_Z_>2 b_Z_>6 ab_Z =_ +/- 1 =4 solve middle layer edge parity, if exists, while permute top bottom corners, if exists. - Obsessive patterns, "Order"
> Subset 4= solve the cube using only HTM-- double moves. R2 L2 Etc. Max= 8 - "Rubricks cyoob?"
> ...


Are you proposing a method? If so, it might help to give some example solves to demonstrate.

Build a face with on corner and one edge missing (can they be any edge and corner, or must they be connected?). I also had no idea what you mean by "General pixel space"
By orient the opposite layer, you mean both the corners and edges, right? That would involve also separating the edges that belong in the equator slice into the middle layer. It's this what you mean by "cage the item"? Square-1 reduction involves driving two adjacent middle layer edges and reducing the cube to a starte that can be solved with <R2, U, D> moves. By "F2L minus 1", do you mean the state what the cross and three F2L pairs need to be solved? If so, that's very different from square-1 reduction.
By middle layer edge parity, do you the state solved by R2 U2 R2 U2 R2? Because permutation of the middle layer edges can be done in step 4, as long as these edges are oriented. Whether it's more efficient to do it in step 3 or 4 varies from scramble to scramble.
Many states that can be solved with half turns only can actually be solved in fewer moves if you allow quarter turns as well.



Pookie said:


> Best start for an FMC is block building technique. Try to build a 2x2x2 block then a 2x2x3 block. After the 2x2x2 block you have 3 sides to extend it to a 2x2x3. Explore all of them...[[ https://www.speedsolving.com/wiki/index.php/Fewest_Moves_techniques ]]
> 
> C F O P = 4 subsets
> 
> ...



Block building is one good technique for FMC, but its arguable whether it's the best. Its a technique that many find natural, but all good FMC solvers will try a variety of techniques on a scramble and pick which is best. Other techniques people use are corner first, edge orientation first, or domino reduction starts.
In not sure what you mean by commutator. The usual definition of a commutator in cubing is when you do one sequence of moves, followed by a second sequence of moves, and then undo the first sequence and then finally undo the second sequence. The advantage of a commutator is that it's effect is limited to a well defined set of pieces, namely the pieces moved into or out of positions that are affected by both sequences. There are other definitions for commutator in mathematics, but this is consistent with the definition used in group theory and the way most cubers understand the word. You seem to use the word to refer to actual pieces, and not sequences of moves, which is not the way the word is usually used. I also don't understand how this relates to what you were talking about previously.
Heise, Petrus and ZZ all have move counts in the 40+ move range for humans. When you include computers, solutions around 20-25 moves can be achieved, but nowhere near as quickly and efficiently as methods


----------



## Pookie (Dec 7, 2017)

AlphaSheep said:


> Are you proposing a method? If so, it might help to give some example solves to demonstrate.
> 
> Build a face with on corner and one edge missing (can they be any edge and corner, or must they be connected?)
> **Generate pixel space
> ...



Absolutely! 

http://ushabbo.webs.com/1.htm 
Cage the cube


http://ushabbo.webs.com/2.htm
Orient chosen layers while considering middle layer edge parities


http://ushabbo.webs.com/3.htm
Permute


I felt these puzzles were the best way to attempt to demonstrate the many methods Cubers attempt to teach to each other. What is God's number for Picture cubes, like 24?


----------



## Bruce MacKenzie (Dec 15, 2017)

Pookie said:


> Absolutely!
> 
> http://ushabbo.webs.com/1.htm
> Cage the cube
> ...


If by Picture cubes you mean 3x3x3 cubes where the orientation of the center cubies matter, then the diameter is not known but it is at least 24f. Superflip requires 24 face turns: R L' U R U F R' L2 U F D' F2 R L' B2 D B' U' L R2 B' U' L' U'


----------

