## Two-Phase Algorithm Details |

I developed the Two-Phase Algorithm in 1991 and 1992. It
was inspired by the the Thistlethwaite algorithm to solve the cube. His
method involves working through the following sequence of subgroups: Reducing the number of intermediate subgroups would give shorter solutions and I decided to use only one subgroup G1 = <U,D,R2,L2,F2,B2> which is equivalent to Thistlethwaite's H1. But it was clear, that in this case static tables for the maneuvers were impossible because of the size of the subgroup. So these maneuvers had to be computed dynamically during the solving procedure. With the hardware I used (8 MHZ Atari ST with 1 MB of RAM) this was far from trivial because there are about 2217 million different positions in phase 1 (getting into G1) and about 19508 million positions in phase 2 (getting the cube solved in G1). After a long struggle I finally found the ingredients which made the maneuver search work: - Mapping permutations and orientations to natural numbers and implementing moves as table-lookups for these numbers.
- Computing from these numbers some indices for tables which hold information about the distance to the goal state.
Phase 1 needs at most 12 moves (see distribution) and phase 2 needs at most 18 moves (Michael Reid showed this in 1995, do not see distribution because the phase 2 pruning table only holds 1/24 of all possible phase 2 positions). So the first solution generated by the Two-Phase Algorithm will always have at most 30 moves. The idea to combine suboptimal solutions of phase 1 with optimal solutions of phase 2 to get shorter overall solutions was quite obvious then, but I was surprised how short the overall solutions are - usually within seconds 22 moves or less on the Atari ST and 20 moves or less in the current implementation and a year 2000 PC. I did not use symmetry reductions in this first version of the Two-Phase Algorithm. The idea for symmetry reduction came from Mike Reid who used it in 1997 to hold a complete phase 1 pruning table in memory then in his one-phase optimal solver. |

In the current implementation (Cube Explorer 2) symmetry reduction also is used. In phase 1 we use two coordinates: The FlipUDSlice coordinate (a sym-coordinate
with 64430 different classes which combines the edge
orientation coordinate and the UDSlice
coordinate) and the corner orientation
coordinate. In phase 2 we have the problem of initializing the three phase 2 coordinates corner permutation, phase 2 UDSlice and phase 2 edge permutation. Because the phase 2 UDSlice and phase 2 edge permutation coordinates
are not defined in phase 1, we would have to go back to the cubie
level to apply our phase 1 solution to the cube before computing
the phase 2 coordinates. In phase 2 the phase 2 UDSlice
coordinate is identical to the UDSliceSorted coordinate, so we to
do not need to do any computation at all. |

As already mentioned above, the algorithm does not stop when a first solution is found but continues to search for shorter solutions by carrying out phase 2 from suboptimal solutions of phase 1. For example, if the first solution has 10 moves in phase 1 followed by 12 moves in phase 2, the second solution could have 11 moves in phase 1 and only 5 moves in phase 2. The length of the phase 1 maneuvers increases and the length of the phase 2 maneuvers decreases. Usually the phase 2 length drops very soon (typically below 9).
The performance of the algorithm increases considerably if we do not initialize
all three coordinates when entering phase 2 but only the corner permutation
coordinate. A small pruning table only for this coordinate shows im most
cases, that even the corner permutation coordinate cannot be restored
within this small number of moves. |

Another way to considerably increase the performance is to throw away certain phase 1 suboptimal solutions. If the maneuver M defines a phase 1 solution, then for example M R2 or M U F2 of course are also suboptimal phase 1 solutions, because R2, F2 and U are phase 2 moves. But these solutions are irrelevant, because phase 2 applied to M R2 will never give a shorter overall solution than phase 2 applied to M. In the current implementation we throw away any phase 1 suboptimal solution maneuver, if some submaneuver beginning with the first move already is a phase 1 solution. We might loose some solutions doing like this, put in practice this is irrelevant except for the fact, that the algorithm now is not suited any more to prove a certain maneuver to be optimal. But this is done better by using the optimal solver anyway. Take for example the cube C generated by R L U2 R L . F (6 moves). The algorithm will not find the solution F' . L' R' U2 L' R' because applying F' to C brings the cube into the subgroup G1 and is therefore is a phase 1 solution. Any suboptimal phase 1 solution starting with F' will be discarded. |