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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
Check stats for all tables using H48stats solver
- implement getcube
x implement stuff in utils.h
x implement functions
x unit tests for permtoindex and indextoperm
x move cubefromarray from cube_io to where needed (cube_generic)
- implement in cube_generic
x getcube_fix
- getcube
x permutation
- orientation
- unit tests
x fix in cube_public
- test shell
- optional: dr states (includes "fix" option)
- implement tool for stats
- output to file, only write cocsep to stdout
Bug in esep table generation
- Fails for UFRUFU, try command
./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \
"$(./run frommoves -moves "UFRUFU")"
- Fundamental error in how tables are generated, each coordinate has too
many representative. I need to use the big table with the full coordinate
first (h=11, ~241 billion positions, 60Gb with k=2). From this the smaller
tables can be easily deduced.
- Investigate the possibility of computing smaller tables directly in some
other way, even if slow.
- use dfs for computing big table, save distance %3 until the last two steps,
then clean the table and double loop over moves to fill the value
Solver
- cleanup h48 solver
- do not copy dfsarg, change and undo
- implement and use premove (and test) instead of inverting
- 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)
## 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?
pthreads or threads.h?
* 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?)
## 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
|
