How to make a cross solver/ any non algorithmic step solver?

[Florentin]

Hello, while looking something up on google, I stumbled upon the phrase : "A computer can solve a cube using a human method in negligible time, well under a second, even in the slowest of programming languages.", I found that it was a nice challenge, so I picked up a method (CFOP) and attempted to do that myself and sure enough I made something that works and that has a movecount average that is similar to the one given on the wiki. But there are a few things that I did that I'm not happy with. So I am sort of looking for the solution.

I would like to precise that my question is only on the algorithmic aspect of the solving method, not on the representation of the cube.

Here are the difficulties I have had:

In order to implement the cross solution, I used the A* search algorithm (apparently not uncommon for that purpose) but it took me a long time to figure out a heuristic that makes the program terminate in a reasonable amount of time (well under a second), and the only one I have found so far is the sum of the amount of moves required to solve each edge individually, but the problem is that that heuristic most of the time overestimates the distance, therefore I have no guarantee that the solution is optimal, therefore it probably isn't.
I'm pretty sure someone (if not everyone) has done a cross solver, what heuristic do competent people use? Do they even use A*?

Basically the same question for F2L, the one I have now is very basic, sum for each pair of this heuristic : If pair solved : 0 (of course), if pair is a trigger away from being solved from U layer : 4 (AUF + 3 move insert), else 7.

And I've been trying do devise a heuristic for Roux first block but nothing I could think of terminated in less than a few minutes.

Thanks in advance, Florentin.

 

[xyzzy]

The standard A* search algorithm has some major issues when being used for cube solving. It requires you to track all of the visited nodes, but this grows exponentially with search depth. In practice, we normally use iterative deepening A* (IDA*), which is mostly the same thing, except you don't keep track of visited nodes, and you also use iterative deepening: try to find one-move paths, then if there are none, move on to two-move paths, and so on.

As for heuristic functions, you can use the maximum of the individual edge distances, rather than the sum; this gives you an admissible heuristic function, albeit one that is not very accurate. ("Admissible" meaning that the distance is never overestimated, so you can get provably optimal solutions. In other words, the heuristic function is a lower bound for the true distance.) The general strategy is to track multiple pieces at once, rather than calculating the distance for individual pieces then taking the maximum.

For cross, there are only \( 2^4\times12\times11\times10\times9=190080 \) cases in all, so you could just pre-compute exact distances for every possible configuration of the cross pieces. This can be formulated as a single source shortest path problem, which can be handled with a breadth-first search.

For Roux first block, if you fix the centres, there are \( (3^2\times8\times7)\times(2^3\times12\times11\times10)=5322240 \) configurations, which is still small enough to make a complete lookup table for, but just for the sake of example, let's say we don't want to do that. Instead, we could compute two different heuristic functions: one for the corners (\( 3^2\times8\times7=504 \)) and one for the edges (\( 2^3\times12\times11\times10=10560 \)). These two heuristic functions are individually admissible, so taking the maximum of the two is still admissible.

(Caveat: The above calculation is with the centres fixed, which isn't the most natural reference for solving Roux FB, since the M slice can be misaligned. Instead, you can fix one corner or one edge, and solve FB (which now includes one centre piece) around that.)

For F2L post-cross, this depends on how exactly you're trying to solve it. It sounds like you're restricting to the 3-move triggers like R U R' / R' U R / etc.? In that case, you have 4 corner pieces and 4 edge pieces to solve, so you can again formulate this as single source shortest path problems, and use (e.g.) a heuristic function for the corner pieces and another one for the edge pieces, then take the maximum value of the two.

(Caveat: It's a bit harder to account for cancellations between triggers, e.g. (R' U' R) (R U R') is two triggers, but only 5 moves after cancelling. Optimal solving can also lead to inscrutable solutions where triggers are done for seemingly no reason and all of a sudden there are four single-trigger pairs in a row.)

If you're not restricting to trigger-based solutions, then you now have to account for the cross pieces also moving out of their original places in the middle of the F2L solution, which vastly increases the search space.

------

For cube solving, you almost always want to use admissible heuristic functions. Inadmissible heuristics seem to be useful for centre pairing on 6×6×6 and up (where optimal solving is extremely slow), but I haven't had any luck using inadmissible heuristics anywhere else.

(edit)
Unlike 15 puzzle, where there are quite a few reasonable examples of additive heuristic functions (a collection of admissible heuristics that you can add and still remain admissible), there aren't as many examples when it comes to solving cubes. You could, just for the sake of example, come up with a lower bound for the number of F or B moves needed to solve a cube by counting the number of bad edges (like in ZZ), then repeat this for the other two axes, and finally add the three values together, but this gives terrible lower bounds.

 

[Florentin]

OK I'll look more closely at how IDA* works and come back if I have a question on that.

As for the heuristics, it was perfectly clear,
Thank you very much for the detailed answer.

 

[qwr]

Obligatory mention of http://www.cubezone.be/crossstudy.html
since there are only 190k cross cases, it is feasible to precompute every cross case and store it in a table

also I agree with everything @xyzzy said about IDA* and not storing the whole tree. Actually you could probably get away with iterative deepening DFS although there is no reason to do so