home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / searchr.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  12KB  |  299 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6. #include "epdglue.h"
  7.  
  8. /* modified 06/05/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   SearchRoot() is the recursive routine used to implement the alpha/beta     *
  13. *   negamax search (similar to minimax but simpler to code.)  SearchRoot() is  *
  14. *   only called when ply=1.  it is somewhat different from Search() in that    *
  15. *   some things (null move search, hash lookup, etc.) are not useful at the    *
  16. *   root of the tree.  SearchRoot() calls Search() to search any positions     *
  17. *   that are below ply=1.                                                      *
  18. *                                                                              *
  19. ********************************************************************************
  20. */
  21. int SearchRoot(TREE *tree, int alpha, int beta, int wtm, int depth) {
  22.   register int first_move=1;
  23.   register int initial_alpha, value;
  24.   register int extensions, begin_root_nodes;
  25. /*
  26.  ----------------------------------------------------------
  27. |                                                          |
  28. |   initialize.  set NextMove() status to 0 so it will     |
  29. |   know what has to be done.                              |
  30. |                                                          |
  31.  ----------------------------------------------------------
  32. */
  33.   tree->in_check[2]=0;
  34.   tree->extended_reason[2]=no_extension;
  35.   initial_alpha=alpha;
  36.   RepetitionCheck(tree,1,wtm);
  37.   tree->in_check[1]=Check(wtm);
  38.   tree->next_status[1].phase=ROOT_MOVES;
  39. /*
  40.  ----------------------------------------------------------
  41. |                                                          |
  42. |   now iterate through the move list and search the       |
  43. |   resulting positions.  note that Search() culls any     |
  44. |   move that is not legal by using Check().  the special  |
  45. |   case is that we must find one legal move to search to  |
  46. |   confirm that it's not a mate or draw.                  |
  47. |                                                          |
  48.  ----------------------------------------------------------
  49. */
  50.   while ((tree->current_phase[1]=NextRootMove(tree,wtm))) {
  51.     tree->extended_reason[1]=0;
  52. #if !defined(FAST)
  53.     if (1 <= trace_level)
  54.       SearchTrace(tree,1,depth,wtm,alpha,beta,"SearchRoot",tree->current_phase[1]);
  55. #endif
  56. /*
  57.  ----------------------------------------------------------
  58. |                                                          |
  59. |   if we push a pawn to the 7th rank, we need to look     |
  60. |   deeper to see if it can promote.                       |
  61. |                                                          |
  62.  ----------------------------------------------------------
  63. */
  64.     extensions=-60;
  65.     if (Piece(tree->current_move[1])==pawn &&
  66.         ((wtm && To(tree->current_move[1]) > H5 && TotalBlackPieces<16 &&
  67.          !And(mask_pawn_passed_w[To(tree->current_move[1])],BlackPawns)) ||
  68.         (!wtm && To(tree->current_move[1]) < A4 && TotalWhitePieces<16 &&
  69.          !And(mask_pawn_passed_b[To(tree->current_move[1])],WhitePawns)) ||
  70.         push_extensions[To(tree->current_move[1])]) &&
  71.         Swap(tree,From(tree->current_move[1]),To(tree->current_move[1]),wtm) >= 0) {
  72.       tree->extended_reason[1]|=passed_pawn_extension;
  73.       tree->passed_pawn_extensions_done++;
  74.       extensions+=pushpp_depth;
  75.     }
  76. /*
  77.  ----------------------------------------------------------
  78. |                                                          |
  79. |   now make the move and search the resulting position.   |
  80. |                                                          |
  81.  ----------------------------------------------------------
  82. */
  83.     MakeMove(tree,1,tree->current_move[1],wtm);
  84. /*
  85.  ----------------------------------------------------------
  86. |                                                          |
  87. |   if the move to be made checks the opponent, then we    |
  88. |   need to remember that he's in check and also extend    |
  89. |   the depth by one ply for him to get out.               |
  90. |                                                          |
  91.  ----------------------------------------------------------
  92. */
  93.     if (Check(ChangeSide(wtm))) {
  94.       tree->in_check[2]=1;
  95.       tree->extended_reason[2]=check_extension;
  96.       tree->check_extensions_done++;
  97.       extensions+=incheck_depth;
  98.     }
  99.     else {
  100.       tree->in_check[2]=0;
  101.       tree->extended_reason[2]=no_extension;
  102.     }
  103. /*
  104.  ----------------------------------------------------------
  105. |                                                          |
  106. |   now call Search to produce a value for this move.      |
  107. |                                                          |
  108.  ----------------------------------------------------------
  109. */
  110.     begin_root_nodes=tree->nodes_searched;
  111.     extensions=Min(extensions,0);
  112.     if (first_move) {
  113.       value=-ABSearch(tree,-beta,-alpha,ChangeSide(wtm),
  114.                       depth+extensions,2,DO_NULL);
  115.       if (abort_search) {
  116.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  117.         return(alpha);
  118.       }
  119.       first_move=0;
  120.     }
  121.     else {
  122.       value=-ABSearch(tree,-alpha-1,-alpha,ChangeSide(wtm),
  123.                       depth+extensions,2,DO_NULL);
  124.       if (abort_search) {
  125.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  126.         return(alpha);
  127.       }
  128.       if ((value > alpha) && (value < beta)) {
  129.         value=-ABSearch(tree,-beta,-alpha,ChangeSide(wtm),
  130.                         depth+extensions,2,DO_NULL);
  131.         if (abort_search) {
  132.           UnMakeMove(tree,1,tree->current_move[1],wtm);
  133.           return(alpha);
  134.         }
  135.       }
  136.     }
  137.     tree->root_nodes[root_move]=tree->nodes_searched-begin_root_nodes;
  138.     if (value > alpha) {
  139.       SearchOutput(tree,value,beta);
  140.       if(value >= beta) {
  141.         History(tree,1,depth,wtm,tree->current_move[1]);
  142.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  143.         StoreRefutation(tree,1,depth,wtm,value,0);
  144.         return(value);
  145.       }
  146.       alpha=value;
  147.       root_value=alpha;
  148.       beta=alpha+30;
  149.       root_beta=beta;
  150.     }
  151.     UnMakeMove(tree,1,tree->current_move[1],wtm);
  152.   }
  153. /*
  154.  ----------------------------------------------------------
  155. |                                                          |
  156. |   all moves have been searched.  if none were legal,     |
  157. |   return either MATE or DRAW depending on whether the    |
  158. |   side to move is in check or not.                       |
  159. |                                                          |
  160.  ----------------------------------------------------------
  161. */
  162.   if (abort_search) return(0);
  163.   if (first_move == 1) {
  164.     value=(Check(wtm)) ? -(MATE-1) : DrawScore(root_wtm==wtm);
  165.     if (value >=alpha && value <beta) {
  166.       SavePVS(tree,1,value,0);
  167. #if !defined(FAST)
  168.       if (1 <= trace_level) printf("Search() no moves!  ply=1\n");
  169. #endif
  170.     }
  171.     return(value);
  172.   }
  173.   else {
  174.     if (alpha != initial_alpha) {
  175.       memcpy(&tree->pv[0].path[1],&tree->pv[1].path[1],(tree->pv[1].path_length)*4);
  176.       memcpy(&tree->pv[0].path_hashed,&tree->pv[1].path_hashed,3);
  177.       History(tree,1,depth,wtm,tree->pv[1].path[1]);
  178.     }
  179.     StoreBest(tree,1,depth,wtm,alpha,initial_alpha,0);
  180.     return(alpha);
  181.   }
  182. }
  183.  
  184. /* modified 03/11/98 */
  185. /*
  186. ********************************************************************************
  187. *                                                                              *
  188. *   SearchOutput() is used to print the principal variation whenever it        *
  189. *   changes.  one additional feature is that SearchOutput() will try to do     *
  190. *   something about variations truncated by the transposition table.  if the   *
  191. *   variation was cut short by a transposition table hit, then we can make the *
  192. *   last move, add it to the end of the variation and extend the depth of the  *
  193. *   variation to cover it.                                                     *
  194. *                                                                              *
  195. ********************************************************************************
  196. */
  197. void SearchOutput(TREE *tree, int value, int bound)
  198. {
  199. #define PrintOK() (tree->nodes_searched>noise_level || value>(MATE-100))
  200.   register int *mv, *mvp;
  201.   register int wtm;
  202.   int temp_root_nodes;
  203.  
  204. /*
  205.  ----------------------------------------------------------
  206. |                                                          |
  207. |   first, move the best move to the top of the ply-1 move |
  208. |   list if it's not already there, so that it will be the |
  209. |   first move tried in the next iteration.                |
  210. |                                                          |
  211.  ----------------------------------------------------------
  212. */
  213.   wtm=root_wtm;
  214.   if (!abort_search) {
  215.     whisper_value=(analyze_mode && !root_wtm) ? -value : value;
  216.     whisper_depth=iteration_depth;
  217.     for (mvp=tree->last[0];mvp<tree->last[1];mvp++) if(tree->current_move[1]== *mvp) break;
  218.     if (mvp != tree->last[0]) {
  219.       temp_root_nodes=tree->root_nodes[mvp-tree->last[0]];
  220.       for (mv=mvp;mv>tree->last[0];mv--) {
  221.         *mv=*(mv-1);
  222.         tree->root_nodes[mv-tree->last[0]]=tree->root_nodes[mv-1-tree->last[0]];
  223.       }
  224.       tree->root_nodes[0]=temp_root_nodes;
  225.       *tree->last[0]=tree->current_move[1];
  226.       easy_move=0;
  227.     }
  228.     end_time=ReadClock(time_type);
  229. /*
  230.  ----------------------------------------------------------
  231. |                                                          |
  232. |   if this is not a fail-high move, then output the PV    |
  233. |   by walking down the path being backed up.              |
  234. |                                                          |
  235.  ----------------------------------------------------------
  236. */
  237.     if(value < bound) {
  238.       UnMakeMove(tree,1,tree->pv[1].path[1],root_wtm);
  239.       DisplayPV(tree,6, wtm, end_time-start_time, value, &tree->pv[1]);
  240.       MakeMove(tree,1,tree->pv[1].path[1],root_wtm);
  241.     }
  242.     else {
  243.       if (PrintOK()) {
  244.         Print(2,"               %2i   %s     ++   ",iteration_depth,
  245.         DisplayTime(end_time-start_time));
  246.         UnMakeMove(tree,1,tree->current_move[1],wtm);
  247.         if (display_options&64) Print(2,"%d. ",move_number);
  248.         if ((display_options&64) && !wtm) Print(2,"... ");
  249.         Print(2,"%s!!\n",OutputMove(tree,tree->current_move[1],1,wtm));
  250.         whisper_text[0]=0;
  251.         if (display_options&64)
  252.           sprintf(whisper_text," %d.",move_number);
  253.         if ((display_options&64) && !wtm)
  254.           sprintf(whisper_text+strlen(whisper_text)," ...");
  255.         sprintf(whisper_text+strlen(whisper_text)," %s!!",
  256.                 OutputMove(tree,tree->current_move[1],1,wtm));
  257.         MakeMove(tree,1,tree->current_move[1],wtm);
  258.         Whisper(6,iteration_depth,end_time-start_time,whisper_value,
  259.                 tree->nodes_searched,-1,whisper_text);
  260.       }
  261.       if (tree->current_move[1] != tree->pv[1].path[1]) {
  262.         tree->pv[1].path[1]=tree->current_move[1];
  263.         tree->pv[1].path_length=1;
  264.         tree->pv[1].path_hashed=0;
  265.         tree->pv[1].path_iteration_depth=iteration_depth;
  266.       }
  267.     }
  268.     tree->pv[0]=tree->pv[1];
  269.   }
  270. }
  271.  
  272. /* modified 03/11/98 */
  273. /*
  274. ********************************************************************************
  275. *                                                                              *
  276. *   SearchTrace() is used to print the search trace output each time a node is *
  277. *   traversed in the tree.                                                     *
  278. *                                                                              *
  279. ********************************************************************************
  280. */
  281. void SearchTrace(TREE *tree, int ply, int depth, int wtm,
  282.                  int alpha, int beta, char* name, int phase)
  283. {
  284.   int i;
  285. #if defined(SMP)
  286.   Lock(lock_io);
  287. #endif
  288.   for (i=1;i<ply;i++) printf("  ");
  289.   printf("%d  %s d:%5.2f [%s,",ply,OutputMove(tree,tree->current_move[ply],ply,wtm),
  290.          (float) depth/ (float) INCREMENT_PLY,DisplayEvaluation(alpha));
  291.   printf("%s] n:%d %s(%d)", DisplayEvaluation(beta),
  292.          (tree->nodes_searched),name,phase);
  293.   if (max_threads > 1) printf(" (t=%d) ",tree->thread_id);
  294.   printf("\n");
  295. #if defined(SMP)
  296.   UnLock(lock_io);
  297. #endif
  298. }
  299.