home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / iterate.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  17KB  |  415 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 07/08/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   Iterate() is the routine used to drive the iterated search.  it repeatedly *
  13. *   calls search, incrementing the search depth after each call, until either  *
  14. *   time is exhausted or the maximum set search depth is reached.              *
  15. *                                                                              *
  16. ********************************************************************************
  17. */
  18. int Iterate(int wtm, int search_type, int root_list_done)
  19. {
  20.   int *mvp;
  21.   int i, value=0, time_used;
  22.   int twtm, used_w, used_b;
  23.   int correct, correct_count, material=0, sorted, temp;
  24.   TREE *tree=local[0];
  25.  
  26. /*
  27.  ----------------------------------------------------------
  28. |                                                          |
  29. |  initialize.                                             |
  30. |                                                          |
  31. |  produce the root move list, which is ordered and kept   |
  32. |  for the duration of this search (the order may change   |
  33. |  as new best moves are backed up to the root of course.) |
  34. |                                                          |
  35.  ----------------------------------------------------------
  36. */
  37.   time_abort=0;
  38.   abort_search=0;
  39.   book_move=0;
  40.   program_start_time=ReadClock(time_type);
  41.   start_time=ReadClock(time_type);
  42.   cpu_time_used=0;
  43.   elapsed_start=ReadClock(elapsed);
  44.   PreEvaluate(tree,wtm);
  45.   tree->nodes_searched=0;
  46.   tree->fail_high=0;
  47.   tree->fail_high_first=0;
  48.   if (booking || !Book(tree,wtm,root_list_done)) do {
  49.     if (abort_search) break;
  50.     if (!root_list_done) RootMoveList(wtm);
  51.     if (EGTB_draw) EGTB_use=0;
  52.     else EGTB_use=EGTBlimit;
  53.     if (EGTBlimit && !EGTB_use)
  54.       Print(128,"Drawn at root, trying for swindle.\n");
  55.     correct_count=0;
  56.     burp=15*100;
  57.     transposition_id=(transposition_id+1)&7;
  58.     if (!transposition_id) transposition_id++;
  59.     program_start_time=ReadClock(time_type);
  60.     start_time=ReadClock(time_type);
  61.     cpu_percent=0;
  62.     elapsed_start=ReadClock(elapsed);
  63.     next_time_check=nodes_between_time_checks;
  64.     tree->evaluations=0;
  65. #if !defined(FAST)
  66.     tree->transposition_hits=0;
  67.     tree->transposition_probes=0;
  68.     tree->pawn_probes=0;
  69.     tree->pawn_hits=0;
  70. #endif
  71.     tree->tb_probes=0;
  72.     tree->tb_probes_successful=0;
  73.     tree->check_extensions_done=0;
  74.     tree->recapture_extensions_done=0;
  75.     tree->passed_pawn_extensions_done=0;
  76.     tree->one_reply_extensions_done=0;
  77.     root_wtm=wtm;
  78.     root_total_white_pieces=TotalWhitePieces;
  79.     root_total_white_pawns=TotalWhitePawns;
  80.     root_total_black_pieces=TotalBlackPieces;
  81.     root_total_black_pawns=TotalBlackPawns;
  82. /*
  83.  ----------------------------------------------------------
  84. |                                                          |
  85. |  if there are no legal moves, it is either mate or draw  |
  86. |  depending on whether the side to move is in check or    |
  87. |  not (mate or stalemate.)                                |
  88. |                                                          |
  89.  ----------------------------------------------------------
  90. */
  91.     if (tree->last[0] == tree->last[1]) {
  92.       program_end_time=ReadClock(time_type);
  93.       tree->pv[0].path_length=0;
  94.       tree->pv[0].path_iteration_depth=10;
  95.       if (Check(wtm)) {
  96.         root_value=-(MATE-1);
  97.         last_search_value=-(MATE-1);
  98.       }
  99.       else {
  100.         root_value=DrawScore(crafty_is_white);
  101.         last_search_value=DrawScore(crafty_is_white);
  102.       }
  103.       Print(6,"              depth   time  score   variation\n");
  104.       Print(6,"                                    (no moves)\n");
  105.       tree->nodes_searched=1;
  106.       return(root_value);
  107.     }
  108. /*
  109.  ----------------------------------------------------------
  110. |                                                          |
  111. |   now set the search time and iteratively call Search()  |
  112. |   to analyze the position deeper and deeper.  note that  |
  113. |   Search() is called with an alpha/beta window roughly   |
  114. |   1/3 of a pawn on either side of the score last         |
  115. |   returned by search.  also, after the first root move   |
  116. |   is searched, this window is collapsed to n and n+1     |
  117. |   (where n is the value for the first root move.)  often |
  118. |   a better move is found, which causes search to return  |
  119. |   <beta> as the score.  we then relax beta depending on  |
  120. |   its value:  if beta = alpha+1, set beta to alpha+1/3   |
  121. |   of a pawn;  if beta = alpha+1/3 pawn, then set beta to |
  122. |   + infinity.                                            |
  123. |                                                          |
  124.  ----------------------------------------------------------
  125. */
  126.     TimeSet(search_type);
  127.     iteration_depth=1;
  128.     if (last_pv.path_iteration_depth > 1)
  129.       iteration_depth=last_pv.path_iteration_depth+1;
  130.     Print(6,"              depth   time  score   variation (%d)\n",
  131.           iteration_depth);
  132.     time_abort=0;
  133.     abort_search=0;
  134.     program_start_time=ReadClock(time_type);
  135.     start_time=ReadClock(time_type);
  136.     elapsed_start=ReadClock(elapsed);
  137. /*
  138.  ----------------------------------------------------------
  139. |                                                          |
  140. |   now install the learned position information in the    |
  141. |   hash table.                                            |
  142. |                                                          |
  143.  ----------------------------------------------------------
  144. */
  145.     LearnPositionLoad(tree);
  146. /*
  147.  ----------------------------------------------------------
  148. |                                                          |
  149. |   set the initial search bounds based on the last search |
  150. |   or default values.                                     |
  151. |                                                          |
  152.  ----------------------------------------------------------
  153. */
  154.     tree->pv[0]=last_pv;
  155.     if (iteration_depth > 1) {
  156.       root_alpha=last_value-40;
  157.       root_value=last_value-40;
  158.       root_beta=last_value+40;
  159.     }
  160.     else {
  161.       root_alpha=-MATE-1;
  162.       root_value=-MATE-1;
  163.       root_beta=MATE+1;
  164.     }
  165.     for (i=0;i<256;i++) tree->root_nodes[i]=0;
  166. /*
  167.  ----------------------------------------------------------
  168. |                                                          |
  169. |   if we are using multiple threads, and they have not    |
  170. |   been started yet, then start them now as the search    |
  171. |   is ready to begin.                                     |
  172. |                                                          |
  173.  ----------------------------------------------------------
  174. */
  175. #if defined(SMP)
  176.     if (max_threads>smp_idle+1) {
  177.       pthread_t pt;
  178.       int proc;
  179.       if (!EGTB_use || !(TotalPieces<=5 && EGTBScore(tree, 1, wtm, &i))) {
  180.         for (proc=smp_threads+1;proc<max_threads;proc++) {
  181.           Print(128,"starting thread %d\n",proc);
  182.           thread[proc]=0;
  183.           tfork(pt,ThreadInit,(void *) proc);
  184.           smp_threads++;
  185.         }
  186.       }
  187.     }
  188. #endif
  189.     for (;iteration_depth<=60;iteration_depth++) {
  190. /*
  191.  ----------------------------------------------------------
  192. |                                                          |
  193. |   now install the old PV into the hash table so that     |
  194. |   these moves will be followed first.                    |
  195. |                                                          |
  196.  ----------------------------------------------------------
  197. */
  198.       twtm=wtm;
  199.       for (i=1;i<=(int) tree->pv[0].path_length;i++) {
  200.         tree->pv[i]=tree->pv[i-1];
  201.         if (!LegalMove(tree,i,twtm,tree->pv[i].path[i])) {
  202.           Print(4095,"ERROR, not installing bogus move at ply=%d\n",i);
  203.           Print(4095,"not installing from=%d  to=%d  piece=%d\n",
  204.                 From(tree->pv[i].path[i]), To(tree->pv[i].path[i]),
  205.                 Piece(tree->pv[i].path[i]));
  206.           break;
  207.         }
  208.         StorePV(tree, i, twtm);
  209.         MakeMove(tree, i,tree->pv[0].path[i],twtm);
  210.         twtm=ChangeSide(twtm);
  211.       }
  212.       for (i--;i>0;i--) {
  213.         twtm=ChangeSide(twtm);
  214.         UnMakeMove(tree, i,tree->pv[0].path[i],twtm);
  215.       }
  216.       if (trace_level) {
  217.         printf("==================================\n");
  218.         printf("=      search iteration %2d       =\n",iteration_depth);
  219.         printf("==================================\n");
  220.       }
  221.       for (mvp=tree->last[0];mvp<tree->last[1];mvp++)
  222.         tree->searched_this_root_move[mvp-tree->last[0]]=0;
  223.       search_failed_high=0;
  224.       search_failed_low=0;
  225.       if (tree->nodes_searched) {
  226.         nodes_between_time_checks=nodes_per_second;
  227.         nodes_between_time_checks=Min(nodes_between_time_checks,MAX_TC_NODES);
  228.         nodes_between_time_checks=Max(nodes_between_time_checks,5000);
  229.         if (!analyze_mode) {
  230.           if (time_limit>300 && !auto232);
  231.           else if (time_limit>100 || auto232) nodes_between_time_checks/=10;
  232.           else if (time_limit > 50) nodes_between_time_checks/=20;
  233.           else nodes_between_time_checks/=100;
  234.         } else nodes_between_time_checks=5000;
  235.       }
  236.       while (!time_abort && !abort_search) {
  237. #if defined(SMP)
  238.         thread[0]=local[0];
  239. #endif
  240.         thread_start_time[0]=ReadClock(cpu);
  241.         value=SearchRoot(tree,root_alpha, root_beta, wtm,
  242.                          iteration_depth*INCREMENT_PLY+45);
  243.         cpu_time_used+=ReadClock(cpu)-thread_start_time[0];
  244.         if (value >= root_beta) {
  245.           search_failed_high=1;
  246.           root_alpha=root_beta-1;
  247.           root_value=root_alpha;
  248.           root_beta=MATE+1;
  249.           tree->searched_this_root_move[0]=0;
  250.         }
  251.         else if (value <= root_alpha) {
  252.           if (!search_failed_high) {
  253.             for (mvp=tree->last[0];mvp<tree->last[1];mvp++)
  254.               tree->searched_this_root_move[mvp-tree->last[0]]=0;
  255.             search_failed_low=1;
  256.             root_alpha=-MATE-1;
  257.             root_value=root_alpha;
  258.             easy_move=0;
  259.             if (tree->nodes_searched>noise_level && !time_abort && !abort_search) {
  260.               Print(4,"               %2i   %s     --   ",iteration_depth,
  261.                     DisplayTime(ReadClock(time_type)-start_time));
  262.               if (display_options&64) Print(4,"%d. ",move_number);
  263.               if ((display_options&64) && !wtm) Print(4,"... ");
  264.               Print(4,"%s\n",OutputMove(tree,*tree->last[0],1,wtm));
  265.             }
  266.           }
  267.           else break;
  268.         }
  269.         else
  270.           break;
  271.       }
  272.       if (root_value>root_alpha && root_value<root_beta) 
  273.         last_search_value=root_value;
  274. /*
  275.  ----------------------------------------------------------
  276. |                                                          |
  277. |   if we are running a test suite, check to see if we can |
  278. |   exit the search.  this happens when N successive       |
  279. |   iterations produce the correct solution.  N is set by  |
  280. |   the test command in Option().                          |
  281. |                                                          |
  282.  ----------------------------------------------------------
  283. */
  284.       correct=solution_type;
  285.       for (i=0;i<number_of_solutions;i++) {
  286.         if (!solution_type) {
  287.           if (solutions[i] == tree->pv[0].path[1]) correct=1;
  288.         }
  289.         else
  290.           if (solutions[i] == tree->pv[0].path[1]) correct=0;
  291.       }
  292.       if (correct) correct_count++;
  293.       else correct_count=0;
  294. /*
  295.  ----------------------------------------------------------
  296. |                                                          |
  297. |   if the search terminated normally, then dump the PV    |
  298. |   and search statistics (we don't do this if the search  |
  299. |   aborts because the opponent doesn't make the predicted |
  300. |   move...)                                               |
  301. |                                                          |
  302.  ----------------------------------------------------------
  303. */
  304.       twtm=wtm;
  305.       end_time=ReadClock(time_type);
  306.       if (end_time-start_time > 10)
  307.         nodes_per_second=(BITBOARD) tree->nodes_searched*100/(BITBOARD) (end_time-start_time);
  308.       else
  309.         nodes_per_second=10000;
  310.       if (!time_abort && !abort_search && (tree->nodes_searched>noise_level ||
  311.           correct_count>=early_exit || value>MATE-100 || tree->pv[0].path_hashed==2)) {
  312.         if (value != -(MATE-1))
  313.           DisplayPV(tree,5,wtm,end_time-start_time,value,&tree->pv[0]);
  314.       }
  315.       root_alpha=value-40;
  316.       root_value=root_alpha;
  317.       root_beta=value+40;
  318.       if ((iteration_depth > 1) && (value > MATE-100) &&
  319.           (value > last_mate_score)) break;
  320.       if ((iteration_depth >= search_depth) && search_depth) break;
  321.       if (time_abort || abort_search) break;
  322.       end_time=ReadClock(time_type)-start_time;
  323.       if (thinking && ((int) end_time >= time_limit)) break;
  324.       if (correct_count >= early_exit) break;
  325.       if (iteration_depth>=2 && TotalPieces<=5 &&
  326.           EGTBScore(tree, 1, wtm, &i) && EGTB_use) break;
  327.       do {
  328.         sorted=1;
  329.         for (mvp=tree->last[0]+1;mvp<tree->last[1]-1;mvp++) {
  330.           if (tree->root_nodes[mvp-tree->last[0]] < tree->root_nodes[mvp-tree->last[0]+1]) {
  331.             temp=*mvp;
  332.             *mvp=*(mvp+1);
  333.             *(mvp+1)=temp;
  334.             temp=tree->root_nodes[mvp-tree->last[0]];
  335.             tree->root_nodes[mvp-tree->last[0]]=tree->root_nodes[mvp-tree->last[0]+1];
  336.             tree->root_nodes[mvp-tree->last[0]+1]=temp;
  337.             sorted=0;
  338.           }
  339.         }
  340.       } while(!sorted);
  341. /*
  342.       for (mvp=tree->last[0];mvp<tree->last[1];mvp++) {
  343.         Print(4095," %10s  %10d\n",OutputMove(tree,*mvp,1,wtm),tree->root_nodes[mvp-tree->last[0]]);
  344.       }
  345. */
  346.     }
  347. /*
  348.  ----------------------------------------------------------
  349. |                                                          |
  350. |   search done, now display statistics, depending on the  |
  351. |   verbosity level set.                                   |
  352. |                                                          |
  353.  ----------------------------------------------------------
  354. */
  355.     used_w=0;
  356.     used_b=0;
  357. #if !defined(FAST)
  358.     for (i=0;i<hash_table_size;i++) {
  359.       if ((int) Shiftr((trans_ref_ba+i)->word1,61) == transposition_id) used_b++;
  360.       if ((int) Shiftr((trans_ref_wa+i)->word1,61) == transposition_id) used_w++;
  361.     }
  362. #endif
  363.     end_time=ReadClock(time_type);
  364.     time_used=(end_time-start_time);
  365.     if (time_used < 10) time_used=10;
  366.     elapsed_end=ReadClock(elapsed)-elapsed_start;
  367.     if (elapsed_end)
  368.       cpu_percent=100*cpu_time_used/elapsed_end;
  369.     else cpu_percent=100;
  370.     if (elapsed_end > 10)
  371.       nodes_per_second=(BITBOARD) tree->nodes_searched*100/(BITBOARD) elapsed_end;
  372.     tree->evaluations=(tree->evaluations) ? tree->evaluations : 1;
  373.     if ((!abort_search || time_abort) && !puzzling) {
  374.       tree->fail_high++;
  375.       tree->fail_high_first++;
  376.       material=Material/PAWN_VALUE;
  377.       if (ChangeSide(wtm)) material=-material;
  378.       Print(8,"              time=%s  cpu=%d%%  mat=%d",
  379.             DisplayTimeWhisper(end_time-start_time), cpu_percent, material); 
  380.       Print(8,"  n=%u", tree->nodes_searched);
  381.       Print(8,"  fh=%u%%", tree->fail_high_first*100/tree->fail_high);
  382.       Print(8,"  nps=%d\n", nodes_per_second);
  383.       Print(16,"              ext-> checks=%d recaps=%d pawns=%d 1rep=%d\n",
  384.             tree->check_extensions_done, tree->recapture_extensions_done,
  385.             tree->passed_pawn_extensions_done, tree->one_reply_extensions_done);
  386.       Print(16,"              predicted=%d  nodes=%u  evals=%u\n", 
  387.              predicted, tree->nodes_searched, tree->evaluations);
  388.       Print(16,"              endgame tablebase-> probes done=%d  successful=%d\n",
  389.             tree->tb_probes, tree->tb_probes_successful);
  390. #if !defined(FAST)
  391.       Print(16,"              hashing-> trans/ref=%d%%  pawn=%d%%  used=w%d%% b%d%%\n",
  392.             100*tree->transposition_hits/(tree->transposition_probes+1),
  393.             100*tree->pawn_hits/(tree->pawn_probes+1),
  394.             used_w*100/(hash_table_size+1), used_b*100/(hash_table_size+1));
  395. #endif
  396.     }
  397.   } while(0);
  398.   else {
  399.     root_value=0;
  400.     last_search_value=0;
  401.     book_move=1;
  402.     tree->pv[0]=tree->pv[1];
  403.     if (analyze_mode) Whisper(4,0,0,0,0,0,whisper_text);
  404.   }
  405.   program_end_time=ReadClock(time_type);
  406. #if defined(SMP)
  407.   if (EGTB_use && TotalPieces<= 5 && EGTBScore(tree, 1, wtm, &i)) {
  408.     int proc;
  409.     for (proc=1;proc<CPUS;proc++) thread[proc]=(TREE*)-1;
  410.     smp_threads=0;
  411.   }
  412. #endif
  413.   return(last_search_value);
  414. }
  415.