Reducing transition tables using symmetries

[Jakube]

I want to reduce my transition table size for edge permutations in my 3x3x3 solver. By using symmetry, I can reduce it by a factor of 48. I have found a way, of calculating the correct index (between 0 and 12! / 48 - 1) from a random permutation, but it is very complicated.

My method is to bring the piece 0 to the UB posititon by rotating the cube. After this, I bring the smallest piece of the positions UR, UL, BL, BR to position UR (by doing y2 x or mirroring). So I converted all 48 identical permutations into the same one. Now I need to convert this permutation into a unique number between 0 and 12! / 48 - 1. The picture shows the code for this.


I checked the results, and it works. But it is ugly as ...

Is there any nicer way of doing this?

 

[rokicki]

Wow, transition tables for edge perms? Wouldn't those be huge, *even* taking into account
symmetry reduction? You can probably go faster using actual permutations, because then
you won't incur a cache miss on the transition table lookup.

But that said, typically symmetry reductions are somewhat messy. Usually you use
approximate reductions that give up a few percent in space for simplicity. For instance
(and I'm not saying this is the best way), you can track six of the edges (doesn't matter
too much which six) and symmetry-reduce specifically on those and only those; this
gives you (12 choose 6) or a 924-element state space. You make a tiny transition table
on this space that tells you the symmetry to reduce the full permutation by. Or you
can track the first two or three edges (12 * 11 * 10, or a space of 1320) and use those.

If you play around I bet you'll come up with something you're happy with.

Note that you'll never get to 12!/48, since there are a few positions with symmetry and
thus it will be 12!/48 + c where c is some smallish value, maybe a few hundred.

 

[cuBerBruce]

One thing I've done is to divide the edge pieces into groups of 4 by which inner layer they belong to. Then represent the edge state by three 0..11880-1 values, specifying the locations for each of the sets of 4 cubies. For FTM, this requires 11,880*18*2 = 427,680 bytes for the move table. You use the same move table for all 3 sets of cubies. The EO move table would be another 2048*18*2 = 73,728 bytes. Total size 501,408 bytes.

The move code is:

	m_e4[0] = e4_move_table[m_e4[0]][move_code];
	m_e4[1] = e4_move_table[m_e4[1]][move_code];
	m_e4[2] = e4_move_table[m_e4[2]][move_code];
	m_eo = eo_move_table[m_eo][move_code];

Another interesting way of handling move tables for edges was suggested by Herbert Kociemba here.

By the way, if you use both symmetry and antisymmetry, you can reduce the 479,001,600 edge permutation positions into a neat palindromic 5022205 equivalence classes.

 

[Jakube]

For instance
(and I'm not saying this is the best way), you can track six of the edges (doesn't matter
too much which six) and symmetry-reduce specifically on those and only those; this
gives you (12 choose 6) or a 924-element state space. You make a tiny transition table
on this space that tells you the symmetry to reduce the full permutation by.

My current implemention uses something like this. I describe my edges by two small arrays of length 6, which I convert into a number between 1 and 12! / 6!.

I don't really understand, what you mean by symmetry reducing these. Of course I can take all the 48 symmetries, but how do you get a factor of 6! ? Can you please explane, how you exactly get (12 choose 6)?

The main reason, why I want to change my current method, is, because I want to build a better pruning table. At the moment I have for each of the 6-edges-group a seperate pruning table with an average depth of 5-6 moves. (Also one for all corner cases and one for all edge orientations)
So I want a bigger and better edge pruning table. But with the two indices, combining those or extracting a part of it, is not really fast.