commit 2f924f942bd6e7126e8f1d8692e475c95bd9fe82
parent 4e2b4e603c7e84c7556f489d7d8dab06915b3a9b
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Thu, 16 Dec 2021 19:25:58 +0100
Added a new pruning table (equivalent to nxopt31). I have not tested it yet, it takes a while to generate.
Plus I have done a whole lot of refactoring in random places because I cannot focus on
one thing at the time.
Diffstat:
16 files changed, 555 insertions(+), 332 deletions(-)
diff --git a/TODO.md b/TODO.md
@@ -14,13 +14,11 @@ It's more of a personal reminder than anything else.
* invert an alg
### More steps for `solve`
-* QTM optimal solving
+* QTM optimal solving (important: fix possible_next, which works only for HTM now)
* Block-building steps (cross, roux blocks, ...)
* Other common steps (LSE, ...)
### Improvements to currently implemented commands
-* batch mode: add separator / info on which command it is executing
-(also change man page for this)
* solve should re-orient first if needed and not just give up if centers are off
* solve should try up to a small bound without loading the large pruning table
* drfin for HTR scrambles should try all 3 axis and pick the best solutions;
@@ -42,7 +40,12 @@ It's more of a personal reminder than anything else.
## Technical stuff
-## Performance
+### Memory management
+* Check if memory is enough for loading pruning tables; if not, abort
+* For optimal solver: choose largest that fits in memory between
+ khuge, shug6 and light
+
+### Performance
* solve (allow_next): filter out based on base_move; only check once for each
triple of moves; how to deal with different movesets?
* try htr corners + edges in slice but not oriented (300Mb table);
@@ -51,12 +54,8 @@ It's more of a personal reminder than anything else.
(like in light optimal solver)
* Another idea: DR + cornershtr (5Gb table); same as above, de Bondt's trick
does not work but I can use half-turn trick
-* On the contrary: DR + separate UD corners allow dB's trick, but no ht-trick
-## Coordinates, symmetries, pruning tables
-* Cleanup symcoord.c: some coordinates and symdata are never actually used;
-remove also sd_eofbepos and just use sd_coud for khuge (this changes the
-coordinate so the whole table must be generated again!) or viceversa
+### Coordinates, symmetries, pruning tables
* Use pruning values mod 4 instead of mod 16 (or maybe not, I like the
current system)
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/src/alg.c b/src/alg.c
@@ -2,27 +2,76 @@
/* Local functions ***********************************************************/
+static bool allowed_HTM(Move m);
+static bool allowed_URF(Move m);
+static bool allowed_eofb(Move m);
+static bool allowed_drud(Move m);
+static bool allowed_htr(Move m);
+static bool allowed_next_HTM(Move l2, Move l1, Move m);
+static int axis(Move m);
+
static void free_alglistnode(AlgListNode *aln);
static void realloc_alg(Alg *alg, int n);
/* Movesets ******************************************************************/
-bool
-moveset_HTM(Move m)
+Moveset
+moveset_HTM = {
+ .allowed = allowed_HTM,
+ .allowed_next = allowed_next_HTM,
+};
+
+Moveset
+moveset_URF = {
+ .allowed = allowed_URF,
+ .allowed_next = allowed_next_HTM,
+};
+
+Moveset
+moveset_eofb = {
+ .allowed = allowed_eofb,
+ .allowed_next = allowed_next_HTM,
+};
+
+Moveset
+moveset_drud = {
+ .allowed = allowed_drud,
+ .allowed_next = allowed_next_HTM,
+};
+
+Moveset
+moveset_htr = {
+ .allowed = allowed_htr,
+ .allowed_next = allowed_next_HTM,
+};
+
+static int nmoveset = 5;
+static Moveset * all_ms[] = {
+ &moveset_HTM,
+ &moveset_URF,
+ &moveset_eofb,
+ &moveset_drud,
+ &moveset_htr,
+};
+
+/* Functions *****************************************************************/
+
+static bool
+allowed_HTM(Move m)
{
return m >= U && m <= B3;
}
-bool
-moveset_URF(Move m)
+static bool
+allowed_URF(Move m)
{
Move b = base_move(m);
return b == U || b == R || b == F;
}
-bool
-moveset_eofb(Move m)
+static bool
+allowed_eofb(Move m)
{
Move b = base_move(m);
@@ -30,8 +79,8 @@ moveset_eofb(Move m)
((b == F || b == B) && m == b+1);
}
-bool
-moveset_drud(Move m)
+static bool
+allowed_drud(Move m)
{
Move b = base_move(m);
@@ -39,16 +88,65 @@ moveset_drud(Move m)
((b == R || b == L || b == F || b == B) && m == b + 1);
}
-bool
-moveset_htr(Move m)
+static bool
+allowed_htr(Move m)
{
Move b = base_move(m);
- return moveset_HTM(m) && m == b + 1;
+ return moveset_HTM.allowed(m) && m == b + 1;
}
+static bool
+allowed_next_HTM(Move l2, Move l1, Move m)
+{
+ bool p, q;
-/* Functions *****************************************************************/
+ p = l1 != NULLMOVE && base_move(l1) == base_move(m);
+ q = l2 != NULLMOVE && base_move(l2) == base_move(m);
+
+ return !(p || (commute(l1, l2) && q));
+}
+
+static int
+axis(Move m)
+{
+ Move i;
+
+ static bool initialized = false;
+ static int aux[NMOVES];
+
+ if (!initialized) {
+ for (i = 0; i < NMOVES; i++) {
+ if (i == NULLMOVE)
+ aux[i] = 0;
+
+ if (i >= U && i <= B3)
+ aux[i] = (i-1)/6 + 1;
+
+ if (i >= Uw && i <= Bw3)
+ aux[i] = (i-1)/6 - 2;
+
+ if (base_move(i) == E || base_move(i) == y)
+ aux[i] = 1;
+
+ if (base_move(i) == M || base_move(i) == x)
+ aux[i] = 2;
+
+ if (base_move(i) == S || base_move(i) == z)
+ aux[i] = 3;
+ }
+
+ initialized = true;
+ }
+
+ return aux[m];
+}
+
+bool
+commute(Move m1, Move m2)
+{
+ return axis(m1) == axis(m2);
+}
void
append_alg(AlgList *l, Alg *alg)
@@ -171,33 +269,6 @@ move_string(Move m)
return move_string_aux[m];
}
-void
-movelist_to_position(Move *movelist, int *position)
-{
- Move m;
-
- for (m = 0; m < NMOVES && movelist[m] != NULLMOVE; m++)
- position[movelist[m]] = m;
-}
-
-void
-moveset_to_list(Moveset ms, Move *r)
-{
- int n = 0;
- Move i;
-
- if (ms == NULL) {
- fprintf(stderr, "Error: no moveset given\n");
- return;
- }
-
- for (i = U; i < NMOVES; i++)
- if (ms(i))
- r[n++] = i;
-
- r[n] = NULLMOVE;
-}
-
Alg *
new_alg(char *str)
{
@@ -405,3 +476,34 @@ unniss(Alg *alg)
}
free(aux);
}
+
+void
+init_movesets()
+{
+ int i, j;
+ uint64_t l, one;
+ Move m, l2, l1;
+ Moveset *ms;
+
+ one = 1;
+
+ for (i = 0; i < nmoveset; i++) {
+ ms = all_ms[i];
+
+ for (j = 0, m = U; m < NMOVES; m++)
+ if (ms->allowed(m))
+ ms->sorted_moves[j++] = m;
+ ms->sorted_moves[j] = NULLMOVE;
+
+ for (l1 = 0; l1 < NMOVES; l1++) {
+ for (l2 = 0; l2 < NMOVES; l2++) {
+ ms->mask[l2][l1] = 0;
+ for (l=0; ms->sorted_moves[l]!=NULLMOVE; l++) {
+ m = ms->sorted_moves[l];
+ if (ms->allowed_next(l2, l1, m))
+ ms->mask[l2][l1] |= (one<<m);
+ }
+ }
+ }
+ }
+}
diff --git a/src/alg.h b/src/alg.h
@@ -8,16 +8,17 @@
#include "cubetypes.h"
#include "utils.h"
-bool moveset_HTM(Move m);
-bool moveset_URF(Move m);
-bool moveset_eofb(Move m);
-bool moveset_drud(Move m);
-bool moveset_htr(Move m);
+extern Moveset moveset_HTM;
+extern Moveset moveset_URF;
+extern Moveset moveset_eofb;
+extern Moveset moveset_drud;
+extern Moveset moveset_htr;
void append_alg(AlgList *l, Alg *alg);
void append_move(Alg *alg, Move m, bool inverse);
-void compose_alg(Alg *alg1, Alg *alg2);
Move base_move(Move m);
+void compose_alg(Alg *alg1, Alg *alg2);
+bool commute(Move m1, Move m2);
void free_alg(Alg *alg);
void free_alglist(AlgList *l);
Alg * inverse_alg(Alg *alg);
@@ -33,5 +34,7 @@ void print_alglist(AlgList *al, bool l);
void swapmove(Move *m1, Move *m2);
void unniss(Alg *alg);
+void init_movesets();
+
#endif
diff --git a/src/commands.c b/src/commands.c
@@ -259,6 +259,7 @@ solve_exec(CommandArgs *args)
Cube c;
AlgList *sols;
+ init_movesets();
init_symcoord();
c = apply_alg(args->scramble, (Cube){0});
@@ -274,6 +275,7 @@ gen_exec(CommandArgs *args)
int i;
fprintf(stderr, "Generating coordinates...\n");
+ init_movesets();
init_symcoord();
fprintf(stderr, "Generating pruning tables...\n");
diff --git a/src/coord.c b/src/coord.c
@@ -13,6 +13,7 @@ static Cube antindex_drud(uint64_t ind);
static Cube antindex_drud_eofb(uint64_t ind);
static Cube antindex_htr_drud(uint64_t ind);
static Cube antindex_htrfin(uint64_t ind);
+static Cube antindex_cpud_separate(uint64_t ind);
static uint64_t index_eofb(Cube cube);
static uint64_t index_eofbepos(Cube cube);
@@ -27,6 +28,7 @@ static uint64_t index_drud(Cube cube);
static uint64_t index_drud_eofb(Cube cube);
static uint64_t index_htr_drud(Cube cube);
static uint64_t index_htrfin(Cube cube);
+static uint64_t index_cpud_separate(Cube cube);
static void init_cphtr_cosets();
static void init_cphtr_left_cosets_bfs(int i, int c);
@@ -135,6 +137,13 @@ coord_drud_eofb = {
.max = POW3TO7 * BINOM12ON4,
};
+Coordinate
+coord_cpud_separate = {
+ .index = index_cpud_separate,
+ .cube = antindex_cpud_separate,
+ .max = BINOM8ON4,
+};
+
/* Antindexers ***************************************************************/
static Cube
@@ -356,6 +365,31 @@ antindex_htrfin(uint64_t ind)
return ret;
}
+static Cube
+antindex_cpud_separate(uint64_t ind)
+{
+ /* Not consistent because of side corner orientations and cp */
+ unsigned int ui;
+ int i, co[8], cp[8];
+ Corner u, d;
+
+ static Cube aux[BINOM8ON4];
+ static bool initialized = false;
+
+ if (!initialized) {
+ for (ui = 0; ui < BINOM8ON4; ui++) {
+ index_to_subset(ui, 8, 4, co);
+ for (i = 0, u = UFR, d = DFR; i < 8; i++)
+ cp[i] = co[i] ? d++ : u++;
+ aux[ui] = (Cube){.cp = perm_to_index(cp, 8)};
+ }
+
+ initialized = true;
+ }
+
+ return aux[ind];
+}
+
/* Indexers ******************************************************************/
static uint64_t
@@ -477,6 +511,29 @@ index_htrfin(Cube cube)
return cp * 24 * 24 * 24 + ep;
}
+static uint64_t
+index_cpud_separate(Cube cube)
+{
+ unsigned int ui;
+ int i, co[8];
+
+ static int aux[FACTORIAL8];
+ static bool initialized = false;
+
+ if (!initialized) {
+ for (ui = 0; ui < FACTORIAL8; ui++) {
+ for (i = 0; i < 8; i++)
+ co[i] = what_corner_at((Cube){.cp=ui},i)>UBR ?
+ 1 : 0;
+ aux[ui] = subset_to_index(co, 8, 4);
+ }
+
+ initialized = true;
+ }
+
+ return aux[cube.cp];
+}
+
/* Init functions implementation *********************************************/
/*
@@ -528,7 +585,7 @@ init_cphtr_left_cosets_bfs(int i, int c)
while (n != 0) {
for (j = 0, n2 = 0; j < n; j++) {
for (k = U2; k < B3; k++) {
- if (!moveset_htr(k))
+ if (!moveset_htr.allowed(k))
continue;
jj = apply_move(k, (Cube){ .cp = next[j] }).cp;
@@ -578,7 +635,7 @@ init_cornershtrfin()
if (cornershtrfin_ind[j] == -1)
continue;
for (m = U; m < NMOVES; m++) {
- if (moveset_htr(m)) {
+ if (moveset_htr.allowed(m)) {
c = apply_move(m, (Cube){.cp = j}).cp;
if (cornershtrfin_ind[c] == -1) {
cornershtrfin_ind[c] = n;
@@ -592,6 +649,31 @@ init_cornershtrfin()
}
void
+test_coord(Coordinate *coord)
+{
+ bool passed;
+ uint64_t ui, failcount;
+
+ if (!(passed = (coord->index((Cube){0}) == 0))) {
+ printf("Failed: coordinate of solved cube is "
+ "%" PRIu64 "\n", coord->index((Cube){0}));
+ }
+
+ printf("Testing %" PRIu64 " coordinates\n", coord->max);
+ for (failcount = 0, ui = 0; ui < coord->max; ui++) {
+ if (!(passed = (coord->index(coord->cube(ui)) == ui))) {
+ printf("Failed at %" PRIu64 "\n", ui);
+ failcount++;
+ }
+ }
+
+ if (passed)
+ printf("Ok\n");
+ else
+ printf("Test failed in %" PRIu64 " cases\n", failcount);
+}
+
+void
init_coord()
{
static bool initialized = false;
diff --git a/src/coord.h b/src/coord.h
@@ -16,7 +16,9 @@ extern Coordinate coord_drud;
extern Coordinate coord_drud_eofb;
extern Coordinate coord_htr_drud;
extern Coordinate coord_htrfin;
+extern Coordinate coord_cpud_separate;
+void test_coord(Coordinate *coord);
void init_coord();
#endif
diff --git a/src/cubetypes.h b/src/cubetypes.h
@@ -8,6 +8,7 @@
#define NMOVES 55 /* Actually 54, but one is NULLMOVE */
#define NTRANS 48
#define NROTATIONS 24
+#define entry_group_t uint8_t /* For pruning tables */
/* Enums *********************************************************************/
@@ -83,6 +84,7 @@ typedef struct cube Cube;
typedef struct cubearray CubeArray;
typedef struct dfsarg DfsArg;
typedef struct estimatedata EstimateData;
+typedef struct moveset Moveset;
typedef struct piecefilter PieceFilter;
typedef struct prunedata PruneData;
typedef struct solveoptions SolveOptions;
@@ -97,7 +99,6 @@ typedef int (*Estimator) (DfsArg *);
typedef bool (*Validator) (Alg *);
typedef void (*Exec) (CommandArgs *);
typedef uint64_t (*Indexer) (Cube);
-typedef bool (*Moveset) (Move);
typedef CommandArgs * (*ArgParser) (int, char **);
typedef Trans (*TransDetector) (Cube);
typedef int (*TransFinder) (uint64_t, Trans *);
@@ -215,8 +216,6 @@ dfsarg
AlgList * sols;
pthread_mutex_t * sols_mutex;
Alg * current_alg;
- Move * sorted_moves;
- int * move_position;
};
struct
@@ -233,6 +232,15 @@ estimatedata
};
struct
+moveset
+{
+ bool (*allowed)(Move);
+ bool (*allowed_next)(Move, Move, Move);
+ Move sorted_moves[NMOVES+1];
+ uint64_t mask[NMOVES][NMOVES];
+};
+
+struct
piecefilter
{
bool epose;
@@ -252,11 +260,11 @@ struct
prunedata
{
char * filename;
- uint8_t * ptable;
+ entry_group_t * ptable;
bool generated;
uint64_t n;
Coordinate * coord;
- Moveset moveset;
+ Moveset * moveset;
};
struct
@@ -284,7 +292,7 @@ step
Checker ready;
char * ready_msg;
Validator is_valid;
- Moveset moveset;
+ Moveset * moveset;
Trans pre_trans;
TransDetector detect;
int ntables;
@@ -312,8 +320,6 @@ threaddatasolve
Cube cube;
Step * step;
int depth;
- Move * sorted_moves;
- int * move_position;
SolveOptions * opts;
AlgList * start;
AlgListNode ** node;
@@ -329,7 +335,6 @@ threaddatagenpt
int nthreads;
PruneData * pd;
int d;
- Move * ms;
int nchunks;
pthread_mutex_t ** mutex;
pthread_mutex_t * upmutex;
diff --git a/src/moves.c b/src/moves.c
@@ -319,57 +319,6 @@ write_mtables_file()
return r;
}
-bool
-commute(Move m1, Move m2)
-{
- static bool initialized = false;
- static bool commute_aux[NMOVES][NMOVES];
-
- if (!initialized) {
- Cube c1, c2;
- int i, j;
-
- for (i = 0; i < NMOVES; i++) {
- for (j = 0; j < NMOVES; j++) {
- c1 = apply_move(i, apply_move(j, (Cube){0}));
- c2 = apply_move(j, apply_move(i, (Cube){0}));
- commute_aux[i][j] = equal(c1, c2) && i && j;
- }
- }
-
- initialized = true;
- }
-
- return commute_aux[m1][m2];
-}
-
-bool
-possible_next(Move m1, Move m2, Move m3)
-{
- static bool initialized = false;
- static bool paux[NMOVES][NMOVES][NMOVES];
-
- if (!initialized) {
- int i, j, k;
- bool p, q, c;
-
- for (i = 0; i < NMOVES; i++) {
- for (j = 0; j < NMOVES; j++) {
- for (k = 0; k < NMOVES; k++) {
- p = j && base_move(j) == base_move(k);
- q = i && base_move(i) == base_move(k);
- c = commute(i, j);
- paux[i][j][k] = !(p || (c && q));
- }
- }
- }
-
- initialized = true;
- }
-
- return paux[m1][m2][m3];
-}
-
void
init_moves() {
static bool initialized = false;
diff --git a/src/moves.h b/src/moves.h
@@ -8,8 +8,6 @@
Cube apply_alg(Alg *alg, Cube cube);
Cube apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a);
Cube apply_move(Move m, Cube cube);
-bool commute(Move m1, Move m2);
-bool possible_next(Move m1, Move m2, Move m3);
void init_moves();
diff --git a/src/pruning.c b/src/pruning.c
@@ -1,11 +1,10 @@
#include "pruning.h"
-/* Chunks for multithreading */
-/* TODO: try smaller */
-#define NCHUNKS 100000
+#define NCHUNKS 100000
+#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t))
static int findchunk(PruneData *pd, int nchunks, uint64_t i);
-static void genptable_bfs(PruneData *pd,int d,Move *ms,int nt,int nc);
+static void genptable_bfs(PruneData *pd, int d, int nt, int nc);
static void genptable_fixnasty(PruneData *pd, int d);
static void * instance_bfs(void *arg);
static void ptable_update(PruneData *pd, Cube cube, int m);
@@ -18,70 +17,77 @@ PruneData
pd_eofb_HTM = {
.filename = "pt_eofb_HTM",
.coord = &coord_eofb,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
};
PruneData
pd_coud_HTM = {
.filename = "pt_coud_HTM",
.coord = &coord_coud,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
};
PruneData
pd_cornershtr_HTM = {
.filename = "pt_cornershtr_HTM",
.coord = &coord_cornershtr,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
};
PruneData
pd_corners_HTM = {
.filename = "pt_corners_HTM",
.coord = &coord_corners,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
};
PruneData
pd_drud_sym16_HTM = {
.filename = "pt_drud_sym16_HTM",
.coord = &coord_drud_sym16,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
};
PruneData
pd_drud_eofb = {
.filename = "pt_drud_eofb",
.coord = &coord_drud_eofb,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
};
PruneData
pd_drudfin_noE_sym16_drud = {
.filename = "pt_drudfin_noE_sym16_drud",
.coord = &coord_drudfin_noE_sym16,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
};
PruneData
pd_htr_drud = {
.filename = "pt_htr_drud",
.coord = &coord_htr_drud,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
};
PruneData
pd_htrfin_htr = {
.filename = "pt_htrfin_htr",
.coord = &coord_htrfin,
- .moveset = moveset_htr,
+ .moveset = &moveset_htr,
};
PruneData
pd_khuge_HTM = {
.filename = "pt_khuge_HTM",
.coord = &coord_khuge,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
+};
+
+PruneData
+pd_nxopt31_HTM = {
+ .filename = "pt_nxopt31_HTM",
+ .coord = &coord_nxopt31,
+ .moveset = &moveset_HTM,
};
PruneData * allpd[NPTABLES] = {
@@ -95,6 +101,7 @@ PruneData * allpd[NPTABLES] = {
&pd_htr_drud,
&pd_htrfin_htr,
&pd_khuge_HTM,
+ &pd_nxopt31_HTM,
};
/* Functions *****************************************************************/
@@ -105,8 +112,7 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
uint64_t chunksize;
chunksize = pd->coord->max / (uint64_t)nchunks;
- if (chunksize % 2 != 0)
- chunksize++;
+ chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP);
return MIN(nchunks-1, (int)(i / chunksize));
}
@@ -114,15 +120,14 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
void
genptable(PruneData *pd, int nthreads)
{
- Move *ms;
int d, nchunks;
- uint64_t j, oldn;
+ uint64_t oldn;
if (pd->generated)
return;
/* TODO: check if memory is enough, otherwise maybe exit gracefully? */
- pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
+ pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
if (read_ptable_file(pd)) {
pd->generated = true;
@@ -130,17 +135,12 @@ genptable(PruneData *pd, int nthreads)
}
pd->generated = true;
- nchunks = MIN(pd->coord->max/2, NCHUNKS);
+ nchunks = MIN(pd->coord->max/ENTRIES_PER_GROUP, NCHUNKS);
fprintf(stderr, "Cannot load %s, generating it "
"with %d threads and %d chunks\n",
pd->filename, nthreads, nchunks);
- ms = malloc(NMOVES * sizeof(Move));
- moveset_to_list(pd->moveset, ms);
-
- /* We use 4 bits per value, so any distance >= 15 is set to 15 */
- for (j = 0; j < pd->coord->max; j++)
- ptable_update_index(pd, j, 15);
+ memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t));
ptable_update(pd, (Cube){0}, 0);
pd->n = 1;
@@ -151,7 +151,7 @@ genptable(PruneData *pd, int nthreads)
0, pd->n - oldn, pd->n, pd->coord->max);
oldn = pd->n;
for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
- genptable_bfs(pd, d, ms, nthreads, nchunks);
+ genptable_bfs(pd, d, nthreads, nchunks);
genptable_fixnasty(pd, d+1);
fprintf(stderr, "Depth %d done, generated %"
PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
@@ -162,12 +162,10 @@ genptable(PruneData *pd, int nthreads)
if (!write_ptable_file(pd))
fprintf(stderr, "Error writing ptable file\n");
-
- free(ms);
}
static void
-genptable_bfs(PruneData *pd, int d, Move *ms, int nthreads, int nchunks)
+genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks)
{
int i;
pthread_t t[nthreads];
@@ -186,7 +184,6 @@ genptable_bfs(PruneData *pd, int d, Move *ms, int nthreads, int nchunks)
td[i].nthreads = nthreads;
td[i].pd = pd;
td[i].d = d;
- td[i].ms = ms;
td[i].nchunks = nchunks;
td[i].mutex = mtx;
td[i].upmutex = upmtx;
@@ -237,8 +234,10 @@ instance_bfs(void *arg)
uint64_t i, ii, blocksize, rmin, rmax, updated;
int j, pval, ichunk;
Cube c, cc;
+ Move *ms;
td = (ThreadDataGenpt *)arg;
+ ms = td->pd->moveset->sorted_moves;
blocksize = td->pd->coord->max / (uint64_t)td->nthreads;
rmin = ((uint64_t)td->thid) * blocksize;
rmax = td->thid == td->nthreads - 1 ?
@@ -253,8 +252,8 @@ instance_bfs(void *arg)
pthread_mutex_unlock(td->mutex[ichunk]);
if (pval == td->d) {
c = td->pd->coord->cube(i);
- for (j = 0; td->ms[j] != NULLMOVE; j++) {
- cc = apply_move(td->ms[j], c);
+ for (j = 0; ms[j] != NULLMOVE; j++) {
+ cc = apply_move(ms[j], c);
ii = td->pd->coord->index(cc);
ichunk = findchunk(td->pd, td->nchunks, ii);
pthread_mutex_lock(td->mutex[ichunk]);
@@ -296,7 +295,7 @@ print_ptable(PruneData *pd)
uint64_t
ptablesize(PruneData *pd)
{
- return (pd->coord->max + 1) / 2;
+ return (pd->coord->max + ENTRIES_PER_GROUP - 1) / ENTRIES_PER_GROUP;
}
static void
@@ -308,14 +307,16 @@ ptable_update(PruneData *pd, Cube cube, int n)
static void
ptable_update_index(PruneData *pd, uint64_t ind, int n)
{
- uint8_t oldval2;
- int other;
+ int sh;
+ entry_group_t mask;
+ uint64_t i;
- oldval2 = pd->ptable[ind/2];
- other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
+ sh = 4 * (ind % ENTRIES_PER_GROUP);
+ mask = ((entry_group_t)15) << sh;
+ i = ind/ENTRIES_PER_GROUP;
- pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n;
- /*pd->n++;*/
+ pd->ptable[i] &= ~mask;
+ pd->ptable[i] |= (((entry_group_t)n)&15) << sh;
}
int
@@ -327,6 +328,10 @@ ptableval(PruneData *pd, Cube cube)
static int
ptableval_index(PruneData *pd, uint64_t ind)
{
+ int sh;
+ entry_group_t mask;
+ uint64_t i;
+
if (!pd->generated) {
fprintf(stderr, "Warning: request pruning table value"
" for uninitialized table %s.\n It's fine, but it"
@@ -335,7 +340,11 @@ ptableval_index(PruneData *pd, uint64_t ind)
genptable(pd, 1); /* TODO: set default or remove this case */
}
- return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16;
+ sh = 4 * (ind % ENTRIES_PER_GROUP);
+ mask = ((entry_group_t)15) << sh;
+ i = ind/ENTRIES_PER_GROUP;
+
+ return (pd->ptable[i] & mask) >> sh;
}
static bool
@@ -354,7 +363,7 @@ read_ptable_file(PruneData *pd)
if ((f = fopen(fname, "rb")) == NULL)
return false;
- r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
+ r = fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
fclose(f);
return r == ptablesize(pd);
@@ -376,7 +385,7 @@ write_ptable_file(PruneData *pd)
if ((f = fopen(fname, "wb")) == NULL)
return false;
- written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
+ written = fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
fclose(f);
return written == ptablesize(pd);
diff --git a/src/pruning.h b/src/pruning.h
@@ -15,6 +15,7 @@ extern PruneData pd_drudfin_noE_sym16_drud;
extern PruneData pd_htr_drud;
extern PruneData pd_htrfin_htr;
extern PruneData pd_khuge_HTM;
+extern PruneData pd_nxopt31_HTM;
extern PruneData * allpd[NPTABLES];
diff --git a/src/solve.c b/src/solve.c
@@ -8,7 +8,7 @@ static void copy_dfsarg(DfsArg *src, DfsArg *dst);
static void dfs(DfsArg *arg);
static void dfs_branch(DfsArg *arg);
static bool dfs_check_solved(DfsArg *arg);
-static bool dfs_switch_final(DfsArg *arg);
+static bool dfs_switch(DfsArg *arg);
static void dfs_niss(DfsArg *arg);
static bool dfs_stop(DfsArg *arg);
static void * instance_thread(void *arg);
@@ -21,25 +21,43 @@ static bool niss_makes_sense(DfsArg *arg);
static bool
allowed_next(Move m, DfsArg *arg)
{
- if ((1 << m) & arg->badmoves)
- return false;
+ bool bad, allowed, order;
+ uint64_t mbit;
- if (!possible_next(arg->last2, arg->last1, m))
- return false;
+ if (arg->last1 == NULLMOVE)
+ return true;
- if (commute(arg->last1, m))
- return arg->move_position[arg->last1] < arg->move_position[m];
+ mbit = ((uint64_t)1) << m;
+ bad = mbit & arg->badmoves;
+ allowed = mbit & arg->step->moveset->mask[arg->last2][arg->last1];
+ order = !commute(arg->last1, m) || arg->last1 < m;
- return true;
+ return allowed && !bad && order;
}
static bool
cancel_niss(DfsArg *arg)
{
- return !possible_next(arg->last2, arg->last1, arg->last1inv) &&
- !(commute(arg->last1inv, arg->last2inv) &&
- arg->last2inv != NULLMOVE &&
- possible_next(arg->last2, arg->last1, arg->last2inv));
+ Moveset *ms;
+ Move i1, i2;
+ bool p, p1, p2, q, q1, q2;
+
+ if (arg->last1inv == NULLMOVE)
+ return false;
+
+ ms = arg->step->moveset;
+ i1 = inverse_move(arg->last1inv);
+ i2 = inverse_move(arg->last2inv);
+
+ p1 = !ms->allowed_next(arg->last2, arg->last1, i1);
+ p2 = !ms->allowed_next(arg->last2, i1, arg->last1);
+ p = p1 || (commute(i1, arg->last1) && p2);
+
+ q1 = !ms->allowed_next(arg->last2, arg->last1, i2);
+ q2 = !ms->allowed_next(arg->last2, i2, arg->last1);
+ q = q1 || (commute(i2, arg->last1) && q2);
+
+ return p || (commute(i1, i2) && q);
}
static void
@@ -60,8 +78,6 @@ copy_dfsarg(DfsArg *src, DfsArg *dst)
dst->sols = src->sols;
dst->sols_mutex = src->sols_mutex;
dst->current_alg = src->current_alg;
- dst->sorted_moves = src->sorted_moves;
- dst->move_position = src->move_position;
copy_estimatedata(src->ed, dst->ed);
}
@@ -77,7 +93,7 @@ dfs(DfsArg *arg)
if (dfs_check_solved(arg))
return;
- if (arg->step->final && (sw = dfs_switch_final(arg)))
+ if (arg->step->final && (sw = dfs_switch(arg)))
invert_branch(arg);
dfs_branch(arg);
@@ -98,8 +114,8 @@ dfs_branch(DfsArg *arg)
newarg = malloc(sizeof(DfsArg));
newarg->ed = malloc(sizeof(EstimateData));
- for (i = 0; arg->sorted_moves[i] != NULLMOVE; i++) {
- m = arg->sorted_moves[i];
+ for (i = 0; arg->step->moveset->sorted_moves[i] != NULLMOVE; i++) {
+ m = arg->step->moveset->sorted_moves[i];
if (allowed_next(m, arg)) {
copy_dfsarg(arg, newarg);
newarg->last2 = arg->last1;
@@ -181,20 +197,22 @@ dfs_stop(DfsArg *arg)
}
static bool
-dfs_switch_final(DfsArg *arg)
+dfs_switch(DfsArg *arg)
{
int i, bn, bi;
- for (bn = 0, i = 0; arg->sorted_moves[i] != NULLMOVE; i++)
- if (allowed_next(arg->sorted_moves[i], arg))
+ bn = 0;
+ for (i = 0; arg->step->moveset->sorted_moves[i] != NULLMOVE; i++)
+ if (allowed_next(arg->step->moveset->sorted_moves[i], arg))
bn++;
swapmove(&(arg->last1), &(arg->last1inv));
swapmove(&(arg->last2), &(arg->last2inv));
swapu64(&(arg->badmoves), &(arg->badmovesinv));
- for (bi = 0, i = 0; arg->sorted_moves[i] != NULLMOVE; i++)
- if (allowed_next(arg->sorted_moves[i], arg))
+ bi = 0;
+ for (i = 0; arg->step->moveset->sorted_moves[i] != NULLMOVE; i++)
+ if (allowed_next(arg->step->moveset->sorted_moves[i], arg))
bi++;
swapmove(&(arg->last1), &(arg->last1inv));
@@ -246,8 +264,6 @@ instance_thread(void *arg)
darg.current_alg = new_alg("");
append_move(darg.current_alg, node->alg->move[0],
node->alg->inv[0]);
- darg.sorted_moves = td->sorted_moves;
- darg.move_position = td->move_position;
darg.ed = new_estimatedata();
darg.badmoves = 0;
darg.badmovesinv = 0;
@@ -281,8 +297,7 @@ invert_branch(DfsArg *arg)
static void
multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
{
- int i, *move_position;
- Move *sorted_moves;
+ int i;
Alg *alg;
AlgList *start;
AlgListNode **node;
@@ -290,8 +305,6 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
ThreadDataSolve td[opts->nthreads];
pthread_mutex_t *start_mutex, *sols_mutex;
- move_position = malloc(NMOVES * sizeof(int));
- sorted_moves = malloc(NMOVES * sizeof(Move));
node = malloc(sizeof(AlgListNode *));
start_mutex = malloc(sizeof(pthread_mutex_t));
sols_mutex = malloc(sizeof(pthread_mutex_t));
@@ -300,14 +313,11 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
pthread_mutex_init(start_mutex, NULL);
pthread_mutex_init(sols_mutex, NULL);
- moveset_to_list(s->moveset, sorted_moves);
- movelist_to_position(sorted_moves, move_position);
-
- for (i = 0; sorted_moves[i] != NULLMOVE; i++) {
+ for (i = 0; s->moveset->sorted_moves[i] != NULLMOVE; i++) {
alg = new_alg("");
/* TODO: start on inverse also in case of final step
and ed->sw true */
- append_move(alg, sorted_moves[i], false);
+ append_move(alg, s->moveset->sorted_moves[i], false);
append_alg(start, alg);
if (opts->can_niss) {
alg->inv[0] = true;
@@ -322,8 +332,6 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
td[i].cube = c;
td[i].step = s;
td[i].depth = d;
- td[i].sorted_moves = sorted_moves;
- td[i].move_position = move_position;
td[i].opts = opts;
td[i].start = start;
td[i].node = node;
@@ -340,8 +348,6 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
free(node);
free(start_mutex);
free(sols_mutex);
- free(move_position);
- free(sorted_moves);
}
static bool
diff --git a/src/steps.c b/src/steps.c
@@ -36,8 +36,11 @@ static int estimate_drudfin_drud(DfsArg *arg);
static int estimate_htr_drud(DfsArg *arg);
static int estimate_htrfin_htr(DfsArg *arg);
static int estimate_optimal_HTM(DfsArg *arg);
+static int estimate_nxopt31_HTM(DfsArg *arg);
static int estimate_light_HTM(DfsArg *arg);
+static int estimate_nxoptlike(DfsArg *arg, PruneData *pd);
+
static bool always_valid(Alg *alg);
static bool validate_singlecw_ending(Alg *alg);
@@ -68,7 +71,7 @@ optimal_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = always_valid,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -77,6 +80,25 @@ optimal_HTM = {
};
Step
+optimal_nxopt31_HTM = {
+ .shortname = "nxopt31",
+ .name = "Optimal solve (in HTM), nxopt31 table",
+
+ .final = true,
+ .is_done = is_solved,
+ .estimate = estimate_nxopt31_HTM,
+ .ready = check_centers,
+ .ready_msg = check_centers_msg,
+ .is_valid = always_valid,
+ .moveset = &moveset_HTM,
+
+ .pre_trans = uf,
+
+ .tables = {&pd_nxopt31_HTM, &pd_corners_HTM},
+ .ntables = 2,
+};
+
+Step
optimal_light_HTM = {
.shortname = "light",
.name = "Optimal solve (in HTM), small table (500Mb RAM total)",
@@ -87,7 +109,7 @@ optimal_light_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = always_valid,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -107,7 +129,7 @@ eoany_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -126,7 +148,7 @@ eofb_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -145,7 +167,7 @@ eorl_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = ur,
@@ -164,7 +186,7 @@ eoud_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = fd,
@@ -183,7 +205,7 @@ coany_HTM = {
.estimate = estimate_coany_HTM,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -201,7 +223,7 @@ coud_HTM = {
.estimate = estimate_coud_HTM,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -219,7 +241,7 @@ corl_HTM = {
.estimate = estimate_coud_HTM,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = rf,
@@ -237,7 +259,7 @@ cofb_HTM = {
.estimate = estimate_coud_HTM,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = fd,
@@ -255,7 +277,7 @@ coany_URF = {
.estimate = estimate_coany_URF,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_URF,
+ .moveset = &moveset_URF,
.pre_trans = uf,
@@ -273,7 +295,7 @@ coud_URF = {
.estimate = estimate_coud_URF,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_URF,
+ .moveset = &moveset_URF,
.pre_trans = uf,
@@ -291,7 +313,7 @@ corl_URF = {
.estimate = estimate_coud_URF,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_URF,
+ .moveset = &moveset_URF,
.pre_trans = rf,
@@ -309,7 +331,7 @@ cofb_URF = {
.estimate = estimate_coud_URF,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_URF,
+ .moveset = &moveset_URF,
.pre_trans = fd,
@@ -328,7 +350,7 @@ cornershtr_HTM = {
.estimate = estimate_cornershtr_HTM,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -346,7 +368,7 @@ cornershtr_URF = {
.estimate = estimate_cornershtr_URF,
.ready = NULL,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_URF,
+ .moveset = &moveset_URF,
.pre_trans = uf,
@@ -364,7 +386,7 @@ corners_HTM = {
.estimate = estimate_corners_HTM,
.ready = NULL,
.is_valid = always_valid,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -382,7 +404,7 @@ corners_URF = {
.estimate = estimate_corners_URF,
.ready = NULL,
.is_valid = always_valid,
- .moveset = moveset_URF,
+ .moveset = &moveset_URF,
.pre_trans = uf,
@@ -402,7 +424,7 @@ drany_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -421,7 +443,7 @@ drud_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = uf,
@@ -440,7 +462,7 @@ drrl_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = rf,
@@ -459,7 +481,7 @@ drfb_HTM = {
.ready = check_centers,
.ready_msg = check_centers_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_HTM,
+ .moveset = &moveset_HTM,
.pre_trans = fd,
@@ -479,7 +501,7 @@ dr_eo = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.detect = detect_pretrans_eofb,
@@ -498,7 +520,7 @@ dr_eofb = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = uf,
@@ -517,7 +539,7 @@ dr_eorl = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = ur,
@@ -536,7 +558,7 @@ dr_eoud = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = fd,
@@ -555,7 +577,7 @@ drud_eofb = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = uf,
@@ -574,7 +596,7 @@ drrl_eofb = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = rf,
@@ -593,7 +615,7 @@ drud_eorl = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = ur,
@@ -612,7 +634,7 @@ drfb_eorl = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = fr,
@@ -631,7 +653,7 @@ drfb_eoud = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = fd,
@@ -650,7 +672,7 @@ drrl_eoud = {
.ready = check_eofb,
.ready_msg = check_eo_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_eofb,
+ .moveset = &moveset_eofb,
.pre_trans = rd,
@@ -670,7 +692,7 @@ dranyfin_DR = {
.ready = check_drud,
.ready_msg = check_drany_msg,
.is_valid = always_valid,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.detect = detect_pretrans_drud,
@@ -689,7 +711,7 @@ drudfin_drud = {
.ready = check_drud,
.ready_msg = check_dr_msg,
.is_valid = always_valid,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.pre_trans = uf,
@@ -708,7 +730,7 @@ drrlfin_drrl = {
.ready = check_drud,
.ready_msg = check_dr_msg,
.is_valid = always_valid,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.pre_trans = rf,
@@ -727,7 +749,7 @@ drfbfin_drfb = {
.ready = check_drud,
.ready_msg = check_dr_msg,
.is_valid = always_valid,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.pre_trans = fd,
@@ -747,7 +769,7 @@ htr_any = {
.ready = check_drud,
.ready_msg = check_drany_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.detect = detect_pretrans_drud,
@@ -766,7 +788,7 @@ htr_drud = {
.ready = check_drud,
.ready_msg = check_dr_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.pre_trans = uf,
@@ -785,7 +807,7 @@ htr_drrl = {
.ready = check_drud,
.ready_msg = check_dr_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.pre_trans = rf,
@@ -804,7 +826,7 @@ htr_drfb = {
.ready = check_drud,
.ready_msg = check_dr_msg,
.is_valid = validate_singlecw_ending,
- .moveset = moveset_drud,
+ .moveset = &moveset_drud,
.pre_trans = fd,
@@ -824,7 +846,7 @@ htrfin_htr = {
.ready = check_htr,
.ready_msg = check_htr_msg,
.is_valid = always_valid,
- .moveset = moveset_htr,
+ .moveset = &moveset_htr,
.pre_trans = uf,
@@ -834,6 +856,7 @@ htrfin_htr = {
Step *steps[NSTEPS] = {
&optimal_HTM, /* first is default */
+ &optimal_nxopt31_HTM,
&optimal_light_HTM,
&eoany_HTM,
@@ -1183,6 +1206,19 @@ estimate_htrfin_htr(DfsArg *arg)
static int
estimate_optimal_HTM(DfsArg *arg)
{
+ return estimate_nxoptlike(arg, &pd_khuge_HTM);
+}
+
+static int
+estimate_nxopt31_HTM(DfsArg *arg)
+{
+ return estimate_nxoptlike(arg, &pd_nxopt31_HTM);
+}
+
+/* TODO: also use generic procedure for this */
+static int
+estimate_light_HTM(DfsArg *arg)
+{
int target, ret;
Cube aux;
@@ -1192,6 +1228,9 @@ estimate_optimal_HTM(DfsArg *arg)
(1<<L) | (1<<L2) | (1<<L3);
static const uint64_t fbmask = (1<<F) | (1<<F2) | (1<<F3) |
(1<<B) | (1<<B2) | (1<<B3);
+ static const uint64_t htmask = (1<<U2) | (1<<D2) |
+ (1<<R2) | (1<<L2) |
+ (1<<F2) | (1<<B2);
ret = -1;
target = arg->d - arg->current_alg->len;
@@ -1204,18 +1243,18 @@ estimate_optimal_HTM(DfsArg *arg)
UPDATECHECKSTOP(ret, arg->ed->corners, target);
/* Normal probing */
- arg->ed->normal_ud = ptableval(&pd_khuge_HTM, arg->cube);
+ arg->ed->normal_ud = ptableval(&pd_drud_sym16_HTM, arg->cube);
UPDATECHECKSTOP(ret, arg->ed->normal_ud, target);
aux = apply_trans(fd, arg->cube);
- arg->ed->normal_fb = ptableval(&pd_khuge_HTM, aux);
+ arg->ed->normal_fb = ptableval(&pd_drud_sym16_HTM, aux);
UPDATECHECKSTOP(ret, arg->ed->normal_fb, target);
aux = apply_trans(rf, arg->cube);
- arg->ed->normal_rl = ptableval(&pd_khuge_HTM, aux);
+ arg->ed->normal_rl = ptableval(&pd_drud_sym16_HTM, aux);
UPDATECHECKSTOP(ret, arg->ed->normal_rl, target);
/* If ret == 0, it's solved (corners + triple slice solved) */
if (ret == 0)
- return 0;
+ return is_solved(arg->cube) ? 0 : 1;
/* Michel de Bondt's trick*/
if (arg->ed->normal_ud == arg->ed->normal_fb &&
@@ -1224,21 +1263,30 @@ estimate_optimal_HTM(DfsArg *arg)
}
/* Inverse probing */
- aux = arg->inverse = inverse_cube(arg->cube);
- if (!((1<<arg->last1) & udmask) || (arg->ed->inverse_ud == -1)) {
- arg->ed->inverse_ud = ptableval(&pd_khuge_HTM, aux);
- }
- UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
- if (!((1<<arg->last1) & fbmask) || (arg->ed->inverse_fb == -1)) {
- aux = apply_trans(fd, arg->inverse);
- arg->ed->inverse_fb = ptableval(&pd_khuge_HTM, aux);
- }
- UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
- if (!((1<<arg->last1) & rlmask) || (arg->ed->inverse_rl == -1)) {
- aux = apply_trans(rf, arg->inverse);
- arg->ed->inverse_rl = ptableval(&pd_khuge_HTM, aux);
+ if (!((1<<arg->last1) & htmask)) {
+ aux = arg->inverse = inverse_cube(arg->cube);
+ if (!((1<<arg->last1) & udmask) || (arg->ed->inverse_ud==-1)) {
+ arg->ed->inverse_ud =
+ ptableval(&pd_drud_sym16_HTM, aux);
+ }
+ UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
+ if (!((1<<arg->last1) & fbmask) || (arg->ed->inverse_fb==-1)) {
+ aux = apply_trans(fd, arg->inverse);
+ arg->ed->inverse_fb =
+ ptableval(&pd_drud_sym16_HTM, aux);
+ }
+ UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
+ if (!((1<<arg->last1) & rlmask) || (arg->ed->inverse_rl==-1)) {
+ aux = apply_trans(rf, arg->inverse);
+ arg->ed->inverse_rl =
+ ptableval(&pd_drud_sym16_HTM, aux);
+ }
+ UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
+ } else {
+ UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
+ UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
+ UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
}
- UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
/* Michel de Bondt's trick*/
if (arg->ed->inverse_ud == arg->ed->inverse_fb &&
@@ -1246,26 +1294,26 @@ estimate_optimal_HTM(DfsArg *arg)
UPDATECHECKSTOP(ret, arg->ed->inverse_ud + 1, target);
}
- /* nxopt trick */
+ /* nxopt trick + half turn trick */
if (arg->ed->normal_ud == target)
- arg->badmovesinv |= udmask;
+ arg->badmovesinv |= udmask | htmask;
if (arg->ed->normal_fb == target)
- arg->badmovesinv |= fbmask;
+ arg->badmovesinv |= fbmask | htmask;
if (arg->ed->normal_rl == target)
- arg->badmovesinv |= rlmask;
+ arg->badmovesinv |= rlmask | htmask;
if (arg->ed->inverse_ud == target)
- arg->badmoves |= udmask;
+ arg->badmoves |= udmask | htmask;
if (arg->ed->inverse_fb == target)
- arg->badmoves |= fbmask;
+ arg->badmoves |= fbmask | htmask;
if (arg->ed->inverse_rl == target)
- arg->badmoves |= rlmask;
+ arg->badmoves |= rlmask | htmask;
return arg->ed->oldret = ret;
}
static int
-estimate_light_HTM(DfsArg *arg)
+estimate_nxoptlike(DfsArg *arg, PruneData *pd)
{
int target, ret;
Cube aux;
@@ -1276,9 +1324,6 @@ estimate_light_HTM(DfsArg *arg)
(1<<L) | (1<<L2) | (1<<L3);
static const uint64_t fbmask = (1<<F) | (1<<F2) | (1<<F3) |
(1<<B) | (1<<B2) | (1<<B3);
- static const uint64_t htmask = (1<<U2) | (1<<D2) |
- (1<<R2) | (1<<L2) |
- (1<<F2) | (1<<B2);
ret = -1;
target = arg->d - arg->current_alg->len;
@@ -1291,18 +1336,17 @@ estimate_light_HTM(DfsArg *arg)
UPDATECHECKSTOP(ret, arg->ed->corners, target);
/* Normal probing */
- arg->ed->normal_ud = ptableval(&pd_drud_sym16_HTM, arg->cube);
+ arg->ed->normal_ud = ptableval(pd, arg->cube);
UPDATECHECKSTOP(ret, arg->ed->normal_ud, target);
aux = apply_trans(fd, arg->cube);
- arg->ed->normal_fb = ptableval(&pd_drud_sym16_HTM, aux);
+ arg->ed->normal_fb = ptableval(pd, aux);
UPDATECHECKSTOP(ret, arg->ed->normal_fb, target);
aux = apply_trans(rf, arg->cube);
- arg->ed->normal_rl = ptableval(&pd_drud_sym16_HTM, aux);
+ arg->ed->normal_rl = ptableval(pd, aux);
UPDATECHECKSTOP(ret, arg->ed->normal_rl, target);
- /* If ret == 0, it's solved (corners + triple slice solved) */
if (ret == 0)
- return 0;
+ return arg->step->is_done(arg->cube) ? 0 : 1;
/* Michel de Bondt's trick*/
if (arg->ed->normal_ud == arg->ed->normal_fb &&
@@ -1311,30 +1355,21 @@ estimate_light_HTM(DfsArg *arg)
}
/* Inverse probing */
- if (!((1<<arg->last1) & htmask)) {
- aux = arg->inverse = inverse_cube(arg->cube);
- if (!((1<<arg->last1) & udmask) || (arg->ed->inverse_ud==-1)) {
- arg->ed->inverse_ud =
- ptableval(&pd_drud_sym16_HTM, aux);
- }
- UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
- if (!((1<<arg->last1) & fbmask) || (arg->ed->inverse_fb==-1)) {
- aux = apply_trans(fd, arg->inverse);
- arg->ed->inverse_fb =
- ptableval(&pd_drud_sym16_HTM, aux);
- }
- UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
- if (!((1<<arg->last1) & rlmask) || (arg->ed->inverse_rl==-1)) {
- aux = apply_trans(rf, arg->inverse);
- arg->ed->inverse_rl =
- ptableval(&pd_drud_sym16_HTM, aux);
- }
- UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
- } else {
- UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
- UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
- UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
+ aux = arg->inverse = inverse_cube(arg->cube);
+ if (!((1<<arg->last1) & udmask) || (arg->ed->inverse_ud == -1)) {
+ arg->ed->inverse_ud = ptableval(pd, aux);
+ }
+ UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
+ if (!((1<<arg->last1) & fbmask) || (arg->ed->inverse_fb == -1)) {
+ aux = apply_trans(fd, arg->inverse);
+ arg->ed->inverse_fb = ptableval(pd, aux);
+ }
+ UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
+ if (!((1<<arg->last1) & rlmask) || (arg->ed->inverse_rl == -1)) {
+ aux = apply_trans(rf, arg->inverse);
+ arg->ed->inverse_rl = ptableval(pd, aux);
}
+ UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
/* Michel de Bondt's trick*/
if (arg->ed->inverse_ud == arg->ed->inverse_fb &&
@@ -1342,24 +1377,25 @@ estimate_light_HTM(DfsArg *arg)
UPDATECHECKSTOP(ret, arg->ed->inverse_ud + 1, target);
}
- /* nxopt trick + half turn trick */
+ /* nxopt trick */
if (arg->ed->normal_ud == target)
- arg->badmovesinv |= udmask | htmask;
+ arg->badmovesinv |= udmask;
if (arg->ed->normal_fb == target)
- arg->badmovesinv |= fbmask | htmask;
+ arg->badmovesinv |= fbmask;
if (arg->ed->normal_rl == target)
- arg->badmovesinv |= rlmask | htmask;
+ arg->badmovesinv |= rlmask;
if (arg->ed->inverse_ud == target)
- arg->badmoves |= udmask | htmask;
+ arg->badmoves |= udmask;
if (arg->ed->inverse_fb == target)
- arg->badmoves |= fbmask | htmask;
+ arg->badmoves |= fbmask;
if (arg->ed->inverse_rl == target)
- arg->badmoves |= rlmask | htmask;
+ arg->badmoves |= rlmask;
return arg->ed->oldret = ret;
}
+
static bool
always_valid(Alg *alg)
{
diff --git a/src/symcoord.c b/src/symcoord.c
@@ -4,23 +4,24 @@
#define CLASSES_CP_16 2768
#define CLASSES_EOFBEPOS_16 64430
-static Cube antindex_coud_sym16(uint64_t ind);
static Cube antindex_cp_sym16(uint64_t ind);
static Cube antindex_eofbepos_sym16(uint64_t ind);
static Cube antindex_drud_sym16(uint64_t ind);
static Cube antindex_drudfin_noE_sym16(uint64_t ind);
static Cube antindex_khuge(uint64_t ind);
+static Cube antindex_nxopt31(uint64_t ind);
-static uint64_t index_coud_sym16(Cube cube);
static uint64_t index_cp_sym16(Cube cube);
static uint64_t index_eofbepos_sym16(Cube cube);
static uint64_t index_drud_sym16(Cube cube);
static uint64_t index_drudfin_noE_sym16(Cube cube);
static uint64_t index_khuge(Cube cube);
+static uint64_t index_nxopt31(Cube cube);
static int transfinder_drud_sym16(uint64_t ind, Trans *ret);
static int transfinder_drudfin_noE_sym16(uint64_t ind, Trans *ret);
static int transfinder_khuge(uint64_t ind, Trans *ret);
+static int transfinder_nxopt31(uint64_t ind, Trans *ret);
static void gensym(SymData *sd);
static bool read_symdata_file(SymData *sd);
@@ -38,15 +39,6 @@ trans_group_udfix[16] = {
};
static SymData
-sd_coud_16 = {
- .filename = "sd_coud_16",
- .coord = &coord_coud,
- .sym_coord = &coord_coud_sym16,
- .ntrans = 16,
- .trans = trans_group_udfix
-};
-
-static SymData
sd_cp_16 = {
.filename = "sd_cp_16",
.coord = &coord_cp,
@@ -64,9 +56,8 @@ sd_eofbepos_16 = {
.trans = trans_group_udfix
};
-static int nsymdata = 3;
+static int nsymdata = 2;
static SymData * all_sd[] = {
- &sd_coud_16,
&sd_cp_16,
&sd_eofbepos_16,
};
@@ -81,12 +72,6 @@ coord_eofbepos_sym16 = {
};
Coordinate
-coord_coud_sym16 = {
- .index = index_coud_sym16,
- .cube = antindex_coud_sym16,
-};
-
-Coordinate
coord_cp_sym16 = {
.index = index_cp_sym16,
.cube = antindex_cp_sym16,
@@ -116,13 +101,15 @@ coord_khuge = {
.trans = transfinder_khuge,
};
-/* Functions *****************************************************************/
+Coordinate
+coord_nxopt31 = {
+ .index = index_nxopt31,
+ .cube = antindex_nxopt31,
+ .max = POW3TO7 * BINOM8ON4 * CLASSES_EOFBEPOS_16 ,
+ .trans = transfinder_nxopt31,
+};
-static Cube
-antindex_coud_sym16(uint64_t ind)
-{
- return sd_coud_16.rep[ind];
-}
+/* Functions *****************************************************************/
static Cube
antindex_cp_sym16(uint64_t ind)
@@ -173,10 +160,16 @@ antindex_khuge(uint64_t ind)
return c;
}
-static uint64_t
-index_coud_sym16(Cube cube)
+static Cube
+antindex_nxopt31(uint64_t ind)
{
- return sd_coud_16.class[coord_coud.index(cube)];
+ Cube c;
+
+ c = antindex_eofbepos_sym16(ind/(BINOM8ON4*POW3TO7));
+ c.cp = coord_cpud_separate.cube((ind/POW3TO7)%BINOM8ON4).cp;
+ c.coud = ind % POW3TO7;
+
+ return c;
}
static uint64_t
@@ -229,6 +222,20 @@ index_khuge(Cube cube)
return a * POW3TO7 + c.coud;
}
+static uint64_t
+index_nxopt31(Cube cube)
+{
+ Trans t;
+ Cube c;
+ uint64_t a;
+
+ t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)];
+ c = apply_trans(t, cube);
+ a = (index_eofbepos_sym16(c)*BINOM8ON4) + coord_cpud_separate.index(c);
+
+ return a * POW3TO7 + c.coud;
+}
+
static int
transfinder_drud_sym16(uint64_t ind, Trans *ret)
{
@@ -295,6 +302,28 @@ transfinder_khuge(uint64_t ind, Trans *ret)
return naux[trueind];
}
+static int
+transfinder_nxopt31(uint64_t ind, Trans *ret)
+{
+ uint64_t i, trueind;
+ int j;
+ static bool initialized = false;
+ static int naux[CLASSES_EOFBEPOS_16];
+ static Trans retaux[CLASSES_EOFBEPOS_16][NTRANS];
+
+ if (!initialized) {
+ for (i = 0; i < CLASSES_EOFBEPOS_16; i++)
+ naux[i] = selfsims(&sd_eofbepos_16, i, retaux[i]);
+
+ initialized = true;
+ }
+
+ trueind = ind/(BINOM8ON4*POW3TO7);
+ for (j = 0; j < naux[trueind]; j++)
+ ret[j] = retaux[trueind][j];
+ return naux[trueind];
+}
+
/* Other functions ***********************************************************/
static void
diff --git a/src/symcoord.h b/src/symcoord.h
@@ -3,12 +3,12 @@
#include "coord.h"
-extern Coordinate coord_coud_sym16;
extern Coordinate coord_cp_sym16;
extern Coordinate coord_eofbepos_sym16;
extern Coordinate coord_drud_sym16;
extern Coordinate coord_drudfin_noE_sym16;
extern Coordinate coord_khuge;
+extern Coordinate coord_nxopt31;
void init_symcoord();
