nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

commit fcb3ac9b02c3ed150fbf6d539613510cc83627ea
parent d97a625e8d96337dfa6a158cd247462b9cac29a5
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sat, 14 Jan 2023 22:33:09 +0100

Re-organized TODO file

Diffstat:
DTODO.md | 155-------------------------------------------------------------------------------
ATODO/2.1.md | 38++++++++++++++++++++++++++++++++++++++
ATODO/build-options.md | 33+++++++++++++++++++++++++++++++++
ATODO/documentation.md | 41+++++++++++++++++++++++++++++++++++++++++
ATODO/easy.md | 16++++++++++++++++
ATODO/installation.md | 14++++++++++++++
ATODO/new-feature-ideas.md | 30++++++++++++++++++++++++++++++
ATODO/parser.md | 13+++++++++++++
ATODO/refactoring.md | 28++++++++++++++++++++++++++++
ATODO/testing.md | 24++++++++++++++++++++++++
ATODO/webapp.md | 19+++++++++++++++++++
11 files changed, 256 insertions(+), 155 deletions(-)

diff --git a/TODO.md b/TODO.md @@ -1,155 +0,0 @@ -# TODO list - -This is a list of things that I would like to add or change at some point. -It's more of a personal reminder than anything else. - -## After symcoord -### Fixing stuff + completing new optimal solver -- clean up fst, check if more can be improved -### generic: -* all files should have an init function, calling the ones - of the files includes + doing more stuff. A static "initiliazed" - variable is probably needed too. -### testing! -* generic test util: function taking an array of tests, an array of testnames - (or maybe tests should be their own type?) and running them -* separate "commands" for testing different parts (e.g. ./test coord) -* test coordinate (needed anyway to test fst) -* other tests (start from bottom: utils.c) -* move test_coord to the testing folder -### Solving standard coordinates -* add Void * extradata to DfsArg and a custom move function -* add optional custom pre-process for generating special table (nx) -* copy_dfsdata should copy extra too! -### Solving simplification / refactor -* Split solve in solve_coord, solve_generic, solve_singlethread... -* Rework choicesteps: simplify, remove one type of rotation... -### nx.c -* implement nxopt with all tables and all tricks - (maybe compile time variable for maximum memory to use?) -* is_valid should also unniss / cleanup the alg -### Other easy refactor -* split cubetypes.h into other files - -## For version 2.1 -### Changes to Step and Solve -* remove cube from dfsarg? (i still need to save the scramble somewhere, - but I really only use it in dfs_niss) -* coord.c: all old coordinates (WIP...) -* steps.c: checkers (use coordinates), all stepalt and steps (WIP...) -* commands gen and freemem -* commands.c: twophase, ...? -### Rotate, not transform, before solving -* solve should re-orient first if needed and not just give up if centers are off -### Documentation -* Document how coordinates and pruning tables work now -* Write an examples.md file -* More screenshots! -### Tables management -* Check files in tables directory automatically remove old / extraneous files -* Add checksum to check that tables are generated / downloaded correctly -### Conditional compiling -* Option to avoid large tables at compile time -* option to avoid multithreading (write a simpler solve for t=1, and also - check if found enough solutions before checking pruning values) -### Technical -* generic option parser -* scan system to get best number of threads -### Commands -* Easy: add option -I (inverse) and -L (linear, like inverse + normal) - to do only linear NISS -* message for -N ignored say -n (lowercase) - -## Commands - -### Commands that are available in nissy 1.0, but not in this version (yet): -* drcorners (solve corners after dr) -* search and improve non-optimal subsequences -* save and edit algs as "variables" - (or just use a "logging system" to keep info about previously run commands, -including e.g. solutions that were not shown because -c) - -### More steps for `solve` -* QTM optimal solving -* 5-side solve (for robots) -* Block-building steps (cross, roux blocks, ...) -* Other common steps (LSE, ...) -* Larger table for drudfin (include epe)? About 1Gb uncompressed, - 500Mb compressed (fallback to noE), 250 compressed + parity trick - (is it doable?) - -### Improvements to currently implemented commands -* solve multidfs: do multithread by step, not by alternative (this way - if there are multiple alternatives it can make use of more threads) -* solve should try up to a small bound without loading the large pruning table - (maybe this is not necessary if loading the table is fast enough) -* silent batch mode without >>> -* Optimal solver: when asking for only one solution, scan for upper bound in - parallel using a two-phase solver. - -### New features -* EO analysis (and also DR and HTR analysis): group similar EOs together - and such (suggested by Jay) -* configurability: add an `alias` command, run config file at startup -* command notation to list available moves -* make multi-step solve much more general and create command -* input directly cube status instead of moves - (graphical: maybe there is a cubing.js function; command line: ???) - -## Distribution -* webapp (cgi) - -## Technical stuff - -### Memory management -* free pruning table after solve is done? if I do this I need to deafault to a - small table for < 8 moves solutions or smth -* improve multi-threading when solving multiple scrambles -* nissy -M maxmem option for running with at most maxmem memory; if exceeded - when loading a pruning table, return failure (or make every solve command - use tiny tables instead?); if maxmem is very 600Mb or - less do not use invtables (the performance loss is minimal anyway). If the - limit is really tiny, do not use mtables or ttables (but this would be - very slow and probably nobody will ever use it) -* Check if memory is enough for loading pruning tables; if not, abort -* For optimal solver: choose largest that fits in memory between nxopt and light - -### Structural changes -* client/server architecture: run a server process in the background so that - multiple client processess can send it queries and get results; this would - open up the door for a web-based version or graphical clients - -### Cleanup -* sort again functions alphabetically in their files -* change some function and variable names to make everything consistent -* more stuff to load at start (or when suitable command is called) rather - than when called directly, to avoid nasty problems with threading -* parse command args: one function per arg type, then each command has - a list of options that it accepts (as a string) - -### Style -* do not declare all variables at the beginning of a function -* remove var names from prototypes -* various stuff from style(9) - -### Random -Collect random info like this somewhere: - -Table pt_nxopt31_HTM -Base value: 9 -0 1 -1 6 -2 29 -3 164 -4 1433 -5 16772 -6 205033 -7 2513871 -8 30329976 -9 342440769 -10 2815191126 -11 6147967200 -12 524918774 -13 3546 -14 0 -15 0 diff --git a/TODO/2.1.md b/TODO/2.1.md @@ -0,0 +1,38 @@ +# TODO-list for version 2.1 (or is it 3.0 at this point?) + +## Rework solver + +* Split solve in solve_coord, solve_generic (and maybe solve_singlethread, see + notes about build options). +* Add a void * extradata to DfsArg. +* remove cube from dfsarg? (i still need to save the scramble somewhere, + but I really only use it in dfs_niss) +* Re-work prepare_step process for solve_generic (nxopt table is special). +* is_valid should also unnis and / or cleanup the alg. + +## 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. + +## Simplify steps + +* Remove one type of rotation. +* Change steps to choicestep and stepalt to step (or was this already done?). + +## Add missing coordinates and steps + +* Check the old file for a list. Many are missing. +* Checkers in steps.c should use coordinates. + +## Missing and new commands + +* gen +* freemem +* twophase + +## Easy improvements + +* Solve should re-orient the cube if centers are off +* Solve: add options for -I (inverse only) and -L (linear = normal + inverse). diff --git a/TODO/build-options.md b/TODO/build-options.md @@ -0,0 +1,33 @@ +# Build options for memory and multithreading + +## Investigate + +* Check exactly how much memory is needed for everything. +* Take note of which parts use threading (solving, genptable, other?). + +## Prepare code + +* Use define / ifdef or similar to compile and build tables only for the + parts to be used. +* If threads = 1, use a much simpler version of the solve method. Remember + that checking if enough solutions have been found is the first thing to + do in singlethread (no locking). +* Do not include pthread if threads = 1. +* Only one optimal solver should be compiled. +* Some simple steps may also need alternatives with smaller tables + (e.g. for staying sub 1Gb). For example dr and drfin. +* If necessary, work out alternatives to "twophase" for low-resource versions. + +## Makefile + +* Figure out how to change these options via makefile. For example: one + variable for the maximum allowed ram and one for the number of threads. +* (Optional) use a configure script? +* (Optional) interactive installation script? + +## Automate + +* Scout for resources during installation and choose best configuration + automatically. +* How to do this in Linux / POSIX? +* How to do this in Windows? diff --git a/TODO/documentation.md b/TODO/documentation.md @@ -0,0 +1,41 @@ +# Documentation + +## Big documentation file on nissy's internals + +* Coordinates +* Symcoordinates +* Pruning tables +* Coordinate solving +* fst cube +* Optimized solver +* Multithreading +* Commands etc... +* Code architecture + +## examples.md + +* Example file for nissy's website and documentation folder +* With screenshots! + +## Random info + +Where to collect random information like this table? + +Table pt_nxopt31_HTM +Base value: 9 +0 1 +1 6 +2 29 +3 164 +4 1433 +5 16772 +6 205033 +7 2513871 +8 30329976 +9 342440769 +10 2815191126 +11 6147967200 +12 524918774 +13 3546 +14 0 +15 0 diff --git a/TODO/easy.md b/TODO/easy.md @@ -0,0 +1,16 @@ +# Easy things to improve or add + +## Improvements + +* Silent batch mode without >>> +* Solutions should be shown sorted: by length first, then by normal moves + (no niss) first, then it depends on the step (e.g. EO by axis). + +## Old commands and steps + +* drcorners (solve corners after DR) +* Search and improve suboptimal subsequences + +## New commands + +* notation: show valid moves diff --git a/TODO/installation.md b/TODO/installation.md @@ -0,0 +1,14 @@ +# Simplify and improve installation + +## Tables + +* Make install should generate tables, or add a "make tables" target to + generate tables. +* Make tables should also check for existing files and remove old ones + (maybe more for nissy's command than for makefile). + +## Correctness + +* Add checksum for all generated files. +* Hard-code results? Check for compatibility problems between different OSes + and filesystems - but there should not be any, since we use stdint.h. diff --git a/TODO/new-feature-ideas.md b/TODO/new-feature-ideas.md @@ -0,0 +1,30 @@ +# Possible new features and improvements + +This file contains non-refined ideas. Once an idea gets refined, it will +get its own file and more details. + +## Steps + +* QTM solver +* 5-side solver (for robots) +* Other steps (cross, blocks, LSE...) + +## UX features + +* Save algs as variables and edit them (like in old nissy) +* Use a logging system for previously run commands, info, results... + (e.g. when solving with -c solutions are not shown, they can be logged here) +* Configurability: add an "alias" command, run config file at startup +* Input cube state directly instead of moves (ugly from command line / file) + +## Improvements + +* 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. +* Multi-step solver: make more general + +## New features + +* EO analysis (and also DR and HTR analysis): group similar EOs (Jay) +* HTR "maze" analysis? diff --git a/TODO/parser.md b/TODO/parser.md @@ -0,0 +1,13 @@ +# Improve command parser + +First, expand this TODO file to be more precise. + +## Refactor + +* The syntax of a command's options should be described by data, not by a + parser function. +* A single parser function can then parse options for all commands. + +## Usability + +* Better error messages! diff --git a/TODO/refactoring.md b/TODO/refactoring.md @@ -0,0 +1,28 @@ +# Refactoring + +## Init functions + +* All .h files should have a single init function. +* This function should initialize everything that this module needs, including + calling the init functions of the modules it depends on. +* To avoid multiple initialization of the same module, each should have a + static bool initialized variable. +* Everything that a module needs should be initialized by init(), avoid + initializing stuff when solving. Exception: pruning tables, move tables. +* Most functions should generate some tables and save them to disk. +* Init functions should have a consistent structure (e.g. the way they check + if the tables are already generated should be the same). + +## Cube types + +* Get rid of cubetype.h, split type definitionss into the other modules. +* Every type definition should be in the most fundamental module that needs it. + +## Code style + +* Stop declaring all variables at the beginning of a function. +* Remove variable names from prototypes. +* 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. +* Read style(9) and decide what to implement. diff --git a/TODO/testing.md b/TODO/testing.md @@ -0,0 +1,24 @@ +# Testing + +## Architecture + +* Folder structure: each module (.h file) has a corresponding test/module_name + folder containing the important tests. +* How to test pre / post -init()? +* Makefile: one target for each module with correct dependencies. +* Makefile: perhaps write a specific makefile for testing in test folder. + +## Test sttructure + +* Make consistent +* Little output for success +* Stop on first failed? (automatic with makefile) + +## Write tests + +* Pretty much all are missing, except fst. +* Start from bottom (utils.c) + +## Other + +* Move test_coord from coord.c to test folder. diff --git a/TODO/webapp.md b/TODO/webapp.md @@ -0,0 +1,19 @@ +# Towards a nissy webapp + +## Architecture + +* Split in client / server. +* Server can load and keep in memory all the tables, client(s) send messages to + the server to run commands. +* Use UNIX sockets only first, maybe later try WinSock. + +## Simple webapp + +* Investigate how to use fastcgi, try simple program first. +* Decide what limits to put in terms of resources and write a "filter" script + to block big requests (maybe use a timeout). + +## Advanced webapp + +* Use cubing.js for nice graphics. +* Port it to a graphical desktop version too.