The most popularly used algorithm is 2-phase algorithm solver.
In a first phase you Reduce the cube state to a one that can be solved in only 180-degree turns, and in the second phase you complete the job using only 180-degree turns.
It has a nice property of splitting the work roughly in half (so both of those phases have roughly half bits of complexity of the full puzzle). And both of them are small enough that can be solved pretty instantly.
The optimal Reduction is not often leading to optimal solution, so you try out many different Reductions and see which one can be completed fastest. Interestingly - this is also the approach top human solvers use in Fewest Moves event.
This very nice library is a minimalistic implementation of 2phase algorithm and can generate hundreds of scrambles per second in the browser (so generating random state and then solving and then printing) and it hardly ever produces scramble longer than 20 moves. It's used by cubing trainers / timers etc.
So a good algorithm in a fast language on a good cpu should solve a cube in roughly 20 moves in probabaly 0.001s.
However to squeeze few miliseconds here and there it would make sense to read the cube state, use some very fast heuristic to make a first move, and utilize the 0.1s it takes to rotate the first face to find the best possible solution afterwards. Probably by the move 3 we will reach optimal solution.
I noticed their solution used a fair number of concurrent opposing side rotations. I don't think these moves are very common unless you specifically optimize for it?
If you have a random sequence of moves then after each move you have 1/5 chance of turning the opposite face. So the fact that in 16 moves sequence they had it twice is roughly expected even if they didn't optimize for it
In a first phase you Reduce the cube state to a one that can be solved in only 180-degree turns, and in the second phase you complete the job using only 180-degree turns.
It has a nice property of splitting the work roughly in half (so both of those phases have roughly half bits of complexity of the full puzzle). And both of them are small enough that can be solved pretty instantly.
The optimal Reduction is not often leading to optimal solution, so you try out many different Reductions and see which one can be completed fastest. Interestingly - this is also the approach top human solvers use in Fewest Moves event.
https://github.com/cs0x7f/min2phase (in java) and https://github.com/cs0x7f/min2phase.js (in js)
This very nice library is a minimalistic implementation of 2phase algorithm and can generate hundreds of scrambles per second in the browser (so generating random state and then solving and then printing) and it hardly ever produces scramble longer than 20 moves. It's used by cubing trainers / timers etc.
So a good algorithm in a fast language on a good cpu should solve a cube in roughly 20 moves in probabaly 0.001s.
However to squeeze few miliseconds here and there it would make sense to read the cube state, use some very fast heuristic to make a first move, and utilize the 0.1s it takes to rotate the first face to find the best possible solution afterwards. Probably by the move 3 we will reach optimal solution.