Pruning Tables

The speed of the Two-Phase-Algorithm and the Optimals Solvers depend on the ability to give a lower bound for the number of moves it takes to bring the cube back to a goal state from a given state because it allows tree pruning during the search. The goal state is a certain subgroup G1 in case of the first phase of the Two-Phase-Algorithm. The goal states for the Optimal Solvers are described on the page Optimal Solvers.

We base the pruning tables on coordinates. Remember that a coordinate or also a tuple of several coordinates represent cosets corresponing to some subgroup H (if we use a tuple of coordinates, the corresponding subgroup H is the intersection of the subgroups defining the single coordinates). A coordinate itself or an index computed from two or three coordinates define the position in the pruning table. In this position we store the number of moves which are necessary to bring the cube back to the subgroup H.
Because the goal state is always included in H (phase 2, optimal solvers) or is identical with H (phase 1), the number of moves stored in the pruning table is always a lower bound for the number of moves to bring the cube back to the goal state. This is essential to make the algorithm work.

We need pruning tables for phase 1 and phase 2 of the Two-Phase Algorithm and for the huge optimal solver. The pruning table for the standard optimal solver is identical to the phase1 pruning table.

In all three cases, the position in the pruning table is computed from a sym-coordinate and one or two raw-coordinates.

Pruning Table
Number of Table-Entries
Maximal pruning depth
Phase 1
(64430 equivalence classes)
Corner Twist x = UDTwist
(2187 cases)
Phase 2
Corner Permutation
(2768 equivalence cases)
Edge Permutation x
(40320 cases)
Huge Optimal Solver
(788 equivalence cases)
Edge Flip x1
(2048 cases)
Corner Twist x2
(2187 cases)

If you are interested in the exact distibution of the pruning values have a look at this table

Let the FlipUDSlice sym-coordinate be for example correspond to the pair (y,i), where y is the index of the equivalence class and i is the index of the corresponding symmetry and let the corner twist be x. Let P be a permutation of the cube belonging to these indices. Then by conjugation S(i)*P*S(i)-1 we get a cube which has the same distance from the goal state and which has the FlipUDSlice sym-coordinate (y,0) and the corner twist x'. Then the position in the pruning table is computed by 2187*y + x'.

This principle holds for the computation of the indices in all pruning tables: Extract the index i (0<=i<16) of the symmetry out of the sym-coordinate and transform the cube by conjugation with S(i) to an equivalent cube with the same equivalence class index y but the symmetry index 0. Transform the raw-coordinate x (or x1 and x2 in case of the Huge Optimal Solver) to x' (x1',x2').

The index in the pruning table in phase 1 is then computed by 2187*y + x', in phase 2 by 2768*x' + y (hmmm, why did I take not 40320*y +x' ?) and in the huge solver (2048*y+x1')*2187+x2'.

The transformation of the raw indices is done by tables (see sourcecode, CordCube.pas)

TwistConjugate: array[0..2187-1,0..15] of Word;
FlipConjugate: array of array of array {[0..2048-1,0..15,0..788-1]}of Word;
Edge8PosConjugate: array[0..40320-1,0..15] of Word;

A you can see, the conjugation for the edge flip which is used in the huge solver pruning table is a bit more complicated. The reason is, that as mentioned here the subgroup which defines the flip coordinate cosets is not compatible with the 16 symmetries. But if you add the information of the UDSliceSorted equivalence class, the transformation is possible.

To reduce memory size, we actually do not store the number of moves but only the number of moves modulo 3. This is possible because each faceturn changes the number of moves only by -1, 0 or 1. So if you apply a faceturn you are able to keep track of the number of moves, if you know the number of moves to solve the cube for the initial state.

This number for the initial state also can be reconstructed with the table mod 3: From the initial state try which one of the 18 faceturns decreases the number modulo 3 (there must be a faceturn with this property, or you already are in the goal state). Repeat this until you have reached the goal state and count the number of moves you needed to do so (procedures GetPrun, GetPrunBig and function GetPrunPhase2 in CordCube.pas)

During table generation we use 2 bits for each entry because we need a fourth state to mark an entry as empty. Afterwards we compress the table storing 5 entries in one byte, using only 1.6 bits for each entry. We do the compression not linear like (0,1,2,3,4),(5,6,7,8,9),(10,11,12,13,14)...but in the way (0,1,2,3,x), (4,5,6,7,x+1),(8,9,10,11,x+2),....where x is about 4/5 of the total number of entries. In this way we do not need a (div 5) and (mod 5) arithmetic but a much faster (div 4) and (mod 4) arithmetic.

We generate the table in a breadth-first "forward-search" manner. We store depth 0 at the position of the goal state and apply all 18 moves to this state. At the corresponding positions we store depth 1. In the next pass we apply the 18 moves to all states corresponding to those positions in the pruning table which have an entry 1. We write 2 at the resulting position if it is marked as empty etc...

If you take a look for example at CreateFlipUDSlicePruningTable in CordCube.pas you see, that the code is not as straightforward as described above. Because we use a sym-coordinate (FlipUDSlice) together with a raw-coordinate (UDTwist) to compute the index in the pruning table, we will built an incorrect table if we do not proceed very carefully.
The problem is a permutations A, where the sym-coordinate is not unique because the permutation has itself some symmetries. Let (y,i1) and (y,i2) correspond to two classindex-symmetryindex pairs of the FlipUDSlice coordinate which belong to the same FlipUDSlice raw-coordinate. Let the UD-Twist coordinate of the permutation A be x. The index of the pruning table is computed by 2187*y + x', where x ' is the UDTwist coordinate of the permutation S(i1)*A*S(i1)-1 respective S(i2)*A*S(i2)-1 . Because these 2 permutations usually have different UDTwist coordinates, there is more than one position in the pruning table we have to fill in this case. So we must carefully analyze the symmetries of the FlipUDSlice coordinate.

If there are not many empty entries left in the pruning table, we flip to "backward search". We apply the 18 moves to all permutations which belong to empty entries and look if the result is a permutation which has a entry corresponding to the depth d of the last pass. In this case we fill the entry with d+1. In this way we save a considerable amount of time when generating the tables.