New hex-axes search 2x faster than triple-axes search
Submitted by rokicki on Tue, 01/22/2008 - 16:00.
One interesting option in Kociemba's Cube Explorer is the Triple Search option.
This option searches along three axes at once, instead of just one.
How much does Triple Search help? For random cubes, when searching for a length
20 solution, it helps tremendously. I implemented my own Kociemba solver with
single-axis search, triple-axis search, and a new "six-axis" search, and compared
the amount of time needed to find length 20 or better solutions for 3,000 random
cubes. This program was single-threaded (Kociemba's cube explorer is multi-threaded),
runs only from the command line, and is brand new code (so it has not been heavily
optimized yet). The time to run is as follows:
Single-axis search 17m50s 2.8 sols/s Triple-axes search 3m55s 12.8 sols/s Hex-axes search 1m40s 30.0 sols/sThis shows that for this specific problem, triple-axes search is much faster than single-axis search, and hex-axes search is faster yet. What is hex-axes search? It is simply solving the three axes of the original position in parallel with the three axes of the *inverse* position. (Of course you should check that the original position is not isomorphic to the inverse position.) If anyone else has a Kociemba solver and would like to confirm these results, that would be greatly appreciated.