commit e864e23e3ec315d5969281c51f24521cde30792a
parent 89268e911e51a7b1c413cfae1520b2db6e60086f
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Fri, 12 Nov 2021 19:59:18 +0100
I tried to remove the dependence on antindex in order to get rid of them
once and for all. I successfully removed from the pruning table generation
part by using an alternative (slower) method, but then I realized that I also
use antindexes when generating symmetry data. So I reverted to the original
pruning table computation method, but I left the alternative way there, commented.
Diffstat:
6 files changed, 155 insertions(+), 26 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+nissy.o
diff --git a/README.md b/README.md
@@ -109,8 +109,9 @@ table to solving EO with HTM moveset and this coordinate would have values 0 (fo
There is one caveat: each coordinates also needs an inverse function that takes a
coordinate value and returns a cube which has that coordinate. This is in general
more complicated, but luckily the cube does not need to be fully built or consistent.
-This inverse-coordinate is used only in one specific step when building pruning tables
-to avoid using up hundreds of Gb of memory.
+This inverse-coordinate is used only in one specific step when generating symmetry
+data, and I don't know if it is possible to avoid it (maybe it is). It is also used
+when building pruning tables, but in that case it is avoidable.
Note: this part is different from what Cube Explorer does. Overall I think it is
conceptually easier, although in practice it was still hard to implement.
diff --git a/src/coord.c b/src/coord.c
@@ -171,7 +171,7 @@ antindex_eofbepos(uint64_t ind)
/* We need eorl for sym16 coordinate */
static int initialized = false;
- static uint64_t eorl_aux[POW2TO11][BINOM12ON4];
+ static uint64_t eorl_a[POW2TO11][BINOM12ON4];
static int eo_aux[12], ep_aux[12];
unsigned int i, j, k;
@@ -181,8 +181,10 @@ antindex_eofbepos(uint64_t ind)
int_to_sum_zero_array(i, 2, 12, eo_aux);
index_to_subset(j, 12, 4, ep_aux);
for (k = 0; k < 12; k++)
- if (ep_aux[k])
+ if ((ep_aux[k] && k < FR) ||
+ (!ep_aux[k] && k >= FR))
eo_aux[k] = 1 - eo_aux[k];
+ eorl_a[i][j] = digit_array_to_int(eo_aux,11,2);
}
}
@@ -191,7 +193,7 @@ antindex_eofbepos(uint64_t ind)
ret.eofb = ind % POW2TO11;
ret.epose = (ind / POW2TO11) * 24;
- ret.eorl = eorl_aux[ret.eofb][ret.epose/24];
+ ret.eorl = eorl_a[ret.eofb][ret.epose/24];
return ret;
}
diff --git a/src/cubetypes.h b/src/cubetypes.h
@@ -213,6 +213,7 @@ dfsdata
Alg * current_alg;
Move sorted_moves[NMOVES];
int move_position[NMOVES];
+ uint8_t * visited;
};
struct
diff --git a/src/pruning.c b/src/pruning.c
@@ -1,7 +1,20 @@
#include "pruning.h"
+/*
+ * The commented functions are a way to generate a pruning table
+ * without using anti-indexes. It does not matter too much because
+ * we still need anti-indexes in gensym.
+ */
+/*
+static bool dfs_get_visited(PruneData *pd, DfsData *dd, Cube c);
+static bool dfs_get_visited_index(DfsData *dd, uint64_t ind);
+static void dfs_set_visited(PruneData *pd, DfsData *dd, Cube c, bool b);
+static void dfs_set_visited_index(DfsData *dd, uint64_t ind, bool b);
+static void genptable_dfs(Cube c, PruneData *pd, DfsData *dd);
+*/
+
static void genptable_bfs(PruneData *pd, int d, Move *ms);
-static void genptable_branch(PruneData *pd, uint64_t i, int d, Move *m);
+static void genptable_branch(PruneData *pd,uint64_t ind,int d,Move *ms);
static void ptable_update(PruneData *pd, Cube cube, int m);
static void ptable_update_index(PruneData *pd, uint64_t ind, int m);
static int ptableval_index(PruneData *pd, uint64_t ind);
@@ -78,6 +91,54 @@ pd_khuge_HTM = {
.moveset = moveset_HTM,
};
+/*
+void
+genptable(PruneData *pd)
+{
+ Move ms[NMOVES];
+ uint64_t j, oldn;
+ DfsData dd;
+
+ if (pd->generated)
+ return;
+
+ pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
+
+ if (read_ptable_file(pd)) {
+ pd->generated = true;
+ return;
+ }
+ pd->generated = true;
+
+ fprintf(stderr, "Cannot load %s, generating it\n", pd->filename);
+
+ moveset_to_list(pd->moveset, ms);
+
+ for (j = 0; j < pd->coord->max; j++)
+ ptable_update_index(pd, j, 15);
+
+ dd = (DfsData) { .m = 0 };
+ dd.visited = malloc((ptablesize(pd)/4 + 1) * sizeof(uint8_t));
+ moveset_to_list(pd->moveset, dd.sorted_moves);
+ oldn = 0;
+ pd->n = 0;
+
+ for (dd.d = 0; dd.d < 15 && pd->n < pd->coord->max; dd.d++) {
+ for (j = 0; j < pd->coord->max; j++)
+ dfs_set_visited_index(&dd, j, false);
+ genptable_dfs((Cube){0}, pd, &dd);
+ fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n",
+ dd.d+1, pd->n - oldn, pd->n, pd->coord->max);
+ oldn = pd->n;
+ }
+
+ if (!write_ptable_file(pd))
+ fprintf(stderr, "Error writing ptable file\n");
+
+ free(dd.visited);
+}
+*/
+
void
genptable(PruneData *pd)
{
@@ -105,13 +166,6 @@ genptable(PruneData *pd)
for (j = 0; j < pd->coord->max; j++)
ptable_update_index(pd, j, 15);
- for (j = 0; j < pd->coord->max; j++)
- if (ptableval_index(pd, j) != 15) {
- printf("Error, non-max value at index %lu!\n", j);
- break;
- }
- printf("Table set, ready to start\n");
-
ptable_update(pd, (Cube){0}, 0);
pd->n = 1;
oldn = 0;
@@ -127,7 +181,81 @@ genptable(PruneData *pd)
if (!write_ptable_file(pd))
fprintf(stderr, "Error writing ptable file\n");
+
+}
+
+/*
+static void
+genptable_dfs(Cube c, PruneData *pd, DfsData *dd)
+{
+ int i, j, pv;
+ Move mm;
+ Cube cc;
+
+ if (pd->coord->index(c) > 2*ptablesize(pd)) {
+ printf("error! %lu > %lu\n", pd->coord->index(c), 2*ptablesize(pd));
+ print_cube(c);
+ exit(1);
+ }
+ pv = ptableval(pd, c);
+
+ if (pv < dd->m || dd->m > dd->d)
+ return;
+
+ if (dfs_get_visited(pd, dd, c))
+ return;
+ dfs_set_visited(pd, dd, c, true);
+
+ if (pv != dd->m)
+ ptable_update(pd, c, dd->m);
+
+ for (i = 0; i < pd->coord->ntrans; i++) {
+ cc = i == 0 ? c :
+ apply_trans(pd->coord->trans[i], c);
+ for (j = 0; dd->sorted_moves[j] != NULLMOVE; j++) {
+ mm = dd->sorted_moves[j];
+ dd->m++;
+ genptable_dfs(apply_move(mm, cc), pd, dd);
+ dd->m--;
+ }
+ }
+}
+*/
+
+/*
+static bool
+dfs_get_visited(PruneData *pd, DfsData *dd, Cube c)
+{
+ return dfs_get_visited_index(dd, pd->coord->index(c));
+}
+*/
+
+/*
+static bool
+dfs_get_visited_index(DfsData *dd, uint64_t ind)
+{
+ return dd->visited[ind/8] & ((uint8_t)1 << (ind % 8));
+}
+*/
+
+/*
+static void
+dfs_set_visited(PruneData *pd, DfsData *dd, Cube c, bool b)
+{
+ dfs_set_visited_index(dd, pd->coord->index(c), b);
+}
+*/
+
+/*
+static void
+dfs_set_visited_index(DfsData *dd, uint64_t ind, bool b)
+{
+ if (b)
+ dd->visited[ind/8] |= ((uint8_t)1 << (ind % 8));
+ else
+ dd->visited[ind/8] &= ~((uint8_t)1 << (ind % 8));
}
+*/
static void
genptable_bfs(PruneData *pd, int d, Move *ms)
@@ -145,22 +273,9 @@ genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
int i, j;
Cube ci, cc, c;
- /*
- * This is the only line of the whole program where we REALLY need an
- * anti-indexer function. We could get rid of it if only we could save
- * a cube object for each index value as we go, but then we would need
- * an incredible amount of memory to generate each ptable: assuming
- * fields in struct cube are 32 bit ints that would take 88 times the
- * memory of the table to be generated, more than 120Gb for
- * ptable_khuge for example!
- *
- * TODO: it would be nice to get rid of this...
- *
- */
ci = pd->coord->cube(ind);
for (i = 0; i < pd->coord->ntrans; i++) {
- /* For simplicity trans[] is NULL when ntrans = 1 */
c = i == 0 ? ci :
apply_trans(pd->coord->trans[i], ci);
for (j = 0; ms[j] != NULLMOVE; j++) {
diff --git a/src/symcoord.c b/src/symcoord.c
@@ -257,7 +257,16 @@ gensym(SymData *sd)
for (i = 0; i < sd->coord->max; i++) {
if (sd->class[i] == sd->coord->max + 1) {
+
+ /*
+ * TODO: this is the only unavoidable use of
+ * antindexes. I also use them in genptable() (see
+ * pruning.c), but there I can do without (see
+ * commented functions in that file.
+ * Removing this would allow for a great simplification
+ */
c = sd->coord->cube(i);
+
sd->rep[nreps] = c;
for (j = 0; j < sd->ntrans; j++) {
d = apply_trans(sd->trans[j], c);
