commit b6fd508253bce9225dd24b6538adb5093892c4f8
parent e528411b1a1be45e1bef0f525fd0f411c9689b11
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Tue, 7 Dec 2021 12:20:51 +0100
Little performance improvement in optimal solver - more to come!
Diffstat:
10 files changed, 278 insertions(+), 167 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,6 +1,6 @@
# See LICENSE file for copyright and license details.
-VERSION = 2.0beta4
+VERSION = 2.0beta5
PREFIX = /usr/local
MANPREFIX = ${PREFIX}/share/man
diff --git a/TODO.md b/TODO.md
@@ -14,6 +14,9 @@ It's more of a personal reminder than anything else.
* invert an alg
### More steps for `solve`
+* "slow" optimal solver, using drud table but all the tricks
+ of khuge (+ trick to avoid 180° moves when one of the inverse
+ probes returns exactly the target value)
* QTM optimal solving
* Block-building steps (cross, roux blocks, ...)
* Other common steps (LSE, ...)
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/nissy-2.0beta4.tar.gz b/nissy-2.0beta4.tar.gz
Binary files differ.
diff --git a/nissy-2.0beta5.tar.gz b/nissy-2.0beta5.tar.gz
Binary files differ.
diff --git a/nissy.exe b/nissy.exe
Binary files differ.
diff --git a/src/cubetypes.h b/src/cubetypes.h
@@ -81,8 +81,9 @@ typedef struct commandargs CommandArgs;
typedef struct coordinate Coordinate;
typedef struct cube Cube;
typedef struct cubearray CubeArray;
-typedef struct cubetarget CubeTarget;
typedef struct dfsdata DfsData;
+typedef struct estimatedata EstimateData;
+typedef struct localinfo LocalInfo;
typedef struct piecefilter PieceFilter;
typedef struct prunedata PruneData;
typedef struct solveoptions SolveOptions;
@@ -92,7 +93,7 @@ typedef struct threaddata ThreadData;
typedef Cube (*AntiIndexer) (uint64_t);
typedef bool (*Checker) (Cube);
-typedef int (*Estimator) (CubeTarget);
+typedef int (*Estimator) (EstimateData *);
typedef bool (*Validator) (Alg *);
typedef void (*Exec) (CommandArgs *);
typedef uint64_t (*Indexer) (Cube);
@@ -196,13 +197,6 @@ cubearray
};
struct
-cubetarget
-{
- Cube cube;
- int target;
-};
-
-struct
dfsdata
{
int d;
@@ -211,6 +205,7 @@ dfsdata
bool niss;
Move last1;
Move last2;
+ EstimateData * ed;
AlgList * sols;
pthread_mutex_t * sols_mutex;
Alg * current_alg;
@@ -220,6 +215,29 @@ dfsdata
};
struct
+estimatedata
+{
+ Cube cube;
+ int target;
+ Move lastmove;
+ uint64_t movebitmask;
+ LocalInfo * li;
+};
+
+struct
+localinfo
+{
+ int corners;
+ int normal_ud;
+ int normal_fb;
+ int normal_rl;
+ int inverse_ud;
+ int inverse_fb;
+ int inverse_rl;
+ int prev_ret;
+};
+
+struct
piecefilter
{
bool epose;
diff --git 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;
diff --git 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<<U) | (1<<U2) | (1<<U3) |
+ (1<<D) | (1<<D2) | (1<<D3);
+ if (ed->li->inverse_fb == ed->target)
+ ed->movebitmask |= (1<<F) | (1<<F2) | (1<<F3) |
+ (1<<B) | (1<<B2) | (1<<B3);
+ if (ed->li->inverse_rl == ed->target)
+ ed->movebitmask |= (1<<R) | (1<<R2) | (1<<R3) |
+ (1<<L) | (1<<L2) | (1<<L3);
+
+ return ret;
}
static bool
@@ -1076,6 +1120,29 @@ detect_pretrans_drud(Cube cube)
/* Public functions **********************************************************/
void
+free_localinfo(LocalInfo *li)
+{
+ free(li);
+}
+
+LocalInfo *
+new_localinfo()
+{
+ LocalInfo *ret = malloc(sizeof(LocalInfo));
+
+ ret->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)
{
int i;
diff --git a/src/steps.h b/src/steps.h
@@ -7,6 +7,8 @@
extern Step * steps[NSTEPS];
+void free_localinfo(LocalInfo *li);
+LocalInfo * new_localinfo();
void prepare_step(Step *step);
#endif
