diff options
Diffstat (limited to 'TODO/2.1.md')
| -rw-r--r-- | TODO/2.1.md | 96 |
1 files changed, 20 insertions, 76 deletions
diff --git a/TODO/2.1.md b/TODO/2.1.md index d65eb93..7448094 100644 --- a/TODO/2.1.md +++ b/TODO/2.1.md | |||
| @@ -1,89 +1,33 @@ | |||
| 1 | # TODO-list for version 2.1 (or is it 3.0 at this point?) | 1 | # TODO-list for version 2.1 (or is it 3.0 at this point?) |
| 2 | 2 | ||
| 3 | ## Alg and moveset changes (prerequisite for solve.h) | ||
| 4 | |||
| 5 | ### moveset.h | ||
| 6 | * split off from alg.h | ||
| 7 | |||
| 8 | ### alg.h | ||
| 9 | * There is a (future) bug in the way the solver checks if a move can | ||
| 10 | be appended (allowed_next and similar): the last two moves are not enough. | ||
| 11 | * Example: using QTM we have last 3 moves U U D. Considering only last 2, | ||
| 12 | U could be appended, but it cannot (cancel to U'). | ||
| 13 | * Solution: the per-moveset bool allowed_next() should take an alg as | ||
| 14 | parameter. There are going to be basically two versions, one for QTM and | ||
| 15 | one for HTM (but more may be added). | ||
| 16 | * Alg should be extended to remember the list of moves on inverse / normal | ||
| 17 | separately (without looping over moves). | ||
| 18 | * Maybe another parameter to know if it can assume there has not been | ||
| 19 | any double switching, i.e. if the last moves are the only ones to | ||
| 20 | be checked and there is no need to go back further (e.g. if alg is | ||
| 21 | U (... stuff on inverse ...) D I don't want to have to check back | ||
| 22 | to the U, but in practice we can often assume this does not happen). | ||
| 23 | * Then we can remove last and lastinv from dfsdata. | ||
| 24 | * move also can_niss to alg.h | ||
| 25 | * the check for the order of the moves (to avoid counting L R and R L as | ||
| 26 | different) can be made separately. Maybe add a "compare" function for moves, | ||
| 27 | such that non-commuting moves are not comparable (return -1 0 1). | ||
| 28 | |||
| 29 | ## Rework solver | 3 | ## Rework solver |
| 30 | 4 | ||
| 31 | * The architecture is the following: solve.h contains a solve() public | 5 | ### 1. Implement minimum viable |
| 32 | function that takes as parameters a set of solver methods (see below) | 6 | |
| 33 | and a thread manager (basically, multithreaded or single threaded). | 7 | * Implement nxopt31 with fst_cube. Remember that the function |
| 34 | It also has a dfs() public function with the same parameters. | 8 | move_check_solved() should do one axis at the time, so that we don't move |
| 35 | * The solve() function, looping over the allowed depths, calls | 9 | everything before checking. |
| 36 | the dispatcher provided by the thread manager, which takes care of | 10 | * test? |
| 37 | instantiating the threads. Each thread calls back to dfs(). The | ||
| 38 | thread manager then takes case of re-assembling the solutions, and | ||
| 39 | finally returns a list of solutions for the given depth. | ||
| 40 | * The specifics of how dfs() works are implemented in a specific solver | ||
| 41 | module. | ||
| 42 | 11 | ||
| 43 | ### solve.h | 12 | ### 2. Rework achitecture and file dependencies |
| 44 | 13 | ||
| 45 | * Interface: define solve(), dfs() and the types dfsdata, solvermethods and | 14 | * solve.h depends only on moves(alg?) (dependency on step and trans is removed). |
| 46 | threadmanager. solve.h is included by specific thread managers and solvers. | 15 | * Other modules have changed dependencies, might as well rework all. |
| 47 | * DfsData: remove Cube *, Movable, Step and extra. Add Void * (containing | 16 | * Make files smaller, do not include definition in .h, separate |
| 48 | either cube, indexes or whatnot) and a moveset (extracted from step, | 17 | data from abstract operations. |
| 49 | necessary). Maybe cleanup solveoptions too (e.g. threads not necessary). | 18 | * remove cubetypes.h |
| 50 | * solve.h depends only on moves (dependency on step and trans is removed). | 19 | * Create a module for multi-step (maybe wait?) |
| 51 | * preparation step should be reworked, maybe removed or delegated to the | 20 | * Possible changes: in step solver, copy cube only if niss; add cleanup function |
| 52 | specific implementations. | 21 | in solver (called by solve()) to free cube and perhaps pruning tables. |
| 53 | * All dfs stuff in the same function. Maybe remove also solvestop. | 22 | * see various TODO's in files |
| 54 | * Move two-step solve to a different module | ||
| 55 | 23 | ||
| 56 | ### Specific thread managers | 24 | ### 4. More threading options |
| 57 | 25 | ||
| 58 | * Single thread. Useful in low-resources environments or when solving multiple | ||
| 59 | scrambles at the same time, or simply when asked to solve with one thread. | ||
| 60 | * Lazy multithread: threads are as independent as possible and only | 26 | * Lazy multithread: threads are as independent as possible and only |
| 61 | merged at the end. Ideal when all solutions of a certain length are requested. | 27 | merged at the end. Ideal when all solutions of a certain length are requested. |
| 62 | * Eager multithread: current implementation, branches communicate the number | 28 | * (Done) Eager multithread: current implementation, branches communicate the |
| 63 | and list of solutions to stop as soon as possible. Good when only one solution | 29 | number and list of solutions to stop as soon as possible. Good when only one |
| 64 | of a certain depth is required. | 30 | solution of a certain depth is required. |
| 65 | |||
| 66 | ### Solver methods | ||
| 67 | |||
| 68 | * bool move_check_stop(DfsArg *, Move): applies the given move (possibly | ||
| 69 | recovered from DfsData, but we avoid checking for niss by passing it | ||
| 70 | directly) and at the same time checks if the branch should be pruned. Not | ||
| 71 | elegant, but it is much more efficient to do the two things at the same time | ||
| 72 | (e.g. when moving a fst_cube we can move one "orientation" at the time, check | ||
| 73 | the pruning table and stop if possible). | ||
| 74 | * void add_solution(DfsArg *, ThreadManager): add the solution to the list. | ||
| 75 | Also checks if the solution is valid / acceptable (e.g. EO does not finish | ||
| 76 | with F' instead of F and such) and cleans it up (rotation, cleanup, unniss). | ||
| 77 | * void copy(void * src, void * dst): copy the cube-part of dfs_data. To be | ||
| 78 | called by copy_dfsdata, which remains in solve.h (but merged into dfs). | ||
| 79 | * void * invert_cube(void *): in preparation for niss. | ||
| 80 | * bool niss_makes_sense(DfsArg *): maybe can be done generically in solve.h? | ||
| 81 | |||
| 82 | ## New optimal solver (use fst) | ||
| 83 | |||
| 84 | * Implement nxopt31 with fst_cube. Remember that the function | ||
| 85 | move_check_solved() should do one axis at the time, so that we don't move | ||
| 86 | everything before checking. | ||
| 87 | 31 | ||
| 88 | ## Simplify steps | 32 | ## Simplify steps |
| 89 | 33 | ||
