1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
|
# Benchmarks for the H48 optimal solver and comparison with vcube
This page contains some benchmarks for some of the possible
configurations of the H48 optimal solver. For comparison we also
include similar measurements for Andrew Skalski's impressive optimal
solver [vcube](https://github.com/Voltara/vcube), which has been taken
as a benchmark reference throughout the development of H48. The two
solvers differ both in method (although they both use an A* search)
and implementation.
Similar benchmarks can be found:
* In Chen Shuang's
[dedicated github page](https://github.com/cs0x7f/cube_solver_test/wiki),
which includes many more solvers. At the time of writing, the version
of H48 used for these benchmarks is a rather old one. Note that
cube48opt is a re-implementation of the H48 solver by Chen Shuang.
* In Enrico Tenuti's [thesis](https://github.com/enricotenuti/h48thesis),
also using an old implementation of H48, but including more data and
nice plots.
## Setting
*All movecounts are in Half Turn Metric*
For the benchmarks we used some sets of random positions that can be found
in `benchmarks/scrambles`. We divide them by optimal solution length,
because the time to solve a scramble grows exponentially on the number of
moves, so mixing up positions with long and short solutions is going to
make the shorter solution almost irrelevant. Even within the same solution
length the time to solve a random position can vary significantly,
so we have used sets of 25 scrambles and taken the average of those,
except for the [Superflip](https://en.wikipedia.org/wiki/Superflip),
which is a single scramble.
For short solutions, the very low numbers we get with the largest solver
may be particularly inaccurate, because writing the solution (together
with some log messages) to standard output may take a significant portion
of the time, depending on the terminal emulator used and other factors.
We ran two different tests: finding a single optimal solution and finding
*all* optimal solution. Both problems involve an exhaustive search at
depth `n-1`, but the second also involves and exhaustive search at depth
`n`. Comparisons with vcube are only done in the first case, because
vcube's current configuration does not allow for finding multiple
solutions, as far as I am aware.
Since the size of the pruning table used by the solver is of utmost
importance, we include two statistics: time per cube and time per cube
*adjusted by table size*. The adjustment we took simply consists in
multiplying the time per cube by the size of the table. Empirically
this leads to more even results across the board, as the speed of the
solvers of the same family seems to scale linearly with the size of the
pruning table.
All benchmark tests were done on the following configuration:
* CPU: AMD Ryzen 7 7700 (8 cores, 16 virtual threads)
* Memory: 2x Corsair Vengeance 32GB 5600MHz
* Motherboard: Gigabyte B650M K
* Operating system: Debian 12 (Linux kernel 6.1.0)
* Compiler: GCC 12.2.0 for H48 and Clang 14.0.6 for vcube
## Single solution
Average time for finding a single optimal solution.
### Single thread
Time per cube (in seconds, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
|H48 h11 k2|56.1GiB | 0.23 | 1.15 | 5.08 | 31.30 | 278.47 |
|vcube 404 |31.8GiB | 0.30 | 1.25 | 6.87 | 57.49 | 291.31 |
|H48 h10 k2|28.1GiB | 0.34 | 1.80 | 7.77 | | |
|vcube 308 |21.2GiB | 0.20 | 1.11 | 6.92 | | |
|H48 h9 k2 |14.1GiB | 0.42 | 2.84 | 12.86 | | |
|vcube 208 | 7.3GiB | 0.57 | 4.41 | 20.75 | | |
|H48 h8 k2 | 7.1GiB | 0.86 | 6.66 | 27.40 | | |
|H48 h7 k2 | 3.6GiB | 1.47 | 8.90 | 42.46 | | |
|vcube 112 | 2.4GiB | 1.01 | 9.39 | | | |
|H48 h6 k2 | 1.8GiB | 2.28 | 16.89 | | | |
Time per cube adjusted for tables size (in seconds \* GiB, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
|H48 h11 k2|56.1GiB | 12.90 | 64.51 | 284.99 |1755.93 |15622.17 |
|vcube 404 |31.8GiB | 9.54 | 39.75 | 218.47 |1828.18 | 9263.66 |
|H48 h10 k2|28.1GiB | 9.55 | 50.58 | 218.34 | | |
|vcube 308 |21.2GiB | 4.24 | 23.53 | 146.70 | | |
|H48 h9 k2 |14.1GiB | 5.92 | 40.04 | 181.33 | | |
|vcube 208 | 7.3GiB | 4.16 | 32.19 | 151.48 | | |
|H48 h8 k2 | 7.1GiB | 6.11 | 47.29 | 194.54 | | |
|H48 h7 k2 | 3.6GiB | 5.29 | 32.04 | 152.86 | | |
|vcube 112 | 2.4GiB | 2.42 | 22.53 | | | |
|H48 h6 k2 | 1.8GiB | 4.10 | 30.40 | | | |
### Multithread (4 threads)
Time per cube (in seconds, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
|H48 h11 k2|56.1GiB | 0.06 | 0.31 | 1.31 | 7.96 | 77.81 |
|vcube 404 |31.8GiB | 0.10 | 0.38 | 1.88 | 16.98 | (a) |
|H48 h10 k2|28.1GiB | 0.10 | 0.47 | 2.00 | 13.54 | 114.35 |
|vcube 308 |21.2GiB | 0.06 | 0.42 | 1.95 | 17.73 | (a) |
|H48 h9 k2 |14.1GiB | 0.14 | 0.83 | 3.82 | 25.98 | 162.72 |
|vcube 208 | 7.3GiB | 0.17 | 1.49 | 5.88 | | (a) |
|H48 h8 k2 | 7.1GiB | 0.27 | 2.02 | 7.94 | | |
|H48 h7 k2 | 3.6GiB | 0.35 | 2.59 | 12.41 | | |
|vcube 112 | 2.4GiB | 0.29 | 3.15 | 12.06 | | (a) |
|H48 h6 k2 | 1.8GiB | 0.65 | 4.79 | 23.91 | | |
Time per cube adjusted for tables size (in seconds \* GiB, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
|H48 h11 k2|56.1GiB | 3.37 | 17.39 | 73.49 | 446.56 | 4365.92 |
|vcube 404 |31.8GiB | 3.80 | 12.08 | 59.78 | 539.96 | (a) |
|H48 h10 k2|28.1GiB | 2.81 | 13.21 | 56.20 | 380.47 | 3213.24 |
|vcube 308 |21.2GiB | 1.27 | 8.90 | 41.34 | 375.88 | (a) |
|H48 h9 k2 |14.1GiB | 1.97 | 11.70 | 53.86 | 366.32 | 2294.35 |
|vcube 208 | 7.3GiB | 1.24 | 10.88 | 42.92 | | (a) |
|H48 h8 k2 | 7.1GiB | 1.92 | 14.34 | 56.37 | | |
|H48 h7 k2 | 3.6GiB | 1.26 | 9.32 | 44.68 | | |
|vcube 112 | 2.4GiB | 0.70 | 7.56 | 28.94 | | (a) |
|H48 h6 k2 | 1.8GiB | 1.17 | 8.62 | 43.04 | | |
(a) vcube cannot parallelize on a single scramble, the results for the
Superflip are going to be the same as in the single thread case.
### Multithread (16 threads)
Time per cube (in seconds, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
|H48 h11 k2|56.1GiB | 0.02 | 0.10 | 0.43 | 2.48 | 26.29 |
|vcube 404 |31.8GiB | 0.03 | 0.16 | 0.67 | 6.36 | (a) |
|H48 h10 k2|28.1GiB | 0.03 | 0.16 | 0.74 | 4.43 | |
|vcube 308 |21.2GiB | 0.04 | 0.22 | 0.89 | 9.53 | (a) |
|H48 h9 k2 |14.1GiB | 0.04 | 0.26 | 1.18 | 8.31 | |
|vcube 208 | 7.3GiB | 0.08 | 0.80 | 2.38 | | (a) |
|H48 h8 k2 | 7.1GiB | 0.08 | 0.60 | 2.48 | | |
|H48 h7 k2 | 3.6GiB | 0.11 | 0.81 | 3.91 | | |
|vcube 112 | 2.4GiB | 0.15 | 1.66 | 5.18 | | (a) |
|H48 h6 k2 | 1.8GiB | 0.21 | 1.53 | 7.82 | | |
Time per cube adjusted for tables size (in seconds \* GiB, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip|
|:---------|:-------|-------:|-------:|-------:|-------:|--------:|
|H48 h11 k2|56.1GiB | 1.12 | 5.61 | 24.12 | 139.13 | 1474.87 |
|vcube 404 |31.8GiB | 1.08 | 5.09 | 21.31 | 202.25 | (a) |
|H48 h10 k2|28.1GiB | 0.84 | 4.50 | 20.79 | 124.48 | |
|vcube 308 |21.2GiB | 0.85 | 4.66 | 18.87 | 202.04 | (a) |
|H48 h9 k2 |14.1GiB | 0.56 | 3.67 | 16.64 | 117.17 | |
|vcube 208 | 7.3GiB | 0.58 | 5.84 | 17.37 | | (a) |
|H48 h8 k2 | 7.1GiB | 0.57 | 4.26 | 17.60 | | |
|H48 h7 k2 | 3.6GiB | 0.40 | 2.92 | 14.07 | | |
|vcube 112 | 2.4GiB | 0.36 | 3.98 | 12.43 | | (a) |
|H48 h6 k2 | 1.8GiB | 0.38 | 2.75 | 14.08 | | |
(a) vcube cannot parallelize on a single scramble, the results for the
Superflip are going to be the same as in the single thread case.
## All optimal solutions (TODO)
Average time for finding all optimal solutions.
### Single thread
Time per cube (in seconds, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|
|:---------|:-------|-------:|-------:|-------:|-------:|
|H48 h11 k2|56.1GiB | | | | |
|H48 h10 k2|28.1GiB | | | | |
|H48 h9 k2 |14.1GiB | | | | |
|H48 h8 k2 | 7.1GiB | | | | |
|H48 h7 k2 | 3.6GiB | | | | |
|H48 h6 k2 | 1.8GiB | | | | |
Time per cube adjusted for tables size (in seconds \* GiB, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|
|:---------|:-------|-------:|-------:|-------:|-------:|
|H48 h11 k2|56.1GiB | | | | |
|H48 h10 k2|28.1GiB | | | | |
|H48 h9 k2 |14.1GiB | | | | |
|H48 h8 k2 | 7.1GiB | | | | |
|H48 h7 k2 | 3.6GiB | | | | |
|H48 h6 k2 | 1.8GiB | | | | |
### Multithread (4 threads)
Time per cube (in seconds, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|
|:---------|:-------|-------:|-------:|-------:|-------:|
|H48 h11 k2|56.1GiB | | | | |
|H48 h10 k2|28.1GiB | | | | |
|H48 h9 k2 |14.1GiB | | | | |
|H48 h8 k2 | 7.1GiB | | | | |
|H48 h7 k2 | 3.6GiB | | | | |
|H48 h6 k2 | 1.8GiB | | | | |
Time per cube adjusted for tables size (in seconds \* GiB, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|
|:---------|:-------|-------:|-------:|-------:|-------:|
|H48 h11 k2|56.1GiB | | | | |
|H48 h10 k2|28.1GiB | | | | |
|H48 h9 k2 |14.1GiB | | | | |
|H48 h8 k2 | 7.1GiB | | | | |
|H48 h7 k2 | 3.6GiB | | | | |
|H48 h6 k2 | 1.8GiB | | | | |
### Multithread (16 threads)
Time per cube (in seconds, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|
|:---------|:-------|-------:|-------:|-------:|-------:|
|H48 h11 k2|56.1GiB | | | | |
|H48 h10 k2|28.1GiB | | | | |
|H48 h9 k2 |14.1GiB | | | | |
|H48 h8 k2 | 7.1GiB | | | | |
|H48 h7 k2 | 3.6GiB | | | | |
|H48 h6 k2 | 1.8GiB | | | | |
Time per cube adjusted for tables size (in seconds \* GiB, lower is better).
| Solver | Size |17 moves|18 moves|19 moves|20 moves|
|:---------|:-------|-------:|-------:|-------:|-------:|
|H48 h11 k2|56.1GiB | | | | |
|H48 h10 k2|28.1GiB | | | | |
|H48 h9 k2 |14.1GiB | | | | |
|H48 h8 k2 | 7.1GiB | | | | |
|H48 h7 k2 | 3.6GiB | | | | |
|H48 h6 k2 | 1.8GiB | | | | |
## Other notes
* Missing values in the table mean that the test is very slow and I did
not want to wait for it to finish. I may add these values in the future.
* All the measurements above exclude the time needed to load the pruning
tables into memory, which can be quite significant for large tables. To
repeat these measurements, one can use the tool `301_solve_file`. For
example:
```
./build tool solve_file h48h7k2 ./benchmarks/scrambles/scrambles-16.txt
```
To find all solutions, add something like `99999 0` at the end of the
command. This will tell the tool to find up to `99999` solutions that
are at most `0` moves longer than optimal.
* The measurements also excluded the one-off computation of the pruning
tables which, for reasons related to the cube coordinates used, is
significantly slower for H48 compared to vcube.
* H48's and vcube's approach to multithreading are extremely different:
H48 parallelize the search for each cube individually, vcube solves
multiple cubes in parallel by dedicating a single thread to each of
them. Both apporaches have pros and cons: vcube's approch has less
overhead in coordination between the threads, but often some threads
may be left without work when there are no more cubes left to solve.
* Per-cube parallelization means that H48 will always be faster than
vcube when solving a single cube.
* vcube only supports x86 processors (Intel, AMD), while H48 runs on any
architecture, including e.g. ARM (Macbook M series, android phones)
and can be compiled to WebAssembly as well.
|
