Updated h48 doc with recent improvements

1 files changed, 22 insertions, 5 deletions

diff --git a/doc/h48.md b/doc/h48.md
index 3781863..c601b75 100644
--- a/doc/h48.md
+++ b/doc/h48.md
@@ -331,6 +331,23 @@ 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.
 
+#### Filtering out symmetric cases
+
+If the cube position we wish to solve is, say, mirrored along the RL
+plane, it is redundant to attempt starting a solution with both R and L',
+as they would lead to mirrored versions of the same solution. Therefore,
+we filter out some tasks by looking for symmetries before each of the
+first 4 moves. Then, unless we are looking for only one solution, we
+have to make sure to report back all symmetric variations of a solution,
+so we need to keep track of which transformations were available at each
+of these 4 points.
+
+This can reduce the number of starting positions drastically: for
+example, for the superflip our method produces 1038 starting tasks -
+a 41.67x improvement! Of course this optimization has no effect on any
+position that isn't 3 moves or fewer away from a symmetric position -
+which is the vast majority of them.
+
 #### Heuristically sorting tasks
 
 The tasks described in the previous paragraph (multi-threading) are
@@ -344,7 +361,7 @@ fact that sequences ending in U, R or F moves have more continuations
 than those ending in D, L or B moves - as we don't allow, for example,
 both U D and D U, but only the former.
 
-Preliminary benchmark show a performance improvement of around 40%
+Preliminary benchmarks 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.
@@ -435,13 +452,13 @@ efficient one)
 
 ## Possible future improvements
 
-*This section should be considered more of a draft with personal
-notes, unlike the rest of the document.*
+*This section should be considered more of a collection of personal
+notes rather than a description of the solver.*
 
 There are some areas where this implementation of the H48 optimal solver
 can be improved:
 
-* Interwtining fallback tables to the main table. This is a trick that
+* Intertwining fallback tables to the main table. This is a trick that
   nxopt uses to reduce the number of cache misses, but we have not
   implemented in H48 yet.
 * Faster pruning table generation for **h11** and **h0**. Since these
@@ -451,4 +468,4 @@ can be improved:
   [BPMX](https://webdocs.cs.ualberta.ca/~nathanst/papers/AStar_Inconsistent.pdf)
   to improve pruning estimation. This optimization sped up
   [vcube](https://github.com/Voltara/vcube/commit/a5b08f51793f81ac34c1d402f2627f6a0495c636).
-  by about 5%-10%. Suggested by Arhan Chaudhary pointed out.
+  by about 5%-10%. Suggested by Arhan Chaudhary.