From 2f924f942bd6e7126e8f1d8692e475c95bd9fe82 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 16 Dec 2021 19:25:58 +0100 Subject: Added a new pruning table (equivalent to nxopt31). I have not tested it yet, it takes a while to generate. Plus I have done a whole lot of refactoring in random places because I cannot focus on one thing at the time. --- src/steps.c | 246 ++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 141 insertions(+), 105 deletions(-) (limited to 'src/steps.c') diff --git a/src/steps.c b/src/steps.c index c4d1279..014b206 100644 --- a/src/steps.c +++ b/src/steps.c @@ -36,8 +36,11 @@ static int estimate_drudfin_drud(DfsArg *arg); static int estimate_htr_drud(DfsArg *arg); static int estimate_htrfin_htr(DfsArg *arg); static int estimate_optimal_HTM(DfsArg *arg); +static int estimate_nxopt31_HTM(DfsArg *arg); static int estimate_light_HTM(DfsArg *arg); +static int estimate_nxoptlike(DfsArg *arg, PruneData *pd); + static bool always_valid(Alg *alg); static bool validate_singlecw_ending(Alg *alg); @@ -68,7 +71,7 @@ optimal_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = always_valid, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -76,6 +79,25 @@ optimal_HTM = { .ntables = 2, }; +Step +optimal_nxopt31_HTM = { + .shortname = "nxopt31", + .name = "Optimal solve (in HTM), nxopt31 table", + + .final = true, + .is_done = is_solved, + .estimate = estimate_nxopt31_HTM, + .ready = check_centers, + .ready_msg = check_centers_msg, + .is_valid = always_valid, + .moveset = &moveset_HTM, + + .pre_trans = uf, + + .tables = {&pd_nxopt31_HTM, &pd_corners_HTM}, + .ntables = 2, +}; + Step optimal_light_HTM = { .shortname = "light", @@ -87,7 +109,7 @@ optimal_light_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = always_valid, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -107,7 +129,7 @@ eoany_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -126,7 +148,7 @@ eofb_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -145,7 +167,7 @@ eorl_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = ur, @@ -164,7 +186,7 @@ eoud_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = fd, @@ -183,7 +205,7 @@ coany_HTM = { .estimate = estimate_coany_HTM, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -201,7 +223,7 @@ coud_HTM = { .estimate = estimate_coud_HTM, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -219,7 +241,7 @@ corl_HTM = { .estimate = estimate_coud_HTM, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = rf, @@ -237,7 +259,7 @@ cofb_HTM = { .estimate = estimate_coud_HTM, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = fd, @@ -255,7 +277,7 @@ coany_URF = { .estimate = estimate_coany_URF, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, + .moveset = &moveset_URF, .pre_trans = uf, @@ -273,7 +295,7 @@ coud_URF = { .estimate = estimate_coud_URF, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, + .moveset = &moveset_URF, .pre_trans = uf, @@ -291,7 +313,7 @@ corl_URF = { .estimate = estimate_coud_URF, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, + .moveset = &moveset_URF, .pre_trans = rf, @@ -309,7 +331,7 @@ cofb_URF = { .estimate = estimate_coud_URF, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, + .moveset = &moveset_URF, .pre_trans = fd, @@ -328,7 +350,7 @@ cornershtr_HTM = { .estimate = estimate_cornershtr_HTM, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -346,7 +368,7 @@ cornershtr_URF = { .estimate = estimate_cornershtr_URF, .ready = NULL, .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, + .moveset = &moveset_URF, .pre_trans = uf, @@ -364,7 +386,7 @@ corners_HTM = { .estimate = estimate_corners_HTM, .ready = NULL, .is_valid = always_valid, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -382,7 +404,7 @@ corners_URF = { .estimate = estimate_corners_URF, .ready = NULL, .is_valid = always_valid, - .moveset = moveset_URF, + .moveset = &moveset_URF, .pre_trans = uf, @@ -402,7 +424,7 @@ drany_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -421,7 +443,7 @@ drud_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = uf, @@ -440,7 +462,7 @@ drrl_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = rf, @@ -459,7 +481,7 @@ drfb_HTM = { .ready = check_centers, .ready_msg = check_centers_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, .pre_trans = fd, @@ -479,7 +501,7 @@ dr_eo = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .detect = detect_pretrans_eofb, @@ -498,7 +520,7 @@ dr_eofb = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = uf, @@ -517,7 +539,7 @@ dr_eorl = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = ur, @@ -536,7 +558,7 @@ dr_eoud = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = fd, @@ -555,7 +577,7 @@ drud_eofb = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = uf, @@ -574,7 +596,7 @@ drrl_eofb = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = rf, @@ -593,7 +615,7 @@ drud_eorl = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = ur, @@ -612,7 +634,7 @@ drfb_eorl = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = fr, @@ -631,7 +653,7 @@ drfb_eoud = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = fd, @@ -650,7 +672,7 @@ drrl_eoud = { .ready = check_eofb, .ready_msg = check_eo_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, .pre_trans = rd, @@ -670,7 +692,7 @@ dranyfin_DR = { .ready = check_drud, .ready_msg = check_drany_msg, .is_valid = always_valid, - .moveset = moveset_drud, + .moveset = &moveset_drud, .detect = detect_pretrans_drud, @@ -689,7 +711,7 @@ drudfin_drud = { .ready = check_drud, .ready_msg = check_dr_msg, .is_valid = always_valid, - .moveset = moveset_drud, + .moveset = &moveset_drud, .pre_trans = uf, @@ -708,7 +730,7 @@ drrlfin_drrl = { .ready = check_drud, .ready_msg = check_dr_msg, .is_valid = always_valid, - .moveset = moveset_drud, + .moveset = &moveset_drud, .pre_trans = rf, @@ -727,7 +749,7 @@ drfbfin_drfb = { .ready = check_drud, .ready_msg = check_dr_msg, .is_valid = always_valid, - .moveset = moveset_drud, + .moveset = &moveset_drud, .pre_trans = fd, @@ -747,7 +769,7 @@ htr_any = { .ready = check_drud, .ready_msg = check_drany_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, + .moveset = &moveset_drud, .detect = detect_pretrans_drud, @@ -766,7 +788,7 @@ htr_drud = { .ready = check_drud, .ready_msg = check_dr_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, + .moveset = &moveset_drud, .pre_trans = uf, @@ -785,7 +807,7 @@ htr_drrl = { .ready = check_drud, .ready_msg = check_dr_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, + .moveset = &moveset_drud, .pre_trans = rf, @@ -804,7 +826,7 @@ htr_drfb = { .ready = check_drud, .ready_msg = check_dr_msg, .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, + .moveset = &moveset_drud, .pre_trans = fd, @@ -824,7 +846,7 @@ htrfin_htr = { .ready = check_htr, .ready_msg = check_htr_msg, .is_valid = always_valid, - .moveset = moveset_htr, + .moveset = &moveset_htr, .pre_trans = uf, @@ -834,6 +856,7 @@ htrfin_htr = { Step *steps[NSTEPS] = { &optimal_HTM, /* first is default */ + &optimal_nxopt31_HTM, &optimal_light_HTM, &eoany_HTM, @@ -1182,6 +1205,19 @@ estimate_htrfin_htr(DfsArg *arg) static int estimate_optimal_HTM(DfsArg *arg) +{ + return estimate_nxoptlike(arg, &pd_khuge_HTM); +} + +static int +estimate_nxopt31_HTM(DfsArg *arg) +{ + return estimate_nxoptlike(arg, &pd_nxopt31_HTM); +} + +/* TODO: also use generic procedure for this */ +static int +estimate_light_HTM(DfsArg *arg) { int target, ret; Cube aux; @@ -1192,6 +1228,9 @@ estimate_optimal_HTM(DfsArg *arg) (1<d - arg->current_alg->len; @@ -1204,18 +1243,18 @@ estimate_optimal_HTM(DfsArg *arg) UPDATECHECKSTOP(ret, arg->ed->corners, target); /* Normal probing */ - arg->ed->normal_ud = ptableval(&pd_khuge_HTM, arg->cube); + arg->ed->normal_ud = ptableval(&pd_drud_sym16_HTM, arg->cube); UPDATECHECKSTOP(ret, arg->ed->normal_ud, target); aux = apply_trans(fd, arg->cube); - arg->ed->normal_fb = ptableval(&pd_khuge_HTM, aux); + arg->ed->normal_fb = ptableval(&pd_drud_sym16_HTM, aux); UPDATECHECKSTOP(ret, arg->ed->normal_fb, target); aux = apply_trans(rf, arg->cube); - arg->ed->normal_rl = ptableval(&pd_khuge_HTM, aux); + arg->ed->normal_rl = ptableval(&pd_drud_sym16_HTM, aux); UPDATECHECKSTOP(ret, arg->ed->normal_rl, target); /* If ret == 0, it's solved (corners + triple slice solved) */ if (ret == 0) - return 0; + return is_solved(arg->cube) ? 0 : 1; /* Michel de Bondt's trick*/ if (arg->ed->normal_ud == arg->ed->normal_fb && @@ -1224,21 +1263,30 @@ estimate_optimal_HTM(DfsArg *arg) } /* Inverse probing */ - aux = arg->inverse = inverse_cube(arg->cube); - if (!((1<last1) & udmask) || (arg->ed->inverse_ud == -1)) { - arg->ed->inverse_ud = ptableval(&pd_khuge_HTM, aux); - } - UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target); - if (!((1<last1) & fbmask) || (arg->ed->inverse_fb == -1)) { - aux = apply_trans(fd, arg->inverse); - arg->ed->inverse_fb = ptableval(&pd_khuge_HTM, aux); - } - UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target); - if (!((1<last1) & rlmask) || (arg->ed->inverse_rl == -1)) { - aux = apply_trans(rf, arg->inverse); - arg->ed->inverse_rl = ptableval(&pd_khuge_HTM, aux); + if (!((1<last1) & htmask)) { + aux = arg->inverse = inverse_cube(arg->cube); + if (!((1<last1) & udmask) || (arg->ed->inverse_ud==-1)) { + arg->ed->inverse_ud = + ptableval(&pd_drud_sym16_HTM, aux); + } + UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target); + if (!((1<last1) & fbmask) || (arg->ed->inverse_fb==-1)) { + aux = apply_trans(fd, arg->inverse); + arg->ed->inverse_fb = + ptableval(&pd_drud_sym16_HTM, aux); + } + UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target); + if (!((1<last1) & rlmask) || (arg->ed->inverse_rl==-1)) { + aux = apply_trans(rf, arg->inverse); + arg->ed->inverse_rl = + ptableval(&pd_drud_sym16_HTM, aux); + } + UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target); + } else { + UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target); + UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target); + UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target); } - UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target); /* Michel de Bondt's trick*/ if (arg->ed->inverse_ud == arg->ed->inverse_fb && @@ -1246,26 +1294,26 @@ estimate_optimal_HTM(DfsArg *arg) UPDATECHECKSTOP(ret, arg->ed->inverse_ud + 1, target); } - /* nxopt trick */ + /* nxopt trick + half turn trick */ if (arg->ed->normal_ud == target) - arg->badmovesinv |= udmask; + arg->badmovesinv |= udmask | htmask; if (arg->ed->normal_fb == target) - arg->badmovesinv |= fbmask; + arg->badmovesinv |= fbmask | htmask; if (arg->ed->normal_rl == target) - arg->badmovesinv |= rlmask; + arg->badmovesinv |= rlmask | htmask; if (arg->ed->inverse_ud == target) - arg->badmoves |= udmask; + arg->badmoves |= udmask | htmask; if (arg->ed->inverse_fb == target) - arg->badmoves |= fbmask; + arg->badmoves |= fbmask | htmask; if (arg->ed->inverse_rl == target) - arg->badmoves |= rlmask; + arg->badmoves |= rlmask | htmask; return arg->ed->oldret = ret; } static int -estimate_light_HTM(DfsArg *arg) +estimate_nxoptlike(DfsArg *arg, PruneData *pd) { int target, ret; Cube aux; @@ -1276,9 +1324,6 @@ estimate_light_HTM(DfsArg *arg) (1<d - arg->current_alg->len; @@ -1291,18 +1336,17 @@ estimate_light_HTM(DfsArg *arg) UPDATECHECKSTOP(ret, arg->ed->corners, target); /* Normal probing */ - arg->ed->normal_ud = ptableval(&pd_drud_sym16_HTM, arg->cube); + arg->ed->normal_ud = ptableval(pd, arg->cube); UPDATECHECKSTOP(ret, arg->ed->normal_ud, target); aux = apply_trans(fd, arg->cube); - arg->ed->normal_fb = ptableval(&pd_drud_sym16_HTM, aux); + arg->ed->normal_fb = ptableval(pd, aux); UPDATECHECKSTOP(ret, arg->ed->normal_fb, target); aux = apply_trans(rf, arg->cube); - arg->ed->normal_rl = ptableval(&pd_drud_sym16_HTM, aux); + arg->ed->normal_rl = ptableval(pd, aux); UPDATECHECKSTOP(ret, arg->ed->normal_rl, target); - /* If ret == 0, it's solved (corners + triple slice solved) */ if (ret == 0) - return 0; + return arg->step->is_done(arg->cube) ? 0 : 1; /* Michel de Bondt's trick*/ if (arg->ed->normal_ud == arg->ed->normal_fb && @@ -1311,30 +1355,21 @@ estimate_light_HTM(DfsArg *arg) } /* Inverse probing */ - if (!((1<last1) & htmask)) { - aux = arg->inverse = inverse_cube(arg->cube); - if (!((1<last1) & udmask) || (arg->ed->inverse_ud==-1)) { - arg->ed->inverse_ud = - ptableval(&pd_drud_sym16_HTM, aux); - } - UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target); - if (!((1<last1) & fbmask) || (arg->ed->inverse_fb==-1)) { - aux = apply_trans(fd, arg->inverse); - arg->ed->inverse_fb = - ptableval(&pd_drud_sym16_HTM, aux); - } - UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target); - if (!((1<last1) & rlmask) || (arg->ed->inverse_rl==-1)) { - aux = apply_trans(rf, arg->inverse); - arg->ed->inverse_rl = - ptableval(&pd_drud_sym16_HTM, aux); - } - UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target); - } else { - UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target); - UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target); - UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target); + aux = arg->inverse = inverse_cube(arg->cube); + if (!((1<last1) & udmask) || (arg->ed->inverse_ud == -1)) { + arg->ed->inverse_ud = ptableval(pd, aux); + } + UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target); + if (!((1<last1) & fbmask) || (arg->ed->inverse_fb == -1)) { + aux = apply_trans(fd, arg->inverse); + arg->ed->inverse_fb = ptableval(pd, aux); + } + UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target); + if (!((1<last1) & rlmask) || (arg->ed->inverse_rl == -1)) { + aux = apply_trans(rf, arg->inverse); + arg->ed->inverse_rl = ptableval(pd, aux); } + UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target); /* Michel de Bondt's trick*/ if (arg->ed->inverse_ud == arg->ed->inverse_fb && @@ -1342,24 +1377,25 @@ estimate_light_HTM(DfsArg *arg) UPDATECHECKSTOP(ret, arg->ed->inverse_ud + 1, target); } - /* nxopt trick + half turn trick */ + /* nxopt trick */ if (arg->ed->normal_ud == target) - arg->badmovesinv |= udmask | htmask; + arg->badmovesinv |= udmask; if (arg->ed->normal_fb == target) - arg->badmovesinv |= fbmask | htmask; + arg->badmovesinv |= fbmask; if (arg->ed->normal_rl == target) - arg->badmovesinv |= rlmask | htmask; + arg->badmovesinv |= rlmask; if (arg->ed->inverse_ud == target) - arg->badmoves |= udmask | htmask; + arg->badmoves |= udmask; if (arg->ed->inverse_fb == target) - arg->badmoves |= fbmask | htmask; + arg->badmoves |= fbmask; if (arg->ed->inverse_rl == target) - arg->badmoves |= rlmask | htmask; + arg->badmoves |= rlmask; return arg->ed->oldret = ret; } + static bool always_valid(Alg *alg) { -- cgit v1.3