commit 8d3fe446815a1631876e4170747bc6cb03a6bbf8
parent e3d0efaebd00af412602ae71062d24d7977e443a
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 1 Oct 2024 19:20:16 +0200
Updated h48 doc
Diffstat:
| M | doc/h48.md | | | 115 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------- |
1 file changed, 87 insertions(+), 28 deletions(-)
diff --git a/doc/h48.md b/doc/h48.md
@@ -132,7 +132,7 @@ The H48 solver uses a target group that is invariant under all 48
symmetries. This group is defined as follows:
* Each corner is placed in the *corner tetrad* it belongs to, and it
- is oriented. Here by corner tetrad we means one of the two sets of
+ is oriented. Here by corner tetrad we mean one of the two sets of
corners {UFR, UBL, DFL, DBR} and {UFL, UBR, DFR, DBL}. For a corner
that is placed in its own tetrad, the orientation does not depend on
the reference axis chosen, and an oriented corner can be defined
@@ -171,17 +171,17 @@ is a little too much for most personal computers.
One can wonder if it is possible to use a coordinate that considers
the orientation of only *some* of the edges, which we may call **h1**
-to **h10**. Such coordinates do exist, but it is not invariant under the
-full symmetry group: indeed an edge whose orientation we keep track of
-could be moved to any of the untracked edges' positions by one of the
-symmetries, making the whole coordinate ill-defined.
+to **h10**. Such coordinates do exist, but they are not invariant under
+the full symmetry group: indeed an edge whose orientation we keep track
+of could be moved to any of the untracked edges' positions by one of
+the symmetries, making the whole coordinate ill-defined.
It is however possible to compute the symmetry-reduced pruning tables
for these coordinates. One way to construct them is by taking the **h11**
pruning table and "forgetting" about some of the edge orientation values,
collapsing 2 (or a power thereof) values to one by taking the minimum.
It is also possible to compute these tables directly, as explained in
-the **Pruning table computation** section below (work in progress).
+the **Pruning table computation** section below.
### Coordinate computation for pruning value estimation
@@ -220,9 +220,6 @@ Once we have computed the full h0 coordinate, we can access the correct
entry in the full pruning table. As mentioned above, the pruning table
can be one of three kinds:
-(Work in progress - the only kind of table currently implemented is
-the 4 bits per entry table)
-
* 4 bits per entry, or `k4`: In this case the pruning value (between 0
and 15) can be simply read off the table.
* 2 bits per entry, or `k2`: Tables of this kind work as described by
@@ -236,7 +233,6 @@ the 4 bits per entry table)
cannot take b as a lower bount. Instead we have to use a pruning value from
another table, for example the corner-only table mentioned in the previous
section, or a completely new one.
- (Work in progress - `k2` tables not available in the code yet)
* 1 bit per entry, or `k1`: With one bit per entry, the only information we
can get from the pruning table is wether or not the current position
requires more or fewer moves than a fixed base value b. This can still be
@@ -249,8 +245,6 @@ the 4 bits per entry table)
After computing the pruning value, there are a number of different tricks
that can be used to improve the estimation.
-(Work in progress - the following techniques are not implemented yet)
-
#### Inverse estimate
A cube position and its inverse will, in general, give a different
@@ -299,8 +293,6 @@ Other possible (low-level) optimizations include:
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.
- (Work in progress - premoves are not implemented yet, but it will take
- little work to add them)
* **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
@@ -314,17 +306,84 @@ Other possible (low-level) optimizations include:
## Pruning table computation
-### The h0 table
-
-TODO - short explanation of how this is computed
-
-### The intermediate tables (h1, ... h10)
-
-TODO - explain why these are more complicated (if one does not
-want to compute the full **h11** table first)
-
-Work in progress - these tables are not implemented yet.
-
-### The h11 table
-
-Work in progress - this tables is not implemented yet.
+### 4 bits tables for h0 and h11
+
+Computing the pruning table for a "real" h48 coordinate, that **h0**
+or **h11**, using 4 bits per entry is quite simple. The method currently
+implemented works as follows.
+
+First, we set the value of the solved cube's coordinate to 0 and every
+other entry to 15, the largest 4-bit integer. Then we iteratively scan
+through the table and compute the coordinates at depth n+1 from those at
+depth n as follows: for each coordinate at depth n, we compute a valid
+representative for it, we apply each of the possible 18 moves to it, and
+we set their value to n+1. Once the table is filled or we have reached
+depth 15, we stop (there are no **h0** coordinates at depth 16 or more,
+but I currently don't know if this is the case for **h11**).
+
+Unfortunately what I described above is an oversimplification: one
+also must take into account the case where the corner coordinate is
+self-symmetric, and handle it accordingly by making sure that every
+symmetric variation of the same coordinate has its value set at the
+right iteration.
+
+When this algorithm reaches the last few iterations, the coordinates at
+depth n are many more than those whose depth is still unknown. Therefore
+it is convenient to look at the unset coordinate and check if they have
+any neighbor whose depth is i; if so, we can set such a coordinate to i+1.
+Thanks to [torchlight](https://github.com/torchlight) for suggesting
+this optimization.
+
+Finally, this algorithm can be easily parallelized by dividing the set
+of coordinates into separate sections, but one must take into account
+that a coordinate and its neighbors are usually not in the same section.
+
+This method is currently implemented only for **h0**, since the 4 bits
+table for **h11** would require around 115GB of RAM to compute, and I
+don't have this much memory.
+
+### 2 bits tables with for h0 and h11
+
+(Work in progress - currently I there is no specialized routine for
+computing 2 bits table for "real" coordinates; instead, an optimized
+version of the generic method explained below is used)
+
+### A generic method for intermediate coordinates (from h1 to h10)
+
+(Work in progress - this method is quite slow and it may be replaced
+by a better algorithm in the future)
+
+Computing the pruning tables for intermediate coordinates is not as
+simple. The reason is that these coordinates are not invariant under
+the 48 transformations of the cube, but we are treating them as such.
+Take for example the case of **h10**. Each **h10** coordinate is
+represented by either of two **h11** coordinates: the one where the 11th
+edge is correctly oriented and the one where this edge is flipped (of
+course, the orientation of the 12th edge can be deduced from the parity
+of the orientation of the other 11). We can take any cube whose **h11**
+coordinate is one of these two to represent our **h10** coordinate, but
+the set of neighbors will change depending on which representative we
+picked. In other words: if I take one of the two cubes and make a move,
+the position reached is not necessarily obtainable by applying a move
+to the other cube. This means that the same algorithm that we described
+for the "real coordinate" case cannot be applied here.
+
+It is still possible to do a brute-force depth-first seach to fill
+these tables. To make it reasonably fast, we apply a couple of
+optimizations. First of all, we restrict ourselves to computing a 2 bits
+table, so we can stop the search early.
+
+The second optimization we employ consists in pre-computing all possible
+**h11** coordinates at a fixed depth, and storing their depth in a hash
+map indexed by their **h11** coordinate value. This way we do not have
+to brute-force our way through from depth 0, and it make this method
+considerably faster. Unfortunately, since the number of coordinates
+at a certain depth increases exponentially with the depth, we are for
+now limited at storing the coordinates at depth 8. (Work in progress -
+we may experiment with depth 9 in the future)
+
+This method works for the "real" coordinates **h0** and **h11** as well.
+Moreover, in this case one can optimize it further by avoiding to repeat
+the search from a coordinate that has already been visited. (Work
+in progress - this method will be replaced in the future by a more
+efficient one)
