commit 9c5bdcb09dc56104f7ea34c71a9418c7908ed227
parent b940b93f6f17d1ac65ca51ba9ec82a1cce0f5017
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 23 Aug 2024 10:41:34 +0200
Added h48 solver description - work in progress
Diffstat:
| A | doc/h48.md | | | 330 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 330 insertions(+), 0 deletions(-)
diff --git a/doc/h48.md b/doc/h48.md
@@ -0,0 +1,330 @@
+# The H48 optimal solver
+
+This document contains information on the H48 Rubik's Cube optimal solver.
+The implementation of the solver is still in progress. This document
+partly describes ideas that have not been implemented yet, and it will
+be updated to reflect the actual implementation.
+
+I highly encourage the reader to check out Jaap Scherphuis'
+[Computer Puzzling page](https://www.jaapsch.net/puzzles/compcube.htm)
+before reading this document.
+
+Other backround material that will be referenced throughout the text includes:
+
+* [Cube coordinates](https://sebastiano.tronto.net/speedcubing/coordinates)
+ by Sebastiano Tronto
+* [Nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md)
+ by Tomas Rokicki
+* [The Mathematics behind Cube Explorer](https://kociemba.org/cube.htm)
+ by Herber Kociemba
+
+Initially I intended to give minimum information here, citing the
+above resources when needed, but I ended up rewriting even some of the
+basic things in this document.
+
+## Optimal solvers
+
+### IDA*
+
+The basic idea behind the solver is an iterative-deepening
+depth-first search with pruning tables, also known as IDA*. You
+can find a detailed explanation of this idea in
+[Jaap's page](https://www.jaapsch.net/puzzles/compcube.htm#tree).
+
+To summarize, the IDA* algorithm finds the shortest solution(s) for a
+scrambled puzzle by using multiple depth-first searches at increasing
+depth. A breadth-first search is not applicable in this scenario because
+of the large amount of memory required. At each depth, the puzzle's state
+is evaluated to obtain an estimated lower bound for how many moves are
+required to solve the puzzle; this is done by employing large pruning
+tables, as well as other techniques. If the lower bound exceeds the
+number of moves required to reach the current target depth, the branch is
+pruned. Otherwise, every possible move is tried, except those that would
+"cancel" with the preceding moves, obtaining new positions at depth N+1.
+
+### Pruning tables and coordinates
+
+A pruning table associates to a cube position a value that is a
+lower bound for the number of moves it takes to solve that position.
+To acces this value, the cube must be turned into an index for the
+given table. This is done using a
+[*coordinate*](https://sebastiano.tronto.net/speedcubing/coordinates),
+by which we mean a function from the set of (admissible, solvable) cube
+positions to the set of non-negative integers. The maximum value N of a
+coordinate must be less than the size of the pruning table; preferably
+there are no "gaps", that is the coordinate reaches all values between
+0 and N and the pruning table has size N+1.
+
+Coordinates are often derived from the cosets of a *target subgroup*.
+As an example, consider the pruning table that has one entry for each
+possible corner position, and the stored values denote the length of
+an optimal corner solution for that position. In this situation, the
+target subgroup is the set of all cube positions with solved corners
+(for the Mathematician: this is indeed a subgroup of the group of all
+cube positions). This group consists of `12! * 2^10` positions. The set
+of cosets of this subgroup can be identified with the set of corner
+configurations, and it has size `8! * 3^7`. By looking at corners,
+from each cube position we can compute a number from `0` to `8! * 3^7 - 1`
+and use it as an index for the pruning table.
+
+The pruning table can be filled in many ways. A common way is starting
+with the coordinate of the solved cube (often 0) and visiting the set
+of all coordinates with a breadth-first search. To do this, one needs
+to apply a cube move to a coordinate; this can either be done directly
+(for example using transistion tables, as explained in Jaap's page) or
+by converting the coordinate back into a valid cube position, applying
+the move and then computing the coordinate of the new position.
+
+The largest a pruning table is, the more information it contains,
+the faster the solvers that uses it is. It is therefore convenient to
+compress the tables as much as possible. This can be achieved by using
+4 bits per position to store the lower bound, or as little as 2 bits
+per position with some caveats (see Jaap's page or Rokicki's nxopt
+description for two possible ways to achieve this). Tables that use
+only 1 bit per position are possible, but the only information they
+can provide is wether the given position requires more or less than a
+certain number of moves to be solved.
+
+### Symmetries
+
+Another, extremely effective way of reducing the size of a pruning table
+is using symmetries. In the example above of the corner table, one can
+notice that all corner positions that are one quarter-turn away from being
+solved are essentially the same: they can be turned one into the other
+by rotating the cube and optionally applying a mirroring transformation.
+Indeed, every position belongs to a set of up to 48 positions that are
+"essentially the same" in this way. Keeping a separate entry in the
+pruning table for each of these positions is a waste of memory.
+
+There are ways to reduce a coordinate by symmetry, grouping every
+transformation-equivalent position into the same index. You can
+find a description in my
+[cube coordinates page](https://sebastiano.tronto.net/speedcubing/coordinates).
+By doing so, the size of the pruning table is reduced without loss of
+information.
+
+Some well-known solvers (Cube Explorer, nxopt) do not take advantage
+of the full group of 48 symmetries of the cube, but they use only the
+16 symmetries that fix the UD axis. However, they make up for this by
+doing 3 pruning table lookups, one for each axis of the cube.
+
+Some cube positions are self-symmetric: when applying certain
+transformations to them, they remain the same. For example, the
+cube obtained by applying U2 to a solved cube is invariant with
+respect to the mirroring along the RL-plane. This fact has a couple
+of consequences:
+
+* Reducing by a group of N symmetries does not reduce the size of
+ the pruning table by a factor of N, but by a slightly smaller
+ factor. If the size of the coordinate is large, this fact is
+ harmless.
+* When combining symmetry-reduced coordinates with other coordinates,
+ one has to be extra careful with handling self-symmetric coordinates.
+ This is a much more painful point, but a precise description of
+ the adjustments needed to handle these cases is out of the scope
+ of this document.
+
+## The H48 solver
+
+### The target subgroup: H48 coordinates
+
+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
+ 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
+ has having the U or D sticker facing U or D.
+* Each edge is placed in the *slice* it belongs to. The three edge slices
+ are M = {UF, UB, DB, DF}, S = {UR, UL, DL, DR} and E = {FR, FL, BL, BR}.
+
+Other options are available for corners: for example, we could
+impose that the corner permutation is even or that corners are in
+*half-turn reduction* state, that is they are in the group generated
+by {U2, D2, R2, L2, F2, B2}. We settled on the corner group described
+above because it is easy to calculate and it gives enough options
+for pruning table sizes, depending on how edge orientation is
+considered (see the next section).
+
+We call the coordinate obtained from the target subgroup described
+above the **h0** coordinate. This coordinate has `C(8,4) * 3^7 *
+C(12,8) * C(8,4) = 5.304.568.500` possible values. If the corner
+part of the coordinate is reduced by symmetry, it consists of only
+3393 elements, giving a total of `3393 * C(12,8) * C(8,4) =
+117.567.450` values. This is not very large for a pruning table,
+as with 2 bits per entry it would occupy less than 30MB. However,
+it is possible to take edge orientation (partially) into account
+to produce larger tables.
+
+### Edge orientation
+
+Like for corners, the orientation of an edge is well-defined independently
+of any axis when said edge is placed in the slice it belongs to. We may
+modify the target subgroup defined in the previous section by imposing
+that the edges are all oriented. This yields a new coordinate, which we
+call **h11**, whose full size with symmetry-reduced corners is `3393 *
+C(12,8) * C(8,4) * 2^11 = 240.778.137.600`. A pruning table based on
+this coordinate with 2 bits per entry would occupy around 60GB, which
+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.
+
+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).
+
+### Coordinate computation for pruning value estimation
+
+In order to access the pruning value for a given cube position, we first
+need to compute its coordinate value. Let's use for simplicity the **h0**
+coordinate, but everything will be valid for any other coordinate of
+the type described in the previous section.
+
+As described in the symmetric-composite coordinate section of
+[my coordinates page](https://sebastiano.tronto.net/speedcubing/coordinates),
+we first need to compute the part of the coordinate where the symmetry
+is applied, that is the corner separation + orientation (also called
+*cocsep*). The value of the coordinate depends on the equivalence
+class of the corner configuration, and is memorized in a table called
+`cocsepdata`. To avoid lengthy computations, the index for a cube position
+in this table is determined by the corner orientation (between `0` and
+`3^7-1`) and a binary representation of the corner separation part (an
+8-bit number with 4 zero digits and 4 one digits, where zeros denote
+corners in one tetrad and 1 denotes corners in the other; the last bit
+can be ignored, as it can easily be deduced from the other 7). This is
+slightly less space-efficient than computing the actual corner-separation
+coordinate as a value between `0` and `C(8,4)`, but it is much faster.
+
+We can now access the value in the `cocsepdata` table corresponding to
+our cube position. This table contains the value of the symmetry-reduced
+coordinate and the so-called *ttrep* (transformation to representative)
+necessary to compute the full **h0** coordinate. For convenience,
+this table also stores a preliminary pruning value based on the corner
+coordinate. If this value is large enough, we may skip the computation of
+the **h0** coordinate and any further estimate. These three values can be
+stored in a single 32 bit integer, so that the table uses less than 12MB.
+
+### Getting the pruning value
+
+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
+ Rokicki in the
+ [nxopt document](https://github.com/rokicki/cube20src/blob/master/nxopt.md).
+ In this case the pruning table also has a *base value*, that determines
+ the offset to be added to each entry (each entry can only be 0, 1, 2 or 3).
+ If the base value is `b`, a pruning value of 1, 2 or 3 can be used directly
+ as a lower bound of b+1, b+2 and b+3 respectively. However, a value of 0
+ could mean that the actual lower bound is anything between 0 and b, so we
+ 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
+ valuable if most positions are more or less equally split between two
+ pruning values.
+ (Work in progress - `k1` tables not available in the code yet)
+
+### Estimation refinements
+
+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
+pruning value. If the normal estimate is not enough to prune the branch,
+the inverse of the position can be computed and a new estimate can be
+obtained from there.
+
+#### Reducing the branching factor - tight bounds
+
+*This trick and the next are and adaptation of a similar technique
+introduced by Rokicki in nxopt.*
+
+We can take advantage of the fact that the **h0** (and **h11**) coordinate
+is invariant under the subgroup `<U2, D2, R2, L2, F2, B2>`. Suppose we
+are looking for a solution of length `m`, we are at depth `d` and the
+pruning value `p` *for the inverse position* is a strict bound, that is
+`d+p = m`. In this situation, from the inverse point of view the solution
+cannot end with a 180° move: if this was the case, since these moves are
+contained in the target group for **h0** (or **h11**), it must be that
+we were in the target subgroup as well *before the last move*, i.e. we
+have found a solution for the **h0** coordinate of length `p-1`. But this
+is in contradiction with the fact that the inverse pruning value is `p`.
+
+From all of this, we conclude that trying any 180° move as next move is
+useless (because it would be the last move from the inverse position).
+We can therefore reduce the branching factor significantly and only try
+quarter-turn moves.
+
+#### Reducing the branching factor - switching to inverse
+
+We can expand on the previous trick by using a technique similar to NISS.
+
+Suppose that we have a strict bound for the *normal position*. As above,
+we can deduce that the last move cannot be a 180° move, but this does not
+tell us anything about the possibilities for the next move. However, if
+we *switch to the inverse scramble* we can take advantage of this fact
+as described above. For doing this, we need to replace the cube with its
+inverse, and keep track of the moves done from now on so that we can
+invert them at the end to construct the final solution.
+
+### 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.
+ (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
+ (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.
+
+## 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.
