From b6fd508253bce9225dd24b6538adb5093892c4f8 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 7 Dec 2021 12:20:51 +0100 Subject: Little performance improvement in optimal solver - more to come! --- src/solve.c | 125 +++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 73 insertions(+), 52 deletions(-) (limited to 'src/solve.c') diff --git a/src/solve.c b/src/solve.c index a35a837..881edd6 100644 --- a/src/solve.c +++ b/src/solve.c @@ -2,7 +2,7 @@ /* Local functions ***********************************************************/ -static bool allowed_next(Move move, DfsData *dd); +static bool allowed_next(Move move, DfsData *dd, uint64_t mm); static void dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd); static void dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd); static bool dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd); @@ -14,8 +14,11 @@ static void multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, /* Local functions ***********************************************************/ static bool -allowed_next(Move move, DfsData *dd) +allowed_next(Move move, DfsData *dd, uint64_t mm) { + if ((1 << move) & mm) + return false; + if (!possible_next(dd->last2, dd->last1, move)) return false; @@ -45,23 +48,21 @@ dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd) { bool b = false; int i; + uint64_t mm; Move m, l1, l2; + LocalInfo li; l1 = dd->last1; l2 = dd->last2; + li = *(dd->ed->li); + mm = dd->ed->movebitmask; for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) { - /* - pthread_mutex_lock(dd->sols_mutex); - b = dd->sols->len >= opts->max_solutions; - pthread_mutex_unlock(dd->sols_mutex); - */ - if (b) break; m = dd->sorted_moves[i]; - if (allowed_next(m, dd)) { + if (allowed_next(m, dd, mm)) { dd->last2 = dd->last1; dd->last1 = m; append_move(dd->current_alg, m, dd->niss); @@ -69,8 +70,9 @@ dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd) dfs(apply_move(m, c), s, opts, dd); dd->current_alg->len--; - dd->last2 = l2; - dd->last1 = l1; + dd->last2 = l2; + dd->last1 = l1; + *(dd->ed->li) = li; } } } @@ -99,13 +101,17 @@ dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd) static void dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd) { - Move l1 = dd->last1, l2 = dd->last2; - CubeTarget ct; + Move l1, l2; + EstimateData *ed; - ct.cube = apply_move(inverse_move(l1), (Cube){0}); - ct.target = 1; + l1 = dd->last1; + l2 = dd->last2; + + ed = malloc(sizeof(EstimateData)); + ed->cube = apply_move(inverse_move(l1), (Cube){0}); + ed->target = 1; - if (dd->current_alg->len == 0 || s->estimate(ct)) { + if (dd->current_alg->len == 0 || s->estimate(ed)) { dd->niss = true; dd->last1 = NULLMOVE; dd->last2 = NULLMOVE; @@ -116,28 +122,31 @@ dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd) dd->last2 = l2; dd->niss = false; } + + free(ed); } static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd) { - bool b = false; + bool b; - CubeTarget ct = { - .cube = c, - .target = dd->d - dd->current_alg->len - }; + dd->ed->cube = c; + dd->ed->target = dd->d - dd->current_alg->len; + dd->ed->lastmove = dd->last1; + dd->ed->movebitmask = 0; - dd->lb = s->estimate(ct); + dd->lb = s->estimate(dd->ed); if (opts->can_niss && !dd->niss) dd->lb = MIN(1, dd->lb); - if (dd->current_alg->len + dd->lb > dd->d) - return true; - - pthread_mutex_lock(dd->sols_mutex); - b = dd->sols->len >= opts->max_solutions; - pthread_mutex_unlock(dd->sols_mutex); + if (dd->current_alg->len + dd->lb > dd->d) { + b = true; + } else { + pthread_mutex_lock(dd->sols_mutex); + b = dd->sols->len >= opts->max_solutions; + pthread_mutex_unlock(dd->sols_mutex); + } return b; } @@ -170,30 +179,28 @@ instance_thread(void *arg) apply_move(node->alg->move[0], inverse_cube(td->cube)) : apply_move(node->alg->move[0], td->cube); - dd.d = td->depth; - dd.m = 1; - dd.niss = node->alg->inv[0]; - dd.lb = -1; - dd.last1 = node->alg->move[0]; - dd.last2 = NULLMOVE; - dd.sols = td->sols; - dd.sols_mutex = td->sols_mutex; - dd.current_alg = new_alg(""); + dd.d = td->depth; + dd.m = 1; + dd.niss = node->alg->inv[0]; + dd.lb = -1; + dd.last1 = node->alg->move[0]; + dd.last2 = NULLMOVE; + dd.sols = td->sols; + dd.sols_mutex = td->sols_mutex; + dd.current_alg = new_alg(""); append_move(dd.current_alg, node->alg->move[0], node->alg->inv[0]); - dd.sorted_moves = td->sorted_moves; - dd.move_position = td->move_position; - -/* - pthread_mutex_lock(td->sols_mutex); - printf("Starting thread %d with move: ", td->thid); - print_alg(dd.current_alg, false); - pthread_mutex_unlock(td->sols_mutex); -*/ + dd.sorted_moves = td->sorted_moves; + dd.move_position = td->move_position; + dd.ed = malloc(sizeof(EstimateData)); + dd.ed->movebitmask = 0; + dd.ed->li = new_localinfo(); dfs(c, td->step, td->opts, &dd); free_alg(dd.current_alg); + free_localinfo(dd.ed->li); + free(dd.ed); } return NULL; @@ -223,6 +230,7 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d) moveset_to_list(s->moveset, sorted_moves); movelist_to_position(sorted_moves, move_position); + for (i = 0; sorted_moves[i] != NULLMOVE; i++) { alg = new_alg(""); append_move(alg, sorted_moves[i], false); @@ -268,9 +276,11 @@ AlgList * solve(Cube cube, Step *step, SolveOptions *opts) { int d; - AlgList *sols = new_alglist(); + AlgList *sols; AlgListNode *node; Cube c; + EstimateData *ed; + bool b; prepare_step(step); @@ -278,19 +288,30 @@ solve(Cube cube, Step *step, SolveOptions *opts) step->pre_trans = step->detect(cube); c = apply_trans(step->pre_trans, cube); + sols = new_alglist(); + if (step->ready != NULL && !step->ready(c)) { fprintf(stderr, "Cube not ready for solving step: "); fprintf(stderr, "%s\n", step->ready_msg); return sols; } - if (step->estimate((CubeTarget){.cube = c, .target = 0}) == 0 && - opts->min_moves == 0) { - append_alg(sols, new_alg("")); - return sols; + if (opts->min_moves == 0) { + ed = malloc(sizeof(EstimateData)); + ed->cube = cube; + ed->target = 0; + ed->li = new_localinfo(); + b = step->estimate(ed) == 0; + free_localinfo(ed->li); + free(ed); + + if (b) { + append_alg(sols, new_alg("")); + return sols; + } } - for (d = MAX(1, opts->min_moves); + for (d = opts->min_moves; d <= opts->max_moves && !(sols->len && opts->optimal_only) && sols->len < opts->max_solutions; -- cgit v1.3