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/steps.c | 277 +++++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 172 insertions(+), 105 deletions(-) (limited to 'src/steps.c') diff --git a/src/steps.c b/src/steps.c index 6478bc2..4646abd 100644 --- a/src/steps.c +++ b/src/steps.c @@ -1,5 +1,7 @@ #include "steps.h" +#define UPDATECHECKSTOP(a, b, c) if ((a=(MAX((a),(b))))>(c)) return (a); + /* Checkers, estimators and validators ***************************************/ static bool check_centers(Cube cube); @@ -7,24 +9,24 @@ static bool check_eofb(Cube cube); static bool check_drud(Cube cube); static bool check_htr(Cube cube); -static int estimate_eoany_HTM(CubeTarget ct); -static int estimate_eofb_HTM(CubeTarget ct); -static int estimate_coany_HTM(CubeTarget ct); -static int estimate_coud_HTM(CubeTarget ct); -static int estimate_coany_URF(CubeTarget ct); -static int estimate_coud_URF(CubeTarget ct); -static int estimate_corners_HTM(CubeTarget ct); -static int estimate_cornershtr_HTM(CubeTarget ct); -static int estimate_corners_URF(CubeTarget ct); -static int estimate_cornershtr_URF(CubeTarget ct); -static int estimate_drany_HTM(CubeTarget ct); -static int estimate_drud_HTM(CubeTarget ct); -static int estimate_drud_eofb(CubeTarget ct); -static int estimate_dr_eofb(CubeTarget ct); -static int estimate_drudfin_drud(CubeTarget ct); -static int estimate_htr_drud(CubeTarget ct); -static int estimate_htrfin_htr(CubeTarget ct); -static int estimate_optimal_HTM(CubeTarget ct); +static int estimate_eoany_HTM(EstimateData *ed); +static int estimate_eofb_HTM(EstimateData *ed); +static int estimate_coany_HTM(EstimateData *ed); +static int estimate_coud_HTM(EstimateData *ed); +static int estimate_coany_URF(EstimateData *ed); +static int estimate_coud_URF(EstimateData *ed); +static int estimate_corners_HTM(EstimateData *ed); +static int estimate_cornershtr_HTM(EstimateData *ed); +static int estimate_corners_URF(EstimateData *ed); +static int estimate_cornershtr_URF(EstimateData *ed); +static int estimate_drany_HTM(EstimateData *ed); +static int estimate_drud_HTM(EstimateData *ed); +static int estimate_drud_eofb(EstimateData *ed); +static int estimate_dr_eofb(EstimateData *ed); +static int estimate_drudfin_drud(EstimateData *ed); +static int estimate_htr_drud(EstimateData *ed); +static int estimate_htrfin_htr(EstimateData *ed); +static int estimate_optimal_HTM(EstimateData *ed); static bool always_valid(Alg *alg); static bool validate_singlecw_ending(Alg *alg); @@ -799,90 +801,106 @@ check_htr(Cube cube) } static int -estimate_eoany_HTM(CubeTarget ct) +estimate_eoany_HTM(EstimateData *ed) { int r1, r2, r3; - r1 = ptableval(&pd_eofb_HTM, ct.cube); - r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, ct.cube)); - r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, ct.cube)); + r1 = ptableval(&pd_eofb_HTM, ed->cube); + r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, ed->cube)); + r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, ed->cube)); return MIN(r1, MIN(r2, r3)); } static int -estimate_eofb_HTM(CubeTarget ct) +estimate_eofb_HTM(EstimateData *ed) { - return ptableval(&pd_eofb_HTM, ct.cube); + return ptableval(&pd_eofb_HTM, ed->cube); } static int -estimate_coany_HTM(CubeTarget ct) +estimate_coany_HTM(EstimateData *ed) { int r1, r2, r3; - r1 = ptableval(&pd_coud_HTM, ct.cube); - r2 = ptableval(&pd_coud_HTM, apply_trans(rf, ct.cube)); - r3 = ptableval(&pd_coud_HTM, apply_trans(fd, ct.cube)); + r1 = ptableval(&pd_coud_HTM, ed->cube); + r2 = ptableval(&pd_coud_HTM, apply_trans(rf, ed->cube)); + r3 = ptableval(&pd_coud_HTM, apply_trans(fd, ed->cube)); return MIN(r1, MIN(r2, r3)); } static int -estimate_coud_HTM(CubeTarget ct) +estimate_coud_HTM(EstimateData *ed) { - return ptableval(&pd_coud_HTM, ct.cube); + return ptableval(&pd_coud_HTM, ed->cube); } static int -estimate_coany_URF(CubeTarget ct) +estimate_coany_URF(EstimateData *ed) { int r1, r2, r3; - CubeTarget ct2, ct3; + EstimateData *ed2, *ed3; + + ed2 = malloc(sizeof(EstimateData)); + ed3 = malloc(sizeof(EstimateData)); - ct2.cube = apply_trans(rf, ct.cube); - ct2.target = ct.target; + ed2->cube = apply_trans(rf, ed->cube); + ed2->target = ed->target; - ct3.cube = apply_trans(fd, ct.cube); - ct3.target = ct.target; + ed3->cube = apply_trans(fd, ed->cube); + ed3->target = ed->target; - r1 = estimate_coud_URF(ct); - r2 = estimate_coud_URF(ct2); - r3 = estimate_coud_URF(ct3); + r1 = estimate_coud_URF(ed); + r2 = estimate_coud_URF(ed2); + r3 = estimate_coud_URF(ed3); + + free(ed2); + free(ed3); return MIN(r1, MIN(r2, r3)); } static int -estimate_coud_URF(CubeTarget ct) +estimate_coud_URF(EstimateData *ed) { /* TODO: I can improve this by checking first the orientation of * the corner in DBL and use that as a reference */ - CubeTarget ct2 = {.cube = apply_move(z, ct.cube), .target = ct.target}; - CubeTarget ct3 = {.cube = apply_move(x, ct.cube), .target = ct.target}; + EstimateData *ed2, *ed3; + + ed2 = malloc(sizeof(EstimateData)); + ed2->cube = apply_move(z, ed->cube); + ed2->target = ed->target; - int ud = estimate_coud_HTM(ct); - int rl = estimate_coud_HTM(ct2); - int fb = estimate_coud_HTM(ct3); + ed3 = malloc(sizeof(EstimateData)); + ed3->cube = apply_move(x, ed->cube); + ed3->target = ed->target; + + int ud = estimate_coud_HTM(ed); + int rl = estimate_coud_HTM(ed2); + int fb = estimate_coud_HTM(ed3); + + free(ed2); + free(ed3); return MIN(ud, MIN(rl, fb)); } static int -estimate_corners_HTM(CubeTarget ct) +estimate_corners_HTM(EstimateData *ed) { - return ptableval(&pd_corners_HTM, ct.cube); + return ptableval(&pd_corners_HTM, ed->cube); } static int -estimate_cornershtr_HTM(CubeTarget ct) +estimate_cornershtr_HTM(EstimateData *ed) { - return ptableval(&pd_cornershtr_HTM, ct.cube); + return ptableval(&pd_cornershtr_HTM, ed->cube); } static int -estimate_cornershtr_URF(CubeTarget ct) +estimate_cornershtr_URF(EstimateData *ed) { /* TODO: I can improve this by checking first the corner in DBL * and use that as a reference */ @@ -891,8 +909,8 @@ estimate_cornershtr_URF(CubeTarget ct) Trans i; for (i = 0; i < NROTATIONS; i++) { - ct.cube = apply_alg(rotation_alg(i), ct.cube); - c = estimate_cornershtr_HTM(ct); + ed->cube = apply_alg(rotation_alg(i), ed->cube); + c = estimate_cornershtr_HTM(ed); ret = MIN(ret, c); } @@ -900,7 +918,7 @@ estimate_cornershtr_URF(CubeTarget ct) } static int -estimate_corners_URF(CubeTarget ct) +estimate_corners_URF(EstimateData *ed) { /* TODO: I can improve this by checking first the corner in DBL * and use that as a reference */ @@ -909,8 +927,8 @@ estimate_corners_URF(CubeTarget ct) Trans i; for (i = 0; i < NROTATIONS; i++) { - ct.cube = apply_alg(rotation_alg(i), ct.cube); - c = estimate_corners_HTM(ct); + ed->cube = apply_alg(rotation_alg(i), ed->cube); + c = estimate_corners_HTM(ed); ret = MIN(ret, c); } @@ -918,104 +936,130 @@ estimate_corners_URF(CubeTarget ct) } static int -estimate_drany_HTM(CubeTarget ct) +estimate_drany_HTM(EstimateData *ed) { int r1, r2, r3; - r1 = ptableval(&pd_drud_sym16_HTM, ct.cube); - r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, ct.cube)); - r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, ct.cube)); + r1 = ptableval(&pd_drud_sym16_HTM, ed->cube); + r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, ed->cube)); + r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, ed->cube)); return MIN(r1, MIN(r2, r3)); } static int -estimate_drud_HTM(CubeTarget ct) +estimate_drud_HTM(EstimateData *ed) { - return ptableval(&pd_drud_sym16_HTM, ct.cube); + return ptableval(&pd_drud_sym16_HTM, ed->cube); } static int -estimate_drud_eofb(CubeTarget ct) +estimate_drud_eofb(EstimateData *ed) { - return ptableval(&pd_drud_eofb, ct.cube); + return ptableval(&pd_drud_eofb, ed->cube); } static int -estimate_dr_eofb(CubeTarget ct) +estimate_dr_eofb(EstimateData *ed) { int r1, r2; - r1 = ptableval(&pd_drud_eofb, ct.cube); - r2 = ptableval(&pd_drud_eofb, apply_trans(rf, ct.cube)); + r1 = ptableval(&pd_drud_eofb, ed->cube); + r2 = ptableval(&pd_drud_eofb, apply_trans(rf, ed->cube)); return MIN(r1, r2); } static int -estimate_drudfin_drud(CubeTarget ct) +estimate_drudfin_drud(EstimateData *ed) { - int val = ptableval(&pd_drudfin_noE_sym16_drud, ct.cube); + int val = ptableval(&pd_drudfin_noE_sym16_drud, ed->cube); if (val != 0) return val; - return ct.cube.epose % 24 == 0 ? 0 : 1; + return ed->cube.epose % 24 == 0 ? 0 : 1; } static int -estimate_htr_drud(CubeTarget ct) +estimate_htr_drud(EstimateData *ed) { - return ptableval(&pd_htr_drud, ct.cube); + return ptableval(&pd_htr_drud, ed->cube); } static int -estimate_htrfin_htr(CubeTarget ct) +estimate_htrfin_htr(EstimateData *ed) { - return ptableval(&pd_htrfin_htr, ct.cube); + return ptableval(&pd_htrfin_htr, ed->cube); } static int -estimate_optimal_HTM(CubeTarget ct) +estimate_optimal_HTM(EstimateData *ed) { - int dr1, dr2, dr3, cor, ret; - Cube inv; + int ret = -1; + Move lbase; + Cube cubeaux, inv; - dr1 = ptableval(&pd_khuge_HTM, ct.cube); - cor = estimate_corners_HTM(ct); - ret = MAX(dr1, cor); - if (ret > ct.target) - return ret; + ed->li->corners = ptableval(&pd_corners_HTM, ed->cube); + UPDATECHECKSTOP(ret, ed->li->corners, ed->target); - dr2 = ptableval(&pd_khuge_HTM, apply_trans(rf, ct.cube)); - ret = MAX(ret, dr2); - if (ret > ct.target) - return ret; + ed->li->normal_ud = ptableval(&pd_khuge_HTM, ed->cube); + UPDATECHECKSTOP(ret, ed->li->normal_ud, ed->target); - dr3 = ptableval(&pd_khuge_HTM, apply_trans(fd, ct.cube)); - if (dr1 == dr2 && dr2 == dr3 && dr1 != 0) - dr3++; - ret = MAX(ret, dr3); - if (ret > ct.target || ret == 0) - return ret; + cubeaux = apply_trans(fd, ed->cube); + ed->li->normal_fb = ptableval(&pd_khuge_HTM, cubeaux); + UPDATECHECKSTOP(ret, ed->li->normal_fb, ed->target); - /* Inverse cube probing */ + cubeaux = apply_trans(rf, ed->cube); + ed->li->normal_rl = ptableval(&pd_khuge_HTM, cubeaux); + UPDATECHECKSTOP(ret, ed->li->normal_rl, ed->target); - inv = inverse_cube(ct.cube); - dr1 = ptableval(&pd_khuge_HTM, inv); - ret = MAX(ret, dr1); - if (ret > ct.target) + if (ret == 0) return ret; - dr2 = ptableval(&pd_khuge_HTM, apply_trans(rf, inv)); - ret = MAX(ret, dr2); - if (ret > ct.target) - return ret; - - dr3 = ptableval(&pd_khuge_HTM, apply_trans(fd, inv)); - if (dr1 == dr2 && dr2 == dr3 && dr1 != 0) - dr3++; - return MAX(ret, dr3); + if (ed->li->normal_ud == ed->li->normal_fb && + ed->li->normal_fb == ed->li->normal_rl) + UPDATECHECKSTOP(ret, ed->li->normal_ud + 1, ed->target); + + /* TODO: avoid computation of inverse if unnecessary */ + lbase = base_move(ed->lastmove); + inv = inverse_cube(ed->cube); + + if ((lbase != U && lbase != D) || + (ed->li->inverse_ud == -1)) { + ed->li->inverse_ud = ptableval(&pd_khuge_HTM, inv); + } + UPDATECHECKSTOP(ret, ed->li->inverse_ud, ed->target); + + if ((lbase != F && lbase != B) || + (ed->li->inverse_fb == -1)) { + cubeaux = apply_trans(fd, inv); + ed->li->inverse_fb = ptableval(&pd_khuge_HTM, cubeaux); + } + UPDATECHECKSTOP(ret, ed->li->inverse_fb, ed->target); + + if ((lbase != R && lbase != L) || + (ed->li->inverse_rl == -1)) { + cubeaux = apply_trans(rf, inv); + ed->li->inverse_rl = ptableval(&pd_khuge_HTM, cubeaux); + } + UPDATECHECKSTOP(ret, ed->li->inverse_rl, ed->target); + + if (ed->li->inverse_ud == ed->li->inverse_fb && + ed->li->inverse_fb == ed->li->inverse_rl) + UPDATECHECKSTOP(ret, ed->li->inverse_ud + 1, ed->target); + + if (ed->li->inverse_ud == ed->target) + ed->movebitmask |= (1<li->inverse_fb == ed->target) + ed->movebitmask |= (1<li->inverse_rl == ed->target) + ed->movebitmask |= (1<corners = -1; + ret->normal_ud = -1; + ret->normal_fb = -1; + ret->normal_rl = -1; + ret->inverse_ud = -1; + ret->inverse_fb = -1; + ret->inverse_rl = -1; + ret->prev_ret = -1; + + return ret; +} + void prepare_step(Step *step) { -- cgit v1.3