Moderator: Ras
Hi Eelco,Eelco de Groot wrote:Code: Select all
if (i < MultiPV) { if (Iteration <= 45) { Value gamma = Value(0x100); if (Iteration >= 6) gamma = alpha; value = -search(pos, ss, -gamma, newDepth + 1, 1, true, 0); if (value > gamma && alpha <= gamma) alpha = Value((gamma + value) >> 1); else alpha = Value((alpha + value - 0x300) >> 1); }
Cheap thing to try and easy way to prove I'm wrongI could try to test speed nodes / sec with 1 and 2 threads (I have an Intel Core 2 Duo) so to see if scaling is better when disabling TT in qsearch.
What do you think?
Yes, you are correct. Tracking down the bug is extremely hard because we've not touched SMP-code anyway. But chess engines are nasty bastards. Changing code in one place can activate hidden bug in some other place.One thing that make me think more of a bug as a possible reason is that tests report didn't talk about speed regressions.
Code: Select all
Stockfish 1.2 JA
Single CPU: elapsed time 1' 45"
Double CPU: elapsed time 1' 1"
Stockfish 1.3 JA
Single CPU: elapsed time 1' 52" (6% slower then 1.2)
Double CPU: elapsed time 1' 4" (5% slower then 1.2)
Hello Marco,mcostalba wrote:Hi Eelco,Eelco de Groot wrote:Code: Select all
if (i < MultiPV) { if (Iteration <= 45) { Value gamma = Value(0x100); if (Iteration >= 6) gamma = alpha; value = -search(pos, ss, -gamma, newDepth + 1, 1, true, 0); if (value > gamma && alpha <= gamma) alpha = Value((gamma + value) >> 1); else alpha = Value((alpha + value - 0x300) >> 1); }
I think I cannot understund the above code. Care to explain me ?
Thanks
Marco
, it is just rather crude, a structure that allows me to try a few starting values for the aspiration window alpha, in case the alpha already provided by Joona's aspiration initialization is a bit too high, which would be a problem, or too low which does not really matter. 
Then again, Stockfish is very fast so clearly Joona's aspiration windows contributes to speed! Also you can't use that - Value Infite for alpha for a nullwindow search so for this Joona's code provided an excellent starting point, a real aspiration alpha, to finally try this first part of the experiment, with a minimum of added overhead! The aspiration alpha in Multi-PV was too high for the rest of the moves. Eelco de Groot wrote: That is basically it, well at least that is how I interpret my own code
Code: Select all
if (Iteration <= 45)
{
Value gamma = Value(0x100);
if (Iteration >= 6) gamma = alpha;
value = -search(pos, ss, -gamma, newDepth + 1, 1, true, 0);
if (value > gamma && alpha <= gamma) alpha = Value((gamma + value) >> 1);
else alpha = Value((alpha + value - 0x300) >> 1);
} Code: Select all
alpha = Value((alpha + value - 0x300) >> 1);Code: Select all
alpha = Value((alpha + alpha -0x20 - 0x300) >> 1) = Value(alpha - 0x170)Hello Marco, yes that is correct, but it is not the only reason at least I think the alpha adjustment may not be the largest advantage you could get from doing this. Maybe I'm wrong, a good alpha is very important to search all the other moves with.mcostalba wrote:Eelco de Groot wrote: That is basically it, well at least that is how I interpret my own codeCode: Select all
if (Iteration <= 45) { Value gamma = Value(0x100); if (Iteration >= 6) gamma = alpha; value = -search(pos, ss, -gamma, newDepth + 1, 1, true, 0); if (value > gamma && alpha <= gamma) alpha = Value((gamma + value) >> 1); else alpha = Value((alpha + value - 0x300) >> 1); }
I interpret in this way, please correct me if I am wrong:
If Iteration <=45 (aka always) you try, before the aspiration window search, a nullwindow search and use the returned value to adjust alpha, i.e. the aspiration window width.
Sorry, here I think there is a misunderstanding but the layout of the code is not very clear, the indents are messed up in places and you don't see the rest of root_search properly aligned. But if I have not messed up, we are still in theNow, suppose we are well beyond iteration 6, so that alpha value is quite centered on the real value (as is in the common case that is what is really important).
You do a null window search with gamma == alpha and return a fail low score (again the common case) as example 0x20 below alpha.
Code: Select all
if (i < MultiPV)As far as I can see this is all a correct interpretation of my interpretation of what is correct
In this case you adjust alpha by
That is, in our exampleCode: Select all
alpha = Value((alpha + value - 0x300) >> 1);
Now, with this very low alpha you try the aspiration window. If aspiration window confirms more or less the value returned by nullwindow (common case) you will have an almost sure fail high at rootCode: Select all
alpha = Value((alpha + alpha -0x20 - 0x300) >> 1) = Value(alpha - 0x170)
Is this intended? I have misread your code?
You want at all times avoid setting your alpha too high for the best move, so high that even your best move fails low against it. But here you are still only searching the best move, or best moves in Multi-PV mode! The value you get from the final search-pv
Code: Select all
value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
// If the value has dropped a lot compared to the last iteration,
Code: Select all
LateMoveDepth < MaxDepth
Also what I had not appreciated before is that OnePly is really Depth(2) so if I increment NewDepth with one I am only adding a half ply. Nothing fatal but it meant what I thought were thirty ply searches that somehow were possible in this code, in reality were only fifteen plies deep Some of those twenty+ testversions were needed to finally figure that out, and I had to bend the UCI procol to get at the information I wanted; Shredder GUI now reports tablebase hits (TB) but in reality that is newDepth which is reported 
But the Shredder GUI only accepts a limited set of output strings so I had to use this.. I am very happy actually that 19...c6 is now negative already after 2 minutes 50 seconds, but it is not yet enough to find 19. Nd5! Code: Select all
for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
{
int k;
std::cout << "info multipv " << j + 1
<< " score " << value_to_string(value)
<< " depth " << LateMoveDepth
<< " time " << current_search_time()
<< " nodes " << nodes_minimum
<< " nps " << newDepth * 1000
<< " tbhits " << (Iteration - 2) * OnePly + ext + InitialDepth
<< " pv ";
std::cout << move << " ";
std::cout << std::endl;
}
Unfortunately, Vas' comment is wrong. It is easy to drive up the time spent on any single move. But that does not necessarily make the program play better. If you have N nodes in your cluster, and you search one root move on each cluster node, the effort for each move will be about the same for normal positions. Some will be searched deeper since the moves are losing or easily winning. Others will not.Eelco de Groot wrote:Thanks for Stockfish 1.3.1 Joona!zamar wrote:This looks like my mistake. The bug went in with new aspiration window search code. This happens when you concentrate only improving program's strength and forget to worry about other important features
Marco, I strongly suspect that you end up here sooner or later. Fix is oneliner:
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -897,7 +897,7 @@ namespace {
if (i < MultiPV)
{
- value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
+ value = -search_pv(pos, ss, -beta, MultiPV == 1 ? -alpha : VALUE_INFINITE, newDepth, 1, 0);
// If the value has dropped a lot compared to the last iteration,
// set the boolean variable Problem to true. This variable is used
// for time managment: When Problem is true, we try to complete the
It is quite by accident, but the experimental version of Stockfish's search.cpp I am using at the moment already repaired this Multi_PV window problem in a way, although I'm not sure the windows it uses are correct always and had not tested the Multi PV option yet. It is just an experiment. It does something of a second pass over your aspiration windows Joona. When I programmed it it seemed more or less clear to me but when I look at it again I have great difficulty understanding what it is all about
Also it uses now search_pv where most programs use the nullwindow search, and vice versa
Code: Select all
const Value NullMoveMargin = Value(0x350);[caveat]Code: Select all
// root_search() is the function which searches the root node. It is // similar to search_pv except that it uses a different move ordering // scheme (perhaps we should try to use this at internal PV nodes, too?) // and prints some information to the standard output. Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) { Value oldAlpha = alpha; Value value, oldvalue, PV_value; Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move()); // Loop through all the moves in the root move list for (int i = 0; i < rml.move_count() && !AbortSearch; i++) { if (alpha >= beta) { // We failed high, invalidate and skip next moves, leave node-counters // and beta-counters as they are and quickly return, we will try to do // a research at the next iteration with a bigger aspiration window. rml.set_move_score(i, -VALUE_INFINITE); continue; } int64_t nodes, nodes_before, nodes_after, nodes_minimum ; Move move; StateInfo st; Depth ext, newDepth, LateMoveDepth; RootMoveNumber = i + 1; FailHigh = false; // Remember the node count before the move is searched. The node counts // are used to sort the root moves at the next iteration. nodes = nodes_searched(); // Reset beta cut-off counters BetaCounter.clear(); // Pick the next root move, and print the move and the move number to // the standard output. move = ss[0].currentMove = rml.get_move(i); if (current_search_time() >= 1000) std::cout << "info currmove " << move << " currmovenumber " << i + 1 << std::endl; // Decide search depth for this move bool dangerous; ext = extension(pos, move, true, pos.move_is_capture(move), pos.move_is_check(move), false, false, &dangerous); newDepth = (Iteration - 2) * OnePly + ext + InitialDepth; // Make the move, and search it pos.do_move(move, st, dcCandidates); if (i < MultiPV) { if (Iteration <= 45) { Value gamma = Value(0x100); if (Iteration >= 6) gamma = alpha; value = -search(pos, ss, -gamma, newDepth + 1, 1, true, 0); if (value > gamma && alpha <= gamma) alpha = Value((gamma + value) >> 1); else alpha = Value((alpha + value - 0x300) >> 1); } value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); // If the value has dropped a lot compared to the last iteration, // set the boolean variable Problem to true. This variable is used // for time management: When Problem is true, we try to complete the // current iteration before playing a move. Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin); if (Problem && StopOnPonderhit) StopOnPonderhit = false; } else { value = -search(pos, ss, -alpha, newDepth, 1, true, 0); oldvalue = value; value = -search(pos, ss, -alpha, newDepth + 2, 1, true, 0); if (value > alpha) { // Fail high! Set the boolean variable FailHigh to true, and // re-search the move with a big window. The variable FailHigh is // used for time management: We try to avoid aborting the search // prematurely during a fail high research. FailHigh = true; value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); value = -search(pos, ss, -alpha, newDepth + 3, 1, true, 0); } else { nodes_minimum = 0; PV_value = -search_pv(pos, ss, -beta, -alpha, newDepth - 1, 1, 0); LateMoveDepth = newDepth; if (value - oldvalue >= 50 || PV_value > oldvalue) { value = -search(pos, ss, -alpha, newDepth + 3, 1, true, 0); PV_value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); if (value - oldvalue >= 75 || value > alpha || PV_value > alpha) { FailHigh = true; oldvalue = value; value = -search(pos, ss, -alpha, newDepth + 5, 1, true, 0); } } else while (nodes_minimum < 10000 && PV_value < alpha && LateMoveDepth < MaxDepth) { nodes_before = nodes_searched(); PV_value = -search_pv(pos, ss, - VALUE_INFINITE, -alpha, LateMoveDepth, 1, 0); nodes_after = nodes_searched(); LateMoveDepth = LateMoveDepth + 1; nodes_minimum = nodes_after - nodes_before; if (PV_value > value) value = PV_value; } } } pos.undo_move(move); // Finished searching the move.
It is possible though that all this does not work with more threads Joona, I have not given it any thought and can't test it yet here. Sorry!
[/caveat]
Important Vas quote in this respect - using nodes_searched() -, they have a list in the Rybka forum but this one is not in it:
Regards, Eelco
Quote from GCP:Depth is a poor measure of search quality, time is much better.
Now, in case of chess, if you split the set of moves equally between CPUs, each move is guaranteed to get pretty much the same effort spent to it. This might result in different depths, but who cares if the effort spent is equal? So, in the clustering-root-unsynchronised case, it seems totally obvious to me that you would just pick the best scoring move, ignoring depth totally.
Vas
I will try to find a test position that shows just how bad an infinite root window can be. Harry Nelson first found the position. the problem with the test position he found is that if you search with an infinite window, there are a nearly infinite number of mates you have to search. But the best play does not lead to a forced mate, just the win of a pawn. If you use the correct aspiration window, all the branches that lead to mates quickly get pruned away and you find the win of a pawn quickly. If you use an infinite aspiration window, you get hung up in all the mates that now don't get pruned by the aspiration window, and you run out of time trying to find the way to win the pawn.Eelco de Groot wrote:Hello Marco,mcostalba wrote:Hi Eelco,Eelco de Groot wrote:Code: Select all
if (i < MultiPV) { if (Iteration <= 45) { Value gamma = Value(0x100); if (Iteration >= 6) gamma = alpha; value = -search(pos, ss, -gamma, newDepth + 1, 1, true, 0); if (value > gamma && alpha <= gamma) alpha = Value((gamma + value) >> 1); else alpha = Value((alpha + value - 0x300) >> 1); }
I think I cannot understund the above code. Care to explain me ?
Thanks
Marco
I don't think there is something mysterious going on here, this was the easy part I thought
Alpha too low does not really matter all that much, why do I say that:
♠ Fruit searches with - Value Infite for alpha in the Root all the time and it is not really much slower than a finite but still relatively large window what I have tried.
♠
♠
♠ Also, second reason, I did not really study Joona's code but figured it would not hurt to put in some checks on the aspiration windows. The nullwindow search is new here and can be used for this purpose but that is not the main reason for it: the main thought is, it is usually a lot faster doing a nullwindow search than doing a search_pv so you can search deeper, as long as your alpha is not too high.
♠ There are some drawbacks I suppose to doing this, but I don't have a clear picture about those. Otherwise -if there were no drawbacks at all- I think even a repeated nullwindow search here with "aspiration nullwindows" in case your alpha differs too much from value, would probably still allow you to search deeper than search_pv. As example of drawbacks, Null move (in the nullwindow search) could go wrong in case of Zugzwang but I suspect that is not the whole story.
♠ But even in this limited way you should at least be able to prime all the sidepaths of the PV, get a TTmove and search some of the sidepaths at least a bit deeper already - using NewDepth + 1 in the null window search, so with one ply deeper than the following standard search_pv. This NewDepth + 1 is actually conservative too but searching deeper has its drawbacks too, for instance the difference in NewDepth + x and NewDepth should not become too large.
♠ That I can adjust the alpha a bit this way with the returned result of the nullwindow is really not all that important, unless of course there would be a bug which in this case actually was true
♠ 45 is just a large number, using a constant alpha = 0x100 for the first 6 iterations is done just because Joona's aspirations only start at plydepths > 6.
♠ In case of a Fail Low in the first nullwindow search, alpha was obviously too high and should be lowered. Lowering to weighted average minus three pawns /2 : Value((alpha + value - 0x300) >> 1); appears to be still functional in the Multi-PV search that was actually broken, at least in a position like Ernest provided, I get at higher depths:
[d]rnbqkbn1/pppppppp/8/8/8/r7/P1PPPPPP/R1BQKBNR w KQq -
Engine: Ancalagon 1.3 WS150 Build 21 (256 MB)
by T. Romstad, M.Costalba, J. Kiiski, E. de Groot
20 39:22 +0.60 1.Bxa3 e5 2.Bb2 d6 3.e3 Qh4 4.Be2 Qa4
5.Nf3 Bf5 6.Bd3 Bxd3 7.cxd3 Qxd1+
8.Rxd1 Nc6 9.Rb1 Nf6 10.Ke2 Be7
11.Bc3 O-O-O 12.Rhc1 (1.158.136.286) 490
20 39:22 -1.27 1.Bb2 Ra4 (1.158.136.286) 490
20 39:22 -3.15 1.Nf3 Ra5 (1.158.136.286) 490
20 39:22 -4.90 1.e3 Ra5 2.Nf3 Nc6 3.d4 Nf6 4.Be2 e5
5.O-O exd4 6.exd4 Ne4 7.Bd3 d5 8.Qe2 Bf5
9.c4 Nb4 10.Bxe4 Bxe4 (1.158.136.286) 490
20 39:22 -4.96 1.d4 Ra5 2.e3 c5 3.Nf3 Nf6 4.Bd3 d5
5.c4 Qc7 6.Bd2 cxd4 7.Bxa5 Qxa5+
8.Qd2 Qxd2+ 9.Kxd2 dxe3+ 10.fxe3 dxc4
11.Bxc4 Nc6 12.Rad1 Ne4+ 13.Kc2 (1.158.136.286) 490
20 39:22 -5.13 1.f4 (1.158.136.286) 490
To be a bit more on the safe side I think you could subtract something like 0x300 + i * 0x50, where i is the number of Multi-PV lines, instead of just three pawns (3 * 0x100) but I don't know if it matters much. Not dividing 0x300 by two is probably the easiest way to be a bit safer in the existing code. In case the moves go quickly towards a lost position or mate, possibly then you can get bad results with my version in Multi_PV mode.
That is basically it, well at least that is how I interpret my own code
Eelco
