7 files changed, 401 insertions, 0 deletions
diff --git a/benchmarks/benchmarks.md b/benchmarks/benchmarks.md
new file mode 100644
index 0000000..abecc85
--- /dev/null
+++ b/benchmarks/benchmarks.md
@@ -0,0 +1,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.
diff --git a/benchmarks/scrambles/scrambles-16.txt b/benchmarks/scrambles/scrambles-16.txt
new file mode 100644
index 0000000..f5d1840
--- /dev/null
+++ b/benchmarks/scrambles/scrambles-16.txt
@@ -0,0 +1,25 @@
+U' D F2 U2 R F' R' U' D2 F' U B R D F R'
+D F' L2 F2 B D2 F U' D B2 R D F2 R2 B' U2
+L F' D L' D2 L F2 D' L2 U' L F2 D R U R
+U2 F D' B D2 R F' B D R F B U B2 R F2
+L' D2 F2 D R2 L' B L B2 U2 L' D' L' R D' L'
+R2 L2 F2 R F2 D2 R2 F' U' L D2 B R' U2 D' R2
+F' D B2 R' D2 B L' D L' U2 F' R' F D F2 U'
+R U B' L2 U L' D F' D B' L2 B2 U' L' U2 L
+R2 F2 R D R2 U L2 U L' U2 F L F D2 F U
+L2 B2 L' F2 L2 U2 F U2 F' B' D' B U D2 B2 U
+U' L2 U2 F L' D2 B R2 U' L' B2 R2 B U2 F' U
+D' F2 U2 D' L2 B D F B' L2 F R' U2 F L2 B
+R2 U' B2 D F2 D2 R2 D' L' F' B R U2 B' L' F'
+D2 R F' D' R2 L2 U L B' R2 D F R2 L2 F D2
+D2 L B' R2 F U' F D' B2 L D R' B L' F2 B2
+R2 F R U L F' R' L2 U R B L' F' D' B U'
+D R D' R U L F' B' U2 F2 L' U' F L' D' R2
+U2 B R B U D B2 L F' D L2 U2 L D' F' U'
+F' R' U B2 R' B' L2 F2 U2 L' U B2 D2 L2 D' L2
+D R2 D' R' L2 B L F L' U' L2 F L2 B R U2
+F' B L F' L U L2 F U R2 L2 U L U2 L F'
+U' R B U2 B L2 B' D' R' U F2 B R U2 R2 B2
+L U' F2 L' D2 R D' B' U' R2 L' U2 L B2 D B'
+U R2 D2 B R D2 F R2 B U R' D' F' R2 U D
+U' D' R2 F L B R' U2 F U2 D2 F2 R L2 B L'
diff --git a/benchmarks/scrambles/scrambles-17.txt b/benchmarks/scrambles/scrambles-17.txt
new file mode 100644
index 0000000..8ff1c5f
--- /dev/null
+++ b/benchmarks/scrambles/scrambles-17.txt
@@ -0,0 +1,25 @@
+F' R2 L D' L U F2 B U2 D B U' F' R' B F' U'
+B' D' R' D F' R' F2 R2 D2 B2 D' B L U R D' B2
+B2 L U L' D' R' L2 U B2 R2 L2 B' L' D R2 L' D
+U' F2 U' R' D2 B' R' D R' B D2 F2 D2 F2 L' U2 R2
+R B2 D' R U' F D' B L' F R U F D' F R2 L2
+U2 D2 R2 B' L2 U F2 L F R B2 D' R2 U2 D2 B L2
+R' U' B R' L2 D2 L U B2 L B U' R' U2 R2 U L2
+D F D' F' U2 D' F2 R2 F' U' L F' B L' B D F2
+L D2 R F2 R F2 U' F' L' B2 D' B R2 B L D R'
+B D R2 U' R2 L D' R D' L F D' L' F2 B' D' F
+U2 L' B D' F' R D2 B' U L' B' L2 U2 B D2 F2 L
+U D R' L2 B U F L2 B' L' F R D2 B U B2 U2
+R U2 R' B2 U' L U2 R' B' U L' B2 D B U' R' B'
+U B' D F2 R D L U2 R2 B' U2 B2 D F' R2 F' U'
+U F' L F2 U L U2 R' B2 L' F' L2 U B2 R' F2 B
+L2 F' U2 L' U' D2 L' B R B U2 B L' F' L' R' B'
+L2 D' L2 F B' L B2 U2 D2 L' U' B2 L2 F2 R2 D' B2
+U' D L U B' U2 L F L2 F B D' B L F2 U D2
+U R D' R' F D F2 U2 R2 B' R2 B2 D2 R U' F2 L
+U' R F' D L D' R2 L' F2 D' B R2 B' U B' U' L
+F' B L' D F' U' R B' L2 D2 F D2 R' L' U L B2
+U F' U2 R' B2 U B2 R B2 L F' D' R' B2 L' D' U
+F' L F U2 L2 B R2 F' B' R2 U2 R B' L2 U F D2
+L2 B D R L F' U2 F2 D2 R' B U2 F2 R' L B R
+L F R2 F L2 F' R U2 F' D2 R' B' U B' R F B2
diff --git a/benchmarks/scrambles/scrambles-18.txt b/benchmarks/scrambles/scrambles-18.txt
new file mode 100644
index 0000000..d5e2a29
--- /dev/null
+++ b/benchmarks/scrambles/scrambles-18.txt
@@ -0,0 +1,25 @@
+D L' D' B2 U2 L F2 D2 R' U' D2 F' L2 F B' L2 D B'
+D' F U D R2 F' R2 D2 R F' R2 B' U2 R' F2 D L U
+U' F' R2 U2 F' U2 R U' L U2 B2 L' F R2 U' L2 B2 D2
+R B2 D' L' F' U' F2 R2 D' F2 R D' R2 B' U2 F2 D B'
+U2 B2 R2 U D R' B U' F2 L2 F' D B D F2 R U L
+U B' D' R' B' D2 F B U2 D' L D' B' U R B D' F2
+R B' U2 B' R2 F2 U' R' D' R' F' L F' D' R2 D' F R2
+U2 R' L U2 D2 R2 B2 U2 F U2 L' F2 L2 U' B2 D' B2 R'
+D2 B' L D2 L' U' F L' D' F2 U2 F B D' L2 D2 B2 U'
+U' L' F D' R2 L' B L' U' B2 L2 U2 L D F' D U' B'
+U' B R2 B2 U2 B R' F2 L' U D R L D' B2 D' B L
+U L D B' D L2 F2 B U2 B D' L U2 D2 F R2 D L2
+U' F' U R' B' R U2 D' L B U2 B' R2 D2 F' R L F2
+D2 B2 R F R2 U' D' L' U2 L' F U2 L' B' L2 F' L D'
+U L2 U B D2 R' F U R B U2 B U D F2 D L U2
+U D L' D R U' D' R U R2 F2 B R2 F U F2 D' B'
+R2 F2 U2 R' B U' R D' B' R U' R' U' D' L2 F2 L D
+F' U' D F2 R U B' D F2 D2 R B' U' L B2 L2 B2 L
+D L2 U2 D L B' U R2 L' B D' R' L D' R2 U' B R'
+U' F U R2 U2 B D2 F D L' F' D' R' L2 U B' L F
+L F2 D' B2 L2 F2 B U L' B R U2 F2 U D2 F' R' D
+U R2 L2 F' U' R2 U D' R2 F2 D2 F' U' D' L2 D' L' U'
+U' R2 B2 R' F B' L F2 U B2 L' U' B2 R F2 U2 B L2
+R2 F' D R' L F L F2 R2 U2 L2 F' U F2 R' L' F B2
+F R D B2 D B2 L' F L U' B' D L' F U' R D' U'
diff --git a/benchmarks/scrambles/scrambles-19.txt b/benchmarks/scrambles/scrambles-19.txt
new file mode 100644
index 0000000..1ed778a
--- /dev/null
+++ b/benchmarks/scrambles/scrambles-19.txt
@@ -0,0 +1,25 @@
+D2 R2 U2 D B2 L2 U2 R F' B' U L2 D L2 F D' R2 U R
+D L2 U D F' U2 R' U2 D' R2 L F' U B2 L D' L' B2 D2
+U' L2 D' B' L D F R' D2 L2 B2 D' L2 D' L2 F2 L U' F'
+U L U2 F2 R' B R' L B' D' L D' B R' D L' U L F
+U F U D L' D' R2 L2 F D2 R2 B2 R B' D F' D' L U'
+D R' U' L2 F R2 U F2 L D2 B U R' B' U2 F L' B D
+U' B' U D' L D' B' R U2 D' F' D2 R L' D L' F2 B D
+D F2 U D F R2 F L2 D2 B' U D' L D2 B' R' L2 B' D'
+U B U' F2 L U' R' U' B2 R2 F2 B' U' R2 D' R' D' R2 D2
+D2 L' U2 F' D2 B U' R2 F U2 B L F L2 D2 B' L' R' D'
+D R2 D R B' R F2 U F2 B2 R U' F' B' U2 L' D R D'
+U B' D' F' U L F2 R2 B D L2 D F' B2 R2 F' R U' L'
+U B U D2 L U L B2 D' R D' F' L' F B2 U' F' B2 R'
+U2 F2 U B L D' B2 L F U' F2 U2 R' B D2 B L' B F
+U L' U2 F U B D2 B' R D2 B' D L D B2 L2 F' D' L
+U R D2 R2 F2 L' U' F L' D' F2 R2 D F' R L F2 R2 B'
+U2 B2 U2 R2 D2 L2 D B R2 D' L F2 L2 F' D2 R' L2 D R2
+U' D' F B' U R F B2 R B D R2 D2 L2 D' R' U' B' F
+D L U D' F' U L2 F U D F R D2 R' D R' B U' B2
+D2 R2 U D' R F2 U D' F L' B R' L D L2 B' L' U2 D'
+U F' D R U2 L' F' L2 B U F2 D B' D2 B' U' F' U B'
+U B2 U' R' F R' D' R L' U D' B U2 R2 D' B2 L D2 L
+U2 R U2 D' L2 B2 D2 R2 F R D F' R2 D B2 R2 F' D L'
+U B' U R B' U' L' F' D R2 U' F D R' U' B2 R L2 B'
+U' B2 U R2 L2 D2 R' U' R U' F U D2 L' B U' F' U2 L2
diff --git a/benchmarks/scrambles/scrambles-20.txt b/benchmarks/scrambles/scrambles-20.txt
new file mode 100644
index 0000000..c4228bc
--- /dev/null
+++ b/benchmarks/scrambles/scrambles-20.txt
@@ -0,0 +1,25 @@
+R2 U2 R F L' B D' R' U2 B2 U2 F D U2 R2 U2 F2 L F2 B2
+F R B' R2 L2 B' R' D2 R' D B L F' L2 F2 U D2 B2 R2 U'
+L2 F' B' R L2 D R2 L' D F' L' U' L' B D2 F R2 F2 L2 D2
+F U2 B2 R' B' U2 F' R' U' L' U2 F B2 U R2 L2 F2 U' B2 D2
+F R D F' L2 U2 D2 R' U2 B' L' U F' R2 L2 U2 F' B D2 B'
+U F L' U' F' B' R D F' L' U F2 R2 L U2 R' L2 B2 R' L'
+F U' L' D' F B' R2 D2 R U2 B' R D2 R' U2 L' B2 L B2 L'
+D2 U2 R2 B2 D2 F L2 B2 F2 L U' B R F2 U' L F' L U2 L
+F R D F' L' U B' R' D R2 U' F R2 F2 R2 L2 B' L2 F D2
+U' L D' F R U' F' U R' B U R F' B2 U2 F2 R2 L' D2 R
+D L2 B2 D F' L' D' R B' U F' U2 R F' U2 D2 F2 U' R2 B2
+L2 D L2 F2 U L2 B2 F2 U' R F U' L' D F' L2 R2 D2 F' L'
+F2 B' R F2 B2 U D2 B' L2 D' L2 F' B2 U2 D2 L D2 R L2 D2
+U2 F2 L B2 U2 L' R' B R D' U' F' R' F' L' B2 R' F L2 D
+F R' B R F' D F' R' D' L F2 U' D' B' U2 F' B2 L2 F2 D2
+R' F2 B' U' D2 B' D' F R' B' D' F2 D2 R L F2 D2 F2 D2 L'
+R' U' D' B' D2 L' F U F' D2 L2 F D' B2 L D2 F2 R2 B2 R
+L' D' F R2 D2 B U' F' U' F R L' F' D' F2 L2 D2 B2 R2 F2
+L2 D B L2 B2 R' F D' L U B R' F D2 F' D2 B' R2 F U2
+F B2 R' D' L U B' R2 D L' B L2 U R L D2 R B2 R2 D2
+R L2 F' U' L B U R D' B2 L U' F' D2 B' D2 L2 F' B R2
+R' B2 F2 L' D2 F2 R B2 D2 R F' U' L' D B' R' B2 F U' L'
+B' R2 L D' B' L2 U' R D B' R F' U2 L U2 R' U2 R2 D2 F2
+B R2 F2 U' D2 B' R' U' D' L U F' B2 U2 D2 L2 D2 L U2 L
+L2 F R2 F L2 F' U2 L U' B2 D B' L R' D' R2 D2 B R2 F
diff --git a/benchmarks/scrambles/superflip.txt b/benchmarks/scrambles/superflip.txt
new file mode 100644
index 0000000..0adb82c
--- /dev/null
+++ b/benchmarks/scrambles/superflip.txt
@@ -0,0 +1 @@
+U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2

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


diff --git a/benchmarks/scrambles/scrambles-16.txt b/benchmarks/scrambles/scrambles-16.txt new file mode 100644 index 0000000..f5d1840 --- /dev/null +++ b/benchmarks/scrambles/scrambles-16.txt
@@ -0,0 +1,25 @@
	1	U' D F2 U2 R F' R' U' D2 F' U B R D F R'
	2	D F' L2 F2 B D2 F U' D B2 R D F2 R2 B' U2
	3	L F' D L' D2 L F2 D' L2 U' L F2 D R U R
	4	U2 F D' B D2 R F' B D R F B U B2 R F2
	5	L' D2 F2 D R2 L' B L B2 U2 L' D' L' R D' L'
	6	R2 L2 F2 R F2 D2 R2 F' U' L D2 B R' U2 D' R2
	7	F' D B2 R' D2 B L' D L' U2 F' R' F D F2 U'
	8	R U B' L2 U L' D F' D B' L2 B2 U' L' U2 L
	9	R2 F2 R D R2 U L2 U L' U2 F L F D2 F U
	10	L2 B2 L' F2 L2 U2 F U2 F' B' D' B U D2 B2 U
	11	U' L2 U2 F L' D2 B R2 U' L' B2 R2 B U2 F' U
	12	D' F2 U2 D' L2 B D F B' L2 F R' U2 F L2 B
	13	R2 U' B2 D F2 D2 R2 D' L' F' B R U2 B' L' F'
	14	D2 R F' D' R2 L2 U L B' R2 D F R2 L2 F D2
	15	D2 L B' R2 F U' F D' B2 L D R' B L' F2 B2
	16	R2 F R U L F' R' L2 U R B L' F' D' B U'
	17	D R D' R U L F' B' U2 F2 L' U' F L' D' R2
	18	U2 B R B U D B2 L F' D L2 U2 L D' F' U'
	19	F' R' U B2 R' B' L2 F2 U2 L' U B2 D2 L2 D' L2
	20	D R2 D' R' L2 B L F L' U' L2 F L2 B R U2
	21	F' B L F' L U L2 F U R2 L2 U L U2 L F'
	22	U' R B U2 B L2 B' D' R' U F2 B R U2 R2 B2
	23	L U' F2 L' D2 R D' B' U' R2 L' U2 L B2 D B'
	24	U R2 D2 B R D2 F R2 B U R' D' F' R2 U D
	25	U' D' R2 F L B R' U2 F U2 D2 F2 R L2 B L'


diff --git a/benchmarks/scrambles/scrambles-17.txt b/benchmarks/scrambles/scrambles-17.txt new file mode 100644 index 0000000..8ff1c5f --- /dev/null +++ b/benchmarks/scrambles/scrambles-17.txt
@@ -0,0 +1,25 @@
	1	F' R2 L D' L U F2 B U2 D B U' F' R' B F' U'
	2	B' D' R' D F' R' F2 R2 D2 B2 D' B L U R D' B2
	3	B2 L U L' D' R' L2 U B2 R2 L2 B' L' D R2 L' D
	4	U' F2 U' R' D2 B' R' D R' B D2 F2 D2 F2 L' U2 R2
	5	R B2 D' R U' F D' B L' F R U F D' F R2 L2
	6	U2 D2 R2 B' L2 U F2 L F R B2 D' R2 U2 D2 B L2
	7	R' U' B R' L2 D2 L U B2 L B U' R' U2 R2 U L2
	8	D F D' F' U2 D' F2 R2 F' U' L F' B L' B D F2
	9	L D2 R F2 R F2 U' F' L' B2 D' B R2 B L D R'
	10	B D R2 U' R2 L D' R D' L F D' L' F2 B' D' F
	11	U2 L' B D' F' R D2 B' U L' B' L2 U2 B D2 F2 L
	12	U D R' L2 B U F L2 B' L' F R D2 B U B2 U2
	13	R U2 R' B2 U' L U2 R' B' U L' B2 D B U' R' B'
	14	U B' D F2 R D L U2 R2 B' U2 B2 D F' R2 F' U'
	15	U F' L F2 U L U2 R' B2 L' F' L2 U B2 R' F2 B
	16	L2 F' U2 L' U' D2 L' B R B U2 B L' F' L' R' B'
	17	L2 D' L2 F B' L B2 U2 D2 L' U' B2 L2 F2 R2 D' B2
	18	U' D L U B' U2 L F L2 F B D' B L F2 U D2
	19	U R D' R' F D F2 U2 R2 B' R2 B2 D2 R U' F2 L
	20	U' R F' D L D' R2 L' F2 D' B R2 B' U B' U' L
	21	F' B L' D F' U' R B' L2 D2 F D2 R' L' U L B2
	22	U F' U2 R' B2 U B2 R B2 L F' D' R' B2 L' D' U
	23	F' L F U2 L2 B R2 F' B' R2 U2 R B' L2 U F D2
	24	L2 B D R L F' U2 F2 D2 R' B U2 F2 R' L B R
	25	L F R2 F L2 F' R U2 F' D2 R' B' U B' R F B2


diff --git a/benchmarks/scrambles/scrambles-18.txt b/benchmarks/scrambles/scrambles-18.txt new file mode 100644 index 0000000..d5e2a29 --- /dev/null +++ b/benchmarks/scrambles/scrambles-18.txt
@@ -0,0 +1,25 @@
	1	D L' D' B2 U2 L F2 D2 R' U' D2 F' L2 F B' L2 D B'
	2	D' F U D R2 F' R2 D2 R F' R2 B' U2 R' F2 D L U
	3	U' F' R2 U2 F' U2 R U' L U2 B2 L' F R2 U' L2 B2 D2
	4	R B2 D' L' F' U' F2 R2 D' F2 R D' R2 B' U2 F2 D B'
	5	U2 B2 R2 U D R' B U' F2 L2 F' D B D F2 R U L
	6	U B' D' R' B' D2 F B U2 D' L D' B' U R B D' F2
	7	R B' U2 B' R2 F2 U' R' D' R' F' L F' D' R2 D' F R2
	8	U2 R' L U2 D2 R2 B2 U2 F U2 L' F2 L2 U' B2 D' B2 R'
	9	D2 B' L D2 L' U' F L' D' F2 U2 F B D' L2 D2 B2 U'
	10	U' L' F D' R2 L' B L' U' B2 L2 U2 L D F' D U' B'
	11	U' B R2 B2 U2 B R' F2 L' U D R L D' B2 D' B L
	12	U L D B' D L2 F2 B U2 B D' L U2 D2 F R2 D L2
	13	U' F' U R' B' R U2 D' L B U2 B' R2 D2 F' R L F2
	14	D2 B2 R F R2 U' D' L' U2 L' F U2 L' B' L2 F' L D'
	15	U L2 U B D2 R' F U R B U2 B U D F2 D L U2
	16	U D L' D R U' D' R U R2 F2 B R2 F U F2 D' B'
	17	R2 F2 U2 R' B U' R D' B' R U' R' U' D' L2 F2 L D
	18	F' U' D F2 R U B' D F2 D2 R B' U' L B2 L2 B2 L
	19	D L2 U2 D L B' U R2 L' B D' R' L D' R2 U' B R'
	20	U' F U R2 U2 B D2 F D L' F' D' R' L2 U B' L F
	21	L F2 D' B2 L2 F2 B U L' B R U2 F2 U D2 F' R' D
	22	U R2 L2 F' U' R2 U D' R2 F2 D2 F' U' D' L2 D' L' U'
	23	U' R2 B2 R' F B' L F2 U B2 L' U' B2 R F2 U2 B L2
	24	R2 F' D R' L F L F2 R2 U2 L2 F' U F2 R' L' F B2
	25	F R D B2 D B2 L' F L U' B' D L' F U' R D' U'


diff --git a/benchmarks/scrambles/scrambles-19.txt b/benchmarks/scrambles/scrambles-19.txt new file mode 100644 index 0000000..1ed778a --- /dev/null +++ b/benchmarks/scrambles/scrambles-19.txt
@@ -0,0 +1,25 @@
	1	D2 R2 U2 D B2 L2 U2 R F' B' U L2 D L2 F D' R2 U R
	2	D L2 U D F' U2 R' U2 D' R2 L F' U B2 L D' L' B2 D2
	3	U' L2 D' B' L D F R' D2 L2 B2 D' L2 D' L2 F2 L U' F'
	4	U L U2 F2 R' B R' L B' D' L D' B R' D L' U L F
	5	U F U D L' D' R2 L2 F D2 R2 B2 R B' D F' D' L U'
	6	D R' U' L2 F R2 U F2 L D2 B U R' B' U2 F L' B D
	7	U' B' U D' L D' B' R U2 D' F' D2 R L' D L' F2 B D
	8	D F2 U D F R2 F L2 D2 B' U D' L D2 B' R' L2 B' D'
	9	U B U' F2 L U' R' U' B2 R2 F2 B' U' R2 D' R' D' R2 D2
	10	D2 L' U2 F' D2 B U' R2 F U2 B L F L2 D2 B' L' R' D'
	11	D R2 D R B' R F2 U F2 B2 R U' F' B' U2 L' D R D'
	12	U B' D' F' U L F2 R2 B D L2 D F' B2 R2 F' R U' L'
	13	U B U D2 L U L B2 D' R D' F' L' F B2 U' F' B2 R'
	14	U2 F2 U B L D' B2 L F U' F2 U2 R' B D2 B L' B F
	15	U L' U2 F U B D2 B' R D2 B' D L D B2 L2 F' D' L
	16	U R D2 R2 F2 L' U' F L' D' F2 R2 D F' R L F2 R2 B'
	17	U2 B2 U2 R2 D2 L2 D B R2 D' L F2 L2 F' D2 R' L2 D R2
	18	U' D' F B' U R F B2 R B D R2 D2 L2 D' R' U' B' F
	19	D L U D' F' U L2 F U D F R D2 R' D R' B U' B2
	20	D2 R2 U D' R F2 U D' F L' B R' L D L2 B' L' U2 D'
	21	U F' D R U2 L' F' L2 B U F2 D B' D2 B' U' F' U B'
	22	U B2 U' R' F R' D' R L' U D' B U2 R2 D' B2 L D2 L
	23	U2 R U2 D' L2 B2 D2 R2 F R D F' R2 D B2 R2 F' D L'
	24	U B' U R B' U' L' F' D R2 U' F D R' U' B2 R L2 B'
	25	U' B2 U R2 L2 D2 R' U' R U' F U D2 L' B U' F' U2 L2


diff --git a/benchmarks/scrambles/scrambles-20.txt b/benchmarks/scrambles/scrambles-20.txt new file mode 100644 index 0000000..c4228bc --- /dev/null +++ b/benchmarks/scrambles/scrambles-20.txt
@@ -0,0 +1,25 @@
	1	R2 U2 R F L' B D' R' U2 B2 U2 F D U2 R2 U2 F2 L F2 B2
	2	F R B' R2 L2 B' R' D2 R' D B L F' L2 F2 U D2 B2 R2 U'
	3	L2 F' B' R L2 D R2 L' D F' L' U' L' B D2 F R2 F2 L2 D2
	4	F U2 B2 R' B' U2 F' R' U' L' U2 F B2 U R2 L2 F2 U' B2 D2
	5	F R D F' L2 U2 D2 R' U2 B' L' U F' R2 L2 U2 F' B D2 B'
	6	U F L' U' F' B' R D F' L' U F2 R2 L U2 R' L2 B2 R' L'
	7	F U' L' D' F B' R2 D2 R U2 B' R D2 R' U2 L' B2 L B2 L'
	8	D2 U2 R2 B2 D2 F L2 B2 F2 L U' B R F2 U' L F' L U2 L
	9	F R D F' L' U B' R' D R2 U' F R2 F2 R2 L2 B' L2 F D2
	10	U' L D' F R U' F' U R' B U R F' B2 U2 F2 R2 L' D2 R
	11	D L2 B2 D F' L' D' R B' U F' U2 R F' U2 D2 F2 U' R2 B2
	12	L2 D L2 F2 U L2 B2 F2 U' R F U' L' D F' L2 R2 D2 F' L'
	13	F2 B' R F2 B2 U D2 B' L2 D' L2 F' B2 U2 D2 L D2 R L2 D2
	14	U2 F2 L B2 U2 L' R' B R D' U' F' R' F' L' B2 R' F L2 D
	15	F R' B R F' D F' R' D' L F2 U' D' B' U2 F' B2 L2 F2 D2
	16	R' F2 B' U' D2 B' D' F R' B' D' F2 D2 R L F2 D2 F2 D2 L'
	17	R' U' D' B' D2 L' F U F' D2 L2 F D' B2 L D2 F2 R2 B2 R
	18	L' D' F R2 D2 B U' F' U' F R L' F' D' F2 L2 D2 B2 R2 F2
	19	L2 D B L2 B2 R' F D' L U B R' F D2 F' D2 B' R2 F U2
	20	F B2 R' D' L U B' R2 D L' B L2 U R L D2 R B2 R2 D2
	21	R L2 F' U' L B U R D' B2 L U' F' D2 B' D2 L2 F' B R2
	22	R' B2 F2 L' D2 F2 R B2 D2 R F' U' L' D B' R' B2 F U' L'
	23	B' R2 L D' B' L2 U' R D B' R F' U2 L U2 R' U2 R2 D2 F2
	24	B R2 F2 U' D2 B' R' U' D' L U F' B2 U2 D2 L2 D2 L U2 L
	25	L2 F R2 F L2 F' U2 L U' B2 D B' L R' D' R2 D2 B R2 F


diff --git a/benchmarks/scrambles/superflip.txt b/benchmarks/scrambles/superflip.txt new file mode 100644 index 0000000..0adb82c --- /dev/null +++ b/benchmarks/scrambles/superflip.txt
@@ -0,0 +1 @@
		U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2