Kociemba's Algorithm

All the discussion above assumes that you actually want to find the shortest solution. A tree search might take a long time even with good pruning tables. Herbert Kociemba managed to combine several ideas into a very effective new algorithm which will give good sub-optimal solutions very quickly. It may well find an optimal solution to a position fairly soon, but it may take a long time for it to actually prove the solution is optimal by trying out all shorter sequences.

The first idea was based on Thistlethwaite's work. Kociemba uses only two phases however. His first phase moves from G0 to G1 = <U, D, R2, L2, F2, B2>, and the second phase from G1 to G2 = I. So each of Kociemba's phases combines two of Thistlethwaite's stages together. Clearly these phases are too large to build a full table. Nevertheless, it is quite straightforward to make pruning tables and use IDA* to solve each phase. Already this two-phase algorithm will clearly lead to some improvement on Thistlethwaite, because the first phase of this algorithm finds the shortest possible way of going through the first two parts of Thistlethwaite, and the second phase the shortest way to go through the last two parts. The phases have actually been fully calculated and their maximum lengths were found to be 12 and 18 moves, so the algorithm's first solution is at most 30 moves long (using the Half Turn Metric). In fact it has been proven that the 29 and 30 move cases can be avoided, so that every cube position can be solved in at most 28 moves. For a while this was the best upper bound for God's Algorithm until different methods reduced to 22 moves.

The second major idea was to continue searching after the first solution is found. As was noted with Thistlethwaite's algorithm, a different phase 1 solution may well have a better possible phase 2 solution. After one solution is found, other phase 1 solutions are tried to see if these give a better phase 2 and hence a better overall solution.

This is not the end of it though. Suppose we have found a solution of length 7+8, and all the other phase 1 solutions of length 7 have been tried. By continuing the phase 1 IDA* even further, it tries to find solutions of length 8, followed by a phase 2 solution of at most 6 (so that the sum 8+6 is less than the solution we have so far). Eventually, as the phase 1 search depth increases, the length of allowed phase 2 solutions decreases until phase 1 has reached the length of the best solution found so far. This means that it is an optimal solution.

The basic outline of the code is listed below. It is essentially two copies of the IDA code we saw previously, except for the parts in bold type.


maxLength=9999

function Kociemba ( position p)
  for depth d from 0 to maxLength
    Phase1search( p; d )
  endfor
endfunction

function Phase1search( position p; depth d )
  if d=0 then
    if subgoal reached and last move was a quarter turn of R, L, F, or B then
      Phase2start( p )
    endif
  elseif d>0 then
    if prune1[p]<=d then
      for each available move m
        Phase1search( result of m applied to p; d-1 )
      endfor
    endif
  endif
endfunction

function Phase2start ( position p)
  for depth d from 0 to maxLength - currentDepth
    Phase2search( p; d )
  endfor
endfunction

function Phase2search( position p; depth d )
  if d=0 then
    if solved then
      Found a solution!
      maxLength = currentDepth-1
    endif
  elseif d>0 then
    if prune2[p]<=d then
      for each available move m
        Phase2search( result of m applied to p; d-1 )
      endfor
    endif
  endif
endfunction

One important subtlety is that phase 1 should end on a move that does not occur in the move set of phase 2 (i.e. F, F', B, B', R, R', L, or L'). If you do not do this, then all the same move sequences will be searched again after the phase 1 length is increased.

This algorithm is extremely effective. It very quickly finds solutions which are not far from being optimal. To see just how powerful this algorithm is, you can download Herbert Kociemba's incredible Cube Explorer from his page.

Although Kociemba originally designed his algorithm for solving the normal Rubik's cube, it is possible to apply it to other puzzles. My first Square-1 solver uses it for example, and I also once made a Siamese Cube solver. Any puzzle for which you can find a subgroup (generated by single moves) that makes the two phases roughly equal, and which is small enough to be calculated by IDA*, can have the Kociemba algorithm applied to it.

Multi-phase Algorithms

Let's reconsider the Thistlethwaite algorithm. It has four stages, where each stage is a sub-problem for which God's Algorithm has been calculated. In its original form each stage is solved once optimally, resulting in a solution to the puzzle. As we have already seen, alternative optimal solutions to an early stage may lead to positions that give shorter solutions in the later stages. Therefore an obvious improvement is to do a search in each stage that visits every alternative optimal solution.

This adaptation of Thistlethwaite works well, and will result in somewhat shorter overall solutions. It is also quite fast since there are usually not that many alternative solutions in a stage, and they can be generated very quickly from the stage's God's Algorithm database. To be really effective however, we would also have to try non-optimal solutions in one or more stages, just like Kociemba's algorithm.

The difficulty with this approach lies in bounding the depth of the search in each phase. Suppose there are n phases, and that we were to naively copy the Kociemba approach exactly. Then phase n-1 keeps getting extended until it consumes phase n, and gives an optimal solution for those two phases combined. At this point phase n-2 is searched for another solution, and then phases n-1 and n-2 are again searched from scratch. This continues until eventually the phase n-2 search has extended so far as to consume phases n-1 and n, thus giving an optimal solution for the last three phases.
This clearly will not work very well. The algorithm spends all its time in the later phases, optimising small parts of the solution, without even trying alternative phase 1 solutions.

It is clearly necessary to limit the search depths of later phases if we ever want to extend the searches of earlier phases. The naive implementation above obviously fails, but there is a better way. First each phase is done optimally, as in the Thistlethwaite adaptation above. Once all those alternatives have been exhaustively searched, introduce one move of slackness which is to be used in any of the first n-1 phases. In other words, any one of those first n-1 phases is allowed to use one extra move, while the other n-2 phases remain optimal. Once all these possibilities have been searched, do the same with two moves of slackness, to be taken up by any one or two of the first n-1 phases. This continues, theoretically until the slackness plus the minimal length of the first phase equals the length of the best solution found. In practice, you would break off the algorithm before then when the solutions are good enough.

I have successfully applied this algorithm to Peter's Black hole, to find a solution of 150 moves in about 90 minutes. I also ran straightforward IDA* for about 24 hours until it exhaustively searched all sequences of up to 118 moves without success. It would take about 30 times as long to get through depth 120.