From 87a15e960e31365698df7e06cd3e6b851e17c1a5 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 5 Mar 2023 10:13:01 +0100 Subject: I made a mess, but it works. Still need to implement new optimal solver. After that, a big redesign is due. --- TODO/2.1.md | 96 ++++++++++------------------------------------- TODO/new-feature-ideas.md | 2 + TODO/refactoring.md | 2 - 3 files changed, 22 insertions(+), 78 deletions(-) (limited to 'TODO') 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 @@ # TODO-list for version 2.1 (or is it 3.0 at this point?) -## Alg and moveset changes (prerequisite for solve.h) - -### moveset.h -* split off from alg.h - -### alg.h -* There is a (future) bug in the way the solver checks if a move can -be appended (allowed_next and similar): the last two moves are not enough. -* Example: using QTM we have last 3 moves U U D. Considering only last 2, -U could be appended, but it cannot (cancel to U'). -* Solution: the per-moveset bool allowed_next() should take an alg as -parameter. There are going to be basically two versions, one for QTM and -one for HTM (but more may be added). -* Alg should be extended to remember the list of moves on inverse / normal -separately (without looping over moves). -* Maybe another parameter to know if it can assume there has not been -any double switching, i.e. if the last moves are the only ones to -be checked and there is no need to go back further (e.g. if alg is -U (... stuff on inverse ...) D I don't want to have to check back -to the U, but in practice we can often assume this does not happen). -* Then we can remove last and lastinv from dfsdata. -* move also can_niss to alg.h -* the check for the order of the moves (to avoid counting L R and R L as -different) can be made separately. Maybe add a "compare" function for moves, -such that non-commuting moves are not comparable (return -1 0 1). - ## Rework solver -* The architecture is the following: solve.h contains a solve() public -function that takes as parameters a set of solver methods (see below) -and a thread manager (basically, multithreaded or single threaded). -It also has a dfs() public function with the same parameters. -* The solve() function, looping over the allowed depths, calls -the dispatcher provided by the thread manager, which takes care of -instantiating the threads. Each thread calls back to dfs(). The -thread manager then takes case of re-assembling the solutions, and -finally returns a list of solutions for the given depth. -* The specifics of how dfs() works are implemented in a specific solver -module. +### 1. Implement minimum viable + +* Implement nxopt31 with fst_cube. Remember that the function + move_check_solved() should do one axis at the time, so that we don't move + everything before checking. +* test? -### solve.h +### 2. Rework achitecture and file dependencies -* Interface: define solve(), dfs() and the types dfsdata, solvermethods and -threadmanager. solve.h is included by specific thread managers and solvers. -* DfsData: remove Cube *, Movable, Step and extra. Add Void * (containing -either cube, indexes or whatnot) and a moveset (extracted from step, -necessary). Maybe cleanup solveoptions too (e.g. threads not necessary). -* solve.h depends only on moves (dependency on step and trans is removed). -* preparation step should be reworked, maybe removed or delegated to the -specific implementations. -* All dfs stuff in the same function. Maybe remove also solvestop. -* Move two-step solve to a different module +* solve.h depends only on moves(alg?) (dependency on step and trans is removed). +* Other modules have changed dependencies, might as well rework all. +* Make files smaller, do not include definition in .h, separate +data from abstract operations. +* remove cubetypes.h +* Create a module for multi-step (maybe wait?) +* Possible changes: in step solver, copy cube only if niss; add cleanup function +in solver (called by solve()) to free cube and perhaps pruning tables. +* see various TODO's in files -### Specific thread managers +### 4. More threading options -* Single thread. Useful in low-resources environments or when solving multiple -scrambles at the same time, or simply when asked to solve with one thread. * Lazy multithread: threads are as independent as possible and only merged at the end. Ideal when all solutions of a certain length are requested. -* Eager multithread: current implementation, branches communicate the number -and list of solutions to stop as soon as possible. Good when only one solution -of a certain depth is required. - -### Solver methods - -* bool move_check_stop(DfsArg *, Move): applies the given move (possibly -recovered from DfsData, but we avoid checking for niss by passing it -directly) and at the same time checks if the branch should be pruned. Not -elegant, but it is much more efficient to do the two things at the same time -(e.g. when moving a fst_cube we can move one "orientation" at the time, check -the pruning table and stop if possible). -* void add_solution(DfsArg *, ThreadManager): add the solution to the list. -Also checks if the solution is valid / acceptable (e.g. EO does not finish -with F' instead of F and such) and cleans it up (rotation, cleanup, unniss). -* void copy(void * src, void * dst): copy the cube-part of dfs_data. To be -called by copy_dfsdata, which remains in solve.h (but merged into dfs). -* void * invert_cube(void *): in preparation for niss. -* bool niss_makes_sense(DfsArg *): maybe can be done generically in solve.h? - -## New optimal solver (use fst) - -* Implement nxopt31 with fst_cube. Remember that the function - move_check_solved() should do one axis at the time, so that we don't move - everything before checking. +* (Done) Eager multithread: current implementation, branches communicate the +number and list of solutions to stop as soon as possible. Good when only one +solution of a certain depth is required. ## Simplify steps diff --git a/TODO/new-feature-ideas.md b/TODO/new-feature-ideas.md index b619e36..067d440 100644 --- a/TODO/new-feature-ideas.md +++ b/TODO/new-feature-ideas.md @@ -22,9 +22,11 @@ get its own file and more details. * Optimal solver: when asking only for one solution, scan for upper bound in parallel using a non-optimal (but fast) solver (e.g. twophase). * Optimal solver: up to a small bound, try with a small pruning table. +* Optimal solver: start at different depths in parallel * Multi-step solver: make more general ## New features +* Allow user to specify moveset manually (see issue \#5 on github) * EO analysis (and also DR and HTR analysis): group similar EOs (Jay) * HTR "maze" analysis? diff --git a/TODO/refactoring.md b/TODO/refactoring.md index 206b402..eedbd20 100644 --- a/TODO/refactoring.md +++ b/TODO/refactoring.md @@ -25,6 +25,4 @@ * Sort function implementations alphabetically, ignore static vs non static. * Rename functions and variable to have a consistent naming scheme. * Functions that copy data: swap src and dest, follow memcpy standard. -* The way coord uses define guards to organize the .h file is good, apply it - to other modules too - including tests. * Read style(9) and decide what to implement. -- cgit v1.3