commit 6c42463b800bbab4583e90aeb748a79037c65a9e
parent 4d0b1a53f04f1c5bc95de20fb92b2bd9cf16a895
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 25 Nov 2025 18:08:24 +0100
Updated h48 doc with recent improvements
Diffstat:
1 file changed, 22 insertions(+), 5 deletions(-)
diff --git 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.
