From e71e2776674a748372e95702be49af2753ff3d48 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 18 Jun 2025 09:53:07 +0200 Subject: Update H48 doc --- doc/h48.md | 52 ++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 36 insertions(+), 16 deletions(-) diff --git a/doc/h48.md b/doc/h48.md index 681d092..6b31503 100644 --- 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 -- cgit v1.3