From: Stefano Cardanobile <stefano.cardanobile@gmail.com>
Date: Wed, 4 Jul 2018 19:54:38 +0000 (+0200)
Subject: Introduce voting system for best move selection
X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=d96c1c32a2fa109e7cc6cd07f6029cd13977121e;hp=571f54b176b5c30aaac35bc7bbd255c79cdcb926

Introduce voting system for best move selection

Introduce voting system for best move selction in multi-threads mode.
Joint work with Stefan Geschwentner, based on ideas introduced by
Michael Stembera.

Moves are upvoted by every thread using the margin to the minimum score
across threads and the completed depth.

First thread voting for the winner move is selected as best thread.

Passed STC, LTC. A further LTC test with only 4 threads failed with positive
score. A LTC with 31 threads was stopped with LLR 0.77 after 25k games to
avoid use of excessive resources (equivalent to 1.5M STC games).

Similar ideas were proposed by Michael Stembera 2 years ago #507, #508.
This implementation seems simpler and more understandable, the results
slightly more promising.

Further possible work:

1) Tweak of the formula using for assigning votes.
2) Use a different baseline for the score dependent part: maximum score
or winning probability could make more sense.
3) Assign votes in `Thread::Search` as iterations are completed and use
voting results to stop search.
4) Select best thread as the threads voting for best move with the highest
completed depth or, alternatively, vote on PV moves.

Link to SPRT tests

[stopped LTC, 31 threads 20+0.02](http://tests.stockfishchess.org/tests/view/5b61dc090ebc5902bdb95192)
LLR: 0.77 (-2.94,2.94) [0.00,5.00]
Total: 25602 W: 3977 L: 3850 D: 17775
Elo: 1.70 [-0.68,4.07] (95%)

[passed LTC, 8 threads 20+0.02](http://tests.stockfishchess.org/tests/view/5b5df5180ebc5902bdb9162d)
LLR: 2.96 (-2.94,2.94) [0.00,5.00]
Total: 44478 W: 7602 L: 7300 D: 29576
Elo: 1.92 [-0.29,3.94] (95%)

[failed LTC, 4 threads 20+0.02](http://tests.stockfishchess.org/tests/view/5b5f39ef0ebc5902bdb92792)
LLR: -2.94 (-2.94,2.94) [0.00,5.00]
Total: 29922 W: 5286 L: 5285 D: 19351
Elo: 0.48 [-1.98,3.10] (95%)

[passed STC, 4 threads 5+0.05](http://tests.stockfishchess.org/tests/view/5b5dbf0f0ebc5902bdb9131c)
LLR: 2.97 (-2.94,2.94) [0.00,5.00]
Total: 9108 W: 2033 L: 1858 D: 5217
Elo: 6.11 [1.26,10.89] (95%)

No functional change (in simple threat mode)
---

diff --git a/src/search.cpp b/src/search.cpp
index e36c6959..990c4123 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -246,18 +246,30 @@ void MainThread::search() {
       && !Skill(Options["Skill Level"]).enabled()
       &&  rootMoves[0].pv[0] != MOVE_NONE)
   {
-      for (Thread* th : Threads)
-      {
-          Depth depthDiff = th->completedDepth - bestThread->completedDepth;
-          Value scoreDiff = th->rootMoves[0].score - bestThread->rootMoves[0].score;
+      std::map<Move, int> votes;
+      Value minScore = this->rootMoves[0].score;
 
-          // Select the thread with the best score, always if it is a mate
-          if (    scoreDiff > 0
-              && (depthDiff >= 0 || th->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY))
-              bestThread = th;
+      // Find out minimum score and reset votes for moves which can be voted
+      for (Thread* th: Threads){
+          minScore = std::min(minScore, th->rootMoves[0].score);
+          votes[th->rootMoves[0].pv[0]] = 0;
+      }
+
+      // Vote according to score and depth
+      for (Thread* th : Threads)
+          votes[th->rootMoves[0].pv[0]] +=  int(th->rootMoves[0].score - minScore)  + int(th->completedDepth);
+
+      // Select best thread
+      int bestVote = votes[this->rootMoves[0].pv[0]];
+      for (Thread* th : Threads){
+          if (votes[th->rootMoves[0].pv[0]] > bestVote){
+            bestVote = votes[th->rootMoves[0].pv[0]];
+            bestThread = th;
+          }
       }
   }
 
+
   previousScore = bestThread->rootMoves[0].score;
 
   // Send again PV info if we have a new best thread