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:
H0 = <L,R,F,B,U2,D2>, H1 = <L,R,F2,B2U2,D2>, H2 = <L2,R2,F2,B2,U2,D2> to find a solution.
He used static tables for the maneuvers and the algorithm requires at most 52 moves.

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.
When computing the index for the pruning table, both coordinates are used. This means, that we have an entry for each possible phase 1 position.

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.
So we use three helper-coordinates which are also defined in phase 1 (UDSliceSorted, RLSliceSorted and FBSliceSorted), each describing the exact positions of the 4 edges of a slice. Helper-coordinate div 24 gives the positional part, helper-coordinate mod 24 describes the possible permutations of the 4 edges within the position.

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.
The phase 2 edge permutation coordinate can be extracted from the RLSliceSorted and and FBSliceSorted coordinates with help of the table GetEdge8Perm of size 11880*24. GetEdge8Perm[RLSliceSorted,FBSliceSorted mod 24] gives the coordinate. We may use FBSliceSorted mod 24 here, because the positional part information of the FB slice cubies is redundant.
The corner permutation coordinate is already defined in phase 1. We use a raw-coordinate (0..40329) in the movetable. Before building the index in the pruning table (together with the phase 2 edge permutation coordinate), it is mapped to a sym-coordinate with 2768 classes.

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.
So we can jump back immediately to find the next subobtimal phase 1 solution .

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.