From d96c1c32a2fa109e7cc6cd07f6029cd13977121e Mon Sep 17 00:00:00 2001 From: Stefano Cardanobile Date: Wed, 4 Jul 2018 21:54:38 +0200 Subject: [PATCH] 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) --- src/search.cpp | 28 ++++++++++++++++++++-------- 1 file changed, 20 insertions(+), 8 deletions(-) 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 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 -- 2.39.2