diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/h48.md | 27 |
1 files changed, 22 insertions, 5 deletions
| @@ -331,6 +331,23 @@ on the symmetries of the starting position, which we take advantage of) | |||
| 331 | which are equally split between the available threads. Any solution | 331 | which are equally split between the available threads. Any solution |
| 332 | encountered in this step is of course added to the list of solutions. | 332 | encountered in this step is of course added to the list of solutions. |
| 333 | 333 | ||
| 334 | #### Filtering out symmetric cases | ||
| 335 | |||
| 336 | If the cube position we wish to solve is, say, mirrored along the RL | ||
| 337 | plane, it is redundant to attempt starting a solution with both R and L', | ||
| 338 | as they would lead to mirrored versions of the same solution. Therefore, | ||
| 339 | we filter out some tasks by looking for symmetries before each of the | ||
| 340 | first 4 moves. Then, unless we are looking for only one solution, we | ||
| 341 | have to make sure to report back all symmetric variations of a solution, | ||
| 342 | so we need to keep track of which transformations were available at each | ||
| 343 | of these 4 points. | ||
| 344 | |||
| 345 | This can reduce the number of starting positions drastically: for | ||
| 346 | example, for the superflip our method produces 1038 starting tasks - | ||
| 347 | a 41.67x improvement! Of course this optimization has no effect on any | ||
| 348 | position that isn't 3 moves or fewer away from a symmetric position - | ||
| 349 | which is the vast majority of them. | ||
| 350 | |||
| 334 | #### Heuristically sorting tasks | 351 | #### Heuristically sorting tasks |
| 335 | 352 | ||
| 336 | The tasks described in the previous paragraph (multi-threading) are | 353 | The tasks described in the previous paragraph (multi-threading) are |
| @@ -344,7 +361,7 @@ fact that sequences ending in U, R or F moves have more continuations | |||
| 344 | than those ending in D, L or B moves - as we don't allow, for example, | 361 | than those ending in D, L or B moves - as we don't allow, for example, |
| 345 | both U D and D U, but only the former. | 362 | both U D and D U, but only the former. |
| 346 | 363 | ||
| 347 | Preliminary benchmark show a performance improvement of around 40% | 364 | Preliminary benchmarks show a performance improvement of around 40% |
| 348 | when searching a single solution. When searching for multiple optimal | 365 | when searching a single solution. When searching for multiple optimal |
| 349 | solutions the effects of this optimization will be less pronounced, and | 366 | solutions the effects of this optimization will be less pronounced, and |
| 350 | they are obviously inexistent when looking for *all* optimal solutions. | 367 | they are obviously inexistent when looking for *all* optimal solutions. |
| @@ -435,13 +452,13 @@ efficient one) | |||
| 435 | 452 | ||
| 436 | ## Possible future improvements | 453 | ## Possible future improvements |
| 437 | 454 | ||
| 438 | *This section should be considered more of a draft with personal | 455 | *This section should be considered more of a collection of personal |
| 439 | notes, unlike the rest of the document.* | 456 | notes rather than a description of the solver.* |
| 440 | 457 | ||
| 441 | There are some areas where this implementation of the H48 optimal solver | 458 | There are some areas where this implementation of the H48 optimal solver |
| 442 | can be improved: | 459 | can be improved: |
| 443 | 460 | ||
| 444 | * Interwtining fallback tables to the main table. This is a trick that | 461 | * Intertwining fallback tables to the main table. This is a trick that |
| 445 | nxopt uses to reduce the number of cache misses, but we have not | 462 | nxopt uses to reduce the number of cache misses, but we have not |
| 446 | implemented in H48 yet. | 463 | implemented in H48 yet. |
| 447 | * Faster pruning table generation for **h11** and **h0**. Since these | 464 | * Faster pruning table generation for **h11** and **h0**. Since these |
| @@ -451,4 +468,4 @@ can be improved: | |||
| 451 | [BPMX](https://webdocs.cs.ualberta.ca/~nathanst/papers/AStar_Inconsistent.pdf) | 468 | [BPMX](https://webdocs.cs.ualberta.ca/~nathanst/papers/AStar_Inconsistent.pdf) |
| 452 | to improve pruning estimation. This optimization sped up | 469 | to improve pruning estimation. This optimization sped up |
| 453 | [vcube](https://github.com/Voltara/vcube/commit/a5b08f51793f81ac34c1d402f2627f6a0495c636). | 470 | [vcube](https://github.com/Voltara/vcube/commit/a5b08f51793f81ac34c1d402f2627f6a0495c636). |
| 454 | by about 5%-10%. Suggested by Arhan Chaudhary pointed out. | 471 | by about 5%-10%. Suggested by Arhan Chaudhary. |
