home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / search.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  21KB  |  489 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. /* last modified 06/05/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   Search() is the recursive routine used to implement the alpha/beta         *
  13. *   negamax search (similar to minimax but simpler to code.)  Search() is      *
  14. *   called whenever there is "depth" remaining so that all moves are subject   *
  15. *   to searching, or when the side to move is in check, to make sure that this *
  16. *   side isn't mated.  Search() recursively calls itself until depth is ex-    *
  17. *   hausted, at which time it calls Quiesce() instead.                         *
  18. *                                                                              *
  19. ********************************************************************************
  20. */
  21. int Search(TREE *tree, int alpha, int beta, int wtm, int depth,
  22.            int ply, int do_null) {
  23.   register int moves_searched=0;
  24.   register BITBOARD save_hash_key;
  25.   register int initial_alpha, value=0;
  26.   register int extensions, pieces;
  27.   int threat=0;
  28. /*
  29.  ----------------------------------------------------------
  30. |                                                          |
  31. |   check to see if we have searched enough nodes that it  |
  32. |   is time to peek at how much time has been used, or if  |
  33. |   is time to check for operator keyboard input.  this is |
  34. |   usually enough nodes to force a time/input check about |
  35. |   once per second, except when the target time per move  |
  36. |   is very small, in which case we try to check the time  |
  37. |   at least 10 times during the search.                   |
  38. |                                                          |
  39.  ----------------------------------------------------------
  40. */
  41.   tree->nodes_searched++;
  42.   if (--next_time_check <= 0) {
  43.     next_time_check=nodes_between_time_checks;
  44.     if (CheckInput()) Interrupt(ply);
  45.     time_abort+=TimeCheck(0);
  46.     if (time_abort) {
  47.       abort_search=1;
  48.       return(0);
  49.     }
  50.   }
  51.   if (ply >= MAXPLY-1) return(beta);
  52. /*
  53.  ----------------------------------------------------------
  54. |                                                          |
  55. |   check for draw by repetition.                          |
  56. |                                                          |
  57.  ----------------------------------------------------------
  58. */
  59.   if (RepetitionCheck(tree,ply,wtm)) {
  60.     value=DrawScore(root_wtm==wtm);
  61.     if (value < beta) SavePV(tree,ply,value,0);
  62. #if !defined(FAST)
  63.     if(ply <= trace_level) printf("draw by repetition detected, ply=%d.\n",ply);
  64. #endif
  65.     return(value);
  66.   }
  67. /*
  68.  ----------------------------------------------------------
  69. |                                                          |
  70. |   now call LookUp() to see if this position has been     |
  71. |   searched before.  if so, we may get a real score,      |
  72. |   produce a cutoff, or get nothing more than a good move |
  73. |   to try first.  there are four cases to handle:         |
  74. |                                                          |
  75. |   1. LookUp() returned "EXACT_SCORE" if this score is    |
  76. |   greater than beta, return beta.  otherwise, return the |
  77. |   score.  In either case, no further searching is needed |
  78. |   from this position.  note that lookup verified that    |
  79. |   the table position has sufficient "draft" to meet the  |
  80. |   requirements of the current search depth remaining.    |
  81. |                                                          |
  82. |   2.  LookUp() returned "UPPER_BOUND" which means that   |
  83. |   when this position was searched previously, every move |
  84. |   was "refuted" by one of its descendents.  as a result, |
  85. |   when the search was completed, we returned alpha at    |
  86. |   that point.  we simply return alpha here as well.      |
  87. |                                                          |
  88. |   3.  LookUp() returned "LOWER_BOUND" which means that   |
  89. |   when we encountered this position before, we searched  |
  90. |   one branch (probably) which promptly refuted the move  |
  91. |   at the previous ply.                                   |
  92. |                                                          |
  93. |   4.  LookUp() returned "AVOID_NULL_MOVE" which means    |
  94. |   the hashed score/bound was no good, but it indicated   |
  95. |   that trying a null-move in this position will be a     |
  96. |   waste of time.                                         |
  97. |                                                          |
  98.  ----------------------------------------------------------
  99. */
  100.   switch (LookUp(tree,ply,depth,wtm,&alpha,&beta,&threat)) {
  101.     case EXACT_SCORE:
  102.       if(alpha < beta) SavePV(tree,ply,alpha,1);
  103.       return(alpha);
  104.     case LOWER_BOUND:
  105.       return(beta);
  106.     case UPPER_BOUND:
  107.       return(alpha);
  108.     case AVOID_NULL_MOVE:
  109.       do_null=0;
  110.   }
  111. /*
  112.  ----------------------------------------------------------
  113. |                                                          |
  114. |   now it's time to try a probe into the endgame table-   |
  115. |   base files.  this is done if (a) the previous move was |
  116. |   a capture or promotion, unless we are at very shallow  |
  117. |   plies (<4) in the search; (b) there are less than 5    |
  118. |   pieces left (currently all interesting 4 piece endings |
  119. |   are available.)                                        |
  120. |                                                          |
  121.  ----------------------------------------------------------
  122. */
  123.   if (EGTB_use) {
  124.     if (TotalPieces<=EGTB_use &&
  125.         (TotalPieces<5 || (WhiteRooks && BlackRooks))) do {
  126.       register int wpawn, bpawn;
  127.       int tb_value;
  128.       if (TotalWhitePawns && TotalBlackPawns) {
  129.         wpawn=FirstOne(WhitePawns);
  130.         bpawn=FirstOne(BlackPawns);
  131.         if (FileDistance(wpawn,bpawn) == 1) {
  132.           if(((Rank(wpawn)==RANK2) && (Rank(bpawn)>RANK3)) ||
  133.              ((Rank(bpawn)==RANK7) && (Rank(wpawn)<RANK6)) || 
  134.              EnPassant(ply)) break;
  135.         }
  136.       }
  137.       tree->tb_probes++;
  138. #if defined(SMP)
  139.       Lock(lock_io);
  140. #endif
  141.       if (EGTBScore(tree, ply, wtm, &tb_value)) {
  142. #if defined(SMP)
  143.         UnLock(lock_io);
  144. #endif
  145.         tree->tb_probes_successful++;
  146.         alpha=tb_value;
  147.         if (abs(alpha) > MATE-100) alpha+=(alpha > 0) ? -(ply-1) : +(ply-1);
  148.         else if (alpha == 0) alpha=DrawScore(root_wtm==wtm);
  149.         if(alpha < beta) SavePV(tree,ply,alpha,2);
  150.         return(alpha);
  151.       }
  152. #if defined(SMP)
  153.       UnLock(lock_io);
  154. #endif
  155.     } while(0);
  156.   }
  157. /*
  158.  ----------------------------------------------------------
  159. |                                                          |
  160. |   initialize.                                            |
  161. |                                                          |
  162.  ----------------------------------------------------------
  163. */
  164.   tree->in_check[ply+1]=0;
  165.   tree->extended_reason[ply+1]=no_extension;
  166.   initial_alpha=alpha;
  167.   tree->last[ply]=tree->last[ply-1];
  168. /*
  169.  ----------------------------------------------------------
  170. |                                                          |
  171. |  first, we try a null move to see if we can get a quick  |
  172. |  cutoff with only a little work.  this operates as       |
  173. |  follows.  instead of making a legal move, the side on   |
  174. |  move 'passes' and does nothing.  the resulting position |
  175. |  is searched to a shallower depth than normal (usually   |
  176. |  one ply less but settable by the operator) this should  |
  177. |  result in a cutoff or at least should set the lower     |
  178. |  bound better since anything should be better than not   |
  179. |  doing anything.                                         |
  180. |                                                          |
  181. |  this is skipped for any of the following reasons:       |
  182. |                                                          |
  183. |  1.  the side on move is in check.  the null move        |
  184. |      results in an illegal position.                     |
  185. |  2.  no more than one null move can appear in succession |
  186. |      or else the search will degenerate into nothing.    |
  187. |  3.  the side on move has little material left making    |
  188. |      zugzwang positions more likely.                     |
  189. |                                                          |
  190. |  the null-move search is also used to detect certain     |
  191. |  types of threats.  the original idea of using the value |
  192. |  returned by the null-move search was reported by C.     |
  193. |  donninger, but was modified by Bruce Moreland (ferret)  |
  194. |  in the following way:  if the null-move search returns  |
  195. |  a score that says "mated in N" then this position is a  |
  196. |  dangerous one, because not moving gets the side to move |
  197. |  mated.  we extend the search one ply in this case, al-  |
  198. |  though, as always, no more than one ply of extensions   |
  199. |  are allowed at any one level in the tree.  note also    |
  200. |  that this "threat" condition is hashed so that later,   |
  201. |  if the hash table says "don't try the null move because |
  202. |  it likely will fail low, we still know that this is a   |
  203. |  threat position and should be extended.                 |
  204. |                                                          |
  205.  ----------------------------------------------------------
  206. */
  207. # if defined(NULL_MOVE_DEPTH)
  208.   pieces=(wtm) ? TotalWhitePieces : TotalBlackPieces;
  209.   if (do_null && !tree->in_check[ply] && pieces &&
  210.       (pieces>5 || depth<421)) {
  211.     tree->current_move[ply]=0;
  212.     tree->current_phase[ply]=NULL_MOVE;
  213. #if !defined(FAST)
  214.     if (ply <= trace_level)
  215.       SearchTrace(tree,ply,depth,wtm,beta-1,beta,"Search",0);
  216. #endif
  217.     tree->position[ply+1]=tree->position[ply];
  218.     Rule50Moves(ply+1)++;
  219.     save_hash_key=HashKey;
  220.     if (EnPassant(ply)) {
  221.       HashEP(EnPassant(ply+1),HashKey);
  222.       EnPassant(ply+1)=0;
  223.     }
  224.     value=-ABSearch(tree,-beta,-beta+1,ChangeSide(wtm),
  225.                     depth-NULL_MOVE_DEPTH-INCREMENT_PLY,ply+1,NO_NULL);
  226.     HashKey=save_hash_key;
  227.     if (abort_search || tree->stop) return(0);
  228.     if (value >= beta) {
  229.       StoreRefutation(tree,ply,depth,wtm,value,threat);
  230.       return(value);
  231.     }
  232.     if (value < -MATE+30) threat=1;
  233.   }
  234. # endif
  235. /*
  236.  ----------------------------------------------------------
  237. |                                                          |
  238. |   if there is no best move from the hash table, and this |
  239. |   is a PV node, then we need a good move to search       |
  240. |   first.  while killers and history moves are good, they |
  241. |   are not "good enough".  the simplest action is to try  |
  242. |   a shallow search (depth-2) to get a move.  note that   |
  243. |   when we call Search() with depth-2, it, too, will      |
  244. |   not have a hash move, and will therefore recursively   |
  245. |   continue this process, hence the name "internal        |
  246. |   iterative deepening."                                  |
  247. |                                                          |
  248.  ----------------------------------------------------------
  249. */
  250.   tree->next_status[ply].phase=FIRST_PHASE;
  251.   if (tree->hash_move[ply]==0 && (depth > 2*INCREMENT_PLY) &&
  252.       (((ply & 1) && alpha == root_alpha && beta == root_beta) ||
  253.       (!(ply & 1) && alpha == -root_beta && beta == -root_alpha))) {
  254.     tree->current_move[ply]=0;
  255.     value=ABSearch(tree,alpha,beta,wtm,depth-2*INCREMENT_PLY,ply,DO_NULL);
  256.     if (abort_search || tree->stop) return(0);
  257.     if (value <= alpha) {
  258.       value=ABSearch(tree,-MATE,beta,wtm,depth-2*INCREMENT_PLY,ply,DO_NULL);
  259.       if (abort_search || tree->stop) return(0);
  260.     }
  261.     else if (value < beta) {
  262.       if ((int) tree->pv[ply-1].path_length >= ply) 
  263.         tree->hash_move[ply]=tree->pv[ply-1].path[ply];
  264.     }
  265.     else tree->hash_move[ply]=tree->current_move[ply];
  266.     tree->last[ply]=tree->last[ply-1];
  267.     tree->next_status[ply].phase=FIRST_PHASE;
  268.   }
  269. /*
  270.  ----------------------------------------------------------
  271. |                                                          |
  272. |   now iterate through the move list and search the       |
  273. |   resulting positions.  note that Search() culls any     |
  274. |   move that is not legal by using Check().  the special  |
  275. |   case is that we must find one legal move to search to  |
  276. |   confirm that it's not a mate or draw.                  |
  277. |                                                          |
  278.  ----------------------------------------------------------
  279. */
  280.   while ((tree->current_phase[ply]=(tree->in_check[ply]) ? NextEvasion(tree,ply,wtm) : 
  281.                                                NextMove(tree,ply,wtm))) {
  282.     tree->extended_reason[ply]&=check_extension;
  283. #if !defined(FAST)
  284.     if (ply <= trace_level)
  285.       SearchTrace(tree,ply,depth,wtm,alpha,beta,"Search",tree->current_phase[ply]);
  286. #endif
  287. /*
  288.  ----------------------------------------------------------
  289. |                                                          |
  290. |   if two successive moves are capture / re-capture so    |
  291. |   that the material score is restored, extend the search |
  292. |   by one ply on the re-capture since it is pretty much   |
  293. |   forced and easy to analyze.                            |
  294. |                                                          |
  295.  ----------------------------------------------------------
  296. */
  297.     extensions=-60;
  298.     if (threat) extensions+=threat_depth;
  299.     if (Captured(tree->current_move[ply]) && Captured(tree->current_move[ply-1]) &&
  300.         To(tree->current_move[ply-1]) == To(tree->current_move[ply]) &&
  301.         (p_values[Captured(tree->current_move[ply-1])+7] == 
  302.          p_values[Captured(tree->current_move[ply])+7] ||
  303.          Promote(tree->current_move[ply-1])) &&
  304.         !(tree->extended_reason[ply-1]&recapture_extension)) {
  305.       tree->extended_reason[ply]|=recapture_extension;
  306.       tree->recapture_extensions_done++;
  307.       extensions+=recap_depth;
  308.     }
  309. /*
  310.  ----------------------------------------------------------
  311. |                                                          |
  312. |   if we push a passed pawn, we need to look deeper to    |
  313. |   see if it is a legitimate threat.                      |
  314. |                                                          |
  315.  ----------------------------------------------------------
  316. */
  317.     if (Piece(tree->current_move[ply])==pawn && 
  318.          ((wtm && To(tree->current_move[ply])>H5 && TotalBlackPieces<16 &&
  319.           !And(mask_pawn_passed_w[To(tree->current_move[ply])],BlackPawns)) ||
  320.          (!wtm && To(tree->current_move[ply])<A4 && TotalWhitePieces<16 &&
  321.           !And(mask_pawn_passed_b[To(tree->current_move[ply])],WhitePawns)) ||
  322.          push_extensions[To(tree->current_move[ply])]) &&
  323.          Swap(tree,From(tree->current_move[ply]),To(tree->current_move[ply]),wtm) ==
  324.            p_values[Captured(tree->current_move[ply])+7]) {
  325.       tree->extended_reason[ply]|=passed_pawn_extension;
  326.       tree->passed_pawn_extensions_done++;
  327.       extensions+=pushpp_depth;
  328.     }
  329. /*
  330.  ----------------------------------------------------------
  331. |                                                          |
  332. |   now make the move and search the resulting position.   |
  333. |   if we are in check, the current move must be legal     |
  334. |   since NextEvasion ensures this, otherwise we have to   |
  335. |   make sure the side-on-move is not in check after the   |
  336. |   move to weed out illegal moves and save time.          |
  337. |                                                          |
  338.  ----------------------------------------------------------
  339. */
  340.     MakeMove(tree,ply,tree->current_move[ply],wtm);
  341.     if (tree->in_check[ply] || !Check(wtm)) {
  342. /*
  343.  ----------------------------------------------------------
  344. |                                                          |
  345. |   if the move to be made checks the opponent, then we    |
  346. |   need to remember that he's in check and also extend    |
  347. |   the depth by one ply for him to get out.               |
  348. |                                                          |
  349.  ----------------------------------------------------------
  350. */
  351.       if (Check(ChangeSide(wtm))) {
  352.         tree->in_check[ply+1]=1;
  353.         tree->extended_reason[ply+1]=check_extension;
  354.         tree->check_extensions_done++;
  355.         extensions+=incheck_depth;
  356.       }
  357.       else {
  358.         tree->in_check[ply+1]=0;
  359.         tree->extended_reason[ply+1]=no_extension;
  360.       }
  361. /*
  362.  ----------------------------------------------------------
  363. |                                                          |
  364. |   now we toss in the "razoring" trick, which simply says |
  365. |   if we are doing fairly badly, we can reduce the depth  |
  366. |   an additional ply, if there was nothing at the current |
  367. |   ply that caused an extension.                          |
  368. |                                                          |
  369.  ----------------------------------------------------------
  370. */
  371.       if (depth<3*INCREMENT_PLY && depth>=2*INCREMENT_PLY &&
  372.           !tree->in_check[ply] && extensions == -60) {
  373.         register int value=-Evaluate(tree,ply+1,ChangeSide(wtm),
  374.                                      -(beta+51),-(alpha-51));
  375.         if (value+50 < alpha) extensions-=60;
  376.       }
  377. /*
  378.  ----------------------------------------------------------
  379. |                                                          |
  380. |   if there's only one legal move, extend the search one  |
  381. |   additional ply since this node is very easy to search. |
  382. |                                                          |
  383.  ----------------------------------------------------------
  384. */
  385.       if (!moves_searched) {
  386.         if (tree->last[ply]-tree->last[ply-1] == 1) {
  387.           tree->extended_reason[ply]|=one_reply_extension;
  388.           tree->one_reply_extensions_done++;
  389.           extensions+=onerep_depth;
  390.         }
  391.         extensions=Min(extensions,0);
  392.         value=-ABSearch(tree,-beta,-alpha,ChangeSide(wtm),
  393.                         depth+extensions,ply+1,DO_NULL);
  394.         if (abort_search || tree->stop) {
  395.           UnMakeMove(tree,ply,tree->current_move[ply],wtm);
  396.           return(0);
  397.         }
  398.       }
  399.       else {
  400.         extensions=Min(extensions,0);
  401.         value=-ABSearch(tree,-alpha-1,-alpha,ChangeSide(wtm),
  402.                         depth+extensions,ply+1,DO_NULL);
  403.         if (abort_search || tree->stop) {
  404.           UnMakeMove(tree,ply,tree->current_move[ply],wtm);
  405.           return(0);
  406.         }
  407.         if (value>alpha && value<beta) {
  408.           value=-ABSearch(tree,-beta,-alpha,ChangeSide(wtm),
  409.                           depth+extensions,ply+1,DO_NULL);
  410.           if (abort_search || tree->stop) {
  411.             UnMakeMove(tree,ply,tree->current_move[ply],wtm);
  412.             return(0);
  413.           }
  414.         }
  415.       }
  416.       if (value > alpha) {
  417.         if(value >= beta) {
  418.           History(tree,ply,depth,wtm,tree->current_move[ply]);
  419.           UnMakeMove(tree,ply,tree->current_move[ply],wtm);
  420.           StoreRefutation(tree,ply,depth,wtm,value,threat);
  421.           tree->fail_high++;
  422.           if (!moves_searched) tree->fail_high_first++;
  423.           return(value);
  424.         }
  425.         alpha=value;
  426.       }
  427.       moves_searched++;
  428.     } else tree->nodes_searched++;
  429.     UnMakeMove(tree,ply,tree->current_move[ply],wtm);
  430. #if defined(SMP)
  431.     if (smp_idle) {
  432.       if (moves_searched>0 && min_thread_depth<=depth && 
  433.         (!tree->in_check[ply] || tree->last[ply]-tree->last[ply-1]>1)) {
  434.         tree->alpha=alpha;
  435.         tree->beta=beta;
  436.         tree->value=value;
  437.         tree->wtm=wtm;
  438.         tree->ply=ply;
  439.         tree->depth=depth;
  440.         tree->threat=threat;
  441.         if(Thread(tree)) {
  442.           if (CheckInput()) Interrupt(ply);
  443.           value=tree->search_value;
  444.           if (value > alpha) {
  445.             if(value >= beta) {
  446.               History(tree,ply,depth,wtm,tree->current_move[ply]);
  447.               StoreRefutation(tree,ply,depth,wtm,value,threat);
  448.               tree->fail_high++;
  449.               return(value);
  450.             }
  451.             alpha=value;
  452.             break;
  453.           }
  454.         }
  455.       }
  456.     }
  457. #endif
  458.   }
  459. /*
  460.  ----------------------------------------------------------
  461. |                                                          |
  462. |   all moves have been searched.  if none were legal,     |
  463. |   return either MATE or DRAW depending on whether the    |
  464. |   side to move is in check or not.                       |
  465. |                                                          |
  466.  ----------------------------------------------------------
  467. */
  468.   if (moves_searched == 0) {
  469.     value=(Check(wtm)) ? -(MATE-ply) : DrawScore(root_wtm==wtm);
  470.     if (value>=alpha && value<beta) {
  471.       SavePV(tree,ply,value,0);
  472. #if !defined(FAST)
  473.       if (ply <= trace_level) printf("Search() no moves!  ply=%d\n",ply);
  474. #endif
  475.     }
  476.     return(value);
  477.   }
  478.   else {
  479.     if (alpha != initial_alpha) {
  480.       memcpy(&tree->pv[ply-1].path[ply],&tree->pv[ply].path[ply],(tree->pv[ply].path_length-ply+1)*4);
  481.       memcpy(&tree->pv[ply-1].path_hashed,&tree->pv[ply].path_hashed,3);
  482.       tree->pv[ply-1].path[ply-1]=tree->current_move[ply-1];
  483.       History(tree,ply,depth,wtm,tree->pv[ply].path[ply]);
  484.     }
  485.     StoreBest(tree,ply,depth,wtm,alpha,initial_alpha,threat);
  486.     return(alpha);
  487.   }
  488. }
  489.