Optimal Solver Challenge: the Hermit position

[Bruce MacKenzie]

Back around 2010, I wrote an IDA optimal cube solver. Both Rokicki and Kociemba had published optimal solver code on the web at that time and my effort was in the same ballpark. A bit slower but not that much. My solver is unusual in that it does not use solving the cosets of the <U, D, R2, L2, F2, B2> subgroup for pruning. Rather, I use solving the cosets of the solved face subgroups for pruning. I've spent the last several days modifying my code to make use of parallel processing by breaking the search tree into several branches and searching the branches concurrently. I have since run a series of benchmarks on the solver and I must say I am rather pleased. On average, the solver optimally solves randomly generated cube states in 20.6 seconds in the q-turn metric and 50.6 seconds in the f-turn metric. Super flip is solved in around 45 seconds in both metrics. And the Hermit position, that is, super flip composed with four spot, is solved in 3 minutes 22 seconds in the f-turn metric. In the q-turn metric the solver finds a solution to the depth 26 antipode in 2 hr 40 min.

I know there are a number of solvers out there. Rokicki has shown in the past that he can dance rings around me writing code to tackle such tasks. However, I would be interested in knowing how my results compare to modern solvers.

 

[bcube]

However, I would be interested in knowing how my results compare to modern solvers.

Compare with results of the first 2 links in this post. I personally like this performance summary because it is reproducible.

 

[Bruce MacKenzie]

Compare with results of the first 2 links in this post. I personally like this performance summary because it is reproducible.

Thank you.

Some of the results shown in the links employ hefty machines with huge pruning tables. My solver makes do with a 1.6 Gb table. In order to fit the table in memory at that time I had to use symmetry reduction which adds a lot of overhead to the search. I should rewrite the code without the reduction. This would require about 13 Gb of memory which my machine can now handle.

 

[qq280833822]

I've collected some sota solvers here: https://github.com/cs0x7f/cube_solver_test (note that some solvers don't support multi-thread solving on a single state, so this is for reference only). With a solver using 2GB of memory, the solving time for finding a single optimal solution in HTM for a random state is approximately 1 second. Since the solving time is highly dependent on hardware, you can compare it with the solver I wrote previously here: https://cstimer.net/cubeopt/

If you're willing to release the source code (or provide an executable file or a webpage for testing), I can also add your solver.

 

[Bruce MacKenzie]

If you're willing to release the source code (or provide an executable file or a webpage for testing), I can also add your solver.

I uploaded the xCode project and executable to GITHUB several years ago. See Cube3x3x3 It's an older version and doesn't handle multitasking on symmetrical states as well but comparable to the latest in most respects. I am in the midst of upgrading my solver now. I'm trying to design a deeper pruning table. With a branching factor of 9.37 each increase of the effective pruning depth of one depth increases the speed by that factor.