home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / next.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  10KB  |  249 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "chess.h"
  4. #include "data.h"
  5.  
  6. /* last modified 03/11/97 */
  7. /*
  8. ********************************************************************************
  9. *                                                                              *
  10. *   NextMove() is used to select the next move from the current move list.     *
  11. *                                                                              *
  12. ********************************************************************************
  13. */
  14. int NextMove(TREE *tree, int ply, int wtm)
  15. {
  16.   register int *bestp, *movep, *sortv, temp;
  17.   register int history_value, bestval, done, index;
  18.  
  19.   switch (tree->next_status[ply].phase) {
  20. /*
  21.  ----------------------------------------------------------
  22. |                                                          |
  23. |   first, try the transposition table move (which will be |
  24. |   the principal variation move as we first move down the |
  25. |   tree).                                                 |
  26. |                                                          |
  27.  ----------------------------------------------------------
  28. */
  29.   case HASH_MOVE:
  30.     tree->next_status[ply].phase=GENERATE_CAPTURE_MOVES;
  31.     if (tree->hash_move[ply]) {
  32.       tree->current_move[ply]=tree->hash_move[ply];
  33.       if (ValidMove(tree,ply,wtm,tree->current_move[ply])) return(HASH_MOVE);
  34.       else Print(128,"bad move from hash table, ply=%d\n",ply);
  35.     }
  36. /*
  37.  ----------------------------------------------------------
  38. |                                                          |
  39. |   generate captures and sort them based on (a) the value |
  40. |   of the captured piece - the value of the capturing     |
  41. |   piece if this is > 0; or, (b) the value returned by    |
  42. |   Swap().                                                |
  43. |                                                          |
  44.  ----------------------------------------------------------
  45. */
  46.   case GENERATE_CAPTURE_MOVES:
  47.     tree->next_status[ply].phase=CAPTURE_MOVES;
  48.     tree->last[ply]=GenerateCaptures(tree, ply, wtm, tree->last[ply-1]);
  49.     tree->next_status[ply].remaining=0;
  50.     if (tree->hash_move[ply]) {
  51.       for (movep=tree->last[ply-1],sortv=tree->sort_value;
  52.            movep<tree->last[ply];movep++,sortv++)
  53.         if (*movep == tree->hash_move[ply]) {
  54.           *sortv=-999999;
  55.           *movep=0;
  56.           tree->hash_move[ply]=0;
  57.         }
  58.         else {
  59.           if (p_values[Piece(*movep)+7] < p_values[Captured(*movep)+7]) {
  60.             *sortv=p_values[Captured(*movep)+7]-p_values[Piece(*movep)+7];
  61.             tree->next_status[ply].remaining++;
  62.           }
  63.           else {
  64.             *sortv=Swap(tree,From(*movep),To(*movep),wtm);
  65.             if (*sortv >= 0)  tree->next_status[ply].remaining++;
  66.           }
  67.         }
  68.     }
  69.     else {
  70.       for (movep=tree->last[ply-1],sortv=tree->sort_value;
  71.            movep<tree->last[ply];movep++,sortv++)
  72.         if (p_values[Piece(*movep)+7] < p_values[Captured(*movep)+7]) {
  73.           *sortv=p_values[Captured(*movep)+7]-p_values[Piece(*movep)+7];
  74.           tree->next_status[ply].remaining++;
  75.         }
  76.         else {
  77.           *sortv=Swap(tree,From(*movep),To(*movep),wtm);
  78.           if (*sortv >= 0)  tree->next_status[ply].remaining++;
  79.         }
  80.     }
  81. /*
  82.  ----------------------------------------------------------
  83. |                                                          |
  84. |   don't disdain the lowly bubble sort here.  the list of |
  85. |   captures is always short, and experiments with other   |
  86. |   algorithms are always slightly slower.                 |
  87. |                                                          |
  88.  ----------------------------------------------------------
  89. */
  90.     do {
  91.       done=1;
  92.       for (movep=tree->last[ply-1],sortv=tree->sort_value;
  93.            movep<tree->last[ply]-1;movep++,sortv++)
  94.         if (*sortv < *(sortv+1)) {
  95.           temp=*sortv;
  96.           *sortv=*(sortv+1);
  97.           *(sortv+1)=temp;
  98.           temp=*movep;
  99.           *movep=*(movep+1);
  100.           *(movep+1)=temp;
  101.           done=0;
  102.         }
  103.     } while(!done);
  104.     tree->next_status[ply].last=tree->last[ply-1];
  105. /*
  106.  ----------------------------------------------------------
  107. |                                                          |
  108. |   try the captures moves, which are in order based on    |
  109. |   the expected gain of material.  captures that lose     |
  110. |   material have been excluded from this phase.           |
  111. |                                                          |
  112.  ----------------------------------------------------------
  113. */
  114.   case CAPTURE_MOVES:
  115.     if (tree->next_status[ply].remaining) {
  116.       tree->current_move[ply]=*(tree->next_status[ply].last);
  117.       *tree->next_status[ply].last++=0;
  118.       tree->next_status[ply].remaining--;
  119.       if (!tree->next_status[ply].remaining) tree->next_status[ply].phase=KILLER_MOVE_1;
  120.       return(CAPTURE_MOVES);
  121.     }
  122.     tree->next_status[ply].phase=KILLER_MOVE_1;
  123. /*
  124.  ----------------------------------------------------------
  125. |                                                          |
  126. |   now, try the killer moves.  this phase tries the two   |
  127. |   killers for the current ply without generating moves,  |
  128. |   which saves time if a cutoff occurs.                   |
  129. |                                                          |
  130.  ----------------------------------------------------------
  131. */
  132.   case KILLER_MOVE_1:
  133.     if ((tree->hash_move[ply] != tree->killer_move1[ply]) &&
  134.         ValidMove(tree,ply,wtm,tree->killer_move1[ply])) {
  135.       tree->current_move[ply]=tree->killer_move1[ply];
  136.       tree->next_status[ply].phase=KILLER_MOVE_2;
  137.       return(KILLER_MOVE_1);
  138.     }
  139.   case KILLER_MOVE_2:
  140.     if ((tree->hash_move[ply] != tree->killer_move2[ply]) &&
  141.         ValidMove(tree,ply,wtm,tree->killer_move2[ply])) {
  142.       tree->current_move[ply]=tree->killer_move2[ply];
  143.       tree->next_status[ply].phase=GENERATE_ALL_MOVES;
  144.       return(KILLER_MOVE_2);
  145.     }
  146.     tree->next_status[ply].phase=GENERATE_ALL_MOVES;
  147. /*
  148.  ----------------------------------------------------------
  149. |                                                          |
  150. |   now, generate all non-capturing moves.                 |
  151. |                                                          |
  152.  ----------------------------------------------------------
  153. */
  154.   case GENERATE_ALL_MOVES:
  155.     tree->last[ply]=GenerateNonCaptures(tree, ply, wtm, tree->last[ply]);
  156.     tree->next_status[ply].phase=HISTORY_MOVES_1;
  157. /*
  158.  ----------------------------------------------------------
  159. |                                                          |
  160. |   now, try the history moves.  this phase takes the      |
  161. |   complete move list, and passes over them in a classic  |
  162. |   selection-sort, choosing the move with the highest     |
  163. |   history score.  this phase is only done one time, as   |
  164. |   it also purges the hash and killer moves from the list.|
  165. |                                                          |
  166.  ----------------------------------------------------------
  167. */
  168.   case HISTORY_MOVES_1:
  169.     tree->next_status[ply].remaining=1;
  170.     tree->next_status[ply].phase=HISTORY_MOVES_2;
  171.     bestval=0;
  172.     bestp=0;
  173.     for (movep=tree->last[ply-1];movep<tree->last[ply];movep++)
  174.       if (*movep && (*movep == tree->hash_move[ply] ||
  175.           *movep == tree->killer_move1[ply] ||
  176.           *movep == tree->killer_move2[ply])) *movep=0;
  177.       else {
  178.         index=*movep&4095;
  179.         history_value= (wtm) ? history_w[index] : history_b[index];
  180.         if (history_value > bestval) {
  181.           bestval=history_value;
  182.           bestp=movep;
  183.         }
  184.       }
  185.     if (bestp) {
  186.       tree->current_move[ply]=*bestp;
  187.       *bestp=0;
  188.       return(HISTORY_MOVES_1);
  189.     }
  190.     goto remaining_moves;
  191. /*
  192.  ----------------------------------------------------------
  193. |                                                          |
  194. |   now, continue with the history moves, but since one    |
  195. |   pass has been made over the complete move list, there  |
  196. |   are no hash/killer moves left in the list, so the test |
  197. |   for these can be avoided.                              |
  198. |                                                          |
  199.  ----------------------------------------------------------
  200. */
  201.   case HISTORY_MOVES_2:
  202.     bestval=0;
  203.     bestp=0;
  204.     for (movep=tree->last[ply-1];movep<tree->last[ply];movep++)
  205.       if (*movep) {
  206.         index=*movep&4095;
  207.         history_value= (wtm) ? history_w[index] : history_b[index];
  208.         if (history_value > bestval) {
  209.           bestval=history_value;
  210.           bestp=movep;
  211.         }
  212.       }
  213.     if (bestval) {
  214.       tree->current_move[ply]=*bestp;
  215.       *bestp=0;
  216.       tree->next_status[ply].remaining++;
  217.       if (tree->next_status[ply].remaining > 3) {
  218.         tree->next_status[ply].phase=REMAINING_MOVES;
  219.         tree->next_status[ply].last=tree->last[ply-1];
  220.       }
  221.       return(HISTORY_MOVES_2);
  222.     }
  223.   remaining_moves:
  224.     tree->next_status[ply].phase=REMAINING_MOVES;
  225.     tree->next_status[ply].last=tree->last[ply-1];
  226. /*
  227.  ----------------------------------------------------------
  228. |                                                          |
  229. |   now try the rest of the set of moves.                  |
  230. |                                                          |
  231.  ----------------------------------------------------------
  232. */
  233.   case REMAINING_MOVES:
  234.     for (;tree->next_status[ply].last<tree->last[ply];
  235.          tree->next_status[ply].last++)
  236.       if (*tree->next_status[ply].last) {
  237.         tree->current_move[ply]=*tree->next_status[ply].last;
  238.         *tree->next_status[ply].last++=0;
  239.         return(REMAINING_MOVES);
  240.       }
  241.     return(NONE);
  242.   
  243.   default:
  244.     Print(4095,"oops!  next_status.phase is bad! [normal %d]\n",
  245.           tree->next_status[ply].phase);
  246.     return(NONE);
  247.   }
  248. }
  249.