Stockfish 1.8 tweaks

[QED]

The original stockfish has lost +189 =577 -234 (LOS=6:93), so it looks this patch can be considered better (bayeselo says better by 12+-17 elo, so nothing certain). This patch still has 'fail high' condition in.

All of my attempts to change the move ordering are hurting nps too much, so I decided to test another SMRC setup, this time with smaller steps. The quoted patch lost to slightly tweaked one +198 =586 -216 (LOS=27:72), where the slight tweak was just removing 'fail high' condition and nothing else this time:

Code: Select all

     // Step 9. Internal iterative deepening
     if (    depth >= IIDDepth[PvNode]
-        &&  ttMove == MOVE_NONE
-        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
+        &&  ttMove == MOVE_NONE)
     {
         Depth d = (PvNode ? depth - 2 * OnePly : depth - 4 * OnePly);

Complete change to original Stockfish is:

Code: Select all

diff -dur src-Ch/search.cpp src-Asm5SmrcCh/search.cpp
--- src-Ch/search.cpp   2010-07-09 13:04:18.000000000 +0200
+++ src-Asm5SmrcCh/search.cpp   2010-08-08 23:18:51.000000000 +0200
@@ -1058,7 +1058,7 @@
     const TTEntry* tte;
     Key posKey;
     Move ttMove, move, excludedMove;
-    Depth ext, newDepth;
+    Depth ext, newDepth, oldDepth = depth;
     Value bestValue, value, oldAlpha;
     Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific
     bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
@@ -1210,7 +1210,9 @@
                 return nullValue;

             ss->skipNullMove = true;
+            (ss-1)->reduction += 5*OnePly;
             Value v = search<NonPV>&#40;pos, ss, alpha, beta, depth-5*OnePly, ply&#41;;
+            &#40;ss-1&#41;->reduction -= 5*OnePly;
             ss->skipNullMove = false;

             if &#40;v >= beta&#41;
@@ -1237,10 +1239,9 @@

     // Step 9. Internal iterative deepening
     if (    depth >= IIDDepth&#91;PvNode&#93;
-        &&  ttMove == MOVE_NONE
-        && &#40;PvNode || (!isCheck && ss->eval >= beta - IIDMargin&#41;))
+        &&  ttMove == MOVE_NONE&#41;
     &#123;
-        Depth d = &#40;PvNode ? depth - 2 * OnePly &#58; depth / 2&#41;;
+        Depth d = &#40;PvNode ? depth - 2 * OnePly &#58; depth - 4 * OnePly&#41;;

         ss->skipNullMove = true;
         search<PvNode>&#40;pos, ss, alpha, beta, d, ply&#41;;
@@ -1262,7 +1263,7 @@
                            && tte && tte->move&#40;)
                            && !excludedMove // Do not allow recursive singular extension search
                            && is_lower_bound&#40;tte->type&#40;))
-                           && tte->depth&#40;) >= depth - 3 * OnePly;
+                           && tte->depth&#40;) >= depth - 4 * OnePly;

     // Step 10. Loop through moves
     // Loop through all legal moves until no moves remain or a beta cutoff occurs
@@ -1285,22 +1286,24 @@
       // its siblings. To verify this we do a reduced search on all the other moves but the
       // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
       if (   singularExtensionNode
-          && move == tte->move&#40;)
-          && ext < OnePly&#41;
+          && move == tte->move&#40;))
       &#123;
-          Value ttValue = value_from_tt&#40;tte->value&#40;), ply&#41;;
-
-          if &#40;abs&#40;ttValue&#41; < VALUE_KNOWN_WIN&#41;
+          if &#40;abs&#40;alpha&#41; < VALUE_KNOWN_WIN&#41;
           &#123;
-              Value b = ttValue - SingularExtensionMargin;
+              Value b = alpha - SingularExtensionMargin;
               ss->excludedMove = move;
               ss->skipNullMove = true;
-              Value v = search<NonPV>&#40;pos, ss, b - 1, b, depth / 2, ply&#41;;
+              assert&#40;&#40;depth + &#40;ss-1&#41;->reduction&#41; / 2 <= depth&#41;;
+              Value v = search<NonPV>&#40;pos, ss, b - 1, b, &#40;depth + &#40;ss-1&#41;->reduction&#41; / 2, ply&#41;;
               ss->skipNullMove = false;
               ss->excludedMove = MOVE_NONE;
-              if &#40;v < ttValue - SingularExtensionMargin&#41;
+              if &#40;v < alpha - SingularExtensionMargin&#41;
                   ext = OnePly;
+              else
+                  singularExtensionNode = false;
           &#125;
+          else
+              singularExtensionNode = false;
       &#125;

       newDepth = depth - OnePly + ext;
@@ -1396,6 +1399,19 @@
           &#125;
       &#125;

+      // Singular Move Reduction Cancellation.
+      if (   singularExtensionNode
+          && ttMove == move
+          && &#40;ss-1&#41;->reduction
+          && value >= beta&#41;
+      &#123;
+          depth += &#40;ss-1&#41;->reduction;
+          newDepth += &#40;ss-1&#41;->reduction;
+          assert&#40;PvNode == NonPV&#41;;
+          value = newDepth < OnePly ? -qsearch<NonPV>&#40;pos, ss+1, -&#40;alpha+1&#41;, -alpha, Depth&#40;0&#41;, ply+1&#41;
+                                    &#58; - search<NonPV>&#40;pos, ss+1, -&#40;alpha+1&#41;, -alpha, newDepth, ply+1&#41;;
+      &#125;
+
       // Step 16. Undo move
       pos.undo_move&#40;move&#41;;

@@ -1444,7 +1460,7 @@

     ValueType f = &#40;bestValue <= oldAlpha ? VALUE_TYPE_UPPER &#58; bestValue >= beta ? VALUE_TYPE_LOWER &#58; VALUE_TYPE_EXACT&#41;;
     move = &#40;bestValue <= oldAlpha ? MOVE_NONE &#58; ss->bestMove&#41;;
-    TT.store&#40;posKey, value_to_tt&#40;bestValue, ply&#41;, f, depth, move, ss->eval, ei.kingDanger&#91;pos.side_to_move&#40;)&#93;);
+    TT.store&#40;posKey, value_to_tt&#40;bestValue, ply&#41;, f, oldDepth, move, ss->eval, ei.kingDanger&#91;pos.side_to_move&#40;)&#93;);

     // Update killers and history only for non capture moves that fails high
     if &#40;bestValue >= beta&#41;

Of course, 27:72 is nothing conclusive, so I will have something to test also if I do not have a new patch ready.

[QED]

There was a discussion in the next singular extension test thread and I had no other good thing to test, so:

Not sure I understand your point regarding SF's relaxed SE correctly. Is the following right?

No, what you describe was indeed one possibility of implementing this SE thing, but you didn't note that special exclusion key is used only in SE node, it's not xorred to the actual position key, so it has no effect to children nodes.

This is because in perfectly ordered tree, in cut node, it's only necessary to examine the first move. Relaxed exclusion search examines all the other moves. So with great probability the search trees do not overlap too heavily.

The only exceptions are the PV nodes and it's possible that indeed bad things happens there in SF. Perhaps we could improve by XORring the exclusion key also to the position key, haven't tested it. It's somewhere down in my TODO list (actually more fine tuned approach than single key would be needed for the optimal solution)

In my view, the worst thing about exclusion search is that it is called with way different alpha, so in the subtree it is likely to overwrite upper bounds with lower bound and vice versa. Using alpha minus margin for detecting singular moves is good in that if ever in the subtree a move is exclusion search tested for singularity, margin would be cancelled. So xoring single exclusion key to position key would make second exclusion (somewhere in the subtree) to be able to use TT entries with the same alpha, same key and bigger depth.

So first I changed original stockfish to use alpha (instead ttValue) to make SF-A:

Code: Select all

diff -dur src-Ch/search.cpp src-AsmCh/search.cpp
--- src-Ch/search.cpp   2010-07-09 13:04:18.000000000 +0200
+++ src-AsmCh/search.cpp        2010-08-10 22:27:23.000000000 +0200
@@ -1288,17 +1288,15 @@
           && move == tte->move()
           && ext < OnePly&#41;
       &#123;
-          Value ttValue = value_from_tt&#40;tte->value&#40;), ply&#41;;
-
-          if &#40;abs&#40;ttValue&#41; < VALUE_KNOWN_WIN&#41;
+          if &#40;abs&#40;alpha&#41; < VALUE_KNOWN_WIN&#41;
           &#123;
-              Value b = ttValue - SingularExtensionMargin;
+              Value b = alpha - SingularExtensionMargin;
               ss->excludedMove = move;
               ss->skipNullMove = true;
               Value v = search<NonPV>&#40;pos, ss, b - 1, b, depth / 2, ply&#41;;
               ss->skipNullMove = false;
               ss->excludedMove = MOVE_NONE;
-              if &#40;v < ttValue - SingularExtensionMargin&#41;
+              if &#40;v <= alpha - SingularExtensionMargin&#41;
                   ext = OnePly;
           &#125;
       &#125;

and from this I made SF-B that xors the exclusion key to position key:

Code: Select all

diff -dur src-AsmCh/position.h src-AsmEhCh/position.h
--- src-AsmCh/position.h        2010-07-09 13:03:34.000000000 +0200
+++ src-AsmEhCh/position.h      2010-08-10 22:32:52.000000000 +0200
@@ -239,6 +239,7 @@
   void detach();
   void do_move(Move m, StateInfo& st);
   void do_move(Move m, StateInfo& st, const CheckInfo& ci, bool moveIsCheck);
+  void apply_exclusion();
   void undo_move(Move m);
   void do_null_move(StateInfo& st);
   void undo_null_move();
@@ -251,7 +252,6 @@

   // Accessing hash keys
   Key get_key() const;
-  Key get_exclusion_key() const;
   Key get_pawn_key() const;
   Key get_material_key() const;

@@ -495,8 +495,8 @@
   return st->key;
 }

-inline Key Position::get_exclusion_key() const {
-  return st->key ^ zobExclusion;
+inline void Position::apply_exclusion() {
+  st->key ^= zobExclusion;
 }

 inline Key Position::get_pawn_key() const {
diff -dur src-AsmCh/search.cpp src-AsmEhCh/search.cpp
--- src-AsmCh/search.cpp        2010-08-10 22:27:23.000000000 +0200
+++ src-AsmEhCh/search.cpp      2010-08-10 22:32:52.000000000 +0200
@@ -1097,7 +1097,7 @@
     // We don't want the score of a partial search to overwrite a previous full search
     // TT value, so we use a different position key in case of an excluded move exists.
     excludedMove = ss->excludedMove;
-    posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
+    posKey = pos.get_key();

     tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
@@ -1293,7 +1293,9 @@
               Value b = alpha - SingularExtensionMargin;
               ss->excludedMove = move;
               ss->skipNullMove = true;
+              pos.apply_exclusion();
               Value v = search<NonPV>&#40;pos, ss, b - 1, b, depth / 2, ply&#41;;
+              pos.apply_exclusion&#40;);
               ss->skipNullMove = false;
               ss->excludedMove = MOVE_NONE;
               if &#40;v <= alpha - SingularExtensionMargin&#41;

Then I ran a match between SF-A and SF-B. But SF-A has won convincingly +231 =618 -151 (LOS 99:0). The most probable explanation is that I have a bug in SF-B somewhere (I am not sure I have guessed corectly how exactly StateInfo is used). Other explanation is "forgetting TT entries is good sometimes", that would be a second appearance of this explanation. The first time it was when I tried to make TT to store both bounds.

[QED]

All of my attempts to change the move ordering are hurting nps too much, so I decided to test another SMRC setup, this time with smaller steps. The quoted patch lost to slightly tweaked one +198 =586 -216 (LOS=27:72), where the slight tweak was just removing 'fail high' condition and nothing else this time:

Code: Select all

     // Step 9. Internal iterative deepening
     if (    depth >= IIDDepth[PvNode]
-        &&  ttMove == MOVE_NONE
-        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
+        &&  ttMove == MOVE_NONE)
     {
         Depth d = (PvNode ? depth - 2 * OnePly : depth - 4 * OnePly);

Another slight tweak. In a match between the quoted patch and the following one upon it:

Code: Select all

diff -dur src-Asm5SmrcCh/search.cpp src-Asm6SmrcCh/search.cpp
--- src-Asm5SmrcCh/search.cpp   2010-08-11 23:12:16.000000000 +0200
+++ src-Asm6SmrcCh/search.cpp   2010-08-11 23:15:26.000000000 +0200
@@ -1239,7 +1239,9 @@

     // Step 9. Internal iterative deepening
     if (    depth >= IIDDepth[PvNode]
-        &&  ttMove == MOVE_NONE)
+        && (   ttMove == MOVE_NONE
+            || !(   tte
+                 && tte->depth() >= depth - 4 * OnePly)))
     {
         Depth d = (PvNode ? depth - 2 * OnePly : depth - 4 * OnePly);

the quoted one lost narrowly +202 =589 -209 (LOS=39:60), so no conclusions.

[QED]

I am back from vacation, so I can test more incrementally and thoroughly, because I have next to no time to code anything substantial.

First, reacting to this older post:

Another tweak. Test was unsuccessfull, bayeselo says original stockfish is better with LOS=87:12.

But it was a lot of work, and I would say there are few bugs left hurting performance, so I am going to post the patch anayway, so you can tell me why is it not working better.

Idea is simple, make transposition table store both lower bound and upper bound with their respective depths. I had to squeeze all that into TTEntry and modify search to use new interface the right way. Implementation is of course a mess. Affected files: value.h, tt.h, tt.cpp and search.cpp

I have polished few thing when the test was running, but here is the tested patch:

(code skipped) I did a slight change:

Code: Select all

diff -dur src-BbCh/search.cpp src-Bb2Ch/search.cpp
--- src-BbCh/search.cpp 2010-07-20 22:24:14.000000000 +0200
+++ src-Bb2Ch/search.cpp        2010-08-22 21:57:53.000000000 +0200
@@ -1151,7 +1151,7 @@
     {
         // Pass ss->eval to qsearch() and avoid an evaluate call
         if (!tte || tte->static_value() == VALUE_NONE)
-            TT.store(posKey, MOVE_NONE, VALUE_TYPE_BOTH, Depth(-128), Depth(-128), -VALUE_INFINITE, VALUE_INFINITE, ss->eval, ei.kingDanger[pos.side_to_move()]);
+            TT.store(posKey, MOVE_NONE, VALUE_TYPE_NONE, Depth(-128), Depth(-128), -VALUE_INFINITE, VALUE_INFINITE, ss->eval, ei.kingDanger[pos.side_to_move()]);

         Value rbeta = beta - razor_margin(depth);
         Value v = qsearch<NonPV>&#40;pos, ss, rbeta-1, rbeta, Depth&#40;0&#41;, ply&#41;;

and now the original version wins with LOS=54:45. It agrees with slight slowdown, which is almost surely a pure coincidence. At least, storing both bounds is no more visibly worse.

In the meantime, I have done another SMRC version with a small change to IID condition. Patch against just previous post:

Code: Select all

diff -dur src-Asm6SmrcCh/search.cpp src-Asm7SmrcCh/search.cpp
--- src-Asm6SmrcCh/search.cpp   2010-08-11 23:15:26.000000000 +0200
+++ src-Asm7SmrcCh/search.cpp   2010-08-13 21:04:40.000000000 +0200
@@ -1238,10 +1238,10 @@
     }

     // Step 9. Internal iterative deepening
-    if (    depth >= IIDDepth[PvNode]
+    if (   depth >= IIDDepth[PvNode]
         && (   ttMove == MOVE_NONE
-            || !(   tte
-                 && tte->depth() >= depth - 4 * OnePly)))
+            || !tte
+            || tte->depth&#40;) < &#40;PvNode ? depth - 2 * OnePly &#58; depth - 4 * OnePly&#41;))
     &#123;
         Depth d = &#40;PvNode ? depth - 2 * OnePly &#58; depth - 4 * OnePly&#41;;

This version played 3 matches, opponents were the original and 2 most successfull previous SMRC versions. Now the newest patch has bayeselo 25+-9, where original has 0+-4 (computed from concatenated .pgn files from matches of 27 least bad versions), and in terms of LOS, only one version has more than 18% chance, that is 23% of the third most successfull previous SMRC version (that played only 1000 games). By the way, original has LOS=3:96 vs the new champion.