Another patch. Stabilises, but hurts performance.
So, I have thought about it a little deeper. I see two main contributions to fail high/low instability. One of them is aspiration re-search, when we visit the same node with the same depth, but in the meantime we have added more data to transposition table. This generally produces better moves, so it is good.
The other contribution is from situations where search() returns values that significantly differ from what search_pv() would return. This can make search_pv() blind to some moves, only do discover them suddenly when aspiration window gets wide enough (if ever). This could make stockfish to waste time (or play suboptimal moves), so it is bad. But if we want to benefit from TT and aggressive non-pv pruning, we could not avoid this situations completely.
Is I understand, the original stockfish 1.7.1 assures that when search_pv() returns value between alpha and beta, it would be based on qsearch() value at the end of pv, and not just on some TT hit. But values outside (alpha, beta) interval could be just TT hits.
So I tried to make a patch that would assure that all return values of search_pv() are from pv end qsearch. It all happens in steps 14 and 15 of search_pv(). Dropping value<beta from pv search condition takes care of fail high situations, fail low situations need another code:
Code: Select all
// Step 14. Reduced search
// if the move fails high will be re-searched at full depth.
bool doFullDepthSearch = true;
if ( depth >= 3 * OnePly
&& !dangerous
&& !captureOrPromotion
&& !move_is_castle(move)
&& !move_is_killer(move, ss[ply]))
{
ss[ply].reduction = pv_reduction(depth, moveCount);
if (ss[ply].reduction)
{
// We are trying to improve bestValue, independently of alpha.
value = -search(pos, ss, -bestValue, newDepth-ss[ply].reduction, ply+1, true, threadID);
doFullDepthSearch = (value > bestValue);
}
}
// Step 15. Full depth search
if (doFullDepthSearch)
{
ss[ply].reduction = Depth(0);
value = -search(pos, ss, -bestValue, newDepth, ply+1, true, threadID);
// Step extra. pv search (only in PV nodes)
if (value > bestValue)
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
}
Basically, this code uses bestValue instead of alpha for decision whether to search at full depth, so it might introduce a big slowdown, especially in the positions like the tesposition at the start of this thread.
Anywyay, I was going to sleep, so I started 1000 games match (1 thread, 32MB hash, 30 seconds/game) between this patch and the short patch. The short patch was only 18 elo stronger, with likelihood of superiority 98 (against 1).
Maybe now I can finally try to implement something MTD-like again, using search_pv() with zero width aspiration window.