How does cube6.h and pre-moving work?

[ArhanChaudhary]

Hello, this is not an actual issue but rather a question about the codebase. During search, it makes sense that the inverse is chosen if there are less available moves from that state. However I don't understand the logic behind how pre-moving works, the cube6 data structure, nor the details of how solver::search works. For example, what does this do, and what is the point of solver::queue_search?

uint8_t face = _popcnt32(011111 << m >> 15);
uint8_t axis = (face + (face > 2)) & 3;

// preserve one of the inverse cube pruning values
skip = axis + 3;
val = (prune_vals >> (4 * skip)) & 0xf;

Additionally, why does the BPMX use sol > max_depth + 2 in particular? It's a bit difficult to visualize how it works just from reading.

[Voltara]

Some of the questions (like the one about BPMX) will take me a bit of time to remember how it works, so I'll either answer those in a followup response, or commit some code comments.

Pre-moves
Say for example you're solving a cube that was scrambled with the sequence R U F L. If you were solving a physical cube, the optimal first move would be L', which cancels the last move in the scramble: R U F L L' → R U F.

Another optimal first move would be to prepend R' to the move sequence, canceling the first move: R' R U F L → U F L. This is not something you can do with a physical cube, but it's very easy to do in software. (It costs exactly the same as making a regular move.)

cube6
There are 24 ways to orient a cube, for example white on top, green in front. Reorienting the cube doesn't change the number of moves required to solve it. If you include mirror-image reflection, the number of symmetries doubles to become 48. And if you include "anti-symmetry" (because the scramble and its inverse both have the same number of moves) then the total becomes 96.

It's easy (in software) to get from one scramble to any of its symmetric equivalents. If y is the whole-cube rotation that parallels the U move, then the conjugation y (R U F L) y' would transform R U F L into B U R F. By conjugating/inverting, we can get up to 96 different, equivalent cubes that we can look up in the pruning table, then keep the maximum value.

Except the pruning table itself already accounts for some symmetry. This is done to keep the table as small as possible, and to reduce the number of lookups required. This pruning table has 16-way symmetry (it doesn't include inverses, and the U/D axis is "special".) Therefore, out of the 96 potential lookups, only 96 / 16 = 6 are distinct.

The cube6 class simply maintains each of those 6 symmetric equivalents. Calling the move() function does the correct move/premove to each of those 6 in order to keep them consistent. This avoids having to conjugate or invert each time we want to do a pruning lookup.

solver::queue_search
The short answer here is (for reasons I don't fully understand) the search order matters. Positions that experienced less pruning during the previous iteration seem more likely to be on the optimal solution path. queue_search implements this prioritization heuristic for the 43,239 positions at distance 4 from the start.

[ArhanChaudhary]

Thank you, that makes much more sense. I would greatly appreciate a commit with code comments.