search.c

#include "chess.h"
#include "data.h"
/* last modified 01/10/16 */
/*
 *******************************************************************************
 *                                                                             *
 *   Search() is the recursive routine used to implement the alpha/beta        *
 *   negamax search (similar to minimax but simpler to code.)  Search() is     *
 *   called whenever there is "depth" remaining so that all moves are subject  *
 *   to searching.  Search() recursively calls itself so long as there is at   *
 *   least one ply of depth left, otherwise it calls Quiesce() instead.        *
 *                                                                             *
 *******************************************************************************
 */
int Search(TREE * RESTRICT tree, int ply, int depth, int wtm, int alpha,
    int beta, int in_check, int do_null) {
  int repeat = 0, value = 0, pv_node = alpha != beta - 1, n_depth;
  int searched[256];

/*
 ************************************************************
 *                                                          *
 *  Timeout.  Check to see if we have searched enough nodes *
 *  that it is time to peek at how much time has been used, *
 *  or if is time to check for operator keyboard input.     *
 *  This is usually enough nodes to force a time/input      *
 *  check about once per second, except when the target     *
 *  time per move is very small, in which case we try to    *
 *  check the time more frequently.                         *
 *                                                          *
 *  Note that we check input or time-out in thread 0.  This *
 *  makes the code simpler and eliminates some problematic  *
 *  race conditions.                                        *
 *                                                          *
 ************************************************************
 */
#if defined(NODES)
  if (search_nodes && --temp_search_nodes <= 0) {
    abort_search = 1;
    return 0;
  }
#endif
  if (tree->thread_id == 0) {
    if (--next_time_check <= 0) {
      next_time_check = nodes_between_time_checks;
      if (TimeCheck(tree, 1)) {
        abort_search = 1;
        return 0;
      }
      if (CheckInput()) {
        Interrupt(ply);
        if (abort_search)
          return 0;
      }
    }
  }
  if (ply >= MAXPLY - 1)
    return beta;
/*
 ************************************************************
 *                                                          *
 *  Draws.  Check for draw by repetition, which includes    *
 *  50 move draws also.  This is the quickest way to get    *
 *  out of further searching, with minimal effort.  This    *
 *  and the next four steps are skipped for moves at the    *
 *  root (ply = 1).                                         *
 *                                                          *
 ************************************************************
 */
  if (ply > 1) {
    if ((repeat = Repeat(tree, ply))) {
      if (repeat == 1 || !in_check) {
        value = DrawScore(wtm);
        if (value < beta)
          SavePV(tree, ply, 3);
#if defined(TRACE)
        if (ply <= trace_level)
          printf("draw by repetition detected, ply=%d.\n", ply);
#endif
        return value;
      }
    }
/*
 ************************************************************
 *                                                          *
 *  Mate distance pruning.  If we have found a mate, we can *
 *  stop if we are too deep to find a shorter mate.  This   *
 *  only affects the size of the tree in positions where    *
 *  there are forced mates.  It does not change the outcome *
 *  of the search at all, just the time it takes.           *
 *                                                          *
 ************************************************************
 */
    alpha = Max(alpha, -MATE + ply - 1);
    beta = Min(beta, MATE - ply);
    if (alpha >= beta)
      return alpha;
/*
 ************************************************************
 *                                                          *
 *  Trans/Ref.  Check the transposition/refutation (hash)   *
 *  table to see if we have searched this position          *
 *  previously and still have the results available.  We    *
 *  might get a real score, or a bound, or perhaps only a   *
 *  good move to try first.  The possible results are:      *
 *                                                          *
 *  1. HashProbe() returns "HASH_HIT".  This terminates the *
 *  search instantly and we simply return the value found   *
 *  in the hash table.  This value is simply the value we   *
 *  found when we did a real search in this position        *
 *  previously, and ProbeTransRef() verifies that the value *
 *  is useful based on draft and current bounds.            *
 *                                                          *
 *  2. HashProbe() returns "AVOID_NULL_MOVE" which means    *
 *  the hashed score/bound was no good, but it indicated    *
 *  that trying a null-move in this position would be a     *
 *  waste of time since it will likely fail low, not high.  *
 *                                                          *
 *  3. HashProbe() returns "HASH_MISS" when forces us to do *
 *  a normal search to resolve this node.                   *
 *                                                          *
 ************************************************************
 */
    switch (HashProbe(tree, ply, depth, wtm, alpha, beta, &value)) {
      case HASH_HIT:
        return value;
      case AVOID_NULL_MOVE:
        do_null = 0;
      case HASH_MISS:
        break;
    }
/*
 ************************************************************
 *                                                          *
 *  EGTBs.  Now it's time to try a probe into the endgame   *
 *  tablebase files.  This is done if we notice that there  *
 *  are 6 or fewer pieces left on the board AND the move at *
 *  the previous ply was a capture.  If it was not, then we *
 *  would have already probed the EGTBs so if it was a miss *
 *  when we probed then, it will also miss here.  EGTB_use  *
 *  tells us how many pieces to probe on.  Note that this   *
 *  can be zero when trying to swindle the opponent, so     *
 *  that no probes are done since we know it is a draw.     *
 *  This is another way to get out of the search quickly,   *
 *  but not as quickly as the previous steps since this can *
 *  result in an I/O operation.                             *
 *                                                          *
 *  Note that in "swindle mode" this can be turned off by   *
 *  Iterate() setting "EGTB_use = 0" so that we won't probe *
 *  the EGTBs since we are searching only the root moves    *
 *  that lead to a draw and we want to play the move that   *
 *  makes the draw more difficult to reach by the opponent  *
 *  to give him a chance to make a mistake.                 *
 *                                                          *
 *  Another special case is that we slightly fudge the      *
 *  score for draws.  In a normal circumstance, draw=0.00   *
 *  since it is "equal".  However, here we add 0.01 if      *
 *  white has more material, or subtract 0.01 if black has  *
 *  more material, since in a drawn KRP vs KR we would      *
 *  prefer to have the KRP side since the opponent can make *
 *  a mistake and convert the draw to a loss.               *
 *                                                          *
 ************************************************************
 */
#if !defined(NOEGTB)
    if (depth > EGTB_depth && TotalAllPieces <= EGTB_use &&
        !Castle(ply, white) && !Castle(ply, black) &&
        (Captured(tree->curmv[ply - 1]) || ply < 3)) {
      int egtb_value;

      tree->egtb_probes++;
      if (EGTBProbe(tree, ply, wtm, &egtb_value)) {
        tree->egtb_hits++;
        alpha = egtb_value;
        if (MateScore(alpha))
          alpha += (alpha > 0) ? -ply + 1 : ply;
        else if (alpha == 0) {
          alpha = DrawScore(wtm);
          if (MaterialSTM(wtm) > 0)
            alpha += 1;
          else if (MaterialSTM(wtm) < 0)
            alpha -= 1;
        }
        if (alpha < beta)
          SavePV(tree, ply, 2);
        return alpha;
      }
    }
#endif
/*
 ************************************************************
 *                                                          *
 *  Null-move.  We now know there is no quick way to get    *
 *  out of here, which leaves one more possibility,         *
 *  although it does require a search, but to a reduced     *
 *  depth.  We try a null move to see if we can get a quick *
 *  cutoff with only a little work.  This operates as       *
 *  follows.  Instead of making a legal move, the side on   *
 *  move passes and does nothing.  The resulting position   *
 *  is searched to a shallower depth than normal (see       *
 *  below).  This will result in a cutoff if our position   *
 *  is very good, but it produces the cutoff much quicker   *
 *  since the search is far shallower than a normal search  *
 *  that would also be likely to fail high.                 *
 *                                                          *
 *  The reduction amount starts off at null_depth (normally *
 *  set to 3 but the user can change this via the crafty    *
 *  personality command) but is then increased as follows:  *
 *                                                          *
 *     R = null_depth + depth / null_divisor                *
 *                                                          *
 *  null_divisor defaults to 6, but this can also be set    *
 *  by the user to try more/less aggressive settings.       *
 *                                                          *
 *  This is skipped for any of the following reasons:       *
 *                                                          *
 *  1. The side on move is in check.  The null move         *
 *     results in an illegal position.                      *
 *  2. No more than one null move can appear in succession  *
 *     as all this does is burn 2x plies of depth.          *
 *  3. The side on move has only pawns left, which makes    *
 *     zugzwang positions more likely.                      *
 *  4. The transposition table probe found an entry that    *
 *     indicates that a null-move search will not fail      *
 *     high, so we avoid the wasted effort.                 *
 *                                                          *
 ************************************************************
 */

    tree->last[ply] = tree->last[ply - 1];
    n_depth = (TotalPieces(wtm, occupied) > 9 || n_root_moves > 17 ||
            depth > 3) ? 1 : 3;
    if (do_null && !pv_node && depth > n_depth && !in_check &&
        TotalPieces(wtm, occupied)) {
      uint64_t save_hash_key;
      int R = null_depth + depth / null_divisor;

      tree->curmv[ply] = 0;
#if defined(TRACE)
      if (ply <= trace_level)
        Trace(tree, ply, depth, wtm, value - 1, value, "SearchNull", serial,
            NULL_MOVE, 0);
#endif
      tree->status[ply + 1] = tree->status[ply];
      Reversible(ply + 1) = 0;
      save_hash_key = HashKey;
      if (EnPassant(ply + 1)) {
        HashEP(EnPassant(ply + 1));
        EnPassant(ply + 1) = 0;
      }
      tree->null_done[Min(R, 15)]++;
      if (depth - R - 1 > 0)
        value =
            -Search(tree, ply + 1, depth - R - 1, Flip(wtm), -beta, -beta + 1,
            0, NO_NULL);
      else
        value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -beta + 1, 1);
      HashKey = save_hash_key;
      if (abort_search || tree->stop)
        return 0;
      if (value >= beta) {
        HashStore(tree, ply, depth, wtm, LOWER, value, tree->hash_move[ply]);
        return value;
      }
    }
/*
 ************************************************************
 *                                                          *
 *  IID.  This step is rarely executed.  It is used when    *
 *  there is no best move from the hash table, and this is  *
 *  a PV node, since we need a good move to search first.   *
 *  While killers moves are good, they are not quite good   *
 *  enough.  the simplest solution is to try a shallow      *
 *  search (depth-2) to get a move.  note that when we call *
 *  Search() with depth-2, it, too, will not have a hash    *
 *  move, and will therefore recursively continue this      *
 *  process, hence the name "internal iterative deepening." *
 *                                                          *
 ************************************************************
 */
    tree->next_status[ply].phase = HASH;
    if (!tree->hash_move[ply] && depth >= 6 && do_null && ply > 1 && pv_node) {
      tree->curmv[ply] = 0;
      if (depth - 2 > 0)
        value =
            Search(tree, ply, depth - 2, wtm, alpha, beta, in_check, DO_NULL);
      else
        value = Quiesce(tree, ply, wtm, alpha, beta, 1);
      if (abort_search || tree->stop)
        return 0;
      if (value > alpha) {
        if (value < beta) {
          if ((int) tree->pv[ply - 1].pathl > ply)
            tree->hash_move[ply] = tree->pv[ply - 1].path[ply];
        } else
          tree->hash_move[ply] = tree->curmv[ply];
        tree->last[ply] = tree->last[ply - 1];
        tree->next_status[ply].phase = HASH;
      }
    }
  }
/*
 ************************************************************
 *                                                          *
 *  Search moves.  Now we call SearchMoveList() to interate *
 *  through the move list and search each new position.     *
 *  Note that this is done in a separate procedure because  *
 *  this is also the code that is used to do the parallel   *
 *  search.                                                 *
 *                                                          *
 ************************************************************
 */
  searched[0] = 0;
  value =
      SearchMoveList(tree, ply, depth, wtm, alpha, beta, searched, in_check,
      repeat, serial);
  return value;
}

/* last modified 09/28/15 */
/*
 *******************************************************************************
 *                                                                             *
 *   SearchMoveList() is the recursive routine used to implement the main      *
 *   search loop.  This code is responsible for iterating through the move     *
 *   list until it encounters a condition that ends the search at this ply.    *
 *   At that point it simply returns the current negamax value to the caller   *
 *   to handle as necessary.                                                   *
 *                                                                             *
 *   The "mode" flag indicates which of the following conditions apply here    *
 *   which directly controls parts of the search.                              *
 *                                                                             *
 *      mode = serial   ->  this is a serial search.                           *
 *                                                                             *
 *      mode = parallel ->  this is a parallel search, which implies that this *
 *                          is a partial search which means we do NOT want to  *
 *                          do any trans/ref updating and we also need to take *
 *                          care about locking things that are being updated   *
 *                          by more than one thread in parallel.               *
 *                                                                             *
 *   When mode = parallel, this code performs the same function as the old     *
 *   SearchParallel() code, except that it is the main search loop for the     *
 *   program, there is no longer any duplicated code.  This is called by the   *
 *   normal Search() function and by ThreadWait() where idle processes wait    *
 *   for work and then call this procedure to search a subset of the moves at  *
 *   this ply (in parallel with other threads).                                *
 *                                                                             *
 *******************************************************************************
 */
int SearchMoveList(TREE * RESTRICT tree, int ply, int depth, int wtm,
    int alpha, int beta, int searched[], int in_check, int repeat, int mode) {
  TREE *current;
  int extend, reduce, check, original_alpha = alpha, t_beta;
  int i, value = 0, pv_node = alpha != beta - 1, status, order;
  int moves_done = 0, phase, bestmove, type;

/*
 ************************************************************
 *                                                          *
 *  Basic initialization before we begin the loop through   *
 *  the move list.  If this is a parallel search, we have   *
 *  already searched one move, so we set t_beta to alpha+1  *
 *  to set up for a normal PVS search (for moves 2-n)       *
 *  instead of using alpha,beta for the first move as we do *
 *  in a normal search.  Also, if this is a serial search,  *
 *  we are fixing to search the first move so we set the    *
 *  searched move counter to zero, where in a parallel      *
 *  search this has already been done and we leave it alone *
 *  here.                                                   *
 *                                                          *
 *  We also set <current> to tree for a serial search, and  *
 *  to tree->parent for a parallel search since we need to  *
 *  share the move list at split nodes.                     *
 *                                                          *
 ************************************************************
 */
  tree->next_status[ply].phase = HASH;
  if (mode == parallel) {
    current = tree->parent;
    t_beta = alpha + 1;
  } else {
    current = tree;
    t_beta = beta;
  }
/*
 ************************************************************
 *                                                          *
 *  Iterate.  Now iterate through the move list and search  *
 *  the resulting positions.  Note that Search() culls any  *
 *  move that is not legal by using Check().  The special   *
 *  case is that we must find one legal move to search to   *
 *  confirm that it's not a mate or draw.                   *
 *                                                          *
 *  We call NextMove() which will generate moves in the     *
 *  normal way (captures, killers, etc) or it will use the  *
 *  GenerateEvasions() generator if we are in check.  For   *
 *  the special case of ply=1, we use NextRootMove() since  *
 *  the ply=1 move list has been generated and the order is *
 *  updated as each search iteration is executed.           *
 *                                                          *
 ************************************************************
 */
  while (1) {
    if (ply == 1 && moves_done == 1 && alpha == original_alpha &&
        mode == serial)
      break;
    if (mode == parallel)
      Lock(current->lock);
    order = (ply > 1) ? NextMove(current, ply, depth, wtm, in_check) :
      NextRootMove(current, tree, wtm);
    phase = current->phase[ply];
    if (mode == parallel) {
      tree->curmv[ply] = tree->parent->curmv[ply];
      Unlock(current->lock);
    }
    if (!order)
      break;
#if defined(TRACE)
    if (ply <= trace_level)
      Trace(tree, ply, depth, wtm, alpha, beta, "SearchMoveList", mode, phase,
          order);
#endif
    MakeMove(tree, ply, wtm, tree->curmv[ply]);
    tree->nodes_searched++;
    status = ILLEGAL;
    if (in_check || !Check(wtm))
      do {
        searched[0]++;
        moves_done++;
        status = LEGAL;
        searched[searched[0]] = tree->curmv[ply];
/*
 ************************************************************
 *                                                          *
 *  Check.  If the move to be made checks the opponent,     *
 *  then we need to remember that he's in check and also    *
 *  extend the depth by one ply for him to get out.         *
 *                                                          *
 *  We do not extend unsafe checking moves (as indicated by *
 *  the SEE algorithm), since these are usually a waste of  *
 *  time and simply blow up the tree search space.          *
 *                                                          *
 *  Note that extending here disables any potential foward  *
 *  pruning or reductions for this move.                    *
 *                                                          *
 ************************************************************
 */
        extend = 0;
        reduce = 0;
        if (Check(Flip(wtm))) {
          check = 1;
          if (SEEO(tree, wtm,
                  tree->curmv[ply]) - pcval[Captured(tree->curmv[ply])] <=
              0) {
            extend = check_depth;
            tree->extensions_done++;
          }
        } else
          check = 0;
/*
 ************************************************************
 *                                                          *
 *  Futility.  First attempt at forward pruning based on    *
 *  the futility idea.                                      *
 *                                                          *
 *  We have an array of pruning margin values that are      *
 *  indexed by depth (remaining plies left until we drop    *
 *  into the quiescence search) and which increase with     *
 *  depth since more depth means a greater chance of        *
 *  bringing the score back up to alpha or beyond.  If the  *
 *  current material + the bonus is less than alpha, we     *
 *  simply avoid searching this move at all, and skip to    *
 *  the next move without expending any more effort.  Note  *
 *  that this is classic forward-pruning and can certainly  *
 *  introduce errors into the search.  However, cluster     *
 *  testing has shown that this improves play in real       *
 *  games.  The current implementation only prunes in the   *
 *  last 6 plies before quiescence, although this can be    *
 *  tuned with the "eval" command changing the "pruning     *
 *  depth" value to something other than 7 (test is for     *
 *  depth < pruning depth, current value is 7 which prunes  *
 *  in last 6 plies only).  Testing shows no benefit in     *
 *  larger values than 7, although this might change in     *
 *  future versions as other things are modified.           *
 *                                                          *
 *  Exception:                                              *
 *                                                          *
 *    We do not prune if we are safely pushing a passed     *
 *    pawn to the 6th rank, where it becomes very dangerous *
 *    since it can promote in two more moves.               *
 *                                                          *
 *  All pruning and reduction code is skipped if any of the *
 *  following are true:                                     *
 *                                                          *
 *  (1) side on move is in check.                           *
 *                                                          *
 *  (2) move has not already been flagged for a search      *
 *      extension.                                          *
 *                                                          *
 *  (3) this is not the first move at this ply.             *
 *                                                          *
 *  (4) we are in the REMAINING phase, which means that a   *
 *      cutoff is not very likely.                          *
 *                                                          *
 ************************************************************
 */
        if (!in_check && !extend && order > 1 && phase >= HISTORY &&
            !(PawnPush(wtm, tree->curmv[ply]))) {
          if (!pv_node && depth < pruning_depth &&
              MaterialSTM(wtm) + pruning_margin[depth] <= alpha) {
            tree->moves_fpruned++;
            break;
          }
/*
 ************************************************************
 *                                                          *
 *  LMP.  Final attempt at forward pruning based on the     *
 *  "late move pruning" idea (a take-off on LMR).           *
 *                                                          *
 *  The basic idea here is that once we have searched a     *
 *  significant number of moves at a ply, it becomes less   *
 *  and less likely that any of the moves left will produce *
 *  a cutoff.  If the move appears to be simple (not a      *
 *  check, etc) then we simply skip it, once the move count *
 *  has been satisfied.  At present, we only do this in the *
 *  last two plies although this might be changed in the    *
 *  future.                                                 *
 *                                                          *
 ************************************************************
 */
          if (!pv_node && alpha > -MATE + 300 && depth < movecnt_depth &&
              !CaptureOrPromote(tree->curmv[ply]) &&
              order > movecnt_pruning[depth]) {
            tree->moves_mpruned++;
            break;
          }
/*
 ************************************************************
 *                                                          *
 *  LMR.  Now it's time to try to reduce the search depth   *
 *  if the move appears to be "poor" because it appears     *
 *  later in the move list.                                 *
 *                                                          *
 *  The reduction is variable and is done via a table look- *
 *  up that uses a function based on remaining depth (more  *
 *  depth remaining, the larger the reduction) and the      *
 *  number of moves searched (more moves searched, the      *
 *  larger the reduction).  The "shape" of this reduction   *
 *  formula is user-settable via the "lmr" command.         *
 *                                                          *
 ************************************************************
 */
          reduce = LMR[Min(depth, 31)][Min(order, 63)];
          tree->LMR_done[reduce]++;
        }
/*
 ************************************************************
 *                                                          *
 *  Now do the PVS search on the current move.              *
 *                                                          *
 *  Note that we do the usual alpha/beta cutoff tests here  *
 *  but we only set an indicator that is used after we have *
 *  called Unmake().  This cleaned up the exit from search  *
 *  and makes it easier to understand when there is only    *
 *  one point where this is done, without needing multiple  *
 *  Unmake() calls when there are different exit points.    *
 *                                                          *
 ************************************************************
 */
        value =
            SearchMove(tree, ply, depth, wtm, alpha, t_beta, beta, extend,
            reduce, check);
        if (value > alpha) {
          status = IN_WINDOW;
          if (value >= beta)
            status = FAIL_HIGH;
          if (mode == parallel && ply == 1)
            status = FAIL_HIGH;
        }
      } while (0);
    UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
    if (abort_search || tree->stop)
      break;
/*
 ************************************************************
 *                                                          *
 *  Test 1.  When we get here, we have made a move,         *
 *  searched it (and re-searched if necessary/appropriate), *
 *  and the move has been unmade so that the board is in a  *
 *  correct state.                                          *
 *                                                          *
 *  If status = FAIL_HIGH, the search failed high.  The     *
 *  first thing to handle is the case where we are at       *
 *  ply=1, which is a special case.  If we are going to     *
 *  fail high here and terminate the search immediately, we *
 *  need to build the fail-high PV to back up to Iterate()  *
 *  so it will produce the correct output and widen the     *
 *  alpha/beta window.                                      *
 *                                                          *
 *  We then check to see if this is a parallel search.  If  *
 *  so then we are done here, but we need to tell all of    *
 *  the siblings that are helping at this split point that  *
 *  they should immediately stop searching here since we    *
 *  don't need their results.                               *
 *                                                          *
 *  Otherwise we update the killer moves and history        *
 *  counters and store the fail-high information in the     *
 *  trans/ref table for future use if we happen to reach    *
 *  this position again.                                    *
 *                                                          *
 ************************************************************
 */
    if (status == FAIL_HIGH) {
      if (ply == 1) {
        if (!tree->stop) {
          tree->pv[1].path[1] = tree->curmv[1];
          tree->pv[1].pathl = 2;
          tree->pv[1].pathh = 0;
          tree->pv[1].pathd = iteration;
          tree->pv[0] = tree->pv[1];
        }
      }
#if (CPUS > 1)
      if (mode == parallel) {
        Lock(lock_smp);
        Lock(tree->parent->lock);
        if (!tree->stop) {
          int proc;

          parallel_aborts++;
          for (proc = 0; proc < smp_max_threads; proc++)
            if (tree->parent->siblings[proc] && proc != tree->thread_id)
              ThreadStop(tree->parent->siblings[proc]);
        }
        Unlock(tree->parent->lock);
        Unlock(lock_smp);
        return value;
      }
#endif
      tree->fail_highs++;
      if (order == 1)
        tree->fail_high_first_move++;
      HashStore(tree, ply, depth, wtm, LOWER, value, tree->curmv[ply]);
      History(tree, ply, depth, wtm, tree->curmv[ply], searched);
      return beta;
/*
 ************************************************************
 *                                                          *
 *  Test 2.  If status = IN_WINDOW, this is a search that   *
 *  improved alpha without failing high.  We simply update  *
 *  alpha and continue searching moves.                     *
 *                                                          *
 *  Special case:  If ply = 1 in a normal search, we have   *
 *  a best move and score that just changed.  We need to    *
 *  update the root move list by adding the PV and the      *
 *  score, and then we look to make sure this new "best     *
 *  move" is not actually worse than the best we have found *
 *  so far this iteration.  If it is worse, we restore the  *
 *  best move and score from the real best move so our      *
 *  search window won't be out of whack, which would let    *
 *  moves with scores in between this bad move and the best *
 *  move fail high, cause re-searches, and waste time.      *
 *                                                          *
 *  If this is ply = 1, we display the PV to keep the user  *
 *  informed.                                               *
 *                                                          *
 ************************************************************
 */
    } else if (status == IN_WINDOW) {
      alpha = value;
      if (ply == 1 && mode == serial) {
        tree->pv[1].pathv = value;
        tree->pv[0] = tree->pv[1];
        for (i = 0; i < n_root_moves; i++)
          if (root_moves[i].move == tree->pv[1].path[1]) {
            root_moves[i].path = tree->pv[1];
            root_moves[i].path.pathv = alpha;
          }
        for (i = 0; i < n_root_moves; i++)
          if (value < root_moves[i].path.pathv) {
            value = root_moves[i].path.pathv;
            alpha = value;
            tree->pv[0] = root_moves[i].path;
            tree->pv[1] = tree->pv[0];
          }
        Output(tree);
        failhi_delta = 16;
        faillo_delta = 16;
      }
    }
/*
 ************************************************************
 *                                                          *
 *  Test 3.  If status = ILLEGAL, this search was given an  *
 *  illegal move and no search was done, we skip any        *
 *  updating and simply select the next move to search.     *
 *                                                          *
 ************************************************************
 */
    else if (status == ILLEGAL)
      continue;
    t_beta = alpha + 1;
/*
 ************************************************************
 *                                                          *
 *  SMP.  If are doing an SMP search, and we have idle      *
 *  processors, now is the time to get them involved.  We   *
 *  have now satisfied the "young brothers wait" condition  *
 *  since we have searched at least one move.  All that is  *
 *  left is to check the split constraints to see if this   *
 *  is an acceptable split point.                           *
 *                                                          *
 *    (1) We can't split within N plies of the frontier     *
 *        nodes to avoid excessive split overhead.          *
 *                                                          *
 *    (2) We can't split until at least N nodes have been   *
 *        searched since this thread was last split, to     *
 *        avoid splitting too often, mainly in endgames.    *
 *                                                          *
 *    (3) We have to have searched one legal move to avoid  *
 *        splitting at a node where we have no legal moves  *
 *        (the first move tried might have been illegal as  *
 *        in when we encounter a stalemate).                *
 *                                                          *
 *    (4) If we are at ply=1, we can't split unless the     *
 *        smp_split_at_root flag is set to 1, AND the next  *
 *        move in the ply=1 move list is not flagged as     *
 *        "do not search in parallel" which happens when    *
 *        this move was a best move in the last couple of   *
 *        searches and we want all processors on it at once *
 *        to get a score back quicker.                      *
 *                                                          *
 *    (5) if the variable smp_split is != 0, we have idle   *
 *        threads that can help, which means we want to get *
 *        them involved quickly, OR if this node is an      *
 *        acceptable "gratuitous-split" point by being far  *
 *        enough from the tips of the tree to avoid         *
 *        excessive overhead.                               *
 *                                                          *
 *  We use this code recursively to perform a parallel      *
 *  search at this ply.  But when we finish a partial piece *
 *  of the search in parallel, we don't need to update any  *
 *  search data structures, we will defer that until all of *
 *  parallel threads complete and return back into this     *
 *  code after the parallel search has been collapsed back  *
 *  to one instance of search at this ply.                  *
 *                                                          *
 *  Special case:  we do not split if we are at ply=1 and   *
 *  alpha == original_alpha.  That means the first move     *
 *  failed low, and we are going to exit search and return  *
 *  to Iterate() to report this.                            *
 *                                                          *
 *  In Generation II, multiple threads can reach this point *
 *  at the same time.  We allow multiple threads to split   *
 *  at the same time, but then the idle threads will choose *
 *  to join the thread with the most attractive split point *
 *  rather than just taking pot-luck.  The only limitation  *
 *  on a thread adding a split point here is that if the    *
 *  thread already has enough joinable split points have    *
 *  not been joined yet, we do not incur the overhead of    *
 *  creating another split point until the existing split   *
 *  point is completed or a thread joins at at that point.  *
 *                                                          *
 *  We do not lock anything here, as the split operation    *
 *  only affects thread-local data.  When the split is done *
 *  then the ThreadJoin() function will acquire the lock    *
 *  needed to avoid race conditions during the join op-     *
 *  eration.                                                *
 *                                                          *
 ************************************************************
 */
#if (CPUS > 1)
    if (mode == serial && moves_done && smp_threads &&
        ThreadSplit(tree, ply, depth, alpha, original_alpha, moves_done))
      do {
        tree->alpha = alpha;
        tree->beta = beta;
        tree->value = alpha;
        tree->wtm = wtm;
        tree->ply = ply;
        tree->depth = depth;
        tree->in_check = in_check;
        tree->searched = searched;
        if (Split(tree)) {
          if (abort_search || tree->stop)
            return 0;
          value = tree->value;
          if (value > alpha) {
            if (ply == 1)
              tree->pv[0] = tree->pv[1];
            if (value >= beta) {
              HashStore(tree, ply, depth, wtm, LOWER, value, tree->cutmove);
              return value;
            }
            alpha = value;
            break;
          }
        }
      } while (0);
#endif
  }
/*
 ************************************************************
 *                                                          *
 *  SMP Cleanup.  If we are doing an SMP search, there are  *
 *  no "end-of-search" things to do.  We have searched all  *
 *  the remaining moves at this ply in parallel, and now    *
 *  return and let the original search that started this    *
 *  sub-tree clean up, do the tests for mate/stalemate,     *
 *  update the hash table, etc.                             *
 *                                                          *
 *  As we return, we end back up in Thread() where we       *
 *  started, which then copies the best score/etc back to   *
 *  the parent thread.                                      *
 *                                                          *
 ************************************************************
 */
  if (abort_search || tree->stop || mode == parallel)
    return alpha;
/*
 ************************************************************
 *                                                          *
 *  Search completed.  All moves have been searched.  If    *
 *  none were legal, return either MATE or DRAW depending   *
 *  on whether the side to move is in check or not.         *
 *                                                          *
 ************************************************************
 */
  if (moves_done == 0) {
    value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);
    if (value >= alpha && value < beta) {
      SavePV(tree, ply, 0);
#if defined(TRACE)
      if (ply <= trace_level)
        printf("Search() no moves!  ply=%d\n", ply);
#endif
    }
    return value;
  } else {
    bestmove =
        (alpha ==
        original_alpha) ? tree->hash_move[ply] : tree->pv[ply].path[ply];
    type = (alpha == original_alpha) ? UPPER : EXACT;
    if (repeat == 2 && alpha != -(MATE - ply - 1)) {
      value = DrawScore(wtm);
      if (value < beta)
        SavePV(tree, ply, 4);
#if defined(TRACE)
      if (ply <= trace_level)
        printf("draw by 50 move rule detected, ply=%d.\n", ply);
#endif
      return value;
    } else if (alpha != original_alpha) {
      tree->pv[ply - 1] = tree->pv[ply];
      tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
    }
    HashStore(tree, ply, depth, wtm, type, alpha, bestmove);
    return alpha;
  }
}

/* last modified 07/01/15 */
/*
 *******************************************************************************
 *                                                                             *
 *   SearchMove() implements the PVS search and returns the value.  We do a    *
 *   null-window search with the window (alpha, t_beta) and if that fails high *
 *   we repeat the search with the window {alpha, beta} assuming that beta !=  *
 *   t_beta.                                                                   *
 *                                                                             *
 *******************************************************************************
 */
int SearchMove(TREE * RESTRICT tree, int ply, int depth, int wtm, int alpha,
    int t_beta, int beta, int extend, int reduce, int check) {
  int value;
/*
 ************************************************************
 *                                                          *
 *  PVS search.  We have determined whether the depth is to *
 *  be changed by an extension or a reduction.  If we get   *
 *  to this point, then the move is not being pruned.  So   *
 *  off we go to a recursive search/quiescence call to work *
 *  our way toward a terminal node.                         *
 *                                                          *
 *  There is one special-case to handle.  If the depth was  *
 *  reduced, and Search() returns a value >= beta then      *
 *  accepting that is risky (we reduced the move as we      *
 *  thought it was bad and expected it to fail low) so we   *
 *  repeat the search using the original (non-reduced)      *
 *  depth to see if the fail-high happens again.            *
 *                                                          *
 ************************************************************
 */
  if (depth + extend - reduce - 1 > 0) {
    value =
        -Search(tree, ply + 1, depth + extend - reduce - 1, Flip(wtm),
        -t_beta, -alpha, check, DO_NULL);
    if (value > alpha && reduce) {
      value =
          -Search(tree, ply + 1, depth - 1, Flip(wtm), -t_beta, -alpha, check,
          DO_NULL);
    }
  } else
    value = -Quiesce(tree, ply + 1, Flip(wtm), -t_beta, -alpha, 1);
  if (abort_search || tree->stop)
    return 0;
/*
 ************************************************************
 *                                                          *
 *  PVS re-search.  This is the PVS re-search code.  If we  *
 *  reach this point and value > alpha and value < beta,    *
 *  then this can not be a null-window search.  We have to  *
 *  re-search the position with the original beta value     *
 *  to see if it still fails high before we treat this as a *
 *  real fail-high and back up the value to the previous    *
 *  ply.                                                    *
 *                                                          *
 ************************************************************
 */
  if (value > alpha && value < beta && t_beta < beta) {
    if (ply == 1)
      return beta;
    if (depth + extend - 1 > 0)
      value =
          -Search(tree, ply + 1, depth + extend - 1, Flip(wtm), -beta, -alpha,
          check, DO_NULL);
    else
      value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 1);
    if (abort_search || tree->stop)
      return 0;
  }
  return value;
}