Difference between revisions of "Kociemba's Algorithm"

From Speedsolving.com Wiki
(make the wikilink text match the target; rm repeated wikilinks; https)
Line 1: Line 1:
A computer algorithm for solving the 3x3x3 cube, created by [[Herbert Kociemba]]. It is similar to the [[Thistlethwaite]] algorithm though with fewer steps thanks to the improvement of computer memory storage and processing speed.
+
A computer algorithm for solving the 3x3x3 cube, created by [[Herbert Kociemba]]. It is similar to the [[Thistlethwaite's algorithm]] though with fewer steps thanks to the improvement of computer memory storage and processing speed.
 +
 
 
==Two Phase Approach==
 
==Two Phase Approach==
 
Let's ignore group theory and use the first two layers as an analogy.
 
Let's ignore group theory and use the first two layers as an analogy.
Line 68: Line 69:
  
 
The last half of the solution becomes the first half of the scramble, which is why the initial moves are in G1. And you can see that G1 is about half of the scramble (9 out of 19 moves).
 
The last half of the solution becomes the first half of the scramble, which is why the initial moves are in G1. And you can see that G1 is about half of the scramble (9 out of 19 moves).
 +
 
== See also ==
 
== See also ==
* [[Thistlethwaite]]
 
 
* [[Cube Explorer]]
 
* [[Cube Explorer]]
 
* [[SSC (Shadowslice Snow Columns)]]
 
* [[SSC (Shadowslice Snow Columns)]]
Line 75: Line 76:
  
 
== External links ==
 
== External links ==
* [http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube#Kociemba.27s_Algorithm Section on Wikipedia article]
+
* [https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube#Kociemba.27s_Algorithm Section on Wikipedia article]
 
* [http://kociemba.org/cube.htm Cube Explorer Website]
 
* [http://kociemba.org/cube.htm Cube Explorer Website]
* [http://www.jaapsch.net/puzzles/compcube.htm#kocal Jaap's Computer Puzzling Page]
+
* [https://www.jaapsch.net/puzzles/compcube.htm#kocal Jaap's Computer Puzzling Page]
  
 
==Notes==
 
==Notes==

Revision as of 12:01, 18 June 2017

A computer algorithm for solving the 3x3x3 cube, created by Herbert Kociemba. It is similar to the Thistlethwaite's algorithm though with fewer steps thanks to the improvement of computer memory storage and processing speed.

Two Phase Approach

Let's ignore group theory and use the first two layers as an analogy.

Two-Phase

The core of the 2-phase approach is this:

  • Solve the cube into a state with a certain property.
  • Solve the rest of the cube.

If we select F2L as our property, we get:

  • Solve the first two layers.
  • Solve the last layer.
    • If you solve F2L with the fewest moves possible, then solve the resulting LL case optimally, you'll end up with a decently short solution. However, there might be a shorter solution: in that case, the first phase might take more moves, but get us an easy LL case (or an LL skip!).

Iterative Deepening (for Phase 1)

  • Let's say our first solution took 15 moves for F2L and 11 moves for LL. That means that our cube takes at most 15 + 11 = 26 moves to solve.
  • So let's try looking at all the solutions that take 15 moves for F2L. If any of them give us an LL that takes fewer than 11 moves, we can find a shorter solution. In fact, we can extend this and keep looking. Here's our plan:
    • Try all the solutions that take 15 moves for F2L and fewer than 26 - 15 = 11 moves for LL.
    • Try all the solutions that take 16 moves for F2L and fewer than 26 - 16 = 10 moves for LL.
    • Try all the solutions that take 17 moves for F2L and fewer than 26 - 17 = 9 moves for LL.
    • ...
    • Try all the solutions that take 25 moves for F2L and fewer than 26 - 25 = 1 moves for LL.
    • Try all the solutions that take 26 moves for F2L and fewer than 26 - 26 = 0 moves for LL.

If there is a solution that takes fewer than 26 moves for the entire cube, F2L clearly has to be finished in at most 26 moves. Therefore, our optimal overall solution has to be in one of these cases.

Now let's say that along the way we find a solution that takes 17 moves for F2L and 8 moves for LL. Now we know that the entire cube can be solved in 17 + 8 = 25 moves. We abort the original 26-plan and continue our search wtih a new upper bound:

  • Try all the solutions that take 17 moves for F2L and fewer than 25 - 17 = 8 moves for LL.
  • Try all the solutions that take 18 moves for F2L and fewer than 25 - 18 = 7 moves for LL.
  • ...
  • Try all the solutions that take 25 moves for F2L and fewer than 25 - 25 = 0 moves for LL.

If we keep going, we reach a point where any solution we haven't considered must be longer than the one we have -- so our solution is optimal. For 3x3x3, we happen to know that the optimal solution must be at most 20 moves... but that's only because we know God's number. The approach works even if we don't know God's number (so can be used for any twisty puzzle).

The Domino Phase (a.k.a. Group Theory is Awesome)

Of course, Kociemba's Algorithm doesn't solve F2L first. Once you've solved F2L, you can only do U moves without breaking up your progress, which is counterproductive.

Instead, Kociemba gets the cube into one of the states in "G1", which means it has the following properties:

  • All the corners are oriented (like in 3OP).
  • All the edges are oriented (like in 3OP).
  • All the middle layer edges are already in the middle layer.

From there, you can solve the cube by using only <U, D, F2, B2, R2, L2>. That is, you can basically pretend it's a 3x3x2 domino. (Try it!) (Aside: This means that you've put the cube into a subgroup which is its own puzzle.)

  • The nice thing about this is that once the cube is in the G1/Domino, you can search for an optimal Domino solution.
  • More importantly, every cube solution ends with some number of domino moves. That number might be 0, but there's a good chance that there is some optimal solution that uses a few. This means we can run the two-phase search similar to before, except we can restrict ourselves to a domino search in the second half.

There are a lots of details, including:

  • Solving a cube into G1 is about as hard as solving the rest. This means that both parts of the search take roughly the same time. (If we tried to find an optimal solution using the F2L approach, we would have to spend way more time trying to solve F2L than a computer could ever handle. There are very few cube states where it's possible to find an optimal solution where F2L is solved early.)
  • Since G1 is a group, there is a lot of symmetry in the search. This speeds things up by allowing you to search multiple things at once.
  • You can take lots of shortcuts. Let's say you already have a solution of 26 moves, and are considering a solution that has taken 18 moves already. If you know that it takes at least 10 more moves to solve the corners, then you can stop searching for that solution. There are efficient ways to do this by using prune tables. The symmetry of G1 also allows these prune tables to be very efficient.
  • If you run Kociemba for a short while, you can get a pretty short solution. If you run it for longer, you will quickly get some better solutions, and after a while verify the optimal solution. The choice of G1 really helps with this.
  • Solvers for other puzzles usually use a similar approach, except they use more phases. This WCA scrambler for 4x4x4 uses 4 phases to generate a scramble for a random state (but it doesn't continue to find an optimal solution).
  • Instead of iterative deepening, Kociemba implementations usually use IDA*, which is iterative deepening combined with a heuristic. Instead of going through the solutions blindly, the algorithm tries to go down path that look like they might have a shorter solution. This helps find shorter solutions earlier, which cuts down on the additional searching.

Example Reconstruction

Look at the reconstruction of Mats Valk's 5.55 WR. The scramble is:

D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2

Notice that the first half uses only <U, D, F2, B2, R2, L2>. This is because TNoodle uses Shuang Chen's min2phase to do the following:

  • Generate a random state.
  • Solve the state using Kociemba.
  • Invert the solution to get a scramble for the state.

The last half of the solution becomes the first half of the scramble, which is why the initial moves are in G1. And you can see that G1 is about half of the scramble (9 out of 19 moves).

See also

External links

Notes

  • With thanks and all credit for the description and example solves to Lucas Garron