From e864e23e3ec315d5969281c51f24521cde30792a Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 12 Nov 2021 19:59:18 +0100 Subject: 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. --- src/pruning.c | 157 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 136 insertions(+), 21 deletions(-) (limited to 'src/pruning.c') diff --git a/src/pruning.c b/src/pruning.c index b7fedd4..ca6f57a 100644 --- 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++) { -- cgit v1.3