Subversion Repositories Games.Chess Giants

#include "chess.h"

#include "data.h"

/* last modified 01/10/16 */

/*

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

 *                                                                             *

 *   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 of the captured piece and the   *

 *   complemented value of the capturing piece.  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 SEE() 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 ply, int wtm, int alpha, int beta,

    int checks) {

  unsigned *next, *movep;

  int original_alpha = alpha, value;

/*

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

 *                                                          *

 *  Initialize.                                             *

 *                                                          *

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

 */

  if (ply >= MAXPLY - 1)

    return beta;

#if defined(NODES)

  if (search_nodes && --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.                                          *

 *                                                          *

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

 */

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

#if defined(TRACE)

  if (ply <= trace_level)

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

#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;

  }

/*

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

 *                                                          *

 *  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    *

 *  SEE() 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]);

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

    if (Captured(*movep) == king)

      return beta;

    *movep += MVV_LVA[Captured(*movep)][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;

  }

  NextSort(tree, ply);

/*

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

 *                                                          *

 *  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 SEE() 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] = Move(*next);

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

        TotalPieces(Flip(wtm), occupied)

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

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

      continue;

#if defined(TRACE)

    if (ply <= trace_level)

      Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", serial, CAPTURES,

          next - tree->last[ply - 1] + 1);

#endif

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

    tree->nodes_searched++;

    if (!checks)

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

    else if (!Check(wtm)) {

      if (Check(Flip(wtm))) {

        tree->qchecks_done++;

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

      } else

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

    }

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

    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 SEE() 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] = Move(*next);

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

#if defined(TRACE)

        if (ply <= trace_level)

          Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce+checks", serial,

              REMAINING, next - tree->last[ply - 1] + 1);

#endif

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

        tree->nodes_searched++;

        if (!Check(wtm)) {

          tree->qchecks_done++;

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

        }

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

        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 01/10/16 */

/*

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

 *                                                                             *

 *   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 ply, int wtm, int alpha,

    int beta) {

  int original_alpha, value, moves_searched = 0, order;

/*

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

 *                                                          *

 *  Initialize.                                             *

 *                                                          *

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

 */

  if (ply >= MAXPLY - 1)

    return beta;

#if defined(NODES)

  if (search_nodes && --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;

  while ((order = NextMove(tree, ply, 0, wtm, 1))) {

#if defined(TRACE)

    if (ply <= trace_level)

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

          tree->phase[ply], order);

#endif

    moves_searched++;

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

    tree->nodes_searched++;

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

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

    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, it   *

 *  must be a mate since we have to be in check to reach    *

 *  QuiesceEvasions().                                      *

 *                                                          *

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

 */

  if (moves_searched == 0) {

    value = -(MATE - ply);

    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;

}