Pruning Table Types

The Cycle Combination Solver uses a separate pruning table per the puzzle orbits. For the Rubik’s Cube, that means one pruning table for the corners and one for the edges. To get an admissible heuristic for an individual position, we query each pruning table based on the states of the position’s corresponding orbits and take the maximum value. A brief example: if querying a Rubik’s Cube state returns on the corners pruning table and on the edges pruning table, then its admissible heuristic is the maximum of the two, . We established that larger heuristic values are better, and the optimality guarantee still stands because each individual pruning table is already admissible.

Generating a pruning table for an orbit is done in two phases. First, we enumerate every single position of the orbit and mark solutions of the Cycle Combination Solver. Then, we search the Rubik’s Cube tree but from these solution states instead of from the solved state, and storing the amount of moves required to reach each state found as the admissible heuristic.

The Cycle Combination Solver supports four different types of pruning tables: the exact pruning table, the approximate pruning table, the cycle structure pruning table, and the fixed pruning table. They are dynamically chosen at runtime based on a maximum memory limit option.

We defer our discussion of pruning table types for a later revision.

Finally, the Cycle Combination Solver generates the pruning tables and performs IDA* search at the same time. It would not be very efficient for the Cycle Combination Solver to spend all of its time generating the pruning tables only for the actual searching part to be easy, so it balances out querying and generation; starting from an uninitialized pruning table, if the number of queries exceeds the number of set values by a factor of , it pauses the search to generate a deeper layer of that pruning table and then continues.

The Cycle Combination Solver supports three different data compression types: no compression, nxopt compression, and tabled asymmetric numeral systems (tANS) compression. They are dynamically chosen at runtime based on a maximum memory limit option.

We defer our discussion of pruning table compression for a later revision.