Symmetry Reduction

Symmetry reduction is the most famous way to compress pruning table entries. We thank Kociemba for his excellent explanations of symmetry reduction on his website. Take a good look at these two cube positions below:

They are different but they are basically identical. If you replace red with blue, blue with orange, orange with green, green with red, you will have transformed into . Because these two cube positions have the exact same structure of pieces, they need the same number of moves to reach a Cycle Combination Solver solution.

We call such positions symmetrically equivalent. If we really wanted to be serious about pruning table compression, what we can do is store a single representative of all symmetrically equivalent cubes because they would all share the same admissible heuristic value, and keeping a separate entry for each of these positions is a waste of memory.

Defining symmetrically equivalent cubes by figuring out an arbitrary way to recolor the cube is a very handwavy way to think about it, nor is it very efficient. The more mathematically precise way to define symmetrically equivalent cubes is with permutations. Two cube positions and are symmetrically equivalent if there exists a symmetry of the cube such that , where the operations are spatial manipulations the whole cube. We can prove that and are symmetrically equivalent using this model:

In group theory, is called a conjugation of by —we first perform the symmetry, apply our desired permutation, and then perform the inverse of the symmetry to restore the original reference frame. The symmetries of arbitrary polyhedra themselves form a group, called a symmetry group, so we can guarantee an element exists.

Symmetry reduction compresses the pruning table by the number distinct symmetries—all possible values of —of the cube, so how many are there? The symmetry group of the cube consists of 24 rotational symmetries and 24 mirror symmetries, for a total of 48 distinct symmetries. You can think of the mirror symmetries by imagining holding a Rubik’s Cube position in a mirror to get a mirror image of that position. In this reflectional domain, we again apply the rotational symmetries. We illustrate one (of very many) ways to uniquely construct all of these symmetries, with the mirror symmetry highlighted in red.

We discussed how symmetry conjugation temporarily changes a position’s frame of reference before subsequently restoring it. Without any further context this would be fine, but in programming we efficiently represent a Rubik’s Cube position by treating the centers as a fixed reference frame to avoid storing their states. This optimization is critical for speed because it makes position composition faster and minimizes data overhead. The ensuing caveat is that we must always refer to a fixed frame of reference, so we have to rethink how symmetry conjugation works. The solution is simple, and the established theory still holds: we define the change of reference frame as a position such that, when composed with the solved state, it transforms the pieces around the fixed frame of reference.

The takeaway is in the observation that every symmetry position has the centers in the same spatial orientation.

Notice that the and symmetries are invalid positions with this fixed reference frame—the latter because of the parity constraint, and the former because the mirror image produces a reflectional coloring. This does not matter because the inconsistencies are un-done when is applied; thus the conjugation always results in a valid position.

symmetries is already quite a lot, but we can still do better. If we can show that both an arbitrary Rubik’s Cube position and its inverse position require the same number of moves to reach a Cycle Combination Solver solution, we can once again store a single representative of the two positions and further compress the table by another factor of . We call this antisymmetry.

Let us prove that our presumption is true.

1. Let and be defined as sequences such that is an optimal solution to the Cycle Combination Solver.

2. We take the inverse of to get of the same sequence length, which is still an optimal solution to the Cycle Combination Solver. Taking the inverse of the “add 1” operation (which is ) is the “sub 1” operation; changing your frame of reference to think of “sub 1” as “add 1” yields another way to construct the exact same register.

3. We conjugate with to get of the same sequence length. It turns out that conjugate elements in a permutation group exhibit the same cycle structure, hence this is also an optimal solution to the Cycle Combination Solver. To understand why, we simplify the problem and examine the general case of two conjugate elements in a permutation group and . If permutation takes element to , then takes element to . Indeed,

   So every cycle of is taken to the cycle of . Viewing permutations as bijective maps of its elements, conjugation only relabels the elements moved by . It does not change the cycle lengths nor how many cycles there are. We apply this corollary with and .

4. We have shown that if is an optimal solution to the Cycle Combination Solver then so is . and are the same sequence length; thus, the positions reached by any arbitrary and by starting from the solved state require the same number of moves to reach an optimal Cycle Combination Solver solution. This completes our proof.

Symmetry and antisymmetry reduction comes with a cost. During IDA* search, every position must be transformed to its “symmetry and antisymmetry” representative before using it to query the pruning table. To do so we conjugate the position by the symmetries and the inverse by the antisymmetries to explore all the possible representatives. To identify the representative position after each conjugation, we look at its raw binary state representation and choose the lexicographic minimum (i.e. the minimum comparing byte-by-byte). Multiple symmetries may produce the representative position, however that is okay because at no point do we actually care about which symmetry conjugation did so; the result is still the same.

The symmetry and antisymmetry reduction algorithm as described so far would be slow—we need to perform 96 symmetry conjugations, and each is about as expensive as two moves. We use the following trick described by Rokicki: instead of computing the full conjugation for every symmetry conjugation, we compute the elements one-at-a-time. We take the least possible value for the first element of all the symmetry conjugations and filter for the ones that give us that value. Then, we compute all the second symmetry conjugation elements, find the least possible value for that, and so on. This optimization usually only ends up performing a single full symmetry conjugation.