From bcd52547af58b15868e24f3904e307548d1fd505 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 14 Dec 2025 15:12:36 +0100 Subject: Cleanup, update documentation, fix examples --- doc/h48.md | 130 +++++++++++++++++++++++---------------------------------- doc/solvers.md | 7 ++-- 2 files changed, 56 insertions(+), 81 deletions(-) (limited to 'doc') 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: - -* 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) - -### Fallback tables - -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. +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. + +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. + +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. + +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. diff --git a/doc/solvers.md b/doc/solvers.md index e90a40b..a246c54 100644 --- a/doc/solvers.md +++ b/doc/solvers.md @@ -10,12 +10,11 @@ An HTM-optimal solver using fully-symmetric pruning tables. For details about how this solver works, see [h48.md](./h48.md). For benchmarks see [benchmarks/benchmarks.md](../benchmarks/benchmarks.md). -* Name: of the form `h8hXk2` for `X` from 0 to 11, or `h48h0k4`. The name - `optimal` is an alias for `h48h7k2`. +* Name: of the form `h8hX` for `X` from 0 to 11. The name `optimal` is + an alias for `h48h7`. * Requisites: none. * Moveset: HTM (all 18 basic moves). -* Data size: 59MB for `h48h0k4`, from 115MB to 59GB for `h48hXk2` - (roughly 59MB + 2X*56MB). +* From 115MB to 59GB (roughly 2X*56MB). ## Coordinate solvers -- cgit v1.3