Subversion Repositories Games.Chess Giants

Rev

Rev 154 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. #include "chess.h"
  2. #include "data.h"
  3. /* last modified 12/29/15 */
  4. /*
  5.  *******************************************************************************
  6.  *                                                                             *
  7.  *   NextMove() is used to select the next move from the current move list.    *
  8.  *                                                                             *
  9.  *   The "excluded move" code below simply collects any moves that were        *
  10.  *   searched without being generated (hash move and up to 4 killers).  We     *
  11.  *   save them in the NEXT structure and make sure to exclude them when        *
  12.  *   searching after a move generation to avoid the duplicated effort.         *
  13.  *                                                                             *
  14.  *******************************************************************************
  15.  */
  16. int NextMove(TREE * RESTRICT tree, int ply, int depth, int side, int in_check) {
  17.   unsigned *movep, *bestp;
  18.   int hist, bestval, possible;
  19.  
  20. /*
  21.  ************************************************************
  22.  *                                                          *
  23.  *  The following "big switch" controls the finate state    *
  24.  *  machine that selects moves.  The "phase" value in the   *
  25.  *  next_status[ply] structure is always set after a move   *
  26.  *  is selected, and it defines the next state of the FSM   *
  27.  *  so select the next move in a sequenced order.           *
  28.  *                                                          *
  29.  ************************************************************
  30.  */
  31.   switch (tree->next_status[ply].phase) {
  32. /*
  33.  ************************************************************
  34.  *                                                          *
  35.  *  First, try the transposition table move (which will be  *
  36.  *  the principal variation move as we first move down the  *
  37.  *  tree) or the best move found in this position during a  *
  38.  *  prior search.                                           *
  39.  *                                                          *
  40.  ************************************************************
  41.  */
  42.     case HASH:
  43.       tree->next_status[ply].order = 0;
  44.       tree->next_status[ply].exclude = &tree->next_status[ply].done[0];
  45.       tree->next_status[ply].phase = GENERATE_CAPTURES;
  46.       if (tree->hash_move[ply]) {
  47.         tree->curmv[ply] = tree->hash_move[ply];
  48.         *(tree->next_status[ply].exclude++) = tree->curmv[ply];
  49.         if (ValidMove(tree, ply, side, tree->curmv[ply])) {
  50.           tree->phase[ply] = HASH;
  51.           return ++tree->next_status[ply].order;
  52.         }
  53. #if defined(DEBUG)
  54.         else
  55.           Print(2048, "ERROR:  bad move from hash table, ply=%d\n", ply);
  56. #endif
  57.       }
  58. /*
  59.  ************************************************************
  60.  *                                                          *
  61.  *  Generate captures and sort them based on the simple     *
  62.  *  MVV/LVA ordering where we try to capture the most       *
  63.  *  valuable victim piece possible, using the least         *
  64.  *  valuable attacking piece possible.  Later we will test  *
  65.  *  to see if the capture appears to lose material and we   *
  66.  *  will defer searching it until later.                    *
  67.  *                                                          *
  68.  *  Or, if in check, generate all the legal moves that      *
  69.  *  escape check by using GenerateCheckEvasions().  After   *
  70.  *  we do this, we sort them using MVV/LVA to move captures *
  71.  *  to the front of the list in the correct order.          *
  72.  *                                                          *
  73.  ************************************************************
  74.  */
  75.     case GENERATE_CAPTURES:
  76.       tree->next_status[ply].phase = CAPTURES;
  77.       if (!in_check)
  78.         tree->last[ply] =
  79.             GenerateCaptures(tree, ply, side, tree->last[ply - 1]);
  80.       else
  81.         tree->last[ply] =
  82.             GenerateCheckEvasions(tree, ply, side, tree->last[ply - 1]);
  83. /*
  84.  ************************************************************
  85.  *                                                          *
  86.  *  Now make a pass over the moves to assign the sort value *
  87.  *  for each.  We simply use MVV/LVA move order here.  A    *
  88.  *  simple optimization is to use the pre-computed array    *
  89.  *  MVV_LVA[victim][attacker] which returns a simple value  *
  90.  *  that indicates MVV/LVA order.                           *
  91.  *                                                          *
  92.  ************************************************************
  93.  */
  94.       tree->next_status[ply].remaining = 0;
  95.       for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
  96.         if (*movep == tree->hash_move[ply]) {
  97.           *movep = 0;
  98.           tree->next_status[ply].exclude = &tree->next_status[ply].done[0];
  99.         } else {
  100.           *movep += MVV_LVA[Captured(*movep)][Piece(*movep)];
  101.           tree->next_status[ply].remaining++;
  102.         }
  103.       NextSort(tree, ply);
  104.       tree->next_status[ply].last = tree->last[ply - 1];
  105.       if (in_check)
  106.         goto remaining_moves;
  107. /*
  108.  ************************************************************
  109.  *                                                          *
  110.  *  Try the captures moves, which are in order based on     *
  111.  *  MVV/LVA ordering.  If a larger-valued piece captures a  *
  112.  *  lesser-valued piece, and SEE() says it loses material,  *
  113.  *  this capture will be deferred until later.              *
  114.  *                                                          *
  115.  *  If we are in check, we jump down to the history moves   *
  116.  *  phase (we don't need to generate any more moves as      *
  117.  *  GenerateCheckEvasions has already generated all legal   *
  118.  *  moves.                                                  *
  119.  *                                                          *
  120.  ************************************************************
  121.  */
  122.     case CAPTURES:
  123.       while (tree->next_status[ply].remaining) {
  124.         tree->curmv[ply] = Move(*(tree->next_status[ply].last++));
  125.         if (!--tree->next_status[ply].remaining)
  126.           tree->next_status[ply].phase = KILLER1;
  127.         if (pcval[Piece(tree->curmv[ply])] <=
  128.             pcval[Captured(tree->curmv[ply])]
  129.             || SEE(tree, side, tree->curmv[ply]) >= 0) {
  130.           *(tree->next_status[ply].last - 1) = 0;
  131.           tree->phase[ply] = CAPTURES;
  132.           return ++tree->next_status[ply].order;
  133.         }
  134.       }
  135. /*
  136.  ************************************************************
  137.  *                                                          *
  138.  *  Now, try the killer moves.  This phase tries the two    *
  139.  *  killers for the current ply without generating moves,   *
  140.  *  which saves time if a cutoff occurs.  After those two   *
  141.  *  killers are searched, we try the killers from two plies *
  142.  *  back since they have greater depth and might produce a  *
  143.  *  cutoff if the current two do not.                       *
  144.  *                                                          *
  145.  ************************************************************
  146.  */
  147.     case KILLER1:
  148.       possible = tree->killers[ply].move1;
  149.       if (!Exclude(tree, ply, possible) &&
  150.           ValidMove(tree, ply, side, possible)) {
  151.         tree->curmv[ply] = possible;
  152.         *(tree->next_status[ply].exclude++) = possible;
  153.         tree->next_status[ply].phase = KILLER2;
  154.         tree->phase[ply] = KILLER1;
  155.         return ++tree->next_status[ply].order;
  156.       }
  157.     case KILLER2:
  158.       possible = tree->killers[ply].move2;
  159.       if (!Exclude(tree, ply, possible) &&
  160.           ValidMove(tree, ply, side, possible)) {
  161.         tree->curmv[ply] = possible;
  162.         *(tree->next_status[ply].exclude++) = possible;
  163.         tree->next_status[ply].phase = (ply < 3) ? COUNTER_MOVE1 : KILLER3;
  164.         tree->phase[ply] = KILLER2;
  165.         return ++tree->next_status[ply].order;
  166.       }
  167.     case KILLER3:
  168.       possible = tree->killers[ply - 2].move1;
  169.       if (!Exclude(tree, ply, possible) &&
  170.           ValidMove(tree, ply, side, possible)) {
  171.         tree->curmv[ply] = possible;
  172.         *(tree->next_status[ply].exclude++) = possible;
  173.         tree->next_status[ply].phase = KILLER4;
  174.         tree->phase[ply] = KILLER3;
  175.         return ++tree->next_status[ply].order;
  176.       }
  177.     case KILLER4:
  178.       possible = tree->killers[ply - 2].move2;
  179.       if (!Exclude(tree, ply, possible) &&
  180.           ValidMove(tree, ply, side, possible)) {
  181.         tree->curmv[ply] = possible;
  182.         *(tree->next_status[ply].exclude++) = possible;
  183.         tree->next_status[ply].phase = COUNTER_MOVE1;
  184.         tree->phase[ply] = KILLER4;
  185.         return ++tree->next_status[ply].order;
  186.       }
  187. /*
  188.  ************************************************************
  189.  *                                                          *
  190.  *  Now, before we give up and generate moves, try the      *
  191.  *  counter-move which was a move that failed high in the   *
  192.  *  past when the move at the previous ply was played.      *
  193.  *                                                          *
  194.  ************************************************************
  195.  */
  196.     case COUNTER_MOVE1:
  197.       possible = tree->counter_move[tree->curmv[ply - 1] & 4095].move1;
  198.       if (!Exclude(tree, ply, possible) &&
  199.           ValidMove(tree, ply, side, possible)) {
  200.         tree->curmv[ply] = possible;
  201.         *(tree->next_status[ply].exclude++) = possible;
  202.         tree->next_status[ply].phase = COUNTER_MOVE2;
  203.         tree->phase[ply] = COUNTER_MOVE1;
  204.         return ++tree->next_status[ply].order;
  205.       }
  206.     case COUNTER_MOVE2:
  207.       possible = tree->counter_move[tree->curmv[ply - 1] & 4095].move2;
  208.       if (!Exclude(tree, ply, possible) &&
  209.           ValidMove(tree, ply, side, possible)) {
  210.         tree->curmv[ply] = possible;
  211.         *(tree->next_status[ply].exclude++) = possible;
  212.         tree->next_status[ply].phase = MOVE_PAIR1;
  213.         tree->phase[ply] = COUNTER_MOVE2;
  214.         return ++tree->next_status[ply].order;
  215.       }
  216. /*
  217.  ************************************************************
  218.  *                                                          *
  219.  *  Finally we try paired moves, which are simply moves     *
  220.  *  that were good when played after the other move in the  *
  221.  *  pair was played two plies back.                         *
  222.  *                                                          *
  223.  ************************************************************
  224.  */
  225.     case MOVE_PAIR1:
  226.       possible = tree->move_pair[tree->curmv[ply - 2] & 4095].move1;
  227.       if (!Exclude(tree, ply, possible) &&
  228.           ValidMove(tree, ply, side, possible)) {
  229.         tree->curmv[ply] = possible;
  230.         *(tree->next_status[ply].exclude++) = possible;
  231.         tree->next_status[ply].phase = MOVE_PAIR2;
  232.         tree->phase[ply] = MOVE_PAIR1;
  233.         return ++tree->next_status[ply].order;
  234.       }
  235.     case MOVE_PAIR2:
  236.       possible = tree->move_pair[tree->curmv[ply - 2] & 4095].move2;
  237.       if (!Exclude(tree, ply, possible) &&
  238.           ValidMove(tree, ply, side, possible)) {
  239.         tree->curmv[ply] = possible;
  240.         *(tree->next_status[ply].exclude++) = possible;
  241.         tree->next_status[ply].phase = GENERATE_QUIET;
  242.         tree->phase[ply] = MOVE_PAIR2;
  243.         return ++tree->next_status[ply].order;
  244.       }
  245. /*
  246.  ************************************************************
  247.  *                                                          *
  248.  *  Now, generate all non-capturing moves, which get added  *
  249.  *  to the move list behind any captures we did not search. *
  250.  *                                                          *
  251.  ************************************************************
  252.  */
  253.     case GENERATE_QUIET:
  254.       if (!in_check)
  255.         tree->last[ply] =
  256.             GenerateNoncaptures(tree, ply, side, tree->last[ply]);
  257.       tree->next_status[ply].last = tree->last[ply - 1];
  258. /*
  259.  ************************************************************
  260.  *                                                          *
  261.  *  Now, try the history moves.  This phase takes the       *
  262.  *  complete move list, and passes over them in a classic   *
  263.  *  selection-sort, choosing the move with the highest      *
  264.  *  history score.  This phase is only done one time, as it *
  265.  *  also purges the hash, killer, counter and paired moves  *
  266.  *  from the list.                                          *
  267.  *                                                          *
  268.  ************************************************************
  269.  */
  270.       tree->next_status[ply].remaining = 0;
  271.       tree->next_status[ply].phase = HISTORY;
  272.       bestval = -99999999;
  273.       bestp = 0;
  274.       for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
  275.         if (*movep) {
  276.           if (Exclude(tree, ply, *movep))
  277.             *movep = 0;
  278.           else if (depth >= 6) {
  279.             tree->next_status[ply].remaining++;
  280.             hist = history[HistoryIndex(side, *movep)];
  281.             if (hist > bestval) {
  282.               bestval = hist;
  283.               bestp = movep;
  284.             }
  285.           }
  286.         }
  287.       tree->next_status[ply].remaining /= 2;
  288.       if (bestp) {
  289.         tree->curmv[ply] = Move(*bestp);
  290.         *bestp = 0;
  291.         tree->phase[ply] = HISTORY;
  292.         return ++tree->next_status[ply].order;
  293.       }
  294.       goto remaining_moves;
  295. /*
  296.  ************************************************************
  297.  *                                                          *
  298.  *  Now, continue with the history moves, but since one     *
  299.  *  pass has been made over the complete move list, there   *
  300.  *  are no hash/killer moves left in the list, so the tests *
  301.  *  for these can be avoided.                               *
  302.  *                                                          *
  303.  ************************************************************
  304.  */
  305.     case HISTORY:
  306.       if (depth >= 6) {
  307.         bestval = -99999999;
  308.         bestp = 0;
  309.         for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
  310.           if (*movep) {
  311.             hist = history[HistoryIndex(side, *movep)];
  312.             if (hist > bestval) {
  313.               bestval = hist;
  314.               bestp = movep;
  315.             }
  316.           }
  317.         if (bestp) {
  318.           tree->curmv[ply] = Move(*bestp);
  319.           *bestp = 0;
  320.           if (--(tree->next_status[ply].remaining) <= 0) {
  321.             tree->next_status[ply].phase = REMAINING;
  322.             tree->next_status[ply].last = tree->last[ply - 1];
  323.           }
  324.           tree->phase[ply] = HISTORY;
  325.           return ++tree->next_status[ply].order;
  326.         }
  327.       }
  328. /*
  329.  ************************************************************
  330.  *                                                          *
  331.  *  Then we try the rest of the set of moves, and we do not *
  332.  *  use Exclude() function to skip any moves we have        *
  333.  *  already searched (hash or killers) since the history    *
  334.  *  phase above has already done that.                      *
  335.  *                                                          *
  336.  ************************************************************
  337.  */
  338.     remaining_moves:
  339.       tree->next_status[ply].phase = REMAINING;
  340.       tree->next_status[ply].last = tree->last[ply - 1];
  341.     case REMAINING:
  342.       for (; tree->next_status[ply].last < tree->last[ply];
  343.           tree->next_status[ply].last++)
  344.         if (*tree->next_status[ply].last) {
  345.           tree->curmv[ply] = Move(*tree->next_status[ply].last++);
  346.           tree->phase[ply] = REMAINING;
  347.           return ++tree->next_status[ply].order;
  348.         }
  349.       return NONE;
  350.     default:
  351.       Print(4095, "oops!  next_status.phase is bad! [phase=%d]\n",
  352.           tree->next_status[ply].phase);
  353.   }
  354.   return NONE;
  355. }
  356.  
  357. /* last modified 07/03/14 */
  358. /*
  359.  *******************************************************************************
  360.  *                                                                             *
  361.  *   NextRootMove() is used to select the next move from the root move list.   *
  362.  *                                                                             *
  363.  *   There is one subtle trick here that must not be broken.  Crafty does LMR  *
  364.  *   at the root, and the reduction amount is dependent on the order in which  *
  365.  *   a specific move is searched.  With the recent changes dealing with this   *
  366.  *   issue in non-root moves, NextRootMove() now simply returns the move's     *
  367.  *   order within the move list.  This might be a problem if the last move in  *
  368.  *   the list fails high, because it would be reduced on the re-search, which  *
  369.  *   is something we definitely don't want.  The solution is found in the code *
  370.  *   inside Iterate().  When a move fails high, it is moved to the top of the  *
  371.  *   move list so that (a) it is searched first on the re-search (more on this *
  372.  *   in a moment) and (b) since its position in the move list is now #1, it    *
  373.  *   will get an order value of 1 which is never reduced.  The only warning is *
  374.  *   that Iterate() MUST re-sort the ply-1 move list after a fail high, even   *
  375.  *   though it seems like a very tiny computational waste.                     *
  376.  *                                                                             *
  377.  *   The other reason for doing the re-sort has to do with the parallel search *
  378.  *   algorithm.  When one thread fails high at the root, it stops the others.  *
  379.  *   they have to carefully undo the "this move has been searched" flag since  *
  380.  *   these incomplete searches need to be re-done after the fail-high move is  *
  381.  *   finished.  But it is possible some of those interrupted moves appear      *
  382.  *   before the fail high move in the move list.  Which would lead Crafty to   *
  383.  *   fail high, then produce a different best move's PV.  By re-sorting, now   *
  384.  *   the fail-high move is always searched first since here we just start at   *
  385.  *   the top of the move list and look for the first "not yet searched" move   *
  386.  *   to return.  It solves several problems, but if that re-sort is not done,  *
  387.  *   things go south quickly.  The voice of experience is all I will say here. *
  388.  *                                                                             *
  389.  *******************************************************************************
  390.  */
  391. int NextRootMove(TREE * RESTRICT tree, TREE * RESTRICT mytree, int side) {
  392.   uint64_t total_nodes;
  393.   int which, i, t;
  394.  
  395. /*
  396.  ************************************************************
  397.  *                                                          *
  398.  *  First, we check to see if we only have one legal move.  *
  399.  *  If so, and we are not pondering, we stop after a short  *
  400.  *  search, saving time, but making sure we have something  *
  401.  *  to ponder.                                              *
  402.  *                                                          *
  403.  ************************************************************
  404.  */
  405.   if (!annotate_mode && !pondering && !booking && n_root_moves == 1 &&
  406.       iteration > 10) {
  407.     abort_search = 1;
  408.     return NONE;
  409.   }
  410. /*
  411.  ************************************************************
  412.  *                                                          *
  413.  *  For the moves at the root of the tree, the list has     *
  414.  *  already been generated and sorted.                      *
  415.  *                                                          *
  416.  *  We simply have to find the first move that has a zero   *
  417.  *  "already searched" flag and choose that one.  We do set *
  418.  *  the "already searched" flag for this move before we     *
  419.  *  return so that it won't be searched again in another    *
  420.  *  thread.                                                 *
  421.  *                                                          *
  422.  ************************************************************
  423.  */
  424.   for (which = 0; which < n_root_moves; which++) {
  425.     if (!(root_moves[which].status & 8)) {
  426.       if (search_move) {
  427.         if (root_moves[which].move != search_move) {
  428.           root_moves[which].status |= 8;
  429.           continue;
  430.         }
  431.       }
  432.       tree->curmv[1] = root_moves[which].move;
  433.       root_moves[which].status |= 8;
  434. /*
  435.  ************************************************************
  436.  *                                                          *
  437.  *  We have found a move to search.  If appropriate, we     *
  438.  *  display this move, along with the time and information  *
  439.  *  such as which move this is in the list and how many     *
  440.  *  are left to search before this iteration is done, and   *
  441.  *  a "status" character that shows the state of the        *
  442.  *  current search ("?" means we are pondering, waiting on  *
  443.  *  a move to be entered, "*" means we are searching and    *
  444.  *  our clock is running).  We also display the NPS for     *
  445.  *  the search, simply for information about how fast the   *
  446.  *  machine is running.                                     *
  447.  *                                                          *
  448.  ************************************************************
  449.  */
  450.       if (ReadClock() - start_time > noise_level && display_options & 16) {
  451.         sprintf(mytree->remaining_moves_text, "%d/%d", which + 1,
  452.             n_root_moves);
  453.         end_time = ReadClock();
  454.         Lock(lock_io);
  455.         if (pondering)
  456.           printf("         %2i   %s%7s?  ", iteration,
  457.               Display2Times(end_time - start_time),
  458.               mytree->remaining_moves_text);
  459.         else
  460.           printf("         %2i   %s%7s*  ", iteration,
  461.               Display2Times(end_time - start_time),
  462.               mytree->remaining_moves_text);
  463.         printf("%d. ", move_number);
  464.         if (Flip(side))
  465.           printf("... ");
  466.         strcpy(mytree->root_move_text, OutputMove(tree, 1, side,
  467.                 tree->curmv[1]));
  468.         total_nodes = block[0]->nodes_searched;
  469.         for (t = 0; t < smp_max_threads; t++)
  470.           for (i = 0; i < 64; i++)
  471.             if (!(thread[t].blocks & SetMask(i)))
  472.               total_nodes += block[t * 64 + 1 + i]->nodes_searched;
  473.         nodes_per_second = (unsigned int) (total_nodes * 100 / Max(end_time - start_time, 1)); // Pierre-Marie Baty -- added type cast
  474.         i = strlen(mytree->root_move_text);
  475.         i = (i < 8) ? i : 8;
  476.         strncat(mytree->root_move_text, "          ", 8 - i);
  477.         printf("%s", mytree->root_move_text);
  478.         printf("(%snps)             \r", DisplayKMB(nodes_per_second, 0));
  479.         fflush(stdout);
  480.         Unlock(lock_io);
  481.       }
  482. /*
  483.  ************************************************************
  484.  *                                                          *
  485.  *  Bit of a tricky exit.  If the move is not flagged as    *
  486.  *  "OK to search in parallel or reduce" then we return     *
  487.  *  "DO_NOT_REDUCE" which will prevent Search() from        *
  488.  *  reducing the move (LMR).  Otherwise we return the more  *
  489.  *  common "REMAINING" value which allows LMR to be used on *
  490.  *  those root moves.                                       *
  491.  *                                                          *
  492.  ************************************************************
  493.  */
  494.       if (root_moves[which].status & 4)
  495.         tree->phase[1] = DO_NOT_REDUCE;
  496.       else
  497.         tree->phase[1] = REMAINING;
  498.       return which + 1;
  499.     }
  500.   }
  501.   return NONE;
  502. }
  503.  
  504. /* last modified 11/13/14 */
  505. /*
  506.  *******************************************************************************
  507.  *                                                                             *
  508.  *   NextRootMoveParallel() is used to determine if the next root move can be  *
  509.  *   searched in parallel.  If it appears to Iterate() that one of the moves   *
  510.  *   following the first move might become the best move, the 'no parallel'    *
  511.  *   flag is set to speed up finding the new best move.  This flag is set if   *
  512.  *   this root move has an "age" value > 0 which indicates this move was the   *
  513.  *   "best move" within the previous 3 search iterations.  We want to search   *
  514.  *   such moves as quickly as possible, prior to starting a parallel search at *
  515.  *   the root, in case this move once again becomes the best move and provides *
  516.  *   a better alpha bound.                                                     *
  517.  *                                                                             *
  518.  *******************************************************************************
  519.  */
  520. int NextRootMoveParallel(void) {
  521.   int which;
  522.  
  523. /*
  524.  ************************************************************
  525.  *                                                          *
  526.  *  Here we simply check the root_move status flag that is  *
  527.  *  set in Iterate() after each iteration is completed.  A  *
  528.  *  value of "1" indicates this move has to be searched by  *
  529.  *  all processors together, splitting at the root must     *
  530.  *  wait until we have searched all moves that have been    *
  531.  *  "best" during the previous three plies.                 *
  532.  *                                                          *
  533.  *  The root move list has a flag, bit 3, used to indicate  *
  534.  *  that this move has been best recently.  If this bit is  *
  535.  *  set, we are forced to use all processors to search this *
  536.  *  move so that it is completed quickly rather than being  *
  537.  *  searched by just one processor, and taking much longer  *
  538.  *  to get a score back.  We do this to give the search the *
  539.  *  best opportunity to fail high on this move before we    *
  540.  *  run out of time.                                        *
  541.  *                                                          *
  542.  ************************************************************
  543.  */
  544.   for (which = 0; which < n_root_moves; which++)
  545.     if (!(root_moves[which].status & 8))
  546.       break;
  547.   if (which < n_root_moves && !(root_moves[which].status & 4))
  548.     return 1;
  549.   return 0;
  550. }
  551.  
  552. /* last modified 09/11/15 */
  553. /*
  554.  *******************************************************************************
  555.  *                                                                             *
  556.  *   Exclude() searches the list of moves searched prior to generating a move  *
  557.  *   list to exclude those that were searched via a hash table best move or    *
  558.  *   through the killer moves for the current ply and two plies back.          *
  559.  *                                                                             *
  560.  *   The variable next_status[].excluded is the total number of non-generated  *
  561.  *   moves we searched.  next_status[].remaining is initially set to excluded, *
  562.  *   but each time an excluded move is found, the counter is decremented.      *
  563.  *   Once all excluded moves have been found, we avoid running through the     *
  564.  *   list of excluded moves on each call and simply return.                    *
  565.  *                                                                             *
  566.  *******************************************************************************
  567.  */
  568. int Exclude(TREE * RESTRICT tree, int ply, int move) {
  569.   unsigned *i;
  570.  
  571.   if (tree->next_status[ply].exclude > &tree->next_status[ply].done[0])
  572.     for (i = &tree->next_status[ply].done[0];
  573.         i < tree->next_status[ply].exclude; i++)
  574.       if (move == *i)
  575.         return 1;
  576.   return 0;
  577. }
  578.  
  579. /* last modified 05/20/15 */
  580. /*
  581.  *******************************************************************************
  582.  *                                                                             *
  583.  *   NextSort() is used to sort the move list.  This is a list of 32 bit       *
  584.  *   values where the rightmost 21 bits is the compressed move, and the left-  *
  585.  *   most 11 bits are the sort key (MVV/LVA values).                           *
  586.  *                                                                             *
  587.  *******************************************************************************
  588.  */
  589. void NextSort(TREE * RESTRICT tree, int ply) {
  590.   unsigned temp, *movep, *tmovep;
  591.  
  592. /*
  593.  ************************************************************
  594.  *                                                          *
  595.  *  This is a simple insertion sort algorithm.              *
  596.  *                                                          *
  597.  ************************************************************
  598.  */
  599.   if (tree->last[ply] > tree->last[ply - 1] + 1) {
  600.     for (movep = tree->last[ply - 1] + 1; movep < tree->last[ply]; movep++) {
  601.       temp = *movep;
  602.       tmovep = movep - 1;
  603.       while (tmovep >= tree->last[ply - 1] && SortV(*tmovep) < SortV(temp)) {
  604.         *(tmovep + 1) = *tmovep;
  605.         tmovep--;
  606.       }
  607.       *(tmovep + 1) = temp;
  608.     }
  609.   }
  610. }
  611.