1 files changed, 50 insertions, 74 deletions

diff --git a/doc/h48.md b/doc/h48.md
index c601b75..0b9541a 100644
--- a/doc/h48.md
+++ b/doc/h48.md
@@ -1,9 +1,8 @@
 # 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.
+This solver is occasionally improved and optimized, and this document
+is updated accordingly to reflect the current implementation.
 
 I highly encourage the reader to check out Jaap Scherphuis'
 [Computer Puzzling page](https://www.jaapsch.net/puzzles/compcube.htm)
@@ -215,46 +214,40 @@ 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:
+Once we have computed the full h0 coordinate, we can access
+the correct entry in the full pruning table. We chose to
+use 2 bits per entry, as described by Rokicki in the [nxopt
+document](https://github.com/rokicki/cube20src/blob/master/nxopt.md).
+This means that every pruning table needs to have an associated *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 bound.
 
-* 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 bound. Instead we have to use a pruning value from
-  another table - see the section "Fallback tables" below.
-* 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)
+To be able to still use some sort of pruning value even when we get a
+0 read, we use a **fallback table**. Inspired by nxopt, this table is
+interleaved with the main table for cache efficiency: every 254 entries
+(508 bits), we store in 4 bits the minimum of the pruning values of these
+254 entries as a number from 0 to 16, without subtracting the table's
+base. Since a cache line is 512 bits long, we never get a cache miss
+when looking up the minimum value in the fallback table after a 0 read.
+Smaller lines (of 256 or 128 bits) have been tried, but they do not
+give any significant improvement over 512 bit lines.
 
-### Fallback tables
+Moreover, as an additional heuristic, in case of a 0 read we also look
+up another pruning value in a table that takes into account only the
+position of the edges. This table is small (around 1MB), so repeated
+accesses to it are not too slow. In practice, this gives a small speed up
+of around 5%.  More tables could be used to refine the fallback estimate,
+but each additional table leads to longer lookup times, especially if
+it is too large to fit in cache.
 
-When a pruning table does not store the exact lower bound value, for
-example in the case of `k2` table as described above, we need to refine
-our estimate using another table, which we call *fallback table*.
-In the current implementation, we actually use two different tables:
-
-* **h0** table: for larger `k2` tables we get a fallback value from the full
-  table for the **h0** coordinate.
-* edges-only table: to improve the pruning value for certain specific
-  scrambles, namely whose with solved corners such as the superflip,
-  we employ a second table that takes into account the edges of a full
-  **h11** coordinate. This table is small (around 1MB).
-
-More tables could be used to refine the fallback estimate, but each
-additional table leads to longer lookup times, especially if it is
-too large to fit in cache.
+Previous versions of this implementation (up to commit 6c42463, or
+to version 0.2) also included the possibility of a table with 4 bits
+per entry, at least for the `h0` case. Such tables did not require
+a fallback lookup, but due to their large size they were not less
+efficient. Therefore, they have been removed.
 
 ### Estimation refinements
 
@@ -368,20 +361,20 @@ they are obviously inexistent when looking for *all* optimal solutions.
 
 ## Pruning table computation
 
-### 4 bits tables for h0 and h11
+We first describe how the pruning table would be computed if we stored
+each pruning value fully, using 4 bits per entry. This algorithm used
+to be implemented (up to commit 6c42463), but has since been removed.
 
-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.
+### Full tables for h0 and h11 (not implemented)
 
-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**).
+If we are allowed to store the full pruning value for each entry,
+computing the pruning tables is not that difficult.  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.
 
 Unfortunately what I described above is an oversimplification: one
 also must take into account the case where the corner coordinate is
@@ -400,20 +393,7 @@ 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 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)
+### 2 bit tables
 
 Computing the pruning tables for intermediate coordinates is not as
 simple.  The reason is that these coordinates are not invariant under
@@ -441,14 +421,13 @@ 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)
+now limited at storing the coordinates at depth 8.
 
 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)
+the search from a coordinate that has already been visited. Further
+optimization are possible for **h0** and **h11**, and we may implement
+them in the future.
 
 ## Possible future improvements
 
@@ -458,9 +437,6 @@ notes rather than a description of the solver.*
 There are some areas where this implementation of the H48 optimal solver
 can be improved:
 
-* 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
   two coordinates are "real" coordinates, we can use a different technique
   to generate their tables faster. This won't affect the solver speed.