Online optimal Rubik's Cube scrambler

[Voltara]

My online scrambler at https://voltara.org/cube/ just got its first major update in nearly ten years. It now produces optimal move sequences, i.e. the minimum number of moves necessary to reach a randomly selected position (17 or 18 moves, ~94% of the time.)

Previously, it used a C++ implementation of Kociemba's algorithm that I wrote back in 2003. The new version uses multiple solvers that work in tandem to find optimal solutions to randomly generated positions. These are written in C++ and CUDA, and use Two-Phase and IDA* to prove upper and lower bounds respectively for a meet-in-the-middle approach.

The solvers are a still work in progress and haven't been tuned yet (I have been favoring correctness over raw speed), but they are currently finding optimal solutions at an average rate of about 2.7/second on my Mini-ITX desktop. This is within the range of what I should expect from this class of hardware, based on results reported previously by Tomas Rokicki.

 

[ch_ts]

Hi, what did you use for pattern databases?

 

[Voltara]

Hi, what did you use for pattern databases?

For the CPU IDA* search, I am using three pattern databases which I arrived at through experimentation. My constraint was the solver had to fit within 32GB of memory. I'm sure these can be improved upon; I stopped experimenting and moved on to other areas of the code when I felt the throughput was "good enough". I would be interested to hear about PDBs that others have had success with.

Edge Permutation (96-way symmetry); Flip: 2GB

Depth       96-way
------------------
 0f              1
 1f              2
 2f              8
 3f             48
 4f            512
 5f           6088
 6f          75166
 7f         924453
 8f       11026268
 9f      121508236
10f     1157264341
11f     5793688256
12f     3197433505
13f        3548931
14f             25
------------------
Total  10285475840

Edge Permutation (96-way symmetry); Corner Permutation: 19GB

Depth       96-way
------------------
 0f              1
 1f              2
 2f              8
 3f             48
 4f            517
 5f           6349
 6f          81319
 7f        1061716
 8f       13907673
 9f      181486649
10f     2311149704
11f    24598779873
12f    71384683232
13f     2756495662
14f             47
------------------
Total 101247652800

UDSliceSorted + 8-Edge Flip (16-way symmetry, tested on 3 axes); Twist + 4-Corner Combination: 5.5GB

Depth       16-way
------------------
 0f              1
 1f              2
 2f             18
 3f            175
 4f           1804
 5f          21146
 6f         265033
 7f        3360283
 8f       42274687
 9f      511135158
10f     5059755130
11f    19065087858
12f     4567238714
13f         235391
------------------
Total  29249375400