Update H48 doc

1 files changed, 35 insertions, 15 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:
+The H48 solver uses various other optimizations.
 
-* **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.
+#### 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