diff options
Diffstat (limited to 'doc/h48.md')
| -rw-r--r-- | doc/h48.md | 31 |
1 files changed, 27 insertions, 4 deletions
| @@ -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 | |||
| 244 | When a pruning table does not store the exact lower bound value, for | ||
| 245 | example in the case of `k2` table as described above, we need to refine | ||
| 246 | our estimate using another table, which we call *fallback table*. | ||
| 247 | In 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 | |||
| 256 | More tables could be used to refine the fallback estimate, but each | ||
| 257 | additional table leads to longer lookup times, especially if it is | ||
| 258 | too large to fit in cache. | ||
| 259 | |||
| 243 | ### Estimation refinements | 260 | ### Estimation refinements |
| 244 | 261 | ||
| 245 | After computing the pruning value, there are a number of different tricks | 262 | After 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 | |||
| 285 | inverse, and keep track of the moves done from now on so that we can | 302 | inverse, and keep track of the moves done from now on so that we can |
| 286 | invert them at the end to construct the final solution. | 303 | invert them at the end to construct the final solution. |
| 287 | 304 | ||
| 305 | When this technique is used, it is also possible to avoid some table | ||
| 306 | lookups: if the last move applied to the cube is a 180° move *on the | ||
| 307 | inverse position*, then the coordinate on the normal position has not | ||
| 308 | changed. Thus if we keep track of the last computed pruning value, | ||
| 309 | we can reuse it and avoid an expensive table lookup. | ||
| 310 | |||
| 288 | ### Other optimizations | 311 | ### Other optimizations |
| 289 | 312 | ||
| 290 | Other possible (low-level) optimizations include: | 313 | Other 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 |
| 348 | computing 2 bits table for "real" coordinates; instead, an optimized | 371 | computing 2 bits table for "real" coordinates; instead, an optimized |
| 349 | version of the generic method explained below is used) | 372 | version of the generic method explained below is used) |
| 350 | 373 | ||
