From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 21:37:34 +0100 Subject: Rewritten from scratch. Welocme nissy 2.0! --- src/pruning.c | 271 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 271 insertions(+) create mode 100644 src/pruning.c (limited to 'src/pruning.c') diff --git a/src/pruning.c b/src/pruning.c new file mode 100644 index 0000000..bc9dd59 --- /dev/null +++ b/src/pruning.c @@ -0,0 +1,271 @@ +#include "pruning.h" + +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 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); +static bool read_ptable_file(PruneData *pd); +static bool write_ptable_file(PruneData *pd); + +PruneData +pd_eofb_HTM = { + .filename = "pt_eofb_HTM", + .coord = &coord_eofb, + .moveset = moveset_HTM, +}; + +PruneData +pd_coud_HTM = { + .filename = "pt_coud_HTM", + .coord = &coord_coud, + .moveset = moveset_HTM, +}; + +PruneData +pd_cornershtr_HTM = { + .filename = "pt_cornershtr_HTM", + .coord = &coord_cornershtr, + .moveset = moveset_HTM, +}; + +PruneData +pd_corners_HTM = { + .filename = "pt_corners_HTM", + .coord = &coord_corners, + .moveset = moveset_HTM, +}; + +PruneData +pd_drud_sym16_HTM = { + .filename = "pt_drud_sym16_HTM", + .coord = &coord_drud_sym16, + .moveset = moveset_HTM, +}; + +PruneData +pd_drud_eofb = { + .filename = "pt_drud_eofb", + .coord = &coord_drud_eofb, + .moveset = moveset_eofb, +}; + +PruneData +pd_drudfin_noE_sym16_drud = { + .filename = "pt_drudfin_noE_sym16_drud", + .coord = &coord_drudfin_noE_sym16, + .moveset = moveset_drud, +}; + +PruneData +pd_htr_drud = { + .filename = "pt_htr_drud", + .coord = &coord_htr_drud, + .moveset = moveset_drud, +}; + +PruneData +pd_htrfin_htr = { + .filename = "pt_htrfin_htr", + .coord = &coord_htrfin, + .moveset = moveset_htr, +}; + +PruneData +pd_khuge_HTM = { + .filename = "pt_khuge_HTM", + .coord = &coord_khuge, + .moveset = moveset_HTM, +}; + +void +genptable(PruneData *pd) +{ + Move ms[NMOVES]; + int d; + uint64_t j, oldn; + + if (pd->generated) + return; + + /* TODO: check if memory is enough, otherwise maybe exit gracefully? */ + 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); + + /* 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); + + 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; + fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n", + 0, pd->n - oldn, pd->n, pd->coord->max); + oldn = 1; + for (d = 0; d < 15 && pd->n < pd->coord->max; d++) { + genptable_bfs(pd, d, ms); + fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n", + 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"); +} + +static void +genptable_bfs(PruneData *pd, int d, Move *ms) +{ + uint64_t i; + + for (i = 0; i < pd->coord->max; i++) + if (ptableval_index(pd, i) == d) + genptable_branch(pd, i, d, ms); +} + +static void +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! + */ + 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++) { + cc = apply_move(ms[j], c); + if (ptableval(pd, cc) > d+1) + ptable_update(pd, cc, d+1); + } + } +} + +void +print_ptable(PruneData *pd) +{ + uint64_t i, a[16]; + + for (i = 0; i < 16; i++) + a[i] = 0; + + if (!pd->generated) + genptable(pd); + + for (i = 0; i < pd->coord->max; i++) + a[ptableval_index(pd, i)]++; + + fprintf(stderr, "Values for table %s\n", pd->filename); + for (i = 0; i < 16; i++) + printf("%2lu\t%10lu\n", i, a[i]); +} + +uint64_t +ptablesize(PruneData *pd) +{ + return (pd->coord->max + 1) / 2; +} + +static void +ptable_update(PruneData *pd, Cube cube, int n) +{ + uint64_t ind = pd->coord->index(cube); + ptable_update_index(pd, ind, n); +} + +static void +ptable_update_index(PruneData *pd, uint64_t ind, int n) +{ + uint8_t oldval2 = pd->ptable[ind/2]; + int other = (ind % 2) ? oldval2 % 16 : oldval2 / 16; + + pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n; + pd->n++; +} + +int +ptableval(PruneData *pd, Cube cube) +{ + return ptableval_index(pd, pd->coord->index(cube)); +} + +static int +ptableval_index(PruneData *pd, uint64_t ind) +{ + if (!pd->generated) + genptable(pd); + + return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16; +} + +static bool +read_ptable_file(PruneData *pd) +{ + init_env(); + + FILE *f; + char fname[strlen(tabledir)+100]; + uint64_t r; + + strcpy(fname, tabledir); + strcat(fname, "/"); + strcat(fname, pd->filename); + + if ((f = fopen(fname, "rb")) == NULL) + return false; + + r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); + fclose(f); + + return r == ptablesize(pd); +} + +static bool +write_ptable_file(PruneData *pd) +{ + init_env(); + + FILE *f; + char fname[strlen(tabledir)+100]; + uint64_t written; + + strcpy(fname, tabledir); + strcat(fname, "/"); + strcat(fname, pd->filename); + + if ((f = fopen(fname, "wb")) == NULL) + return false; + + written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); + fclose(f); + + return written == ptablesize(pd); +} + -- cgit v1.3