Subversion Repositories Games.Chess Giants

#include "chess.h"

#include "data.h"

/* last modified 05/07/14 */

/*

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

 *                                                                             *

 *   Quiece() is the recursive routine used to implement the quiescence        *

 *   search part of the alpha/beta negamax search.  It performs the following  *

 *   functions:                                                                *

 *                                                                             *

 *   (1) It computes a stand-pat score, which gives the side-on-move the       *

 *   choice of standing pat and not playing any move at all and just accepting *

 *   the current static evaluation, or else it may try captures and/or         *

 *   checking moves to see if it can improve the stand-pat score by making a   *

 *   move that leads to some sort of positional or material gain.              *

 *                                                                             *

 *   (2) The first phase is to generate all possible capture moves and then    *

 *   sort them into descending using the value                                 *

 *                                                                             *

 *        val = 128 * captured_piece_value + capturing_piece_value             *

 *                                                                             *

 *   This is the classic MVV/LVA ordering approach that removes heavy pieces   *

 *   first in an attempt to reduce the size of the sub-tree these pieces       *

 *   produce.                                                                  *

 *                                                                             *

 *   (3) When we get ready to actually search each capture, we analyze each    *

 *   move to see if it appears reasonable.  Small pieces can capture larger    *

 *   ones safely, ditto for equal exchanges.  For the rest, we use Swap() to   *

 *   compute the SEE score.  If this is less than zero, we do not search this  *

 *   move at all to avoid wasting time, since a losing capture rarely helps    *

 *   improve the score in the q-search.  The goal here is to find a capture    *

 *   that improves on the stand-pat score and gets us closer to a position     *

 *   that we would describe as "quiet" or "static".                            *

 *                                                                             *

 *   (4) If the parameter "checks" is non-zero then after searching the        *

 *   captures, we generate checking moves and search those.  This value also   *

 *   slightly changes the way captures are searched, since those that are also *

 *   checks result in calling QuiesceEvasions() which evades checks to see if  *

 *   the check is actually a mate.  This means that we have one layer of full- *

 *   width search to escape checks and do not allow a stand-pat which would    *

 *   hide the effect of the check completely.                                  *

 *                                                                             *

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

 */

int Quiesce(TREE * RESTRICT tree, int alpha, int beta, int wtm, int ply,

    int checks) {

  int original_alpha = alpha, value;

  int *next;

  int *movep, *sortv;

/*

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

 *                                                          *

 *  Initialize.                                             *

 *                                                          *

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

 */

  if (ply >= MAXPLY - 1)

    return beta;

#if defined(NODES)

  if (--temp_search_nodes <= 0) {

    abort_search = 1;

    return 0;

  }

#endif

  if (tree->thread_id == 0)

    next_time_check--;

/*

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

 *                                                          *

 *  Check for draw by repetition, which includes 50 move    *

 *  draws also.  This is only done at the first ply of the  *

 *  quiescence search since we are following checking moves *

 *  as well.  The parameter "checks" passed in is "1" for   *

 *  that particular case only (when called from Search()).  *

 *  all other calls (from inside Quiesce()) pass a value of *

 *  zero so that additional plies of checks are not tried.  *

 *                                                          *

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

 */

  if (checks) {

    if (Repeat(tree, ply)) {

      value = DrawScore(wtm);

      if (value < beta)

        SavePV(tree, ply, 0);

#if defined(TRACE)

      if (ply <= trace_level)

        printf("draw by repetition detected, ply=%d.\n", ply);

#endif

      return value;

    }

  }

/*

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

 *                                                          *

 *  Now call Evaluate() to produce the "stand-pat" score    *

 *  that will be returned if no capture is acceptable.  If  *

 *  this score is > alpha and < beta, then we also have to  *

 *  save the path to this node as it is the PV that leads   *

 *  to this score.                                          *

 *                                                          *

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

 */

  tree->curmv[ply] = 0;

  value = Evaluate(tree, ply, wtm, alpha, beta);

#if defined(TRACE)

  if (ply <= trace_level)

    Trace(tree, ply, value, wtm, alpha, beta, "Quiesce", EVALUATION);

#endif

  if (value > alpha) {

    if (value >= beta)

      return value;

    alpha = value;

    tree->pv[ply].pathl = ply;

    tree->pv[ply].pathh = 0;

    tree->pv[ply].pathd = iteration_depth;

  }

/*

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

 *                                                          *

 *  Generate captures and sort them based on simple MVV/LVA *

 *  order.  We simply try to capture the most valuable      *

 *  piece possible, using the least valuable attacker       *

 *  possible, to get rid of heavy pieces quickly and reduce *

 *  the overall size of the tree.                           *

 *                                                          *

 *  Note that later we use the value of the capturing       *

 *  piece, the value of the captured piece, and possibly    *

 *  Swap() to exclude captures that appear to lose          *

 *  material, but we delay expending this effort as long as *

 *  possible, since beta cutoffs make it unnecessary to     *

 *  search all of these moves anyway.                       *

 *                                                          *

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

 */

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

  sortv = tree->sort_value;

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

    if (Captured(*movep) == king)

      return beta;

    *sortv++ = 128 * pcval[Captured(*movep)] - pcval[Piece(*movep)];

  }

  if (!checks && tree->last[ply] == tree->last[ply - 1]) {

    if (alpha != original_alpha) {

      tree->pv[ply - 1] = tree->pv[ply];

      tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];

    }

    return value;

  }

/*

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

 *                                                          *

 *  This is a simple insertion sort algorithm.  It seems be *

 *  be no faster than a normal bubble sort, but using this  *

 *  eliminated a lot of explaining about "why?". :)         *

 *                                                          *

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

 */

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

    int temp1, temp2, *tmovep, *tsortv, *end;

    sortv = tree->sort_value + 1;

    end = tree->last[ply];

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

      temp1 = *movep;

      temp2 = *sortv;

      tmovep = movep - 1;

      tsortv = sortv - 1;

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

        *(tsortv + 1) = *tsortv;

        *(tmovep + 1) = *tmovep;

        tmovep--;

        tsortv--;

      }

      *(tmovep + 1) = temp1;

      *(tsortv + 1) = temp2;

    }

  }

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

/*

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

 *                                                          *

 *  Iterate through the move list and search the resulting  *

 *  positions.  Now that we are ready to actually search    *

 *  the set of capturing moves, we try three quick tests to *

 *  see if the move should be excluded because it appears   *

 *  to lose material.                                       *

 *                                                          *

 *  (1) If the capturing piece is not more valuable than    *

 *  the captured piece, then the move can't lose material   *

 *  and should be searched.                                 *

 *                                                          *

 *  (2) If the capture removes the last opponent piece, we  *

 *  always search this kind of capture since this can be    *

 *  the move the allows a passed pawn to promote when the   *

 *  opponent has no piece to catch it.                      *

 *                                                          *

 *  (3) Otherwise, If the capturing piece is more valuable  *

 *  than the captured piece, we use Swap() to determine if  *

 *  the capture is losing or not so that we don't search    *

 *  hopeless moves.                                         *

 *                                                          *

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

 */

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

    tree->curmv[ply] = *next;

    if (pcval[Piece(tree->curmv[ply])] > pcval[Captured(tree->curmv[ply])] &&

        TotalPieces(wtm, occupied)

        - p_vals[Captured(tree->curmv[ply])] > 0 &&

        Swap(tree, tree->curmv[ply], wtm) < 0)

      continue;

#if defined(TRACE)

    if (ply <= trace_level)

      Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", CAPTURE_MOVES);

#endif

    MakeMove(tree, ply, tree->curmv[ply], wtm);

    tree->nodes_searched++;

    if (!checks)

      value = -Quiesce(tree, -beta, -alpha, Flip(wtm), ply + 1, 0);

    else if (!Check(wtm)) {

      if (Check(Flip(wtm))) {

        tree->qchecks_done++;

        value = -QuiesceEvasions(tree, -beta, -alpha, Flip(wtm), ply + 1);

      } else

        value = -Quiesce(tree, -beta, -alpha, Flip(wtm), ply + 1, 0);

    }

    UnmakeMove(tree, ply, tree->curmv[ply], wtm);

    if (abort_search || tree->stop)

      return 0;

    if (value > alpha) {

      if (value >= beta)

        return value;

      alpha = value;

    }

  }

/*

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

 *                                                          *

 *  The next block of code is only executed if the checks   *

 *  parameter is non-zero, otherwise we skip this and exit  *

 *  with no further searching.                              *

 *                                                          *

 *  Generate just the moves (non-captures) that give check  *

 *  and search the ones that Swap() says are safe.  Subtle  *

 *  trick:  we discard the captures left over from the      *

 *  above search since we labeled them "losing moves."      *

 *                                                          *

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

 */

  if (checks) {

    tree->last[ply] = GenerateChecks(tree, wtm, tree->last[ply - 1]);

/*

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

 *                                                          *

 *  Iterate through the move list and search the resulting  *

 *  positions.  We take them in the normal order that       *

 *  GenerateChecks() provides.                              *

 *                                                          *

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

 */

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

      tree->curmv[ply] = *next;

      if (Swap(tree, tree->curmv[ply], wtm) >= 0) {

#if defined(TRACE)

        if (ply <= trace_level)

          Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", REMAINING_MOVES);

#endif

        MakeMove(tree, ply, tree->curmv[ply], wtm);

        tree->nodes_searched++;

        if (!Check(wtm)) {

          tree->qchecks_done++;

          value = -QuiesceEvasions(tree, -beta, -alpha, Flip(wtm), ply + 1);

        }

        UnmakeMove(tree, ply, tree->curmv[ply], wtm);

        if (abort_search || tree->stop)

          return 0;

        if (value > alpha) {

          if (value >= beta)

            return value;

          alpha = value;

        }

      }

    }

  }

/*

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

 *                                                          *

 *  All moves have been searched.  Return the search result *

 *  that was found.  If the result is not the original      *

 *  alpha score, then we need to back up the PV that is     *

 *  associated with this score.                             *

 *                                                          *

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

 */

  if (alpha != original_alpha) {

    tree->pv[ply - 1] = tree->pv[ply];

    tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];

  }

  return alpha;

}

/* last modified 05/07/14 */

/*

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

 *                                                                             *

 *   QuiesceEvasions() is the recursive routine used to implement the alpha/   *

 *   beta negamax quiescence search.  The primary function here is to escape a *

 *   check that was delivered by QuiesceChecks() at the previous ply.  We do   *

 *   not have the usual "stand pat" option because we have to find a legal     *

 *   move to prove we have not been checkmated.                                *

 *                                                                             *

 *   QuiesceEvasions() uses the legal move generator (GenerateCheckEvasions()) *

 *   to produce only the set of legal moves that escape check.  We try those   *

 *   in the the order they are generated since we are going to try them all    *

 *   unless we get a fail-high.                                                *

 *                                                                             *

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

 */

int QuiesceEvasions(TREE * RESTRICT tree, int alpha, int beta, int wtm,

    int ply) {

  int original_alpha, value;

  int moves_searched = 0;

/*

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

 *                                                          *

 *  Initialize.                                             *

 *                                                          *

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

 */

  if (ply >= MAXPLY - 1)

    return beta;

#if defined(NODES)

  if (--temp_search_nodes <= 0) {

    abort_search = 1;

    return 0;

  }

  if (tree->thread_id == 0)

    next_time_check--;

#endif

/*

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

 *                                                          *

 *  Check for draw by repetition, which includes 50 move    *

 *  draws also.                                             *

 *                                                          *

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

 */

  if (Repeat(tree, ply)) {

    value = DrawScore(wtm);

    if (value < beta)

      SavePV(tree, ply, 0);

#if defined(TRACE)

    if (ply <= trace_level)

      printf("draw by repetition detected, ply=%d.\n", ply);

#endif

    return value;

  }

  original_alpha = alpha;

/*

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

 *                                                          *

 *  Iterate through the move list and search the resulting  *

 *  positions.  These moves are searched in the order that  *

 *  GenerateEvasions() produces them.  No hash move is      *

 *  possible since we don't do probes in Quiesce().  We do  *

 *  clear the hash move before we start selecting moves so  *

 *  that we don't search a bogus move from a different      *

 *  position.                                               *

 *                                                          *

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

 */

  tree->hash_move[ply] = 0;

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

  while ((tree->phase[ply] = NextEvasion(tree, ply, wtm))) {

#if defined(TRACE)

    if (ply <= trace_level)

      Trace(tree, ply, 0, wtm, alpha, beta, "QuiesceEvasions",

          tree->phase[ply]);

#endif

    moves_searched++;

    MakeMove(tree, ply, tree->curmv[ply], wtm);

    tree->nodes_searched++;

    value = -Quiesce(tree, -beta, -alpha, Flip(wtm), ply + 1, 0);

    UnmakeMove(tree, ply, tree->curmv[ply], wtm);

    if (abort_search || tree->stop)

      return 0;

    if (value > alpha) {

      if (value >= beta)

        return value;

      alpha = value;

    }

  }

/*

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

 *                                                          *

 *  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_searched == 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 if (alpha != original_alpha) {

    tree->pv[ply - 1] = tree->pv[ply];

    tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];

  }

  return alpha;

}