commit e71e2776674a748372e95702be49af2753ff3d48
parent 5a8ca71aa8255fb76335bf41c8168cfe45eb9574
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 18 Jun 2025 09:53:07 +0200
Update H48 doc
Diffstat:
| M | doc/h48.md | | | 52 | ++++++++++++++++++++++++++++++++++++---------------- |
1 file changed, 36 insertions(+), 16 deletions(-)
diff --git a/doc/h48.md b/doc/h48.md
@@ -309,22 +309,42 @@ we can reuse it and avoid an expensive table lookup.
### Other optimizations
-Other possible (low-level) optimizations include:
-
-* **Avoid inverse computation**: computing the inverse of a cube position
- is expensive. We can avoid doing that (for the inverse pruning value
- estimate) if we bring along both the normal and the inverse cube during
- the search, and we use *premoves* to apply moves to the inverse scramble.
-* **Multi-threading (multiple scrambles)**: It is easy to parallelize this
- algorithm when solving multiple cubes at once, by firing up multiple
- instances of the solver. It is important to make sure that the same
- (read-only) pruning table is used for all instances, to avoid expensive
- memory duplication.
-* **Multi-threading (single scramble)**: It is also possible to parallelize
- the search for a single scramble. For example, we can generate 18 different
- cubes, one for each possible starting move, and solve each of them in a
- separate thread. Some coordination between threads is necessary to stop
- the search when the desired number of solutions has been found.
+The H48 solver uses various other optimizations.
+
+#### Avoiding inverse cube computation
+
+Computing the inverse of a cube position is expensive. We avoid doing
+that (for the inverse pruning value estimate) if we bring along both
+the normal and the inverse cube during the search, and we use *premoves*
+to apply moves to the inverse scramble.
+
+#### Multi-threading
+
+The solution search is parallelized *per-scramble*. Although when solving
+multiple positions it would be more efficient to solve them in parallel
+by dedicating a single thread to each of them, the current H48 solver
+optimizes for solving a single cube at the time.
+
+To do this, we first compute all cube positions that are 4 moves away
+from the scramble. This way we prepare up to 43254 *tasks* (depending
+on the symmetries of the starting position, which we take advantage of)
+which are equally split between the available threads. Any solution
+encountered in this step is of course added to the list of solutions.
+
+#### Heuristically sorting tasks
+
+The tasks described in the previous paragraph (multi-threading) are
+initially searched in an arbitrary order. However, after searching at a
+sufficient depth, we have gathered some data that allows us to make some
+heuristical improvements: the tasks that leads to visiting more positions
+(or in other words, where we go over the estimated lower bounds less
+often), are more likely to yield the optimal solution. Thus we sort the
+tasks based on this.
+
+Preliminary benchmark show a performance improvement of around 40%
+when searching a single solution. When searching for multiple optimal
+solutions the effects of this optimization will be less pronounced, and
+they are obviously inexistent when looking for *all* optimal solutions.
## Pruning table computation
