WebSVN – Games.Chess Giants – Diff – //engine-crafty/quiesce.c

 #include "chess.h"
 #include "data.h"
-/* last modified 05/07/14 */
+/* 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  *
  *   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                                 *
+ *   sort them into descending using the value of the captured piece and the   *
- *                                                                             *
- *        val = 128 * captured_piece_value + capturing_piece_value             *
+ *   complemented value of the capturing piece.  This is the classic MVV/LVA   *
- *                                                                             *
- *   This is the classic MVV/LVA ordering approach that removes heavy pieces   *
+ *   ordering approach that removes heavy pieces first in an attempt to reduce *
- *   first in an attempt to reduce the size of the sub-tree these pieces       *
- *   produce.                                                                  *
+ *   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   *
+ *   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        *
+ *   (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 Quiesce(TREE * RESTRICT tree, int ply, int wtm, int alpha, int beta,
     int checks) {
+  unsigned *next, *movep;
   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) {
+  if (search_nodes && --temp_search_nodes <= 0) {
     abort_search = 1;
     return 0;
+  }
 #endif
   if (tree->thread_id == 0)
  *  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);
+    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_depth;
+    tree->pv[ply].pathd = iteration;
+  }
 /*
  ************************************************************
  *                                                          *
  *  Generate captures and sort them based on simple MVV/LVA *
  *  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          *
+ *  SEE() to exclude captures that appear to lose material, *
- *  material, but we delay expending this effort as long as *
+ *  but we delay expending this effort as long as possible, *
- *  possible, since beta cutoffs make it unnecessary to     *
+ *  since beta cutoffs make it unnecessary to search all of *
- *  search all of these moves anyway.                       *
+ *  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)];
+    *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;
+  }
-/*
- ************************************************************
- *                                                          *
- *  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];
+  NextSort(tree, 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.                                 *
  *                                                          *
  *  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  *
+ *  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] = *next;
+    tree->curmv[ply] = Move(*next);
     if (pcval[Piece(tree->curmv[ply])] > pcval[Captured(tree->curmv[ply])] &&
-        TotalPieces(wtm, occupied)
+        TotalPieces(Flip(wtm), occupied)
         - p_vals[Captured(tree->curmv[ply])] > 0 &&
-        Swap(tree, tree->curmv[ply], wtm) < 0)
+        SEE(tree, wtm, tree->curmv[ply]) < 0)
       continue;
 #if defined(TRACE)
     if (ply <= trace_level)
-      Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", CAPTURE_MOVES);
+      Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", serial, CAPTURES,
+          next - tree->last[ply - 1] + 1);
 #endif
-    MakeMove(tree, ply, tree->curmv[ply], wtm);
+    MakeMove(tree, ply, wtm, tree->curmv[ply]);
     tree->nodes_searched++;
     if (!checks)
-      value = -Quiesce(tree, -beta, -alpha, Flip(wtm), ply + 1, 0);
+      value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 0);
     else if (!Check(wtm)) {
       if (Check(Flip(wtm))) {
         tree->qchecks_done++;
-        value = -QuiesceEvasions(tree, -beta, -alpha, Flip(wtm), ply + 1);
+        value = -QuiesceEvasions(tree, ply + 1, Flip(wtm), -beta, -alpha);
       } else
-        value = -Quiesce(tree, -beta, -alpha, Flip(wtm), ply + 1, 0);
+        value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 0);
+    }
-    UnmakeMove(tree, ply, tree->curmv[ply], wtm);
+    UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
     if (abort_search || tree->stop)
       return 0;
     if (value > alpha) {
       if (value >= beta)
         return 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  *
+ *  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."      *
  *                                                          *
  ************************************************************
  */
  *  GenerateChecks() provides.                              *
  *                                                          *
  ************************************************************
  */
     for (next = tree->last[ply - 1]; next < tree->last[ply]; next++) {
-      tree->curmv[ply] = *next;
+      tree->curmv[ply] = Move(*next);
-      if (Swap(tree, tree->curmv[ply], wtm) >= 0) {
+      if (SEE(tree, wtm, tree->curmv[ply]) >= 0) {
 #if defined(TRACE)
         if (ply <= trace_level)
-          Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce", REMAINING_MOVES);
+          Trace(tree, ply, 0, wtm, alpha, beta, "Quiesce+checks", serial,
+              REMAINING, next - tree->last[ply - 1] + 1);
 #endif
-        MakeMove(tree, ply, tree->curmv[ply], wtm);
+        MakeMove(tree, ply, wtm, tree->curmv[ply]);
         tree->nodes_searched++;
         if (!Check(wtm)) {
           tree->qchecks_done++;
-          value = -QuiesceEvasions(tree, -beta, -alpha, Flip(wtm), ply + 1);
+          value = -QuiesceEvasions(tree, ply + 1, Flip(wtm), -beta, -alpha);
+        }
-        UnmakeMove(tree, ply, tree->curmv[ply], wtm);
+        UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
         if (abort_search || tree->stop)
           return 0;
         if (value > alpha) {
           if (value >= beta)
             return value;
     tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
+  }
   return alpha;
+}
-/* last modified 05/07/14 */
+/* 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 *
  *   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 QuiesceEvasions(TREE * RESTRICT tree, int ply, int wtm, int alpha,
-    int ply) {
+    int beta) {
-  int original_alpha, value;
+  int original_alpha, value, moves_searched = 0, order;
-  int moves_searched = 0;
 /*
  ************************************************************
  *                                                          *
  *  Initialize.                                             *
  ************************************************************
  */
   if (ply >= MAXPLY - 1)
     return beta;
 #if defined(NODES)
-  if (--temp_search_nodes <= 0) {
+  if (search_nodes && --temp_search_nodes <= 0) {
     abort_search = 1;
     return 0;
+  }
   if (tree->thread_id == 0)
     next_time_check--;
  *  position.                                               *
  *                                                          *
  ************************************************************
  */
   tree->hash_move[ply] = 0;
-  tree->next_status[ply].phase = HASH_MOVE;
+  tree->next_status[ply].phase = HASH;
-  while ((tree->phase[ply] = NextEvasion(tree, ply, wtm))) {
+  while ((order = NextMove(tree, ply, 0, wtm, 1))) {
 #if defined(TRACE)
     if (ply <= trace_level)
-      Trace(tree, ply, 0, wtm, alpha, beta, "QuiesceEvasions",
+      Trace(tree, ply, 0, wtm, alpha, beta, "QuiesceEvasions", serial,
-          tree->phase[ply]);
+          tree->phase[ply], order);
 #endif
     moves_searched++;
-    MakeMove(tree, ply, tree->curmv[ply], wtm);
+    MakeMove(tree, ply, wtm, tree->curmv[ply]);
     tree->nodes_searched++;
-    value = -Quiesce(tree, -beta, -alpha, Flip(wtm), ply + 1, 0);
+    value = -Quiesce(tree, ply + 1, Flip(wtm), -beta, -alpha, 0);
-    UnmakeMove(tree, ply, tree->curmv[ply], wtm);
+    UnmakeMove(tree, ply, wtm, tree->curmv[ply]);
     if (abort_search || tree->stop)
       return 0;
     if (value > alpha) {
       if (value >= beta)
         return value;
+    }
+  }
 /*
  ************************************************************
  *                                                          *
- *  All moves have been searched.  If none were legal,      *
+ *  All moves have been searched.  If none were legal, it   *
- *  return either MATE or DRAW depending on whether the     *
+ *  must be a mate since we have to be in check to reach    *
- *  side to move is in check or not.                        *
+ *  QuiesceEvasions().                                      *
  *                                                          *
  ************************************************************
  */
   if (moves_searched == 0) {
-    value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);
+    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);

Subversion Repositories Games.Chess Giants

Games.Chess Giants//engine-crafty/quiesce.c – Rev 33 → 108