aboutsummaryrefslogtreecommitdiff
path: root/TODO/2.1.md
diff options
context:
space:
mode:
Diffstat (limited to 'TODO/2.1.md')
-rw-r--r--TODO/2.1.md96
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
10be 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,
12U could be appended, but it cannot (cancel to U').
13* Solution: the per-moveset bool allowed_next() should take an alg as
14parameter. There are going to be basically two versions, one for QTM and
15one for HTM (but more may be added).
16* Alg should be extended to remember the list of moves on inverse / normal
17separately (without looping over moves).
18* Maybe another parameter to know if it can assume there has not been
19any double switching, i.e. if the last moves are the only ones to
20be checked and there is no need to go back further (e.g. if alg is
21U (... stuff on inverse ...) D I don't want to have to check back
22to 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
26different) can be made separately. Maybe add a "compare" function for moves,
27such 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
32function that takes as parameters a set of solver methods (see below) 6
33and a thread manager (basically, multithreaded or single threaded). 7* Implement nxopt31 with fst_cube. Remember that the function
34It 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.
36the dispatcher provided by the thread manager, which takes care of 10* test?
37instantiating the threads. Each thread calls back to dfs(). The
38thread manager then takes case of re-assembling the solutions, and
39finally returns a list of solutions for the given depth.
40* The specifics of how dfs() works are implemented in a specific solver
41module.
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).
46threadmanager. 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
48either cube, indexes or whatnot) and a moveset (extracted from step, 17data from abstract operations.
49necessary). 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
52specific implementations. 21in 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
59scrambles 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
61merged at the end. Ideal when all solutions of a certain length are requested. 27merged 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
63and list of solutions to stop as soon as possible. Good when only one solution 29number and list of solutions to stop as soon as possible. Good when only one
64of a certain depth is required. 30solution of a certain depth is required.
65
66### Solver methods
67
68* bool move_check_stop(DfsArg *, Move): applies the given move (possibly
69recovered from DfsData, but we avoid checking for niss by passing it
70directly) and at the same time checks if the branch should be pruned. Not
71elegant, 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
73the pruning table and stop if possible).
74* void add_solution(DfsArg *, ThreadManager): add the solution to the list.
75Also checks if the solution is valid / acceptable (e.g. EO does not finish
76with 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
78called 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

Generated with cgit - Back to sebastiano.tronto.net