Optimal 3x3x3 solvers, Korf and Kociemba questions

Discussion in 'Puzzle Theory' started by hatebreeder02, Nov 12, 2015.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. hatebreeder02

    hatebreeder02 Member

    2
    1
    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 :)
     
  2. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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
     
  3. cuBerBruce

    cuBerBruce Member

    912
    4
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    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.

    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.
     
  4. hatebreeder02

    hatebreeder02 Member

    2
    1
    Nov 12, 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 !
     
    abunickabhi likes this.
  5. Jakube

    Jakube Member

    790
    4
    Feb 3, 2011
    Austria
    WCA:
    2011KOGL01
    YouTube:
    JakubeBLD
    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/
     
    abunickabhi likes this.
  6. Rune

    Rune Premium Member

    276
    11
    May 11, 2006
    WCA:
    2003WESS01
    Why can´t you solve them in three moves?
     
  7. rokicki

    rokicki Member

    255
    4
    Oct 31, 2008
    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.

    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.
     
    abunickabhi likes this.
  8. unsolved

    unsolved Member

    566
    7
    Mar 2, 2014
    Doylestown, PA
    I'm going to go out on a limb here and guess you meant 256 MB :)

    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 :)
     
    Last edited: Feb 14, 2016
    abunickabhi likes this.
  9. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    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.
     
    Last edited: Feb 15, 2016
    abunickabhi likes this.
  10. Pookie

    Pookie Member

    5
    2
    Dec 2, 2017

    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= aZ>2 bZ>6 abZ = +/- 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
     
    Last edited: Dec 7, 2017 at 6:10 AM
    mDiPalma likes this.
  11. xyzzy

    xyzzy Member

    777
    337
    Dec 24, 2015
    1. This literally makes no sense.
    2. You replied to someone who hasn't logged in since 2015.
     
  12. Pookie

    Pookie Member

    5
    2
    Dec 2, 2017
    I would love to clarify, is there a specific part you are having trouble understanding?
     
    mDiPalma likes this.
  13. xyzzy

    xyzzy Member

    777
    337
    Dec 24, 2015
    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= aZ>2 bZ>6 abZ = +/- 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?
     
  14. Pookie

    Pookie Member

    5
    2
    Dec 2, 2017
    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.
     
  15. xyzzy

    xyzzy Member

    777
    337
    Dec 24, 2015
    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.)
     
  16. Pookie

    Pookie Member

    5
    2
    Dec 2, 2017
    As long as half of my post is english, I don't care anymore man
     
  17. AlphaSheep

    AlphaSheep Member

    1,017
    526
    Nov 11, 2014
    Gauteng, South Africa
    WCA:
    2014GRAY03
    Are you proposing a method? If so, it might help to give some example solves to demonstrate.
    1. 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"
    2. 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.
    3. 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.
    4. Many states that can be solved with half turns only can actually be solved in fewer moves if you allow quarter turns as well.
    1. 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.
    2. 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.
    3. 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
     
  18. Pookie

    Pookie Member

    5
    2
    Dec 2, 2017
    Absolutely!
    1. http://ushabbo.webs.com/1.htm
      Cage the cube

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

    3. 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?
     

Share This Page