/* POTM ENTRY : shufflemania */ /* Author : Stan Peijffers */ /* E-mail : s.peijffers@ns-nl.att.com */ /* Shufflemania is based on hybrid search. It contains 2 search algoritms that (recursively) call each other. The first search algoritm is an Iterative Deepening A* (IDA*) Algorithm. This is a well known algoritm initially developped by Korf (ref Artificial Intelligence 27 (1985)). It has the following characteristics : - depth-first search using an evaluation function f* f* = g* + h* where g* = number of moves sofar h* = (underestimate of the) number of moves to reach goal = sum of Manhattan distances - looks for an optimal solution - does not eliminate duplicate positions - requires little memory (it is a recursive algoritm that only uses stack space) - rather CPU intensive The second search algoritm is a variant of the A* algorithm (as described in any book on heuristic search). It has the following characteristics : - heuristic search using an evaluation function f* that systematically overestimates the distance to the goal f* = g* + a.h* where g* = number of moves sofar h* = (overestimate of the) number of moves to reach goal a = factor that increases weigth of h* as the search goes deeper. Note that the original A* algorithm works with a h* function that always UNDERestimates the distance to the goal and has an "a" factor that DEcreases the weight of h* as the search goes deeper. - The advantage of using an h* function that does not have to underestimate the distance to the goal (typically h* is the sum of the Manhattan distances) is that the h* function can be tailored to steer the search into a particular direction. The h* function used is the following : h* = sum over all tiles of "long" distances, where "long" distance is dependent on the number of moves (as opposed to distance) to make to get the tile to the goal. This dependency takes into account the actual distance to the goal, and this dependency is non-linear, such that higher distances are favored more than lower distances. (It is indeed rather wasteful to spend time in placing tiles at the correct place when there are still many tiles far away from their final place). Another dependency which is factored in is the degree of mobility of a tile. There are 3 different levels of mobility : corner tiles (A,E, etc), border tiles and central tiles. The dependency on the h* function is such that corner tiles are more mobile (i.e moved more quickly) than border tiles, which are more mobile than central tiles. The net result of this is that the algorithm will first of all attempt to get corner tiles in place before border tiles, before central tiles. - does not strictly expand nodes on a best-first basis. - does not use a single queue, rather a set of queues. - performs a substantial amount of pruning + solutions that deviate too much from the best solution sofar are pruned. + solutions that will not be able to improve on the currently best solution are pruned (To this end a second h* function based on Manhattan distances is maintained as well, but this second h* function does not steer the search. It is only used for pruning). - When memory becomes full, the most-promising position is used as the starting point for a new search. As a consequence of the above limitations : does not search for optimal solutions (but recognizes an optimal solution when it sees one). - does not eliminate duplicate positions (only avoids sequences of moves that would generate duplicates such as lr, du, etc) - requires a lot of memory for the queues - prime characteristics of the algoritm are : speed and the possibility of generating long sequences of moves leading to (sub)optimal solutions. These 2 algoritms are complementary from a CPU and memory usage viewpoint. The solution that was adopted is a hybrid search based on the above 2 algoritms where the IDA* algorithm is used at the top of the search tree and the A* algorithm used at the bottom of the search tree. This approach has been mentioned in "Heuristics : Intelligent Search Strategies for Computer Problem Solving" By Judea Pearl. [Note : an interesting article describing a hybrid search method with A* used at the top and IDA* used at the bottom is "Effective use of memory in iterative deepening search" by Sarkar, Chakrabarti, Ghose, De Sarkar - Information Processing Letters 42(1992).] The depth d0 at which the IDA* algoritm stops and hands over control to the A* algorithm is fixed and is a linear function of the "complexity" of the initial problem (complexity = number of misplaced tiles). The upperbound for d0 is 30. This means that in practice problems with an optimal solution less than or a little over 30 moves will always be found. In a number of instances the A* algorithm calls the IDA* algorithm (and the associated A* algorithms) again lower in the search tree. The IDA* algorithm is then called at the point where the next higher IDA* algorithm was stopped. This happens in 3 cases : 1. A* detects a new solution which is an improvment over the currently best solution. IDA* is called to see whether it is not possible to still improve the solution. 2. A* has found too many "promising" intermediate solutions (i.e queue overflow). This is an interesting situation in which an IDA* search may uncover good solutions. (Note that in "normal" situations the queue overflow will not happen because of the substantial amount of pruning in A*). 3. A* has not found a solution at all. i.e all examined positions are worse than the starting position. This happens e.g in cases where all tiles are in place except for 2 that need to be swapped. The maximum depth of recursive calls to the IDA* algorithm is limited to 4. Some other characteristics of the program : - The algorithm stops when the 10 minute limit is reached (unless an optimal solution is found by either the IDA* or the A* algoritm). A time check is made at anytime the A* algorithm is started. - The handover point between IDA* and A* is not exactly d0, but the first "negative" move before d0 is reached. This is done to avoid working with locally optimized solutions detected by IDA*. */ #include "stdio.h" #include/* for the TMS structure */ #define CLK_TCK 100 /* Note: this may be different on YOUR box, you might find the value of HZ in YOUR param.h, but it's gotta be 100 when you ship your entry! Alternatively, use sysconf to deduce CLK_TCK - this approach should work on both systems! */ /* location of center */ #define center 12 #define LEFT 0 #define RIGHT 1 #define UP 2 #define DOWN 3 #define TRANS 4 #define SOL_FND 0 /* solution found */ #define ISOL_FND 1 /* intermediate solution found */ #define NOSOL_FND 2 /* no solution found */ #define NBSOL_FND 3 /* no better solution found */ #define IDA_CONT 0 /* continue IDA search */ #define IDA_STOP 1 /* stop IDA search */ #define IDA_TOUT 2 /* time out IDA search */ #define PSZ 5 /* dimension of puzzle */ #define PSIZE 25 /* total size of puzzle */ #define POSSZ 5 /* size of puzzle representation (in words) */ #define NBR_MOVES 5 /* number of moves : lrudt */ #define NBR_PASS 2 /* number of passes */ #define NBR_LVL1 2 /* number of IDA levels (normal case) */ #define NBR_LVL 4 /* number of IDA levels (tricky case) */ #define SOME_HIGH_VAL 30000 #define NREIDA 0 /* no reiteration of IDA */ #define REIDA1 1 /* reiteration of IDA reason 1 */ #define REIDA2 2 /* reiteration of IDA reason 2 */ #define REIDA3 3 /* reiteration of IDA reason 3 */ #define IDAMK 0 /* IDA position marked */ #define IDANMK 1 /* IDA position not marked */ #define IDAMKDUP 2 /* IDA position marked as a duplicate */ /* heuristics */ #define IDAMAXDP 31 /* depth d0 at which IDA stops */ #define IDAINCDP 10 /* increment to calculate new d0 for IDA searches lower in the tree */ #define GHPRUN 1000 /* pruning value used in A* algorithm. = max deviation from best solution so far */ #define GHEPS 200 /* factor applied to h* in A* algorithm */ #define GHFVAL 100 /* factor applied to f* in A* algorithm */ /* representation of a "move" in recursive IDA algorithm */ typedef struct tmove { struct tmove *mdir_ptr; /* pointer to previous "move" */ int mpos[5]; /* representation of current position */ int mspp; /* position of space in mpos */ int mdir; /* direction by which current position reached = dulrt */ int mval; /* value f* of current position */ int mmark; /* mark : position already elaborated by an A* search or not */ } move; /* 25x25 table showing Manhattan distances (generated) */ int manhtab[PSIZE*PSIZE] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,1,2,2,3,4,2,2,1,2,3,3,3,2,3,4,4,4,3,4,5, 1,0,1,2,3,2,1,2,3,4,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5, 2,1,0,1,2,3,2,1,2,3,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5, 3,2,1,0,1,4,3,2,1,2,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5, 4,3,2,1,0,4,3,2,2,1,3,2,1,2,2,4,3,2,3,3,5,4,3,4,4, 1,2,3,4,5,0,1,2,3,4,1,2,1,2,3,2,3,2,3,4,3,4,3,4,5, 2,1,2,3,4,1,0,1,2,3,2,1,1,2,3,3,2,2,3,4,4,3,3,4,5, 3,2,1,2,3,2,1,0,1,2,3,2,1,2,3,4,3,2,3,4,5,4,3,4,5, 4,3,2,1,2,3,2,1,0,1,3,2,1,1,2,4,3,2,2,3,5,4,3,3,4, 5,4,3,2,1,4,3,2,1,0,3,2,1,2,1,4,3,2,3,2,5,4,3,4,3, 2,3,3,4,5,1,2,2,3,4,0,1,1,2,3,1,2,2,3,4,2,3,3,4,5, 3,2,3,4,5,2,1,2,3,4,1,0,1,2,3,2,1,2,3,4,3,2,3,4,5, 4,3,2,3,4,3,2,1,2,3,2,1,0,1,2,3,2,1,2,3,4,3,2,3,4, 5,4,3,2,3,4,3,2,1,2,3,2,1,0,1,4,3,2,1,2,5,4,3,2,3, 5,4,3,3,2,4,3,2,2,1,3,2,1,1,0,4,3,2,2,1,5,4,3,3,2, 3,4,3,4,5,2,3,2,3,4,1,2,1,2,3,0,1,2,3,4,1,2,3,4,5, 4,3,3,4,5,3,2,2,3,4,2,1,1,2,3,1,0,1,2,3,2,1,2,3,4, 5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,2,1,0,1,2,3,2,1,2,3, 5,4,3,3,4,4,3,2,2,3,3,2,1,1,2,3,2,1,0,1,4,3,2,1,2, 5,4,3,4,3,4,3,2,3,2,3,2,1,2,1,4,3,2,1,0,5,4,3,2,1, 4,4,3,4,5,3,3,2,3,4,2,2,1,2,3,1,2,2,3,4,0,1,2,3,4, 5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,2,1,2,3,4,1,0,1,2,3, 5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,3,2,1,2,3,2,1,0,1,2, 5,4,3,4,5,4,3,2,3,4,3,2,1,2,3,4,3,2,1,2,3,2,1,0,1}; /* 25x25 table showing long distances (generated by the following algorithm : #include "stdio.h" #define min(x,y) (((x)>(y))?(y):(x)) #define get_x(loc) ((loc) % 5) #define get_y(loc) ((loc) / 5) #define indx(x,y) (((y)*5) + (x)) #define PSIZE 25 int a1[PSIZE] = { 12,8,4,8,12,8,4,2,4,8,4,2,0,2,4,8,4,2,4,8,12,8,4,8,12}; int a2[3*PSIZE] = {0,0,6,12,18,0,4,8,14,20,6,8,12,16,22,12,14,16,20,24,18,20,22,24,28, 0,0,5,10,15,0,3,6,11,16,5,6,9,12,17,10,11,12,15,18,15,16,17,18,21, 0,0,4,8,12,0,2,5,9,13,4,5,7,10,14,8,9,10,12,15,12,13,14,15,17}; int mob[PSIZE] = {2,3,3,3,2,3,4,4,4,3,3,4,4,4,3,3,4,4,4,3,2,3,3,3,2}; #define center 12 #define DIST(loc1,loc2) (abs(get_x(loc1) - get_x(loc2)) + abs(get_y(loc1) - get_y(loc2))) #define XDIST(loc1,loc2) (abs(get_x(loc1) - get_x(loc2))) #define YDIST(loc1,loc2) (abs(get_y(loc1) - get_y(loc2))) main() { int ppos, piece, d1, d2; for (piece=1; piece < PSIZE; piece++) { printf("\n"); for (ppos=0; ppos < PSIZE; ppos ++) { d1 = DIST(ppos, piece-1); d2 = 0; if (d1 != 0) { d1 = a1[ppos]+1; d2 = a2[(mob[piece-1]-2)*PSIZE + indx(XDIST(ppos,piece-1),YDIST(ppos,piece-1))]; d2 += 1; } printf("%d,", min(d1,d2)); } } } */ int brkltab[PSIZE*PSIZE] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,5,9,13,1,5,3,5,9,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13, 1,0,1,6,11,4,1,3,5,9,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13, 6,1,0,1,6,7,4,1,4,7,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13, 11,6,1,0,1,9,5,3,1,4,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13, 13,9,5,1,0,9,5,3,5,1,5,3,1,3,5,9,5,3,5,9,13,9,5,9,13, 1,4,5,9,13,0,1,3,5,9,1,3,1,3,5,6,5,3,5,9,11,9,5,9,13, 3,1,3,6,10,1,0,1,5,9,3,1,1,3,5,6,5,3,5,9,10,9,5,9,13, 6,3,1,3,6,5,1,0,1,5,5,3,1,3,5,8,5,3,5,8,11,9,5,9,11, 10,6,3,1,3,9,5,1,0,1,5,3,1,1,3,9,5,3,5,6,13,9,5,9,10, 13,9,5,4,1,9,5,3,1,0,5,3,1,3,1,9,5,3,5,6,13,9,5,9,11, 6,7,5,9,13,1,4,3,5,9,0,1,1,3,5,1,4,3,5,9,6,7,5,9,13, 6,5,5,8,11,3,1,3,5,9,1,0,1,3,5,3,1,3,5,9,6,5,5,8,11, 8,6,5,6,8,6,3,1,3,6,5,1,0,1,5,6,3,1,3,6,8,6,5,6,8, 11,8,5,5,6,9,5,3,1,3,5,3,1,0,1,9,5,3,1,3,11,8,5,5,6, 13,9,5,7,6,9,5,3,4,1,5,3,1,1,0,9,5,3,4,1,13,9,5,7,6, 11,9,5,9,13,6,5,3,5,9,1,3,1,3,5,0,1,3,5,9,1,4,5,9,13, 10,9,5,9,13,6,5,3,5,9,3,1,1,3,5,1,0,1,5,9,3,1,3,6,10, 11,9,5,9,11,8,5,3,5,8,5,3,1,3,5,5,1,0,1,5,6,3,1,3,6, 13,9,5,9,10,9,5,3,5,6,5,3,1,1,3,9,5,1,0,1,10,6,3,1,3, 13,9,5,9,11,9,5,3,5,6,5,3,1,3,1,9,5,3,1,0,13,9,5,4,1, 13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,1,5,3,5,9,0,1,5,9,13, 13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,4,1,3,5,9,1,0,1,6,11, 13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,7,4,1,4,7,6,1,0,1,6, 13,9,5,9,13,9,5,3,5,9,5,3,1,3,5,9,5,3,1,4,11,6,1,0,1}; /* 5x25 table representing next positions (generated). -1 means : invalid */ int nexttab[5*PSIZE] = { -1,1,-1,5,12, 0,2,-1,6,12, 1,3,-1,7,12, 2,4,-1,8,12, 3,-1,-1,9,12, -1,6,0,10,12, 5,7,1,11,12, 6,8,2,12,-1, 7,9,3,13,12, 8,-1,4,14,12, -1,11,5,15,12, 10,12,6,16,-1, 11,13,7,17,-1, 12,14,8,18,-1, 13,-1,9,19,12, -1,16,10,20,12, 15,17,11,21,12, 16,18,12,22,-1, 17,19,13,23,12, 18,-1,14,24,12, -1,21,15,-1,12, 20,22,16,-1,12, 21,23,17,-1,12, 22,24,18,-1,12, 23,-1,19,-1,12 }; int maxtime[NBR_PASS] = {10, 580}; /* time control : one for each pass */ int pass; int solution[200]; /* current best solution */ /* a set of indices pointing to various points in "solution" + counters for the number of transports in each part of "solution" */ int solix; /* index to end of ida solution and begin of A* solution */ int solix_tcnt; /* number of transports in ida part of solution */ int solval; /* length of solution (number of moves) */ int soltcnt; /* number of transports in solution */ int solstart; /* start of ida solution */ int solst_tcnt; /* number of transports in part of solution preceeding start of ida solution */ /* a set of parameters which are used by the IDA algorithm. There is an instance for each recursion level of IDA */ int minnval[NBR_LVL]; /* next minimum value for IDA */ int cutoff[NBR_LVL]; /* cutoff value for current iteration of iDA */ int fnd_sol[NBR_LVL]; /* minimum number of A* runs */ int maxdepth[NBR_LVL]; /* d0 */ int idalevel; /* recursion level of IDA */ int tghsol[200]; /* place to store (temporarily) the solution found by A* */ /* representation of a position used by the A* algorithm = same representation as used in the IDA algorithm */ typedef struct { int compos[POSSZ]; } tiles; /* representation of initial position, position of space, and f* value */ int strt_position[POSSZ]; int strt_pos_sp; int strt_valpos; /* representation of position, position of space, and f* value used at start of each pass */ int position[POSSZ]; int pos_sp; int valpos; int lastmove; int nbr_mpp; /* number of misplaced tiles in the initial position */ int locked[PSIZE]; /* array of tiles which are locked during prepass */ #define MAX_NQUE 50 /* maximum number of queues (A* alg) */ #define MAX_SQUE 10000 /* size of a queue (A* alg) */ int que_head[MAX_NQUE]; /* head of queue */ int que_tail[MAX_NQUE]; /* tail of queue */ int prunval[MAX_NQUE]; /* pruning values in each queue */ /* pointers to malloc-ed space for A* queues */ tiles *gh_pos; /* space for position representations */ int *sp_pos; /* space for space-positions */ int *feval; /* space for f* values (f* = g* + a.h*) */ int *heval; /* space for h* values */ int *geval; /* space for g* values */ int *mov_dir; /* space for move directions */ int *prev_que; /* space for pointers to previous elements */ int start_que; /* pointer to start of first queue */ int ifile; /* file descriptor */ int mineval, bstque; /* value and index of best position (in A* algo) */ int shcnt; /* number of moves of solution found by A* algo */ int trancnt; /* number of transports in solution found by A* algo */ main(argc,argv) int argc; char **argv; { int j; /* open input file */ ifile = open(argv[1], 0); /* initialize */ init_mat(); /* if all tiles are in place (never know) -> exit */ if (strt_valpos == 0) exit (0); /* calculate d0 for IDA search depth */ maxdepth[0] = IDAMAXDP - (PSIZE-nbr_mpp+1)/2; /* There are 2 passes : - an initial pass (in which all correctly placed tiles are locked) - the main pass The initial pass is just a wild shot whose only purpose is to find quick solutions to tricky positions. Its effect is limited (but it doesn't hardly cost anything). */ for (pass=((nbr_mpp<=16)?0:1); pass< NBR_PASS; pass++) { /* initialize position */ for (j=0; j = maxtime[pass]) return 1; return 0; } init_mat() { int i,j; char s[6]; int ppos,piece; /* read input file */ for (j=0; j > ((ppos % POSSZ)*5)) & 0x1f)) != 0) { if (manhtab[piece*PSIZE+ppos] != 0) nbr_mpp++; else locked[ppos] = 1; strt_valpos += manhtab[piece*PSIZE+ppos]; } /* initialize value of solution to sime high value */ solval = SOME_HIGH_VAL; soltcnt = 0; } ida_search(pos, spp, oldval, lmove) int (*pos)[]; int spp; int oldval; int lmove; { move initdir; int i,ret; /* initialize a "move" structure with its initial values */ initdir.mdir = lmove; initdir.mmark = IDANMK; initdir.mval = oldval; initdir.mspp = spp; for (i=0; i mmark == IDANMK) { mdir->mmark = IDAMK; if (mdir->mval != oldval) { break; } mdir = mdir->mdir_ptr; } else if (mdir->mmark == IDAMK) { break; } else { return IDA_CONT; } } /* mdir contains the position from which an A* search will be started. Mark it. */ mdir->mmark = IDAMKDUP; /* depth - j is the length of the resulting intermediate solution from IDA. */ idacnt = shcnt = depth-j; trancnt = 0; /* initialize the queue for the A* search */ hval = init_que(mdir, solstart+shcnt); done = ISOL_FND; nbr_ghp=1; reida = NREIDA; /* The A* search continues as long as intermediate solutions are found */ while (done == ISOL_FND) { done = gh_search(&que_in); /* A* search did not find a solution better than the current one. Return.*/ if (done == NBSOL_FND) { return IDA_CONT; } /* A* search did not find a solution at all. Prepare an additional IDA search. */ if (done == NOSOL_FND) { reida = REIDA3; for (k=0; k mpos[k]; pos_sp = mdir->mspp; valpos = mdir->mval - idacnt; lastmove = mdir->mdir; break; } /* A* search found an intermediate solution. Either - reinit the A* queue and restart the A* algorithm, or - prepare an additional IDA search, or - abandon the search and return */ if (done == ISOL_FND) if (fnd_sol[idalevel] > nbr_ghp++) { sv_ghsol(que_in); reinit_que(que_in); } else { if (idalevel == 0) { reida = REIDA2; for (k=0; k mpos[k]; pos_sp = mdir->mspp; valpos = mdir->mval - idacnt; lastmove = mdir->mdir; break; } else return IDA_CONT; } else { fnd_sol[idalevel] = nbr_ghp; break; } } /* temporarily save the A* solution (if there is one) */ if (reida == REIDA3) trancnt = trascnt = 0; else { sv_ghsol(que_in); trascnt = trancnt; } /* count number of transports in the A* solution */ if ((shcnt + solstart <= solval) || (reida)) { tmdir = mdir; for (k=idacnt-1;k>=0;k--) { if (tmdir->mdir == TRANS) trancnt++; tmdir = tmdir->mdir_ptr; } } trascnt = trancnt - trascnt; /* If the solution found by A* is an improvment over the currently best (either because of less moves, or because of less transport moves, then prepare an extra IDA search. */ if (!reida) { if ((shcnt + solstart < solval) || ((shcnt + solstart == solval) && (trancnt + solst_tcnt < soltcnt))) { if (shcnt + solstart < solval) reida = REIDA1; solix = solstart; sv_idasol(mdir, idacnt); for (i=idacnt; i mpos[i]; pos_sp = mdir->mspp; valpos = mdir->mval - idacnt; lastmove = mdir->mdir; } /* This check detects optimal solutions from the A* search. I.e. when the number of moves from A* is lower or equal to the estimated minimal number of moves, then this has to be an optimal solution. Therfore, stop the search. */ if (shcnt - idacnt <= hval + oldval - mdir->mval) { return IDA_STOP; } } /* This is the time to restart an IDA search as prepared before */ if (((((reida == REIDA1) && (nbr_ghp <= 1)) || ((reida == REIDA2) && (nbr_ghp <= 2))) && (idalevel < NBR_LVL1-1)) || ((reida == REIDA3) && (idalevel < NBR_LVL-1))) { solix = solstart; solstart += idacnt; solst_tcnt += trascnt; /* maxdepth (d0) is set to either the d0 value of the outer level IDA search (when REIDA3), or to the number of moves that had been backed up from the previous IDA search + some increment (when !REIDA3). */ maxdepth[++idalevel] = ((reida == REIDA3)?maxdepth[0]:(j + IDAINCDP)); /* call IDA search again */ ret = ida_search(position, pos_sp, valpos, lastmove); idalevel--; solstart -= idacnt; solst_tcnt -= trascnt; /* When this new IDA search finds a solution (this is checked by comparing solstart (start index of IDA search) and solix (end index of IDA search), for the case REIDA1 the previous IDA solution still needs to be stored. */ if ((solix != solstart) && (reida != REIDA1)) { /* still store solution */ solix = solstart; sv_idasol(mdir, idacnt); solix = solstart + idacnt; solix_tcnt = solst_tcnt + trascnt; } if (ret == IDA_TOUT) return IDA_TOUT; else /* IDA_STOP */ if (idalevel < NBR_LVL1-1) return IDA_CONT; else { return IDA_STOP; } } else return IDA_CONT; } /* The heart of the IDA algorithm */ df_search(pos, spp, oldval, dir, depth) int (*pos)[]; int spp; int oldval; move *dir; int depth; { move movdir, *tmdir; int newval; int nspp; int d12old; int d12new; int i,k,ret; int npiece; int trascnt; movdir.mdir_ptr = dir; /* If d0 reached : - check time, - call more_search (A* and/or IDA again), only if the current value equals the cutoff value, otherwize the position was already uncovered during the previous call of df_search. */ if (depth == maxdepth[idalevel]) { if (checktime()) return IDA_TOUT; if (oldval == cutoff[idalevel]) return more_search(oldval, dir, depth); else return IDA_CONT; } else { for (i=0; i mdir != TRANS) && (i == (dir->mdir ^ 1))) continue; /* update new position */ npiece = ((movdir.mpos[nspp/POSSZ] >> ((nspp%POSSZ)*5)) & 0x1f); movdir.mpos[spp/POSSZ] += (npiece << ((spp%POSSZ)*5)); movdir.mpos[nspp/POSSZ] &= (0xfe0fffff >> ((4 - (nspp%POSSZ))*5)); /* calculate new f */ d12old = manhtab[npiece*PSIZE+nspp]; d12new = manhtab[npiece*PSIZE+spp]; newval = oldval + 1 + d12new - d12old; /* If new f greater than the cutoff value, update the cutoff value for the next iteration (when needed), undo the last move and continue with the next one. */ if (newval > cutoff[idalevel]) { if (newval < minnval[idalevel]) minnval[idalevel] = newval; movdir.mpos[nspp/POSSZ] += (npiece << ((nspp%POSSZ)*5)); movdir.mpos[spp/POSSZ] &= (0xfe0fffff >> ((4 - (spp%POSSZ))*5)); continue; } /* store move information */ movdir.mdir = i; movdir.mval = newval; movdir.mmark = IDANMK; movdir.mspp = nspp; /* check to see whether we found a solution */ if (newval <= depth+1) { /* hit the goal */ /* In this case : - save the solution, - count the number of transports - and stop the search. */ solix = solstart; sv_idasol(&movdir, depth+1); solval = solix = solstart + depth + 1; trascnt = 0; tmdir = &movdir; for (k=depth;k>=0;k--) { if (tmdir->mdir == TRANS) trascnt++; tmdir = tmdir->mdir_ptr; } solix_tcnt = soltcnt = solst_tcnt + trascnt; return IDA_STOP; } /* call df_search recursively from new position */ ret = df_search(movdir.mpos, nspp, newval, &movdir, depth+1); if (ret != IDA_CONT) return ret; /* restore nposition */ movdir.mpos[nspp/POSSZ] += (npiece << ((nspp%POSSZ)*5)); movdir.mpos[spp/POSSZ] &= (0xfe0fffff >> ((4 - (spp%POSSZ))*5)); } /* for */ return IDA_CONT; } } sv_idasol(mdir, dpth) move *mdir; int dpth; { int j; for (j=dpth-1; j>=0; j--) { solution[solix+j] = mdir->mdir; mdir = mdir->mdir_ptr; } } init_que(mdir, gval) move *mdir; int gval; { int que_entry; int i,f; int ppos,piece; int fval,hval; /* set all queue pointers to zero */ for (f=0; f mpos[i]; sp_pos[que_entry] = mdir->mspp; /* calculate f* */ fval = hval = 0; for (ppos=0; ppos< PSIZE; ppos++) if ((piece = ((mdir->mpos[ppos / POSSZ] >> ((ppos % POSSZ)*5)) & 0x1f)) != 0) { hval += manhtab[piece*PSIZE+ppos]; fval += brkltab[piece*PSIZE+ppos]; } mov_dir[que_entry] = mdir->mdir; feval[que_entry] = GHFVAL * fval; prev_que[que_entry] = 0; heval[que_entry] = hval; geval[que_entry] = gval; /* set low water marks for best positions */ mineval = GHFVAL * fval; bstque=1; /* initialize pruning values in all queues to some high value */ for (i=0; i< MAX_NQUE; i++) prunval[i] = SOME_HIGH_VAL; /* add this first element to the queue */ que_head[que_entry]++; start_que = que_entry; return hval; } reinit_que(que_in) int que_in; { int que_entry,f,i; /* set all queue pointers to zero */ for (f=0; f = geval[0]) { que_tail[f]++; continue; } csp_pos = sp_pos[que_entry]; /* for every possible move (udlrt) */ for (i=0; i > ((nsp_pos%POSSZ)*5)) & 0x1f); d12old = manhtab[npiece*PSIZE+nsp_pos]; old_d = brkltab[npiece*PSIZE+nsp_pos]; d12new = manhtab[npiece*PSIZE +csp_pos]; new_d = brkltab[npiece*PSIZE+csp_pos]; /* calculate new queue */ new_q = f + 1 + new_d - old_d; /* calculate new f* */ new_f = feval[que_entry] + feval[que_entry]/GHEPS + GHFVAL*(new_d -old_d); /* did we find a solution (i.e new h* == 0)? */ if (heval[que_entry] + d12new - d12old == 0) { /* hooray were done */ /* If this solution is better or equally good than the best so far, count number of transports. */ if (geval[que_entry] < geval[0]) { tque = que_entry; trcnt = 0; while (prev_que[tque] != 0) { if (mov_dir[tque] == TRANS) trcnt++; tque = prev_que[tque]; } if (i== TRANS) trcnt++; } found_sol = 1; /* If solution is an improvment, either in terms of number of moves, or number of transports, store this last queue_entry as queue_entry 0. */ if ((geval[que_entry]+1 < geval[0]) || ((geval[que_entry]+1 == geval[0]) && (trcnt < trcnt0))) { /* add entry to queue 0 */ trcnt0 = trcnt; mov_dir[0] = i; prev_que[0] = que_entry; geval[0] = geval[que_entry]+1; *que_in = 0; break; } } /* If the new queue, exceeds number of available queues, well ... just drop and continue. */ if (new_q >= MAX_NQUE) continue; /* If the new queue lies before the current queue, put the entry in the current queue, since we want to traverse queues strictly from start to finish in a sequential order (for reasons of speed). */ if (new_q < f) { new_q =f; } /* compare new g+h value with g+h value of the best solution so far. If greater, prune. */ nsolval = heval[que_entry] + d12new - d12old +geval[que_entry] + 1; if (nsolval > solval) continue; /* compare new f* value with the best f* value in this queue so far. If deviation is more than 1000, prune. This is a very tight heuristic. */ if (new_f > prunval[new_q]+ GHPRUN) continue; if (feval[que_entry] < prunval[new_q]) prunval[new_q] = feval[que_entry]; /* Now put this new position in its new queue position */ /* If the new queue is full, just pick the next one */ if(que_head[new_q] > MAX_SQUE-1) { while ((new_q++ < MAX_NQUE) && (que_head[new_q] > MAX_SQUE-1)); /* If all queues are full, terminate search with either - SOL_FND if a solution was found - ISOL_FND if no solution found but there is a position from which a new search can be started - NOSOL_FND if no solution found. */ if (new_q >= MAX_NQUE) { if (found_sol) return SOL_FND; if (bstque != 1) { *que_in = bstque; return ISOL_FND; } else { return NOSOL_FND; } } } /* add entry to queue */ new_que = que_head[new_q]*MAX_NQUE+new_q; for (j=0; j > ((4 - (nsp_pos%POSSZ))*5)); sp_pos[new_que] = nsp_pos; /* calculate new distances */ heval[new_que] = heval[que_entry] + d12new - d12old; geval[new_que] = geval[que_entry] + 1; mov_dir[new_que] = i; feval[new_que] = new_f; prev_que[new_que] = que_entry; /* keep track of best position */ if (new_f < mineval) { mineval = new_f; bstque = new_que; } que_head[new_q]++; } que_tail[f]++; } /* while */ que_head[f] = que_tail[f] = 0; } /* for */ /* If all queues have been handled, return - SOL_FND if a solution has been found - NBSOL_FND/NOSOL_FND if no solution found */ if (found_sol) return SOL_FND; else if (pass == 0) return NOSOL_FND; else return NBSOL_FND; } sv_ghsol(que) int que; { int i; int que_in; /* save A* solution in tghsol, and in the process count number of transports. */ que_in = que; for (i=geval[que_in] - solstart -1; i>= shcnt; i--) { tghsol[i] = mov_dir[que_in]; if (tghsol[i] == TRANS) trancnt++; que_in = prev_que[que_in]; } shcnt = geval[que] - solstart; }