Fast solver for arbitrary target groups

As you know one of the breakthrough of cube computing is Silviu's successful depth calculation of all symmetrical positions. This breakthrough used a two phase algorithm that has the symmetrical positions as its target group. Regular solvers will simply stop once they hit the position they want to solve but Silviu's idea is to never stop until all positions in the target group are hit... This way of solving is very fast and it is what Rokiki has used to calculate the "group that fixes the edges".

My question is can this be applied to arbitrary target groups whose elements share something in common? for example let's say my target group is some conjugacy class of the cube. How can I calculate the depth of each element in this conjugacy class using Silviu's idea?

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

My common property is anti-symmetry

The method of Silviu is exactly what I though: using Rokicki's method on the coset on the clean cube. I read Rokicki's paper about 25f. The reason why it is fast is that you have a perfect prune system for the target class. I do not know how to make such a system for conjugacy classes, a system that requires a reasonable amount of memory.

In this topic, I formulated a prune system that is a factor of about 3300 from perfect to solve anti-symmetric cube positions where the symmetry has order ≤ 2 (others are symmetric in addition), using less than 1GB of memory. Now I think that the table should be twice as large, about 1.7 GB. The prune system only looks at the positional cube and is a factor 12/5 away from perfect for that cube. The prune table is 24*48*5 times smaller than the positional cube (the factor 5 for 5 entries per byte). You can improve the prune system by adding more tables, but in that case, you cannot tell how far the prune system is away from being perfect.

The prune system solves a more general problem, namely all positions of order 2 on the centerless cube, with rotations and reflections of the cube added as moves to the face turns. Rotations and reflections of the cube count for zero in the metric (so it is uneconomical to do a double rotation with face turns), since they do nothing with the centerless cube by definition: they only change the meanings of subsequent moves. Order 2 means that some generator of the position generates the clean centerless cube when applied twice, without the need to view the cube differently to get the same clean cube as before (the centerless cube is not a group). If the rotations and reflections of the whole cube add up to a symmetry of order ≤ 2, then you have an anti-symmetry of order ≤ 2. Since there are 20 symmetries of order ≤ 2, the prune system will get a factor 12/5 better for the more general problem.

I think that solving all anti-symmetric cube positions can be done, but it takes a huge amount of processor time. But there are also many computers with 2 GB of memory that do nothing. In order to use a binary check table for all anti-symmetric positions, your computer must have 32GB. But since you will not compute all solutions on a single computer, you will need to pick the bests solutions anyway, so why using a binary check table? Picking the best solutions can be done as follows. You first distribute the solutions among bags of 1G = 2^30 positions. Next, you scan those bags and pick the best solutions, using a table of 1 GB or something.

But it might be a good idea to first solve the group that fixes the corners. This group is even larger than the number of antisymmetric positions, but has a perfect prune system, namely the corner table.

GAP for prunning

Silviu used GAP to generate the pruning table for the symmertical positions somehow... So I think it should be possible to do the same thing for a conjugacy class. Unfortunately I do not understand very well what he did to be able to implement this myself and there is no code around as far as I know that explains what he did.