From 5ee16a180a7eb3f51f7cabd86cf17d8c217b13b3 Mon Sep 17 00:00:00 2001
From: Eelco de Groot <eelcogro@gmail.com>
Date: Mon, 29 Jul 2013 01:16:25 +0200
Subject: [PATCH] Increase pruning if evaluation is not improving

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 | 25 +++++++++++++++----------
 src/types.h    |  2 +-
 2 files changed, 16 insertions(+), 11 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index c6bc8e37..78a72bec 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -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();
diff --git a/src/types.h b/src/types.h
index d27f390a..d7dfb7ad 100644
--- a/src/types.h
+++ b/src/types.h
@@ -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
 ///
-- 
2.39.2