Root node search in Stockfish

[Onno Garms]

....but this absolutely should not explain a -20 ELO regression !!!

Remember that I have much fewer games in my test than you. While -20 Elo is practically a certainty in your tests, for me it is "only" a probability of 95%.

Test with the patch but also with root node reordering at every depth is still running, currently looks OK (i.e. approx same results as without the patch). If this stands, this would mean that the MovePicker heuristic is better than a depth 1 search. (With the incrementation of alpha at depth 1, we don't really sort by depth 1, but keep some of the MovePicker ordering.)

[Onno Garms]

Tests finished now with the following results:

Code: Select all

     resort  alpha-update  Elo
1.0   yes       yes          0
1.0c  no        yes         +3
1.0d  no        no         -17
1.0e  yes       no           0

alpha-update "yes" means original Stockfish. alpha-update "no" means no alpha update at DEPTH_ONE i.e. above patch (being equivalent to Marcos simpler modification).

resort "yes"means that moves get reordered at every iteration by the MovePicker. resort "no" means that MovePicker is used only once, after Rml.init.

+3 is not significant at 1120 games, but +3 vs. -17 is. My interpretation is that MovePicker provides a better move ordering then DEPTH_ONE. When we resort, the move ordering by DEPTH_ONE is discarded anyway. When we increment alpha at root node, some of the MovePicker ordering might survive.

Consequence: Special handling of DEPTH_ONE is not needed at all for move ordering. If it turns out that the it is not needed for other purposes (easy move detection?) just remove it entirely without replacement.

With DEPTH_ONE removed, the MovePicker must be used at least once at the beginning for move ordering. Tests with more games must show which option is the best:
- use MovePicker only once at the beginning (as in 1.0c). If we have to keep DEPTH_ONE specials, beginning would mean after DEPTH_ONE.
- use MovePicker for all moves without PV scores (current Stockfish)
- use MovePicker for all moves, even if there is a PV score. Keep the best move as the first one / TT move (idea by Marco).

Patch for 1.0c is this one:

Code: Select all

--- src/search.cpp	21 May 2011 08:23:53 -0000	1.11
+++ src/search.cpp	5 Jun 2011 20:22:04 -0000	1.11.6.2
@@ -507,6 +507,27 @@
 
     // Moves to search are verified and copied
     Rml.init(pos, searchMoves);
+    {
+      Move move;
+      Value score = VALUE_ZERO;
+      TTEntry* tte = TT.probe(pos.get_key());
+      MovePicker mp (pos, tte ? tte->move() : MOVE_NONE, PLY_MAX*ONE_PLY, H, ss, -VALUE_INFINITE);
+
+      // Score root moves using standard ordering used in main search, the moves
+      // are scored according to the order in which they are returned by MovePicker.
+      // This is the second order score that is used to compare the moves when
+      // the first orders pv_score of both moves are equal.
+      while ((move = mp.get_next_move()) != MOVE_NONE)
+        for (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm)
+          if (rm->pv[0] == move)
+          {
+            rm->non_pv_score = score--;
+            break;
+          }
+      Rml.sort();
+      for (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm)
+        rm->non_pv_score = VALUE_ZERO;
+    }
 
     // Handle special case of searching on a mate/stalemate position
     if (Rml.size() == 0)
@@ -2059,22 +2080,6 @@
   MovePickerExt<false, true>&#58;&#58;MovePickerExt&#40;const Position& p, Move ttm, Depth d,
                                             const History& h, SearchStack* ss, Value b&#41;
                             &#58; MovePicker&#40;p, ttm, d, h, ss, b&#41;, firstCall&#40;true&#41; &#123;
-    Move move;
-    Value score = VALUE_ZERO;
-
-    // Score root moves using standard ordering used in main search, the moves
-    // are scored according to the order in which they are returned by MovePicker.
-    // This is the second order score that is used to compare the moves when
-    // the first orders pv_score of both moves are equal.
-    while (&#40;move = MovePicker&#58;&#58;get_next_move&#40;)) != MOVE_NONE&#41;
-        for &#40;rm = Rml.begin&#40;); rm != Rml.end&#40;); ++rm&#41;
-            if &#40;rm->pv&#91;0&#93; == move&#41;
-            &#123;
-                rm->non_pv_score = score--;
-                break;
-            &#125;
-
-    Rml.sort&#40;);
     rm = Rml.begin&#40;);
   &#125;

[mcostalba]

Tests finished now with the following results:

Thanks Onno ! As you know we are testing these ideas one by one and it will take some time to get it done, but I will come back with test results when done.

The full scoring at depth one seems needed by easy move detection logic, we could use it just for that and not for ordering....

[Onno Garms]

With DEPTH_ONE removed, the MovePicker must be used at least once at the beginning for move ordering. Tests with more games must show which option is the best:
- use MovePicker only once at the beginning (as in 1.0c). If we have to keep DEPTH_ONE specials, beginning would mean after DEPTH_ONE.
- use MovePicker for all moves without PV scores (current Stockfish)
- use MovePicker for all moves, even if there is a PV score. Keep the best move as the first one / TT move (idea by Marco).

Marco, did you get any results on this in the meantime?

I wasn't idle over the last weeks either. But the things I tried did not (yet?) work out, so I won't post them.

[mcostalba]

Marco, did you get any results on this in the meantime?

Yes I have tested all this variations, but at the end it seems the current one is the stronger, for instance:

Order root moves only once (Onno suggestion)
After 3380 games 450 - 537 - 2393 ELO -8 (+- 6.5)

And mine was bad too.