Root node search in Stockfish
Posted: Sun Jun 12, 2011 12:09 pm
I studied a bit the root node search in Stockfish. Unlike Onno, it has stepwise widening of the search window. Given that this is useful, it does not make sense to try Onno's root node search in Stockfish (as I suggested here: http://talkchess.com/forum/viewtopic.php?t=38404).
However, comparing the two root node searches, I found some aspects where Onno's root node search might be better (or in other words, Stockfish's root node search looks strange).
1. Stockfish re-orders the moves at root node by the MovePicker at every depth. This would only make sense if MovePicker is a better heuristic than the order we already have. Note that the order we already have was initialized by a depth 1 search (which is btw wasted if we re-order at every depth), and then modified by moving PV moves to the head. My intuition is that the latter move ordering is the better one. I did a test where I removed the reordering by MovePicker at root node from Stockfish. Differences in playing strength were not measurable, but at least the results indicate that I am not completely wrong. (Without re-ordering did 3 Elo better, at an error margin of 18 Elo.)
2. Stockfish does not do windowing in MultiPV mode. Onno does. One window for all PV moves is likely to be a bad idea; not windowing at all is the simplest solution. Onno chooses separate windows for each move. I did not compare the approaches empirically and am not planning to do so (as I have little interest in MultiPV).
3. Stockfish's alpha modification in MultiPV mode looks like a hack, and it most likely is.
Looks like if you set alpha in the line that has a FIXME comment, and before doing anything with it, at the beginning of the next iteration set back to -VALUE_INFINITE ???
The correct way to handle this should be:
1. As we don't have windowing at root node, alpha=-VALUE_INFINITE comes in and is used for the first move anyway.
2. Instead of the FIXME line set alpha in the following way for any value of MultiPV:
3. Do not set alpha back to -VALUE_INFINITE
Above changes are not tested.
However, comparing the two root node searches, I found some aspects where Onno's root node search might be better (or in other words, Stockfish's root node search looks strange).
1. Stockfish re-orders the moves at root node by the MovePicker at every depth. This would only make sense if MovePicker is a better heuristic than the order we already have. Note that the order we already have was initialized by a depth 1 search (which is btw wasted if we re-order at every depth), and then modified by moving PV moves to the head. My intuition is that the latter move ordering is the better one. I did a test where I removed the reordering by MovePicker at root node from Stockfish. Differences in playing strength were not measurable, but at least the results indicate that I am not completely wrong. (Without re-ordering did 3 Elo better, at an error margin of 18 Elo.)
2. Stockfish does not do windowing in MultiPV mode. Onno does. One window for all PV moves is likely to be a bad idea; not windowing at all is the simplest solution. Onno chooses separate windows for each move. I did not compare the approaches empirically and am not planning to do so (as I have little interest in MultiPV).
3. Stockfish's alpha modification in MultiPV mode looks like a hack, and it most likely is.
Code: Select all
while (move=get_next_move())
{
// Aspiration window is disabled in multi-pv case
if (Root && MultiPV > 1)
alpha = -VALUE_INFINITE;
...
// Update alpha. In multi-pv we don't use aspiration window, so
// set alpha equal to minimum score among the PV lines.
if (MultiPV > 1)
alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
else if (value > alpha)
alpha = value;
}
The correct way to handle this should be:
1. As we don't have windowing at root node, alpha=-VALUE_INFINITE comes in and is used for the first move anyway.
2. Instead of the FIXME line set alpha in the following way for any value of MultiPV:
Code: Select all
if (moveCount >= MultiPV)
alpha = Rml[MultiPV-1].pv_score;
Above changes are not tested.