1 files changed, 0 insertions, 193 deletions
diff --git a/TODO.txt b/TODO.txt
deleted file mode 100644
index 68fe8a2..0000000
--- a/TODO.txt
+++ /dev/null
@@ -1,193 +0,0 @@
-# Documentation and cleanup
- Internal documentation
-  - h48 solver and co
-    - what is h and k
-  - cube representation and base routines?
- Split files
-  - h48 into:
-    - h48_base (coordinate computation)
-    - h48_map (only the hashmap thing)
-    - h48_gendata (table generation)
-    - h48_solve (including stats solver)
-# H48 table generation
-  - compute all tables for h<11
-    x compute visited up to a fixed depth 8
-    - compute additional step (if needed) to fill <=base
-    - brute-force the last 2 steps (only 18 moves + 18*15 move pairs, + sim)
-    - compare with known h0 results (from long-running test)
-  - compute table for h=11
-    - can it be unified to the other computation, or is it much better
-      to do it ad hoc?
-    - derive small tables from the large one to check correctness
-      - this requires too much ram, but I can print the summary of the table
-  - Add long-running test for h0k4 (maybe as a tool?)
-    - tests for other sizes?
-  - gendata tool: save tables?
-  - optimize
-    - use only transform_edges (need compose trans)
-    - parallelize with pthread
-# Solver (Enrico)
- Add a solver for h=0
- check if this (or equivalent) works:
-    ./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \
-         "$(./run frommoves -moves "UFRUFU")"
-table base for k=2 (4 most common values start at)
-  0     8
-  1     8
-  2     8
-  3     8 or 9 (very close)
-  4     9
-  5     9
-  6     9
-  7     9 or 10 (very close)
-  8     10
-  9     10
-  10    10
-  11    11
-Solver
-  - cleanup h48 solver
-    - do not copy dfsarg, change and undo
-    - implement and use premove (and test) instead of inverting
-    - improve name of tables file in shell.c (include h value, maybe k, max)
-  - benchmark for solve
-    table generation, where to keep tables? in benchmark folder or in tables/?
-  - more tricks for solver, optimize, try larger tables
-  - remove solve_simple and maybe the whole solve_generic
-  - shell: silently accept other formats too?
-  - shell: allow generating multiple tables for different options
-  - gendata: move info at start of tables?
-Cleanup cube_public and interface
-  - remove options, use only solver name
-    cleanup also benchmark
-  - write a generic parse + dispatch to solver
-    (maybe use helper function from solve_h48 for parsing hXkY)
-Goal: find out which k value is best
-  - temporarily call current table and solver "k4" instead of h48
-  - write table generation and solver for k2 and k1
-  - benchmark for different sizes!
-Improvements
-  - check hash of generated data
-  - use interleaved tables (e.g. big table with k=2 or k=1 and interleaved
-    small table with k=4 for better backup pruning)
-small things
-  - maybe move part of the logic for coord_h48 (and its inverse) to
-    utils.h (subsettoindex-like)
-  - rename TYPE build switch to something more intuitive like ARCH
-    remove one of TYPE and CUBE_TYPE (why do I have two?)
-  - merge constants and utils?
-## H48 optimal solver (some has already been implemented)
-First compute co + csep. Use csep as a binary number (2^7 instead of 70,
-loose a factor of 1.8 but still fits in a few megabytes or less). Use
-co + csep as an index in a table whose entries have: 6 bits for ttrep,
-12 bits for rep, 4 bits for pruning. Optionally, 4 more bits could be
-used for the base of the pruning table, if we want to have a different
-base for each corner state; but probably not useful.
-If the first pruning is enough, or if the base value of the pruning table
-(see below) is too low, do not compute the full coordinate (which includes
-epsep + partial EO, 12 different sizes depending on how many edges).
-Otherwise, transform edges only using ttrep and compute full coordinate.
-Look up in table. 3 types of table:
-1. 4 bits per entry, full pruning table
-2. 3 bits with base value (let's try, why not)
-3. 2 bits with base value, nxopt style
-4. 1 bit per entry, telling only if more or less than mid value
-Types 2-4 require benchmarks, a lot of them.
-Inverse probing (no need to compute inverse, compute one at the beginning
-and keep adding premoves); better do first part of pruning for both
-normal and inverse and only then search in the full table.
-If inverse probing gives tight bound, reduce branching factor, optionally
-switch. Here NISS may be useful.
-## Other solvers
-* nxopt (various sizes, for comparison; also use base value probing
-  and benchmarking)
-* Coordinate solver for replacing nissy backend (specify in the comments
-  that coordinates return 0 if solved)
-* simple solver with small table for short solutions
-## ARM NEON intrinsics and other architectures
-* For ARM: use two uint8x16_t (or uint8x16x2_t) and vqtbl* instructions;
-  see https://developer.arm.com/architectures/instruction-sets/intrinsics
-* Implement also SSE? Why not...
-## Optimizations
-* Moves: don't do full compose for U*, D*, *2 (I removed this because I
-  was using shuffle intructions wrong, should re-do it)
-* transform edges only for h48 coord calculation
-* ptable: since it is fully symmetric, do only U or U2 at depth 1
-* use threads: how to detect at runtime? what is sane number to default to?
-* multisolve with adaptive threading
-* Trans: don't do full compose, for some trans composing perm is enough.
-  Split out sumco() as a separate function and refactor, optimize.
-* Use multi-move (up to 4/5 moves at once)
-* see if vcube's method to flip all corners is better
-* find a better way for computing the inverse?
-* Transform with big table: make static cube actually static (how?)
-* Use selfsim: in generating some tables, it is in thery possible to only check
-  the few transformations that give self-similarity instead of all 48.
-  The performance drop is almost insignificant, but I would like to figure out
-  the mistake I made previously.
-## Improvements and other things
-* Rename to libnissy (prefix public functions with nissy_?)
-* add centers (and slice moves and rotations)
-  for avx2: centers in the same lane as corners, numbered from 9 to 14
-* for CO: move to bits 5 and 6, no need for padding bit
-* manipulate move sequences (invert, unniss, cleanup, mirror / transform...)
-* NISS: Add mask to moves (e.g. U | NISS where NISS = 32 or something);
-  adapt readmoves and writemoves.
-* More I/O formats:
-  reid format
-  nissy
-  ascii art (color = 1 letter? color print?)
-  twizzle binary https://www.experiments.cubing.net/cubing.js/spec/binary/
-## "Front-end"
-* nissy shell: make more usable, meaningful error messages etc
-  for example, it should check that the solver is valid
-* Write adapter code for other languages:
-  python
-  hare (see blog post 2023-12-01 for ffi)
-  rust, go
-  dart ffi, js
-  java
-## More documentation?
-* Add documentation comments inside cube.c?
-* Copy this to cube.c
-Transformations can be either simple rotations or a rotation composed
-with a mirroring.  A composed rotation + mirror is obtained by applying
-the corresponding rotation to the solved cube mirrored along the M plane.
-For example, to apply the transformation RBm (mirrored RB) to a cube C:
-        1. Apply a mirror along the M plane to the solved cube
-        2. Rotate the mirrored cube with z' y2
-        3. Apply the cube C to the transformed solved cube
-        4. Apply the transformations of step 1a and 1b in reverse
-## Future work?
-* A* on GPU? https://github.com/mwarzynski/uw_parallel_a_star

diff --git a/TODO.txt b/TODO.txt deleted file mode 100644 index 68fe8a2..0000000 --- a/TODO.txt +++ /dev/null
@@ -1,193 +0,0 @@
1	# Documentation and cleanup
2
3	- Internal documentation
4	- h48 solver and co
5	- what is h and k
6	- cube representation and base routines?
7	- Split files
8	- h48 into:
9	- h48_base (coordinate computation)
10	- h48_map (only the hashmap thing)
11	- h48_gendata (table generation)
12	- h48_solve (including stats solver)
13
14	# H48 table generation
15	- compute all tables for h<11
16	x compute visited up to a fixed depth 8
17	- compute additional step (if needed) to fill <=base
18	- brute-force the last 2 steps (only 18 moves + 18*15 move pairs, + sim)
19	- compare with known h0 results (from long-running test)
20	- compute table for h=11
21	- can it be unified to the other computation, or is it much better
22	to do it ad hoc?
23	- derive small tables from the large one to check correctness
24	- this requires too much ram, but I can print the summary of the table
25	- Add long-running test for h0k4 (maybe as a tool?)
26	- tests for other sizes?
27	- gendata tool: save tables?
28	- optimize
29	- use only transform_edges (need compose trans)
30	- parallelize with pthread
31
32	# Solver (Enrico)
33
34	- Add a solver for h=0
35	- check if this (or equivalent) works:
36	./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \
37	"$(./run frommoves -moves "UFRUFU")"
38
39	table base for k=2 (4 most common values start at)
40	0 8
41	1 8
42	2 8
43	3 8 or 9 (very close)
44	4 9
45	5 9
46	6 9
47	7 9 or 10 (very close)
48	8 10
49	9 10
50	10 10
51	11 11
52
53	Solver
54	- cleanup h48 solver
55	- do not copy dfsarg, change and undo
56	- implement and use premove (and test) instead of inverting
57	- improve name of tables file in shell.c (include h value, maybe k, max)
58	- benchmark for solve
59	table generation, where to keep tables? in benchmark folder or in tables/?
60	- more tricks for solver, optimize, try larger tables
61	- remove solve_simple and maybe the whole solve_generic
62	- shell: silently accept other formats too?
63	- shell: allow generating multiple tables for different options
64	- gendata: move info at start of tables?
65
66	Cleanup cube_public and interface
67	- remove options, use only solver name
68	cleanup also benchmark
69	- write a generic parse + dispatch to solver
70	(maybe use helper function from solve_h48 for parsing hXkY)
71
72	Goal: find out which k value is best
73	- temporarily call current table and solver "k4" instead of h48
74	- write table generation and solver for k2 and k1
75	- benchmark for different sizes!
76
77	Improvements
78	- check hash of generated data
79	- use interleaved tables (e.g. big table with k=2 or k=1 and interleaved
80	small table with k=4 for better backup pruning)
81
82	small things
83	- maybe move part of the logic for coord_h48 (and its inverse) to
84	utils.h (subsettoindex-like)
85	- rename TYPE build switch to something more intuitive like ARCH
86	remove one of TYPE and CUBE_TYPE (why do I have two?)
87	- merge constants and utils?
88
89	## H48 optimal solver (some has already been implemented)
90
91	First compute co + csep. Use csep as a binary number (2^7 instead of 70,
92	loose a factor of 1.8 but still fits in a few megabytes or less). Use
93	co + csep as an index in a table whose entries have: 6 bits for ttrep,
94	12 bits for rep, 4 bits for pruning. Optionally, 4 more bits could be
95	used for the base of the pruning table, if we want to have a different
96	base for each corner state; but probably not useful.
97
98	If the first pruning is enough, or if the base value of the pruning table
99	(see below) is too low, do not compute the full coordinate (which includes
100	epsep + partial EO, 12 different sizes depending on how many edges).
101
102	Otherwise, transform edges only using ttrep and compute full coordinate.
103	Look up in table. 3 types of table:
104	1. 4 bits per entry, full pruning table
105	2. 3 bits with base value (let's try, why not)
106	3. 2 bits with base value, nxopt style
107	4. 1 bit per entry, telling only if more or less than mid value
108	Types 2-4 require benchmarks, a lot of them.
109
110	Inverse probing (no need to compute inverse, compute one at the beginning
111	and keep adding premoves); better do first part of pruning for both
112	normal and inverse and only then search in the full table.
113
114	If inverse probing gives tight bound, reduce branching factor, optionally
115	switch. Here NISS may be useful.
116
117	## Other solvers
118
119	* nxopt (various sizes, for comparison; also use base value probing
120	and benchmarking)
121	* Coordinate solver for replacing nissy backend (specify in the comments
122	that coordinates return 0 if solved)
123	* simple solver with small table for short solutions
124
125	## ARM NEON intrinsics and other architectures
126
127	* For ARM: use two uint8x16_t (or uint8x16x2_t) and vqtbl* instructions;
128	see https://developer.arm.com/architectures/instruction-sets/intrinsics
129	* Implement also SSE? Why not...
130
131	## Optimizations
132
133	* Moves: don't do full compose for U, D, *2 (I removed this because I
134	was using shuffle intructions wrong, should re-do it)
135	* transform edges only for h48 coord calculation
136	* ptable: since it is fully symmetric, do only U or U2 at depth 1
137	* use threads: how to detect at runtime? what is sane number to default to?
138	* multisolve with adaptive threading
139	* Trans: don't do full compose, for some trans composing perm is enough.
140	Split out sumco() as a separate function and refactor, optimize.
141	* Use multi-move (up to 4/5 moves at once)
142	* see if vcube's method to flip all corners is better
143	* find a better way for computing the inverse?
144	* Transform with big table: make static cube actually static (how?)
145	* Use selfsim: in generating some tables, it is in thery possible to only check
146	the few transformations that give self-similarity instead of all 48.
147	The performance drop is almost insignificant, but I would like to figure out
148	the mistake I made previously.
149
150	## Improvements and other things
151
152	* Rename to libnissy (prefix public functions with nissy_?)
153	* add centers (and slice moves and rotations)
154	for avx2: centers in the same lane as corners, numbered from 9 to 14
155	* for CO: move to bits 5 and 6, no need for padding bit
156	* manipulate move sequences (invert, unniss, cleanup, mirror / transform...)
157	* NISS: Add mask to moves (e.g. U \| NISS where NISS = 32 or something);
158	adapt readmoves and writemoves.
159	* More I/O formats:
160	reid format
161	nissy
162	ascii art (color = 1 letter? color print?)
163	twizzle binary https://www.experiments.cubing.net/cubing.js/spec/binary/
164
165	## "Front-end"
166
167	* nissy shell: make more usable, meaningful error messages etc
168	for example, it should check that the solver is valid
169	* Write adapter code for other languages:
170	python
171	hare (see blog post 2023-12-01 for ffi)
172	rust, go
173	dart ffi, js
174	java
175
176	## More documentation?
177
178	* Add documentation comments inside cube.c?
179	* Copy this to cube.c
180
181	Transformations can be either simple rotations or a rotation composed
182	with a mirroring. A composed rotation + mirror is obtained by applying
183	the corresponding rotation to the solved cube mirrored along the M plane.
184
185	For example, to apply the transformation RBm (mirrored RB) to a cube C:
186	1. Apply a mirror along the M plane to the solved cube
187	2. Rotate the mirrored cube with z' y2
188	3. Apply the cube C to the transformed solved cube
189	4. Apply the transformations of step 1a and 1b in reverse
190
191	## Future work?
192
193	* A* on GPU? https://github.com/mwarzynski/uw_parallel_a_star