## 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. 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.
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) 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; 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. 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. |