• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Online optimal Rubik's Cube scrambler

Voltara

Member
Joined
May 12, 2018
Messages
12
WCA
2018SKAL02
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.
 

Voltara

Member
Joined
May 12, 2018
Messages
12
WCA
2018SKAL02
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
Code:
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
Code:
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
Code:
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
 
Top