Similarize pruning code in search() and sp_search()

Use futility pruning also in split points.
Do not use history pruning in split points when
getting mated.

After 1000 games on Joona QUAD
Orig - Mod: 496 - 504

Added an optimization to avoid a costly lock in the
very common case that sp->futilityValue <= sp->bestValue.
A test on a dual CPU shows only 114 hits on 23196 events,
so avoid a lock in all the other cases.

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

diff --git a/src/search.cpp b/src/search.cpp
index 53811de04701c4705053dc0d3ed1e52049db0aed..13affe1b2f06e0a30fd95b5ea5548aad61c3c524 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -308,7 +308,9 @@ namespace {
   bool thread_is_available(int slave, int master);
   bool idle_thread_exists(int master);
   bool split(const Position& pos, SearchStack* ss, int ply,
   bool thread_is_available(int slave, int master);
   bool idle_thread_exists(int master);
   bool split(const Position& pos, SearchStack* ss, int ply,

-             Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
+             Value *alpha, Value *beta, Value *bestValue,
+             const Value futilityValue, const Value approximateValue,
+             Depth depth, int *moves,

              MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
   void wake_sleeping_threads();
 
              MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
   void wake_sleeping_threads();
 


@@ -1176,7 +1178,7 @@ namespace {
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)

-          && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
+          && split(pos, ss, ply, &alpha, &beta, &bestValue, VALUE_NONE, VALUE_NONE, depth,

                    &moveCount, &mp, dcCandidates, threadID, true))
           break;
     }
                    &moveCount, &mp, dcCandidates, threadID, true))
           break;
     }


@@ -1437,7 +1439,7 @@ namespace {
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)

-          && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
+          && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, approximateEval, depth, &moveCount,

                    &mp, dcCandidates, threadID, false))
         break;
     }
                    &mp, dcCandidates, threadID, false))
         break;
     }


@@ -1693,10 +1695,37 @@ namespace {
       if (    useFutilityPruning
           && !dangerous
           && !moveIsCapture
       if (    useFutilityPruning
           && !dangerous
           && !moveIsCapture

-          && !move_is_promotion(move)
-          &&  moveCount >= 2 + int(sp->depth)
-          &&  ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
-        continue;
+          && !move_is_promotion(move))
+      {
+          // History pruning. See ok_to_prune() definition
+          if (   moveCount >= 2 + int(sp->depth)
+              && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth)
+              && sp->bestValue > value_mated_in(PLY_MAX))
+              continue;
+
+          // Value based pruning
+          if (sp->approximateEval < sp->beta)
+          {
+              if (sp->futilityValue == VALUE_NONE)
+              {
+                  EvalInfo ei;
+                  sp->futilityValue =  evaluate(pos, ei, threadID)
+                                    + FutilityMargins[int(sp->depth) - 2];
+              }
+
+              if (sp->futilityValue < sp->beta)
+              {
+                  if (sp->futilityValue > sp->bestValue) // Less then 1% of cases
+                  {
+                      lock_grab(&(sp->lock));
+                      if (sp->futilityValue > sp->bestValue)
+                          sp->bestValue = sp->futilityValue;
+                      lock_release(&(sp->lock));
+                  }
+                  continue;
+              }
+          }
+      }

 
       // Make and search the move.
       StateInfo st;
 
       // Make and search the move.
       StateInfo st;


@@ -2756,7 +2785,8 @@ namespace {
   // splitPoint->cpus becomes 0), split() returns true.
 
   bool split(const Position& p, SearchStack* sstck, int ply,
   // splitPoint->cpus becomes 0), split() returns true.
 
   bool split(const Position& p, SearchStack* sstck, int ply,

-             Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
+             Value* alpha, Value* beta, Value* bestValue, const Value futilityValue,
+             const Value approximateEval, Depth depth, int* moves,

              MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
 
     assert(p.is_ok());
              MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
 
     assert(p.is_ok());


@@ -2796,6 +2826,8 @@ namespace {
     splitPoint->pvNode = pvNode;
     splitPoint->dcCandidates = dcCandidates;
     splitPoint->bestValue = *bestValue;
     splitPoint->pvNode = pvNode;
     splitPoint->dcCandidates = dcCandidates;
     splitPoint->bestValue = *bestValue;

+    splitPoint->futilityValue = futilityValue;
+    splitPoint->approximateEval = approximateEval;

     splitPoint->master = master;
     splitPoint->mp = mp;
     splitPoint->moves = *moves;
     splitPoint->master = master;
     splitPoint->mp = mp;
     splitPoint->moves = *moves;

diff --git a/src/thread.h b/src/thread.h
index dc839d441518d51f2f7204b7b6a5adbdbbcda8f7..6c6ccf7ea9750b6cec2d7b071c8f30e0ca3a1ace 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -50,7 +50,8 @@ struct SplitPoint {
   SearchStack *parentSstack;
   int ply;
   Depth depth;
   SearchStack *parentSstack;
   int ply;
   Depth depth;

-  volatile Value alpha, beta, bestValue;
+  volatile Value alpha, beta, bestValue, futilityValue;
+  Value approximateEval;

   bool pvNode;
   Bitboard dcCandidates;
   int master, slaves[THREAD_MAX];
   bool pvNode;
   Bitboard dcCandidates;
   int master, slaves[THREAD_MAX];