1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
## (find better name) H48 solver, ideas
First compute co + csep. Use csep as a binary number (2^8 instead of 70,
loose a factor of 3.66 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
* ptable should contain some extra data at the beginning: an integer (size)
a checksum some summary info, maybe even in text form
* multisolve
* use threads
* 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)
* improve light solver with no table; consider using a small, hard-coded
table, e.g. H48 corner table?
## Optimizations
### General things
* Moves: don't do full compose for U*, D*, *2 (I removed this because I
was using shuffle intructions wrong, should re-do it)
* 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)
* CO is the worst part of moving, transforming and inverting. Try basing
everything on representing the cube without CO and apply it only at the
end to check that it is actually solved.
* see if vcube's method to flip all corners is better
* find a better way for computing the inverse?
* Improve avx2 instructions in general
### Threading
* THREADS build time option for the number of threads. If set to one,
do not include any threading library or code. Try detecting at build
time, or set to a sane default (e.g. 8? 16?) for generic builds.
* pthread or threads.h? I am more familiar with pthread, but threads.h
is standard (from C11, so it requires switching to it from C99).
Does using threads.h help in any way (e.g. building on Windows)?
## Improvements and other things
* Rename to libnissy (prefix public functions with nissy_?)
* add centers (and moves...)
* 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.
* Consider adding centers and other moves (for avx2: centers in the
same lane as corners, numbered from 9 to 14)
* More I/O:
nissy
ascii art (color = 1 letter)
twizzle binary https://www.experiments.cubing.net/cubing.js/spec/binary/
reid?
* print ptables (or layout data in such a way that can be printed
easily, e.g. first bytes are null-terminated strig and can be
printed by user)
* remove writetrans?
## "Front-end"
* Write adapter code for other languages:
python
hare
rust, go
dart ffi, js
java
* add also example code (e.g. an optimal solver) in examples/
## 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
## Roadmap
* Tests for multisolve
* More tests for simple solver?
* Benchmarks?
* More complex optimal solvers, pruning tables
* (More) benchmarks
* Multithreading (build-time option number of threads)
* Other optimizations
* Extend cube and moves to include centers
* NISS
* Move manipulation utilities
* Coordinate solvers and other steps
* More output formats
* Adapters for other languages (at least python)
* More documentation (or keep all in cube.h?)
* Rename to libnissy
* Release 1.0
|
