Try only recaptures in qsearch if depth is very low

This avoids search explosion in qsearch for some
patological cases like:

r1n1n1b1/1P1P1P1P/1N1N1N2/2RnQrRq/2pKp3/3BNQbQ/k7/4Bq2 w - - 0 1

After 9078 games 20"+0.1 QUAD:
Mod vs Orig 1413 - 1319 - 6346 ELO +3 (+- 4)

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 04fa40d625ba8212a4dceb2ed0278a966a5b7fe5..71c9810d6096e9741c7d5fbb836282a364cac6de 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -37,6 +37,7 @@ namespace {
     PH_BAD_CAPTURES,  // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0)
     PH_EVASIONS,      // Check evasions
     PH_QCAPTURES,     // Captures in quiescence search
     PH_BAD_CAPTURES,  // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0)
     PH_EVASIONS,      // Check evasions
     PH_QCAPTURES,     // Captures in quiescence search

+    PH_QRECAPTURES,   // Recaptures in quiescence search

     PH_QCHECKS,       // Non-capture checks in quiescence search
     PH_STOP
   };
     PH_QCHECKS,       // Non-capture checks in quiescence search
     PH_STOP
   };


@@ -46,6 +47,7 @@ namespace {
   const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP };
   const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP };
   const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP };
   const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP };
   const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP };
   const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP };

+  const uint8_t QsearchRecapturesTable[] = { PH_TT_MOVE, PH_QRECAPTURES, PH_STOP };

   const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP };
 }
 
   const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP };
 }
 


@@ -85,7 +87,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h,
   go_next_phase();
 }
 
   go_next_phase();
 }
 

-MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h)
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, Square recaptureSq)

                       : pos(p), H(h) {
 
   assert(d <= DEPTH_ZERO);
                       : pos(p), H(h) {
 
   assert(d <= DEPTH_ZERO);


@@ -94,7 +96,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h)
       phasePtr = EvasionTable;
   else if (d >= DEPTH_QS_CHECKS)
       phasePtr = QsearchWithChecksTable;
       phasePtr = EvasionTable;
   else if (d >= DEPTH_QS_CHECKS)
       phasePtr = QsearchWithChecksTable;

-  else
+  else if (d >= DEPTH_QS_RECAPTURES)

   {
       phasePtr = QsearchWithoutChecksTable;
 
   {
       phasePtr = QsearchWithoutChecksTable;
 


@@ -104,6 +106,12 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h)
       if (ttm != MOVE_NONE && !pos.move_is_capture(ttm) && !move_is_promotion(ttm))
           ttm = MOVE_NONE;
   }
       if (ttm != MOVE_NONE && !pos.move_is_capture(ttm) && !move_is_promotion(ttm))
           ttm = MOVE_NONE;
   }

+  else
+  {
+      phasePtr = QsearchRecapturesTable;
+      recaptureSquare = recaptureSq;
+      ttm = MOVE_NONE;
+  }

 
   ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
   phasePtr += int(ttMove == MOVE_NONE) - 1;
 
   ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
   phasePtr += int(ttMove == MOVE_NONE) - 1;


@@ -184,6 +192,10 @@ void MovePicker::go_next_phase() {
       score_captures();
       return;
 
       score_captures();
       return;
 

+  case PH_QRECAPTURES:
+      lastMove = generate<MV_CAPTURE>(pos, moves);
+      return;
+

   case PH_QCHECKS:
       lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
       return;
   case PH_QCHECKS:
       lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
       return;


@@ -347,6 +359,12 @@ Move MovePicker::get_next_move() {
               return move;
           break;
 
               return move;
           break;
 

+      case PH_QRECAPTURES:
+          move = (curMove++)->move;
+          if (move_to(move) == recaptureSquare)
+              return move;
+          break;
+

       case PH_QCHECKS:
           move = (curMove++)->move;
           if (move != ttMove)
       case PH_QCHECKS:
           move = (curMove++)->move;
           if (move != ttMove)

diff --git a/src/movepick.h b/src/movepick.h
index d0ced0474ffd901e6b34275acf520147001fe506..1316e7c03933198e8dff5e6eb0760d6b3bf4edf2 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -41,7 +41,7 @@ class MovePicker {
 
 public:
   MovePicker(const Position&, Move, Depth, const History&, SearchStack*, Value);
 
 public:
   MovePicker(const Position&, Move, Depth, const History&, SearchStack*, Value);

-  MovePicker(const Position&, Move, Depth, const History&);
+  MovePicker(const Position&, Move, Depth, const History&, Square recaptureSq);

   MovePicker(const Position&, Move, const History&, int parentCapture);
   Move get_next_move();
 
   MovePicker(const Position&, Move, const History&, int parentCapture);
   Move get_next_move();
 


@@ -56,6 +56,7 @@ private:
   Depth depth;
   Move ttMove;
   MoveStack killers[2];
   Depth depth;
   Move ttMove;
   MoveStack killers[2];

+  Square recaptureSquare;

   int captureThreshold, phase;
   const uint8_t* phasePtr;
   MoveStack *curMove, *lastMove, *lastNonCapture, *badCaptures;
   int captureThreshold, phase;
   const uint8_t* phasePtr;
   MoveStack *curMove, *lastMove, *lastNonCapture, *badCaptures;

diff --git a/src/search.cpp b/src/search.cpp
index 3862e27b74a1c4d6123441616cbcefa428a0f201..50dfcc0ced1dc210acb6bf8cb23ffe9c7e6458e7 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1393,7 +1393,7 @@ split_point_start: // At split points actual search starts from here
     // to search the moves. Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
     // be generated.
     // to search the moves. Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
     // be generated.

-    MovePicker mp(pos, ttMove, depth, H);
+    MovePicker mp(pos, ttMove, depth, H, move_to((ss-1)->currentMove));

     CheckInfo ci(pos);
     Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 
     CheckInfo ci(pos);
     Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 

diff --git a/src/types.h b/src/types.h
index 345751455dbf54d853a88dd874eea367ecd58e35..d02755c1adcbd46eeb83f8c1bb89f8eb87198a6f 100644 (file)
--- a/src/types.h
+++ b/src/types.h
@@ -201,9 +201,10 @@ enum Depth {
 
   ONE_PLY = 2,
 
 
   ONE_PLY = 2,
 

-  DEPTH_ZERO         =  0 * ONE_PLY,
-  DEPTH_QS_CHECKS    = -1 * ONE_PLY,
-  DEPTH_QS_NO_CHECKS = -2 * ONE_PLY,
+  DEPTH_ZERO          =  0 * ONE_PLY,
+  DEPTH_QS_CHECKS     = -1 * ONE_PLY,
+  DEPTH_QS_NO_CHECKS  = -2 * ONE_PLY,
+  DEPTH_QS_RECAPTURES = -4 * ONE_PLY,

 
   DEPTH_NONE = -127 * ONE_PLY
 };
 
   DEPTH_NONE = -127 * ONE_PLY
 };