home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / quiesce.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  6KB  |  158 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6.  
  7. /* last modified 06/05/98 */
  8. /*
  9. ********************************************************************************
  10. *                                                                              *
  11. *   Quiesce() is the recursive routine used to implement the alpha/beta        *
  12. *   negamax search (similar to minimax but simpler to code.)  Quiesce() is     *
  13. *   called whenever there is no "depth" remaining so that only capture moves   *
  14. *   are searched deeper.                                                       *
  15. *                                                                              *
  16. ********************************************************************************
  17. */
  18. int Quiesce(TREE *tree, int alpha, int beta, int wtm, int ply) {
  19.   register int initial_alpha, value, delta;
  20.   register int *next_move;
  21.   register int *goodmv, *movep, moves=0, *sortv, temp;
  22. /*
  23.  ----------------------------------------------------------
  24. |                                                          |
  25. |   initialize.                                            |
  26. |                                                          |
  27.  ----------------------------------------------------------
  28. */
  29.   if (ply >= MAXPLY-1) return(beta);
  30.   tree->nodes_searched++;
  31.   next_time_check--;
  32.   tree->last[ply]=tree->last[ply-1];
  33.   initial_alpha=alpha;
  34. /*
  35.  ----------------------------------------------------------
  36. |                                                          |
  37. |   now call Evaluate() to produce the "stand-pat" score   |
  38. |   that will be returned if no capture is acceptable.     |
  39. |   if this score is > alpha, then we also have to save    |
  40. |   the "path" to this node as it is the PV that leads     |
  41. |   to this score.                                         |
  42. |                                                          |
  43.  ----------------------------------------------------------
  44. */
  45.   value=Evaluate(tree,ply,wtm,alpha,beta);
  46.   if (value > alpha) {
  47.     if (value >= beta) return(value);
  48.     alpha=value;
  49.     tree->pv[ply].path_length=ply-1;
  50.     tree->pv[ply].path_hashed=0;
  51.     tree->pv[ply].path_iteration_depth=iteration_depth;
  52.   }
  53. /*
  54.  ----------------------------------------------------------
  55. |                                                          |
  56. |   generate captures and sort them based on (a) the value |
  57. |   of the captured piece - the value of the capturing     |
  58. |   piece if this is > 0; or, (b) the value returned by    |
  59. |   Swap().  if the value of the captured piece won't      |
  60. |   bring the material score back up to near alpha, that   |
  61. |   capture is discarded as "futile."                      |
  62. |                                                          |
  63.  ----------------------------------------------------------
  64. */
  65.   tree->last[ply]=GenerateCaptures(tree, ply, wtm, tree->last[ply-1]);
  66.   delta=alpha-50-(wtm?Material:-Material);
  67.   goodmv=tree->last[ply-1];
  68.   sortv=tree->sort_value;
  69.   for (movep=tree->last[ply-1];movep<tree->last[ply];movep++)
  70.     if (p_values[Captured(*movep)+7]+p_values[Promote(*movep)+7] >= delta) {
  71.       if (Captured(*movep) == king) return(beta);
  72.       if (p_values[Piece(*movep)+7] < p_values[Captured(*movep)+7] ||
  73.           (p_values[Piece(*movep)+7] <= p_values[Captured(*movep)+7] &&
  74.            delta<=0)) {
  75.         *goodmv++=*movep;
  76.         *sortv++=p_values[Captured(*movep)+7];
  77.         moves++;
  78.       }
  79.       else {
  80.         temp=Swap(tree,From(*movep),To(*movep),wtm);
  81.         if (temp >= 0) {
  82.           *sortv++=temp;
  83.           *goodmv++=*movep;
  84.           moves++;
  85.         }
  86.       }
  87.     }
  88. /*
  89.  ----------------------------------------------------------
  90. |                                                          |
  91. |   don't disdain the lowly bubble sort here.  the list of |
  92. |   captures is always short, and experiments with other   |
  93. |   algorithms are always slightly slower.                 |
  94. |                                                          |
  95.  ----------------------------------------------------------
  96. */
  97.   if (moves > 1) {
  98.     register int done;
  99.     register int *end=tree->last[ply-1]+moves-1;
  100.     do {
  101.       done=1;
  102.       sortv=tree->sort_value;
  103.       movep=tree->last[ply-1];
  104.       for (;movep<end;movep++,sortv++)
  105.         if (*sortv < *(sortv+1)) {
  106.           temp=*sortv;
  107.           *sortv=*(sortv+1);
  108.           *(sortv+1)=temp;
  109.           temp=*movep;
  110.           *movep=*(movep+1);
  111.           *(movep+1)=temp;
  112.           done=0;
  113.         }
  114.     } while(!done);
  115.   }
  116.   next_move=tree->last[ply-1];
  117. /*
  118.  ----------------------------------------------------------
  119. |                                                          |
  120. |   now iterate through the move list and search the       |
  121. |   resulting positions.                                   |
  122. |                                                          |
  123.  ----------------------------------------------------------
  124. */
  125.   while (moves--) {
  126.     tree->current_move[ply]=*(next_move++);
  127. #if !defined(FAST)
  128.     if (ply <= trace_level)
  129.       SearchTrace(tree,ply,0,wtm,alpha,beta,"quiesce",CAPTURE_MOVES);
  130. #endif
  131.     MakeMove(tree,ply,tree->current_move[ply],wtm);
  132.     value=-Quiesce(tree,-beta,-alpha,ChangeSide(wtm),ply+1);
  133.     UnMakeMove(tree,ply,tree->current_move[ply],wtm);
  134.     if (value > alpha) {
  135.       if(value >= beta) return(value);
  136.       alpha=value;
  137.     }
  138.     if (tree->stop) return(0);
  139.   }
  140. /*
  141.  ----------------------------------------------------------
  142. |                                                          |
  143. |   all moves have been searched.  return the search       |
  144. |   result that was found.  if the result is not the       |
  145. |   original alpha score, then we need to return the PV    |
  146. |   that is associated with this score.                    |
  147. |                                                          |
  148.  ----------------------------------------------------------
  149. */
  150.   if (alpha != initial_alpha) {
  151.     memcpy(&tree->pv[ply-1].path[ply],&tree->pv[ply].path[ply],
  152.            (tree->pv[ply].path_length-ply+1)*sizeof(int));
  153.     memcpy(&tree->pv[ply-1].path_hashed,&tree->pv[ply].path_hashed,3);
  154.     tree->pv[ply-1].path[ply-1]=tree->current_move[ply-1];
  155.   }
  156.   return(alpha);
  157. }
  158.