aboutsummaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--doc/h48.md31
-rw-r--r--doc/transformations.md3
2 files changed, 29 insertions, 5 deletions
diff --git a/doc/h48.md b/doc/h48.md
index 323453a..678e160 100644
--- a/doc/h48.md
+++ b/doc/h48.md
@@ -230,9 +230,8 @@ can be one of three kinds:
230 If the base value is `b`, a pruning value of 1, 2 or 3 can be used directly 230 If the base value is `b`, a pruning value of 1, 2 or 3 can be used directly
231 as a lower bound of b+1, b+2 and b+3 respectively. However, a value of 0 231 as a lower bound of b+1, b+2 and b+3 respectively. However, a value of 0
232 could mean that the actual lower bound is anything between 0 and b, so we 232 could mean that the actual lower bound is anything between 0 and b, so we
233 cannot take b as a lower bount. Instead we have to use a pruning value from 233 cannot take b as a lower bound. Instead we have to use a pruning value from
234 another table, for example the corner-only table mentioned in the previous 234 another table - see the section "Fallback tables" below.
235 section, or a completely new one.
236* 1 bit per entry, or `k1`: With one bit per entry, the only information we 235* 1 bit per entry, or `k1`: With one bit per entry, the only information we
237 can get from the pruning table is wether or not the current position 236 can get from the pruning table is wether or not the current position
238 requires more or fewer moves than a fixed base value b. This can still be 237 requires more or fewer moves than a fixed base value b. This can still be
@@ -240,6 +239,24 @@ can be one of three kinds:
240 pruning values. 239 pruning values.
241 (Work in progress - `k1` tables not available in the code yet) 240 (Work in progress - `k1` tables not available in the code yet)
242 241
242### Fallback tables
243
244When a pruning table does not store the exact lower bound value, for
245example in the case of `k2` table as described above, we need to refine
246our estimate using another table, which we call *fallback table*.
247In the current implementation, we actually use two different tables:
248
249* **h0** table: for larger `k2` tables we get a fallback value from the full
250 table for the **h0** coordinate.
251* edges-only table: to improve the pruning value for certain specific
252 scrambles, namely whose with solved corners such as the superflip,
253 we employ a second table that takes into account the edges of a full
254 **h11** coordinate. This table is small (around 1MB).
255
256More tables could be used to refine the fallback estimate, but each
257additional table leads to longer lookup times, especially if it is
258too large to fit in cache.
259
243### Estimation refinements 260### Estimation refinements
244 261
245After computing the pruning value, there are a number of different tricks 262After computing the pruning value, there are a number of different tricks
@@ -285,6 +302,12 @@ as described above. For doing this, we need to replace the cube with its
285inverse, and keep track of the moves done from now on so that we can 302inverse, and keep track of the moves done from now on so that we can
286invert them at the end to construct the final solution. 303invert them at the end to construct the final solution.
287 304
305When this technique is used, it is also possible to avoid some table
306lookups: if the last move applied to the cube is a 180° move *on the
307inverse position*, then the coordinate on the normal position has not
308changed. Thus if we keep track of the last computed pruning value,
309we can reuse it and avoid an expensive table lookup.
310
288### Other optimizations 311### Other optimizations
289 312
290Other possible (low-level) optimizations include: 313Other possible (low-level) optimizations include:
@@ -344,7 +367,7 @@ don't have this much memory.
344 367
345### 2 bits tables with for h0 and h11 368### 2 bits tables with for h0 and h11
346 369
347(Work in progress - currently I there is no specialized routine for 370(Work in progress - currently there is no specialized routine for
348computing 2 bits table for "real" coordinates; instead, an optimized 371computing 2 bits table for "real" coordinates; instead, an optimized
349version of the generic method explained below is used) 372version of the generic method explained below is used)
350 373
diff --git a/doc/transformations.md b/doc/transformations.md
index a180ce6..65212ea 100644
--- a/doc/transformations.md
+++ b/doc/transformations.md
@@ -6,4 +6,5 @@ For example, to apply the transformation RBm (mirrored RB) to a cube C:
6 1. Apply a mirror along the M plane to the solved cube 6 1. Apply a mirror along the M plane to the solved cube
7 2. Rotate the mirrored cube with z' y2 7 2. Rotate the mirrored cube with z' y2
8 3. Apply the cube C to the transformed solved cube 8 3. Apply the cube C to the transformed solved cube
9 4. Apply the transformations of step 1a and 1b in reverse 9 4. Apply the transformations of step 2 in reverse
10 5. Apply the transformations of step 1 in reverse

Generated with cgit - Back to sebastiano.tronto.net