Root node search in Stockfish

[Onno Garms]

I studied a bit the root node search in Stockfish. Unlike Onno, it has stepwise widening of the search window. Given that this is useful, it does not make sense to try Onno's root node search in Stockfish (as I suggested here: http://talkchess.com/forum/viewtopic.php?t=38404).

However, comparing the two root node searches, I found some aspects where Onno's root node search might be better (or in other words, Stockfish's root node search looks strange).


1. Stockfish re-orders the moves at root node by the MovePicker at every depth. This would only make sense if MovePicker is a better heuristic than the order we already have. Note that the order we already have was initialized by a depth 1 search (which is btw wasted if we re-order at every depth), and then modified by moving PV moves to the head. My intuition is that the latter move ordering is the better one. I did a test where I removed the reordering by MovePicker at root node from Stockfish. Differences in playing strength were not measurable, but at least the results indicate that I am not completely wrong. (Without re-ordering did 3 Elo better, at an error margin of 18 Elo.)


2. Stockfish does not do windowing in MultiPV mode. Onno does. One window for all PV moves is likely to be a bad idea; not windowing at all is the simplest solution. Onno chooses separate windows for each move. I did not compare the approaches empirically and am not planning to do so (as I have little interest in MultiPV).


3. Stockfish's alpha modification in MultiPV mode looks like a hack, and it most likely is.

Code: Select all

while (move=get_next_move())
{
          // Aspiration window is disabled in multi-pv case
          if (Root && MultiPV > 1)
              alpha = -VALUE_INFINITE;

...

          // Update alpha. In multi-pv we don't use aspiration window, so
          // set alpha equal to minimum score among the PV lines.
          if (MultiPV > 1)
              alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
          else if (value > alpha)
              alpha = value;
}

Looks like if you set alpha in the line that has a FIXME comment, and before doing anything with it, at the beginning of the next iteration set back to -VALUE_INFINITE ???

The correct way to handle this should be:

1. As we don't have windowing at root node, alpha=-VALUE_INFINITE comes in and is used for the first move anyway.

2. Instead of the FIXME line set alpha in the following way for any value of MultiPV:

Code: Select all

if (moveCount >= MultiPV)
    alpha = Rml[MultiPV-1].pv_score;

3. Do not set alpha back to -VALUE_INFINITE

Above changes are not tested.

[Onno Garms]

PS: The third point is just about writing understandable code. I think that Stockfish's code does the same in a complicated way.

[Onno Garms]

PS: The third point is just about writing understandable code. I think that Stockfish's code does the same in a complicated way.

Not quite. When MultiPv>1, the original code correctly leaves alpha at -VALUE_INFINITE for all moves at depth 1, while the modified code increases it incorrectly for late moves.

When MultiPv==1, both versions increase alpha at depth 1, which looks strange.

Started a test of the modification with a localMultiPv to overcome these problems.

[mcostalba]

1. Stockfish re-orders the moves at root node by the MovePicker at every depth. This would only make sense if MovePicker is a better heuristic than the order we already have. Note that the order we already have was initialized by a depth 1 search (which is btw wasted if we re-order at every depth), and then modified by moving PV moves to the head. My intuition is that the latter move ordering is the better one. I did a test where I removed the reordering by MovePicker at root node from Stockfish. Differences in playing strength were not measurable, but at least the results indicate that I am not completely wrong. (Without re-ordering did 3 Elo better, at an error margin of 18 Elo.)

I think your observation makes a lot of sense, I will remove the MovePicker ordering as you did and test it.

2. Stockfish does not do windowing in MultiPV mode. Onno does. One window for all PV moves is likely to be a bad idea; not windowing at all is the simplest solution. Onno chooses separate windows for each move. I did not compare the approaches empirically and am not planning to do so (as I have little interest in MultiPV).

Yes, MultiPV ia a bit hackish regarding aspiration window...

[mcostalba]

Started a test of the modification with a localMultiPv to overcome these problems.

I'd suggest the following rule to update alpha (it works in both single and multi PV)

Code: Select all

// Update alpha. In multi-pv change alpha only after searching all
// the PV lines and set it to the minimum score among PV lines. Note
// that at depth ONE_PLY we want to score all the moves and so do not
// change alpha.
if (depth > ONE_PLY && moveCount >= MultiPV)
    alpha = Max(alpha, Rml[MultiPV - 1].score);

[Onno Garms]

I'd suggest the following rule to update alpha (it works in both single and multi PV)

Code: Select all

if (depth > ONE_PLY && moveCount >= MultiPV)
    alpha = Max(alpha, Rml[MultiPV - 1].score);

Yes, the Max is important. I already noted that error in my suggestion a couple of days ago.

Your suggestion makes less code modifications but seems to be logically equivalent to what I have just completed to test:

Code: Select all

--- src/search.cpp	21 May 2011 08:23:53 -0000	1.11
+++ src/search.cpp	14 Jun 2011 19:33:33 -0000
@@ -681,10 +681,11 @@
     ValueType vt;
     Value bestValue, value, oldAlpha;
     Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
-    bool isPvMove, inCheck, singularExtensionNode, givesCheck, captureOrPromotion, dangerous;
+    bool inCheck, singularExtensionNode, givesCheck, captureOrPromotion, dangerous;
     int moveCount = 0, playedMoveCount = 0;
     int threadID = pos.thread();
     SplitPoint* sp = NULL;
+    int localMultiPv;
 
     refinedValue = bestValue = value = -VALUE_INFINITE;
     oldAlpha = alpha;
@@ -961,7 +962,13 @@
       }
 
       // At Root and at first iteration do a PV search on all the moves to score root moves
-      isPvMove = &#40;PvNode && moveCount <= &#40;Root ? depth <= ONE_PLY ? 1000 &#58; MultiPV &#58; 1&#41;);
+      if &#40;PvNode&#41;
+      &#123;
+          if &#40;Root&#41;
+              localMultiPv = &#40;depth <= ONE_PLY ? 1000 &#58; MultiPV&#41;;
+          else
+              localMultiPv = 1;
+      &#125;
       givesCheck = pos.move_gives_check&#40;move, ci&#41;;
       captureOrPromotion = pos.move_is_capture_or_promotion&#40;move&#41;;
 
@@ -1057,12 +1064,8 @@
 
       // Step extra. pv search &#40;only in PV nodes&#41;
       // The first move in list is the expected PV
-      if &#40;isPvMove&#41;
+      if &#40;PvNode && moveCount <= localMultiPv&#41;
       &#123;
-          // Aspiration window is disabled in multi-pv case
-          if &#40;Root && MultiPV > 1&#41;
-              alpha = -VALUE_INFINITE;
-
           value = -search<PV>&#40;pos, ss+1, -beta, -alpha, newDepth&#41;;
       &#125;
       else
@@ -1160,7 +1163,7 @@
           mp.rm->nodes += pos.nodes_searched&#40;) - nodes;
 
           // PV move or new best move ?
-          if &#40;isPvMove || value > alpha&#41;
+          if &#40;moveCount <= localMultiPv || value > alpha&#41;
           &#123;
               // Update PV
               ss->bestMove = move;
@@ -1170,17 +1173,14 @@
               // We record how often the best move has been changed in each
               // iteration. This information is used for time management&#58; When
               // the best move changes frequently, we allocate some more time.
-              if (!isPvMove && MultiPV == 1&#41;
+              if &#40;localMultiPv == 1 && moveCount > 1&#41;
                   Rml.bestMoveChanges++;
 
               Rml.sort_multipv&#40;moveCount&#41;;
 
-              // Update alpha. In multi-pv we don't use aspiration window, so
-              // set alpha equal to minimum score among the PV lines.
-              if &#40;MultiPV > 1&#41;
-                  alpha = Rml&#91;Min&#40;moveCount, MultiPV&#41; - 1&#93;.pv_score; // FIXME why moveCount?
-              else if &#40;value > alpha&#41;
-                  alpha = value;
+              // Update alpha.
+              if &#40;moveCount >= localMultiPv && Rml&#91;localMultiPv-1&#93;.pv_score > alpha&#41;
+                  alpha = Rml&#91;localMultiPv-1&#93;.pv_score;
           &#125;
           else
               mp.rm->pv_score = -VALUE_INFINITE;

Edit: Patch is over sf-2-1-1-og-1-0

I tested a version with above patch and root move reordering removed. Unfortunately with above patch, results were significantly worse (l.o.s. 5%, -20 Elo) than with removal of move reordering alone. Now I am testing only above patch, root moves reordered at every depth.

Reasonning what's going on:
- Bug in above patch. (Can you spot one?)
- Bad luck with statistics
- For some strange reason alpha-beta-pruning (in MovePicker order) at depth 1 (which is removed by above patch) gives better move ordering than normal search at depth 1. This would be highly surprising, and I'm currently running above patch with move reordering to exclude this possibility.
- Normal search at depth 1 might activate easy move detection more often than the presumed buggy alpha-beta pruning at depth 1. Maybe easy move detection has a problem that was hidden by the root-node-depth-1-"bug"?
- Any other interference with something?

[mcostalba]

I tested a version with above patch and root move reordering removed. Unfortunately with above patch, results were significantly worse (l.o.s. 5%, -20 Elo) than with removal of move reordering alone. Now I am testing only above patch, root moves reordered at every depth.

When localMultiPv == 1 the above patch should behave in the same way of current standard one, so I suggest to functional test the above patch with:

./stockfish bench

and to verify searched nodes are the same with and without the patch applied.

[Onno Garms]

When localMultiPv == 1 the above patch should behave in the same way of current standard one, so I suggest to functional test the above patch with: ./stockfish bench

But localMultiPv is never 1 at depth 1.

[Onno Garms]

Just did a test. Stockfish 2.1.1 has 6.487.630 nodes in bench.

The following all have 7.355.539 nodes:
- my patch
- your patch
- your patch augmented by the removal of the no longer needed "if (Root && MultiPV > 1) alpha = -VALUE_INFINITE;"

The difference over Stockfish 2.1.1 is that they disable incrementation of alpha at depth 1. Logically, we should not increment, but for some strange reason my patch did worse than the original.

[mcostalba]

The difference over Stockfish 2.1.1 is that they disable incrementation of alpha at depth 1. Logically, we should not increment, but for some strange reason my patch did worse than the original.

You are right ! This is very strange indeed !

The only thing that comes to my mind is different TT behaviour: with a raised alpha you can have TT hits on childern nodes, while you don't have with infinite window....but this absolutely should not explain a -20 ELO regression !!!

I will finish current testing later today, then I will start to test this patch....