Subversion Repositories Games.Chess Giants

#include "chess.h"

#include "data.h"

/* last modified 12/29/15 */

/*

 *******************************************************************************

 *                                                                             *

 *   NextMove() is used to select the next move from the current move list.    *

 *                                                                             *

 *   The "excluded move" code below simply collects any moves that were        *

 *   searched without being generated (hash move and up to 4 killers).  We     *

 *   save them in the NEXT structure and make sure to exclude them when        *

 *   searching after a move generation to avoid the duplicated effort.         *

 *                                                                             *

 *******************************************************************************

 */

int NextMove(TREE * RESTRICT tree, int ply, int depth, int side, int in_check) {

  unsigned *movep, *bestp;

  int hist, bestval, possible;

/*

 ************************************************************

 *                                                          *

 *  The following "big switch" controls the finate state    *

 *  machine that selects moves.  The "phase" value in the   *

 *  next_status[ply] structure is always set after a move   *

 *  is selected, and it defines the next state of the FSM   *

 *  so select the next move in a sequenced order.           *

 *                                                          *

 ************************************************************

 */

  switch (tree->next_status[ply].phase) {

/*

 ************************************************************

 *                                                          *

 *  First, try the transposition table move (which will be  *

 *  the principal variation move as we first move down the  *

 *  tree) or the best move found in this position during a  *

 *  prior search.                                           *

 *                                                          *

 ************************************************************

 */

    case HASH:

      tree->next_status[ply].order = 0;

      tree->next_status[ply].exclude = &tree->next_status[ply].done[0];

      tree->next_status[ply].phase = GENERATE_CAPTURES;

      if (tree->hash_move[ply]) {

        tree->curmv[ply] = tree->hash_move[ply];

        *(tree->next_status[ply].exclude++) = tree->curmv[ply];

        if (ValidMove(tree, ply, side, tree->curmv[ply])) {

          tree->phase[ply] = HASH;

          return ++tree->next_status[ply].order;

        }

#if defined(DEBUG)

        else

          Print(2048, "ERROR:  bad move from hash table, ply=%d\n", ply);

#endif

      }

/*

 ************************************************************

 *                                                          *

 *  Generate captures and sort them based on the simple     *

 *  MVV/LVA ordering where we try to capture the most       *

 *  valuable victim piece possible, using the least         *

 *  valuable attacking piece possible.  Later we will test  *

 *  to see if the capture appears to lose material and we   *

 *  will defer searching it until later.                    *

 *                                                          *

 *  Or, if in check, generate all the legal moves that      *

 *  escape check by using GenerateCheckEvasions().  After   *

 *  we do this, we sort them using MVV/LVA to move captures *

 *  to the front of the list in the correct order.          *

 *                                                          *

 ************************************************************

 */

    case GENERATE_CAPTURES:

      tree->next_status[ply].phase = CAPTURES;

      if (!in_check)

        tree->last[ply] =

            GenerateCaptures(tree, ply, side, tree->last[ply - 1]);

      else

        tree->last[ply] =

            GenerateCheckEvasions(tree, ply, side, tree->last[ply - 1]);

/*

 ************************************************************

 *                                                          *

 *  Now make a pass over the moves to assign the sort value *

 *  for each.  We simply use MVV/LVA move order here.  A    *

 *  simple optimization is to use the pre-computed array    *

 *  MVV_LVA[victim][attacker] which returns a simple value  *

 *  that indicates MVV/LVA order.                           *

 *                                                          *

 ************************************************************

 */

      tree->next_status[ply].remaining = 0;

      for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)

        if (*movep == tree->hash_move[ply]) {

          *movep = 0;

          tree->next_status[ply].exclude = &tree->next_status[ply].done[0];

        } else {

          *movep += MVV_LVA[Captured(*movep)][Piece(*movep)];

          tree->next_status[ply].remaining++;

        }

      NextSort(tree, ply);

      tree->next_status[ply].last = tree->last[ply - 1];

      if (in_check)

        goto remaining_moves;

/*

 ************************************************************

 *                                                          *

 *  Try the captures moves, which are in order based on     *

 *  MVV/LVA ordering.  If a larger-valued piece captures a  *

 *  lesser-valued piece, and SEE() says it loses material,  *

 *  this capture will be deferred until later.              *

 *                                                          *

 *  If we are in check, we jump down to the history moves   *

 *  phase (we don't need to generate any more moves as      *

 *  GenerateCheckEvasions has already generated all legal   *

 *  moves.                                                  *

 *                                                          *

 ************************************************************

 */

    case CAPTURES:

      while (tree->next_status[ply].remaining) {

        tree->curmv[ply] = Move(*(tree->next_status[ply].last++));

        if (!--tree->next_status[ply].remaining)

          tree->next_status[ply].phase = KILLER1;

        if (pcval[Piece(tree->curmv[ply])] <=

            pcval[Captured(tree->curmv[ply])]

            || SEE(tree, side, tree->curmv[ply]) >= 0) {

          *(tree->next_status[ply].last - 1) = 0;

          tree->phase[ply] = CAPTURES;

          return ++tree->next_status[ply].order;

        }

      }

/*

 ************************************************************

 *                                                          *

 *  Now, try the killer moves.  This phase tries the two    *

 *  killers for the current ply without generating moves,   *

 *  which saves time if a cutoff occurs.  After those two   *

 *  killers are searched, we try the killers from two plies *

 *  back since they have greater depth and might produce a  *

 *  cutoff if the current two do not.                       *

 *                                                          *

 ************************************************************

 */

    case KILLER1:

      possible = tree->killers[ply].move1;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = KILLER2;

        tree->phase[ply] = KILLER1;

        return ++tree->next_status[ply].order;

      }

    case KILLER2:

      possible = tree->killers[ply].move2;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = (ply < 3) ? COUNTER_MOVE1 : KILLER3;

        tree->phase[ply] = KILLER2;

        return ++tree->next_status[ply].order;

      }

    case KILLER3:

      possible = tree->killers[ply - 2].move1;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = KILLER4;

        tree->phase[ply] = KILLER3;

        return ++tree->next_status[ply].order;

      }

    case KILLER4:

      possible = tree->killers[ply - 2].move2;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = COUNTER_MOVE1;

        tree->phase[ply] = KILLER4;

        return ++tree->next_status[ply].order;

      }

/*

 ************************************************************

 *                                                          *

 *  Now, before we give up and generate moves, try the      *

 *  counter-move which was a move that failed high in the   *

 *  past when the move at the previous ply was played.      *

 *                                                          *

 ************************************************************

 */

    case COUNTER_MOVE1:

      possible = tree->counter_move[tree->curmv[ply - 1] & 4095].move1;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = COUNTER_MOVE2;

        tree->phase[ply] = COUNTER_MOVE1;

        return ++tree->next_status[ply].order;

      }

    case COUNTER_MOVE2:

      possible = tree->counter_move[tree->curmv[ply - 1] & 4095].move2;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = MOVE_PAIR1;

        tree->phase[ply] = COUNTER_MOVE2;

        return ++tree->next_status[ply].order;

      }

/*

 ************************************************************

 *                                                          *

 *  Finally we try paired moves, which are simply moves     *

 *  that were good when played after the other move in the  *

 *  pair was played two plies back.                         *

 *                                                          *

 ************************************************************

 */

    case MOVE_PAIR1:

      possible = tree->move_pair[tree->curmv[ply - 2] & 4095].move1;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = MOVE_PAIR2;

        tree->phase[ply] = MOVE_PAIR1;

        return ++tree->next_status[ply].order;

      }

    case MOVE_PAIR2:

      possible = tree->move_pair[tree->curmv[ply - 2] & 4095].move2;

      if (!Exclude(tree, ply, possible) &&

          ValidMove(tree, ply, side, possible)) {

        tree->curmv[ply] = possible;

        *(tree->next_status[ply].exclude++) = possible;

        tree->next_status[ply].phase = GENERATE_QUIET;

        tree->phase[ply] = MOVE_PAIR2;

        return ++tree->next_status[ply].order;

      }

/*

 ************************************************************

 *                                                          *

 *  Now, generate all non-capturing moves, which get added  *

 *  to the move list behind any captures we did not search. *

 *                                                          *

 ************************************************************

 */

    case GENERATE_QUIET:

      if (!in_check)

        tree->last[ply] =

            GenerateNoncaptures(tree, ply, side, tree->last[ply]);

      tree->next_status[ply].last = tree->last[ply - 1];

/*

 ************************************************************

 *                                                          *

 *  Now, try the history moves.  This phase takes the       *

 *  complete move list, and passes over them in a classic   *

 *  selection-sort, choosing the move with the highest      *

 *  history score.  This phase is only done one time, as it *

 *  also purges the hash, killer, counter and paired moves  *

 *  from the list.                                          *

 *                                                          *

 ************************************************************

 */

      tree->next_status[ply].remaining = 0;

      tree->next_status[ply].phase = HISTORY;

      bestval = -99999999;

      bestp = 0;

      for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)

        if (*movep) {

          if (Exclude(tree, ply, *movep))

            *movep = 0;

          else if (depth >= 6) {

            tree->next_status[ply].remaining++;

            hist = history[HistoryIndex(side, *movep)];

            if (hist > bestval) {

              bestval = hist;

              bestp = movep;

            }

          }

        }

      tree->next_status[ply].remaining /= 2;

      if (bestp) {

        tree->curmv[ply] = Move(*bestp);

        *bestp = 0;

        tree->phase[ply] = HISTORY;

        return ++tree->next_status[ply].order;

      }

      goto remaining_moves;

/*

 ************************************************************

 *                                                          *

 *  Now, continue with the history moves, but since one     *

 *  pass has been made over the complete move list, there   *

 *  are no hash/killer moves left in the list, so the tests *

 *  for these can be avoided.                               *

 *                                                          *

 ************************************************************

 */

    case HISTORY:

      if (depth >= 6) {

        bestval = -99999999;

        bestp = 0;

        for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)

          if (*movep) {

            hist = history[HistoryIndex(side, *movep)];

            if (hist > bestval) {

              bestval = hist;

              bestp = movep;

            }

          }

        if (bestp) {

          tree->curmv[ply] = Move(*bestp);

          *bestp = 0;

          if (--(tree->next_status[ply].remaining) <= 0) {

            tree->next_status[ply].phase = REMAINING;

            tree->next_status[ply].last = tree->last[ply - 1];

          }

          tree->phase[ply] = HISTORY;

          return ++tree->next_status[ply].order;

        }

      }

/*

 ************************************************************

 *                                                          *

 *  Then we try the rest of the set of moves, and we do not *

 *  use Exclude() function to skip any moves we have        *

 *  already searched (hash or killers) since the history    *

 *  phase above has already done that.                      *

 *                                                          *

 ************************************************************

 */

    remaining_moves:

      tree->next_status[ply].phase = REMAINING;

      tree->next_status[ply].last = tree->last[ply - 1];

    case REMAINING:

      for (; tree->next_status[ply].last < tree->last[ply];

          tree->next_status[ply].last++)

        if (*tree->next_status[ply].last) {

          tree->curmv[ply] = Move(*tree->next_status[ply].last++);

          tree->phase[ply] = REMAINING;

          return ++tree->next_status[ply].order;

        }

      return NONE;

    default:

      Print(4095, "oops!  next_status.phase is bad! [phase=%d]\n",

          tree->next_status[ply].phase);

  }

  return NONE;

}

/* last modified 07/03/14 */

/*

 *******************************************************************************

 *                                                                             *

 *   NextRootMove() is used to select the next move from the root move list.   *

 *                                                                             *

 *   There is one subtle trick here that must not be broken.  Crafty does LMR  *

 *   at the root, and the reduction amount is dependent on the order in which  *

 *   a specific move is searched.  With the recent changes dealing with this   *

 *   issue in non-root moves, NextRootMove() now simply returns the move's     *

 *   order within the move list.  This might be a problem if the last move in  *

 *   the list fails high, because it would be reduced on the re-search, which  *

 *   is something we definitely don't want.  The solution is found in the code *

 *   inside Iterate().  When a move fails high, it is moved to the top of the  *

 *   move list so that (a) it is searched first on the re-search (more on this *

 *   in a moment) and (b) since its position in the move list is now #1, it    *

 *   will get an order value of 1 which is never reduced.  The only warning is *

 *   that Iterate() MUST re-sort the ply-1 move list after a fail high, even   *

 *   though it seems like a very tiny computational waste.                     *

 *                                                                             *

 *   The other reason for doing the re-sort has to do with the parallel search *

 *   algorithm.  When one thread fails high at the root, it stops the others.  *

 *   they have to carefully undo the "this move has been searched" flag since  *

 *   these incomplete searches need to be re-done after the fail-high move is  *

 *   finished.  But it is possible some of those interrupted moves appear      *

 *   before the fail high move in the move list.  Which would lead Crafty to   *

 *   fail high, then produce a different best move's PV.  By re-sorting, now   *

 *   the fail-high move is always searched first since here we just start at   *

 *   the top of the move list and look for the first "not yet searched" move   *

 *   to return.  It solves several problems, but if that re-sort is not done,  *

 *   things go south quickly.  The voice of experience is all I will say here. *

 *                                                                             *

 *******************************************************************************

 */

int NextRootMove(TREE * RESTRICT tree, TREE * RESTRICT mytree, int side) {

  uint64_t total_nodes;

  int which, i, t;

/*

 ************************************************************

 *                                                          *

 *  First, we check to see if we only have one legal move.  *

 *  If so, and we are not pondering, we stop after a short  *

 *  search, saving time, but making sure we have something  *

 *  to ponder.                                              *

 *                                                          *

 ************************************************************

 */

  if (!annotate_mode && !pondering && !booking && n_root_moves == 1 &&

      iteration > 10) {

    abort_search = 1;

    return NONE;

  }

/*

 ************************************************************

 *                                                          *

 *  For the moves at the root of the tree, the list has     *

 *  already been generated and sorted.                      *

 *                                                          *

 *  We simply have to find the first move that has a zero   *

 *  "already searched" flag and choose that one.  We do set *

 *  the "already searched" flag for this move before we     *

 *  return so that it won't be searched again in another    *

 *  thread.                                                 *

 *                                                          *

 ************************************************************

 */

  for (which = 0; which < n_root_moves; which++) {

    if (!(root_moves[which].status & 8)) {

      if (search_move) {

        if (root_moves[which].move != search_move) {

          root_moves[which].status |= 8;

          continue;

        }

      }

      tree->curmv[1] = root_moves[which].move;

      root_moves[which].status |= 8;

/*

 ************************************************************

 *                                                          *

 *  We have found a move to search.  If appropriate, we     *

 *  display this move, along with the time and information  *

 *  such as which move this is in the list and how many     *

 *  are left to search before this iteration is done, and   *

 *  a "status" character that shows the state of the        *

 *  current search ("?" means we are pondering, waiting on  *

 *  a move to be entered, "*" means we are searching and    *

 *  our clock is running).  We also display the NPS for     *

 *  the search, simply for information about how fast the   *

 *  machine is running.                                     *

 *                                                          *

 ************************************************************

 */

      if (ReadClock() - start_time > noise_level && display_options & 16) {

        sprintf(mytree->remaining_moves_text, "%d/%d", which + 1,

            n_root_moves);

        end_time = ReadClock();

        Lock(lock_io);

        if (pondering)

          printf("         %2i   %s%7s?  ", iteration,

              Display2Times(end_time - start_time),

              mytree->remaining_moves_text);

        else

          printf("         %2i   %s%7s*  ", iteration,

              Display2Times(end_time - start_time),

              mytree->remaining_moves_text);

        printf("%d. ", move_number);

        if (Flip(side))

          printf("... ");

        strcpy(mytree->root_move_text, OutputMove(tree, 1, side,

                tree->curmv[1]));

        total_nodes = block[0]->nodes_searched;

        for (t = 0; t < smp_max_threads; t++)

          for (i = 0; i < 64; i++)

            if (!(thread[t].blocks & SetMask(i)))

              total_nodes += block[t * 64 + 1 + i]->nodes_searched;

        nodes_per_second = (unsigned int) (total_nodes * 100 / Max(end_time - start_time, 1)); // Pierre-Marie Baty -- added type cast

        i = strlen(mytree->root_move_text);

        i = (i < 8) ? i : 8;

        strncat(mytree->root_move_text, "          ", 8 - i);

        printf("%s", mytree->root_move_text);

        printf("(%snps)             \r", DisplayKMB(nodes_per_second, 0));

        fflush(stdout);

        Unlock(lock_io);

      }

/*

 ************************************************************

 *                                                          *

 *  Bit of a tricky exit.  If the move is not flagged as    *

 *  "OK to search in parallel or reduce" then we return     *

 *  "DO_NOT_REDUCE" which will prevent Search() from        *

 *  reducing the move (LMR).  Otherwise we return the more  *

 *  common "REMAINING" value which allows LMR to be used on *

 *  those root moves.                                       *

 *                                                          *

 ************************************************************

 */

      if (root_moves[which].status & 4)

        tree->phase[1] = DO_NOT_REDUCE;

      else

        tree->phase[1] = REMAINING;

      return which + 1;

    }

  }

  return NONE;

}

/* last modified 11/13/14 */

/*

 *******************************************************************************

 *                                                                             *

 *   NextRootMoveParallel() is used to determine if the next root move can be  *

 *   searched in parallel.  If it appears to Iterate() that one of the moves   *

 *   following the first move might become the best move, the 'no parallel'    *

 *   flag is set to speed up finding the new best move.  This flag is set if   *

 *   this root move has an "age" value > 0 which indicates this move was the   *

 *   "best move" within the previous 3 search iterations.  We want to search   *

 *   such moves as quickly as possible, prior to starting a parallel search at *

 *   the root, in case this move once again becomes the best move and provides *

 *   a better alpha bound.                                                     *

 *                                                                             *

 *******************************************************************************

 */

int NextRootMoveParallel(void) {

  int which;

/*

 ************************************************************

 *                                                          *

 *  Here we simply check the root_move status flag that is  *

 *  set in Iterate() after each iteration is completed.  A  *

 *  value of "1" indicates this move has to be searched by  *

 *  all processors together, splitting at the root must     *

 *  wait until we have searched all moves that have been    *

 *  "best" during the previous three plies.                 *

 *                                                          *

 *  The root move list has a flag, bit 3, used to indicate  *

 *  that this move has been best recently.  If this bit is  *

 *  set, we are forced to use all processors to search this *

 *  move so that it is completed quickly rather than being  *

 *  searched by just one processor, and taking much longer  *

 *  to get a score back.  We do this to give the search the *

 *  best opportunity to fail high on this move before we    *

 *  run out of time.                                        *

 *                                                          *

 ************************************************************

 */

  for (which = 0; which < n_root_moves; which++)

    if (!(root_moves[which].status & 8))

      break;

  if (which < n_root_moves && !(root_moves[which].status & 4))

    return 1;

  return 0;

}

/* last modified 09/11/15 */

/*

 *******************************************************************************

 *                                                                             *

 *   Exclude() searches the list of moves searched prior to generating a move  *

 *   list to exclude those that were searched via a hash table best move or    *

 *   through the killer moves for the current ply and two plies back.          *

 *                                                                             *

 *   The variable next_status[].excluded is the total number of non-generated  *

 *   moves we searched.  next_status[].remaining is initially set to excluded, *

 *   but each time an excluded move is found, the counter is decremented.      *

 *   Once all excluded moves have been found, we avoid running through the     *

 *   list of excluded moves on each call and simply return.                    *

 *                                                                             *

 *******************************************************************************

 */

int Exclude(TREE * RESTRICT tree, int ply, int move) {

  unsigned *i;

  if (tree->next_status[ply].exclude > &tree->next_status[ply].done[0])

    for (i = &tree->next_status[ply].done[0];

        i < tree->next_status[ply].exclude; i++)

      if (move == *i)

        return 1;

  return 0;

}

/* last modified 05/20/15 */

/*

 *******************************************************************************

 *                                                                             *

 *   NextSort() is used to sort the move list.  This is a list of 32 bit       *

 *   values where the rightmost 21 bits is the compressed move, and the left-  *

 *   most 11 bits are the sort key (MVV/LVA values).                           *

 *                                                                             *

 *******************************************************************************

 */

void NextSort(TREE * RESTRICT tree, int ply) {

  unsigned temp, *movep, *tmovep;

/*

 ************************************************************

 *                                                          *

 *  This is a simple insertion sort algorithm.              *

 *                                                          *

 ************************************************************

 */

  if (tree->last[ply] > tree->last[ply - 1] + 1) {

    for (movep = tree->last[ply - 1] + 1; movep < tree->last[ply]; movep++) {

      temp = *movep;

      tmovep = movep - 1;

      while (tmovep >= tree->last[ply - 1] && SortV(*tmovep) < SortV(temp)) {

        *(tmovep + 1) = *tmovep;

        tmovep--;

      }

      *(tmovep + 1) = temp;

    }

  }

}