benbotto/rubiks-cube-cracker

Some help on optimization

Opened this issue · 0 comments

Hi Ben !
I'm currently working on a university project for which I decided to program a Rubik's Cube solver. My project is coded in Ocaml, and I'm using your project and Medium articles, with a few other additional math articles, as a reference and they have been a great help so far, so first off, thank you !
However, I'm currently having a hard time optimizing the heuristics building phase. Right now I'm stuck on the corner heuristics ; the IDS program i made works, but it super slow, it takes about quarter an hour to reach depth 7. As a consequence, I was wondering if I could request your help for a few questions.

  • My main question is about Korf's algorithm on the Lehmer Sequence. I was a bit surprised to see that my implementation of the linear version using a pre-computed hashtable to count ones... Runs slower than the quadratic version ?! I couldn't make the built-in modules with bitstring structures work on my device, so i made my own structure using int Arrays. Nevertheless, the implementation is quite efficient, but still, timing 1M executions of the program is 1 second faster with the quadratic version. Did this algorithm cause you any trouble in optimisation, and if so would you have any advices to make it more optimal ?
  • Another quick question : what type of data structure do you use to store the heuristics outside of your program ? Would a CSV file do the job, or would you suggest something better ?

Thank you for your help, have a good day :))