commit f3171b749cfd1a80742ee58dbc77d29c901639e5
parent 1a5bfe9b08707b0aef748d7921a419ba4a046fba
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 1 May 2023 12:27:52 +0200
Beginning of new repo
Diffstat:
12 files changed, 301 insertions(+), 116 deletions(-)
diff --git a/README.md b/README.md
@@ -1,104 +1,6 @@
-# WARNING
+# A Rubik's cube optimal solver
-I am currently rewriting some important parts of the code
-and the git version is not working.
-You can download the last stable version from the
-[download page](https://nissy.tronto.net/download).
-
-# Nissy
-
-A Rubik's cube solver and FMC assistant.
-For optimal HTM solving Nissy uses techniques from Herbert Kociemba's
-[Cube Explorer](http://kociemba.org/cube.htm) and Tomas Rokicki's
-[nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md).
-With 4 cores at 2.5GHz and using about 3Gb of RAM, Nissy can find an
-optimal solution in about a minute on average.
-
-Nissy can also solve many different substeps of Thistlethwaite's algorithm
-(DR/HTR), and can use NISS (Normal-Inverse Scramble Switch).
-It can be useful to analyze your DR solves (and more, once I implement more features).
-
-You can get Nissy from [nissy.tronto.net](https://nissy.tronto.net).
-The download links and installation instructions can be found on the
-[download page](https://nissy.tronto.net/download).
-
-## Structure of the code
-
-You can find all the source code in the `src` folder.
-I strived to keep it legible but I did not write many comments (barely any at all).
-I'll try to explain here the main parts of the program.
-
-### Cube, moves and transformations
-
-There are many ways to represent a cube. In Nissy I use two:
-
-* An array representation `CubeArray`: 3 arrays representing the permutation
-of corners, edges and centers and 2 arrays for the orientation of corners and edges.
-* An 11-integers representation `Cube`: 3 integers for edge orientation (with respect
-to the three axes), 3 for corner orientation, and so on. Edge permutation is a bit
-complicated because encoding 12 factorial as a single number is too large for some
-practical reasons, so I use 3 integers for that.
-
-Moves are easy to apply on the array form, but they are slow. So `moves.c`
-contains the instructions to create all the transition tables necessary
-to get the next position for the cube with just 11 lookup operations
-(one for each of the 11 integers in the second representation).
-These transition tables are saved in the `mtables` file in the
-`tables` folder in binary format.
-
-The 11 integers are obviously redundant, but keeping all of them makes it easy
-to apply transformations. A transformation is a rotation of the whole cube, possibly
-combined with a mirror operation. Applying a transformation to a cube (say obtained
-by applying a scramble to the solved cube) means applying the transformation to a
-solved cube, then the scramble and then the inverse of the transformation
-(i.e. conjugating by it).
-
-### Coordinates and pruning tables
-
-A *coordinate* consists of a function that takes a cube (in the 11-integer
-representation) and return an (unsigned, 64-bit) integer. They are used
-to "linearize" a cube and build pruning tables, which speed up significantly the
-solving process. To be able to access the pruning table quickly, the function
-needs to be very fast (e.g. it should not convert between the two representations
-of the cube if not necessary).
-
-Some coordinates make use of symmetries to reduce the size of the resulting
-pruning table. Unfortunately this complicates the code a lot, but it is a huge
-advantage: it reduces by a factor of about 16 the pruning table size.
-
-Pruning tables are related to a specific step, a moveset and a coordinate. They
-contain one value from 0 to 15 (4 bits) for each possible value for the coordinate,
-which is less or equal than the minimum number of moves required to solve the
-given step with the given moveset for a cube which has the given coordinate. For example,
-say the coordinate `neo` gives the number of non-oriented edges (say with respect to
-F/B). Then the possible values for the coordinate are 0,2,4,...,12. An associated
-pruning table to solving EO with HTM moveset and this coordinate would have values 0
-(for `neo=0`), 3 (for `neo=2`), 1 (for `neo=4`)...
-
-The values for most pruning tables are memorized modulo 16, so they only occupy
-4 bits per entry, and values larger than 15 are saved as 15. This is good enough
-for most applications.
-Some large tables are memorized in compact form using only 2 bits, similarly
-to what [nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md) does:
-a base value `b` is picked and a value of `n` is saved as `MIN(3,MAX(0,n-b))`.
-When a value of `v=1,2,3` is read it is simply returned as `v+b`, while if
-`0` is a successive lookup to a fallback table is performed. The base value `b`
-is picked to maximize the sum frequency of the values `1,2,3`.
-
-In order to generate the pruning tables, it is necessary to be able to move
-a transform a coordinate; it is possible to do so without passing through a
-complete cube representations, in a way similar to what Cube Explorer does.
-This used to be different before version 2.1 (June 2022).
-
-More documentation on this and on the different types of coordinates (base
-vs composed) is work in progress.
-
-### Solving
-
-Solving is implemented as a generic function that takes both a step and
-a (scrambled) cube as input, as well as some extra parameters that say e.g.
-how many solution one wants. A step consists, among other things, of
-an estimator function that, given a cube, gives a lower bound for the number
-of moves needed to complete the step. Many of these estimators simply
-look up the corresponding values in the appropriate pruning table.
+Work in progress, need to clean up and fix.
+This is an optimal solver only, for other versions see
+[nissy](https://git.tronto.net/nissy).
diff --git a/TODO/2.1.md b/TODO/2.1.md
@@ -4,10 +4,10 @@
### 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?
+* Check current optimal implementation (implement command, this is not step)
+* Save old pruning values in cubedata
+* Implement branch switching
+* Get rid of useless allocations, pass empty pointer and copy there
### 2. Rework achitecture and file dependencies
@@ -21,7 +21,7 @@ data from abstract operations.
in solver (called by solve()) to free cube and perhaps pruning tables.
* see various TODO's in files
-### 4. More threading options
+### 3. More threading options
* Lazy multithread: threads are as independent as possible and only
merged at the end. Ideal when all solutions of a certain length are requested.
@@ -33,6 +33,10 @@ solution of a certain depth is required.
* Remove one type of rotation.
* Change steps to choicestep and stepalt to step (or was this already done?).
+* Maybe: split optimal solver to a completely different module. This allows
+ for good semplification on the main generic solver (e.g. get rid of
+ move_check_stop). To be evaluated in terms of performance gain and actual
+ simplification (might not be much for either).
## Add missing coordinates and steps
diff --git a/TODO/refactoring.md b/TODO/refactoring.md
@@ -20,9 +20,22 @@
## 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.
+* Use goto for error handling (if needed)
+* Headers: blank line between <> and "" includes
+* Remove variable names from prototypes (debatable).
+* Stop declaring all variables at the beginning of a function (debatable).
* Rename functions and variable to have a consistent naming scheme.
+* Sort functions: prototypes in logical blocks, then alphabetic.
+ Implementations in the same order as the prototypes.
+* Order of variable declarations (in files, functions and structs):
+ Size first (large to small), then alphabetic.
+* Indent: make second level indent consistent to 4 spaces.
+ Try to avoid long statements.
+* Avoid include statements in .h files, use ifdef guards in .c files
+ (to reconsider as part of the redesign).
* Functions that copy data: swap src and dest, follow memcpy standard.
-* Read style(9) and decide what to implement.
+
+## Generic
+
+* Avoid malloc and free/new function pointers for cube objects,
+ use array of char on stack.
diff --git a/src/commands.c b/src/commands.c
@@ -221,14 +221,20 @@ solve_exec(CommandArgs *args)
make_solved(&c);
apply_alg(args->scramble, &c);
/* TODO: adjust */
-/* threader = &threader_single;*/
- threader = &threader_eager;
+ threader = &threader_single;
+/* threader = &threader_eager;*/
/* TODO: adjust */
+/* This was to solve steps
int i;
for (i = 0; args->cs->step[i] != NULL; i++)
solver[i] = new_stepsolver_lazy(args->cs->step[i]);
solver[i] = NULL;
+*/
+
+ prepare_solver_nxopt31();
+ solver[0] = &solver_nxopt31;
+ solver[1] = NULL;
sols = solve(&c, args->opts, solver, threader);
if (args->opts->count_only)
diff --git a/src/commands.h b/src/commands.h
@@ -6,6 +6,7 @@
#include "solve.h"
#include "steps.h"
#include "solver_step.h"
+#include "solver_nxopt31.h"
#include "threader_single.h"
#include "threader_eager.h"
diff --git a/src/fst.c b/src/fst.c
@@ -151,6 +151,15 @@ fst_inverse(FstCube fst)
return ret;
}
+bool
+fst_is_solved(FstCube fst)
+{
+ /* We only check one orientation */
+
+ return fst.uf_eofb == 0 && fst.uf_eposepe == 0 &&
+ fst.uf_coud == 0 && fst.uf_cp == 0;
+}
+
FstCube
fst_move(Move m, FstCube fst)
{
diff --git a/src/fst.h b/src/fst.h
@@ -5,6 +5,7 @@
FstCube cube_to_fst(Cube *cube);
FstCube fst_inverse(FstCube fst);
+bool fst_is_solved(FstCube fst);
FstCube fst_move(Move m, FstCube fst);
void fst_to_cube(FstCube fst, Cube *cube);
void init_fst();
diff --git a/src/solve.c b/src/solve.c
@@ -20,7 +20,9 @@ validate to null */
/* TODO: we also have to check if cancel with NISS;
we can't because we have no access to the s->final field
this should be done by the step's validator? */
- sol = solver->validate_solution(solver->param,arg->current_alg);
+ sol = solver->validate_solution == NULL ?
+ arg->current_alg :
+ solver->validate_solution(solver->param, arg->current_alg);
bool accepted = sol != NULL;
bool too_short = arg->current_alg->len != arg->d;
diff --git a/src/solve.h b/src/solve.h
@@ -1,6 +1,10 @@
#ifndef SOLVE_H
#define SOLVE_H
+/* TODO: remove multiple solvers?
+ can just run solver multiple times and then merge the results
+*/
+
#include "moves.h"
#define MAX_SOLVERS 99
@@ -38,6 +42,7 @@ struct solver {
/* TODO: remove alloc? */
/* TODO: revisit apply_move, maybe apply_alg? or both? */
void * (*alloc_cubedata)(void *);
+ /* TODO: replace by knowing size and doing memcpy? */
void (*copy_cubedata)(void *, void *, void *);
void (*free_cubedata)(void *, void *);
void (*invert_cube)(void *, void *);
diff --git a/src/solver_nxopt31.c b/src/solver_nxopt31.c
@@ -0,0 +1,230 @@
+#include "solver_nxopt31.h"
+
+/* TODO: make generic for nxopt solvers */
+
+static void apply_move_fst(void *, void *, Move);
+static void * prepare_cube_fst(void *, Cube *);
+static bool move_check_stop_nxopt31(void *, DfsArg *, Threader *);
+static bool is_solved_fst(void *, void *);
+static void * alloc_cubedata_fst(void *);
+static void copy_cubedata_fst(void *, void *, void *);
+static void free_cubedata_fst(void *, void *);
+static void invert_cubedata_fst(void *, void *);
+static uint64_t index_nxopt31(uint16_t, uint16_t, uint16_t, uint16_t, Trans);
+static int update(PruneData*, uint16_t *, uint16_t *,
+ uint16_t *, uint16_t, Move, Trans);
+
+static uint16_t cpudsep_table[FACTORIAL8];
+
+Solver solver_nxopt31 = {
+ .moveset = &moveset_HTM,
+ .move_check_stop = move_check_stop_nxopt31,
+ .validate_solution = NULL,
+ .niss_makes_sense = NULL,
+ .param = NULL,
+ .alloc_cubedata = alloc_cubedata_fst,
+ .copy_cubedata = copy_cubedata_fst,
+ .free_cubedata = free_cubedata_fst,
+ .invert_cube = invert_cubedata_fst,
+ .is_solved = is_solved_fst,
+ .apply_move = apply_move_fst,
+ .prepare_cube = prepare_cube_fst,
+};
+
+/* TODO: this is a bit weird because of realloc,
+ but we want to refactor this in any case */
+static void
+apply_move_fst(void *param, void *cubedata, Move m)
+{
+ FstCube *fst = (FstCube *)cubedata;
+
+ FstCube *moved = malloc(sizeof(FstCube));
+ *moved = fst_move(m, *fst);
+
+ free(fst);
+ cubedata = moved;
+}
+
+static void
+init_cpudsep_table()
+{
+ static bool generated = false;
+ uint64_t i;
+ Cube c;
+
+ if (generated)
+ return;
+
+ gen_coord(&coord_coud_cpudsep);
+ for (i = 0; i < FACTORIAL8; i++) {
+ index_to_perm(i, 8, c.cp);
+ cpudsep_table[i] = index_coord(&coord_cpudsep, &c, NULL);
+ }
+
+ generated = true;
+}
+
+/* TODO: ugly */
+void
+prepare_solver_nxopt31()
+{
+ init_fst();
+ gen_coord(&coord_eposepe);
+ gen_coord(&coord_eofbepos_sym16);
+ gen_coord(&coord_coud);
+ gen_coord(&coord_cp);
+
+ /* TODO: prepare also table cp pruning and
+ internal table for cpudsep from cp */
+ /* TODO: also check if ptables are already generated? */
+
+ init_cpudsep_table();
+
+ PruneData *pd = malloc(sizeof(PruneData));
+ pd->moveset = &moveset_HTM;
+ init_moveset(&moveset_HTM);
+ pd->coord = &coord_nxopt31;
+ gen_coord(&coord_nxopt31);
+ pd->compact = true;
+ solver_nxopt31.param = genptable(pd, 4); /* TODO: threads */
+}
+
+static void *
+prepare_cube_fst(void *param, Cube *cube)
+{
+ FstCube *fst = malloc(sizeof(FstCube));
+
+ *fst = cube_to_fst(cube);
+
+ return fst;
+}
+
+static bool
+is_solved_fst(void *param, void *cubedata)
+{
+ return fst_is_solved(*(FstCube *)cubedata);
+}
+
+static void *
+alloc_cubedata_fst(void *param)
+{
+ return malloc(sizeof(FstCube));
+}
+
+static void
+copy_cubedata_fst(void *param, void *src, void *dst)
+{
+ memcpy(dst, src, sizeof(FstCube));
+}
+
+static void
+free_cubedata_fst(void *param, void *cubedata)
+{
+ free(cubedata);
+}
+
+/* TODO: again, weird reallocation */
+static void
+invert_cubedata_fst(void *param, void *cubedata)
+{
+ FstCube *inv = malloc(sizeof(FstCube));
+
+ *inv = fst_inverse(*(FstCube *)cubedata);
+ free(cubedata);
+
+ cubedata = inv;
+}
+
+static uint64_t
+index_nxopt31(uint16_t eofb, uint16_t eposepe, uint16_t coud, uint16_t cp, Trans t)
+{
+ uint64_t eofbepos = (eposepe / FACTORIAL4) * POW2TO11 + eofb;
+ uint64_t eofbepos_sym16 = coord_eofbepos_sym16.symclass[eofbepos];
+ Trans ttr = coord_eofbepos_sym16.transtorep[eofbepos];
+ if (t != uf)
+ cp = trans_coord(&coord_cp, t, cp);
+ uint64_t sep = cpudsep_table[cp];
+ uint64_t coud_cpudsep = coud * BINOM8ON4 + sep;
+ uint64_t cc = trans_coord(&coord_coud_cpudsep, ttr, coud_cpudsep);
+ uint64_t ind = eofbepos_sym16 * POW3TO7 * BINOM8ON4 + cc;
+
+ return ind;
+}
+
+static int
+update(PruneData *pd, uint16_t *eofb, uint16_t *eposepe,
+ uint16_t *coud, uint16_t cp, Move m, Trans t)
+{
+ uint64_t ind;
+
+/* TODO fix
+ *eofb = coord_eofb.mtable[m][*eofb];
+ *eposepe = coord_eposepe.mtable[m][*eposepe];
+ *coud = coord_coud.mtable[m][*coud];
+*/
+
+ ind = index_nxopt31(*eofb, *eposepe, *coud, cp, t);
+
+ return ptableval(pd, ind);
+}
+
+static bool
+move_check_stop_nxopt31(void *param, DfsArg *arg, Threader *threader)
+{
+/* TODO: implement nxopt trick, i.e. inverse probing + switching */
+/* this means making the cube data structure more complex,
+ because we need to memorize the values from last probing
+ not hard, but it means we can't delegate everything to
+ a cube structure (unless we change FstCube to also include
+ tmhe probing values, but it does not make much sense) */
+
+ uint64_t ind;
+ PruneData *pd = (PruneData *)param;
+ FstCube *fst = (FstCube *)arg->cubedata;
+
+ int l = arg->current_alg->len;
+ int target = arg->d - l;
+
+ Move m = l > 0 ? arg->current_alg->move[l-1] : NULLMOVE;
+ /*fst->uf_cp = coord_cp.mtable[m][fst->uf_cp];*/
+ fst_move(m, *fst);
+
+ int nuf = update(pd, &fst->uf_eofb, &fst->uf_eposepe, &fst->uf_coud,
+ fst->uf_cp, m, uf);
+ if (nuf > target)
+ return true;
+ int nfr = update(pd, &fst->fr_eofb, &fst->fr_eposepe, &fst->fr_coud,
+ fst->uf_cp, m, fr);
+ if (nfr > target)
+ return true;
+ int nrd = update(pd, &fst->rd_eofb, &fst->rd_eposepe, &fst->rd_coud,
+ fst->uf_cp, m, rd);
+ if (nrd > target)
+ return true;
+
+ if (nuf == nfr && nuf == nrd && nuf == target)
+ return true;
+
+ FstCube inv = fst_inverse(*fst);
+
+ ind = index_nxopt31(inv.uf_eofb, inv.uf_eposepe, inv.uf_coud, inv.uf_cp, uf);
+ int iuf = ptableval(pd, ind);
+ if (iuf > target)
+ return true;
+ ind = index_nxopt31(inv.fr_eofb, inv.fr_eposepe, inv.fr_coud, inv.uf_cp, fr);
+ int ifr = ptableval(pd, ind);
+ if (ifr > target)
+ return true;
+ ind = index_nxopt31(inv.rd_eofb, inv.rd_eposepe, inv.rd_coud, inv.uf_cp, rd);
+ int ird = ptableval(pd, ind);
+ if (ird > target)
+ return true;
+
+ if (iuf == ifr && iuf == ird && iuf == target)
+ return true;
+
+ fst->uf_cp = coord_cp.mtable[m][fst->uf_cp];
+
+/* TODO: check also pd_corners */
+ return false;
+}
diff --git a/src/solver_nxopt31.h b/src/solver_nxopt31.h
@@ -0,0 +1,13 @@
+#ifndef SOLVER_NXOPT31_H
+#define SOLVER_NXOPT31_H
+
+#include "fst.h"
+#include "pruning.h"
+#include "solve.h"
+#include "movesets.h"
+
+extern Solver solver_nxopt31;
+
+void prepare_solver_nxopt31();
+
+#endif
diff --git a/src/steps.h b/src/steps.h
@@ -212,10 +212,9 @@ drfbfin_drfb = {
/* TODO: htrfin_htr */
ChoiceStep *csteps[] = {
-/* TODO: re-implement optimal
+/* TODO: this is not a step anymore
&optimal_HTM,
*/
-
&eoany_HTM, &eofb_HTM, &eorl_HTM, &eoud_HTM,
&drany_HTM, &drud_HTM, &drrl_HTM, &drfb_HTM,
&dranyfin_DR, &drudfin_drud, &drrlfin_drrl, &drfbfin_drfb,
