Increase pruning if evaluation is not improving
authorEelco de Groot <eelcogro@gmail.com>
Sun, 28 Jul 2013 23:16:25 +0000 (01:16 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Sun, 28 Jul 2013 23:21:21 +0000 (01:21 +0200)
Add an additional set of margins to movecount pruning
to be used when static evaluation is getting worse
than previous move.

Here are the margins table with changing
depth (fm0 not improving, fm1 improving):

    d: 0, fm0: 3, fm1: 3
    d: 1, fm0: 4, fm1: 4
    d: 2, fm0: 6, fm1: 6
    d: 3, fm0: 7, fm1: 10
    d: 4, fm0: 11, fm1: 15
    d: 5, fm0: 15, fm1: 21
    d: 6, fm0: 21, fm1: 29
    d: 7, fm0: 27, fm1: 37
    d: 8, fm0: 35, fm1: 47
    d: 9, fm0: 42, fm1: 57
    d: 10, fm0: 51, fm1: 68
    d: 11, fm0: 60, fm1: 81
    d: 12, fm0: 70, fm1: 94
    d: 13, fm0: 81, fm1: 108
    d: 14, fm0: 92, fm1: 123
    d: 15, fm0: 104, fm1: 139

Good at both short TC

LLR: 2.97 (-2.94,2.94)
Total: 11502 W: 2503 L: 2361 D: 6638

And long TC

LLR: 2.98 (-2.94,2.94)
Total: 7189 W: 1421 L: 1277 D: 4491

bench: 4364793

src/search.cpp
src/types.h

index c6bc8e372bcd28d4c02c8b2a6ccd1b22a3e4a6e8..78a72beccfdc777e549a7dd786d8483208089b9f 100644 (file)
@@ -66,7 +66,7 @@ namespace {
 
   // Futility lookup tables (initialized at startup) and their access functions
   Value FutilityMargins[16][64]; // [depth][moveNumber]
-  int FutilityMoveCounts[32];    // [depth]
+  int FutilityMoveCounts[2][32]; // [improving][depth]
 
   inline Value futility_margin(Depth d, int mn) {
 
@@ -146,7 +146,11 @@ void Search::init() {
 
   // Init futility move count array
   for (d = 0; d < 32; d++)
-      FutilityMoveCounts[d] = int(3.001 + 0.3 * pow(double(d), 1.8));
+  {
+      FutilityMoveCounts[1][d] = int(3.001 + 0.3 * pow(double(d), 1.8));
+      FutilityMoveCounts[0][d] = d < 5 ? FutilityMoveCounts[1][d]
+                                       : 3 * FutilityMoveCounts[1][d] / 4;
+  }
 }
 
 
@@ -294,11 +298,11 @@ namespace {
 
   void id_loop(Position& pos) {
 
-    Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1)
+    Stack stack[MAX_PLY_PLUS_3], *ss = stack+2; // To allow referencing (ss-2)
     int depth, prevBestMoveChanges;
     Value bestValue, alpha, beta, delta;
 
-    std::memset(ss-1, 0, 4 * sizeof(Stack));
+    std::memset(ss-2, 0, 5 * sizeof(Stack));
     (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains
 
     depth = BestMoveChanges = 0;
@@ -496,7 +500,7 @@ namespace {
     Depth ext, newDepth;
     Value bestValue, value, ttValue;
     Value eval, nullValue, futilityValue;
-    bool inCheck, givesCheck, pvMove, singularExtensionNode;
+    bool inCheck, givesCheck, pvMove, singularExtensionNode, improving;
     bool captureOrPromotion, dangerous, doFullDepthSearch;
     int moveCount, quietCount;
 
@@ -765,6 +769,7 @@ moves_loop: // When in check and at SpNode search starts from here
     MovePicker mp(pos, ttMove, depth, History, countermoves, ss);
     CheckInfo ci(pos);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
+    improving = ss->staticEval >= (ss-2)->staticEval;
     singularExtensionNode =   !RootNode
                            && !SpNode
                            &&  depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY)
@@ -861,7 +866,7 @@ moves_loop: // When in check and at SpNode search starts from here
       {
           // Move count based pruning
           if (   depth < 16 * ONE_PLY
-              && moveCount >= FutilityMoveCounts[depth]
+              && moveCount >= FutilityMoveCounts[improving][depth]
               && (!threatMove || !refutes(pos, move, threatMove)))
           {
               if (SpNode)
@@ -1562,7 +1567,7 @@ moves_loop: // When in check and at SpNode search starts from here
 
 void RootMove::extract_pv_from_tt(Position& pos) {
 
-  StateInfo state[MAX_PLY_PLUS_2], *st = state;
+  StateInfo state[MAX_PLY_PLUS_3], *st = state;
   const TTEntry* tte;
   int ply = 0;
   Move m = pv[0];
@@ -1595,7 +1600,7 @@ void RootMove::extract_pv_from_tt(Position& pos) {
 
 void RootMove::insert_pv_in_tt(Position& pos) {
 
-  StateInfo state[MAX_PLY_PLUS_2], *st = state;
+  StateInfo state[MAX_PLY_PLUS_3], *st = state;
   const TTEntry* tte;
   int ply = 0;
 
@@ -1670,10 +1675,10 @@ void Thread::idle_loop() {
 
           Threads.mutex.unlock();
 
-          Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1)
+          Stack stack[MAX_PLY_PLUS_3], *ss = stack+2; // To allow referencing (ss-2)
           Position pos(*sp->pos, this);
 
-          std::memcpy(ss-1, sp->ss-1, 4 * sizeof(Stack));
+          std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack));
           ss->splitPoint = sp;
 
           sp->mutex.lock();
index d27f390a2d970d0eeeeb2acd39b8a527f43874de..d7dfb7ad9feecb0f28cf8e0ec8aad55c3ccd9dc1 100644 (file)
@@ -90,7 +90,7 @@ typedef uint64_t Bitboard;
 
 const int MAX_MOVES      = 192;
 const int MAX_PLY        = 100;
-const int MAX_PLY_PLUS_2 = MAX_PLY + 2;
+const int MAX_PLY_PLUS_3 = MAX_PLY + 3;
 
 /// A move needs 16 bits to be stored
 ///