There are problems with single evasion extensions in search() and pv_search() when the side to move is in check.
In case we have a move from TT the MovePicker::number_of_evasions() result is wrong.
If we must search more evasion moves than the ttMove, then the result is correct, but the condition
mp.number_of_evasions() == 1
never can become true. Therfore it makes no sense to use this condition
singleEvasion = (isCheck && mp.number_of_evasions() == 1);
within the pick move loop.
Forthermore the MovePicker::number_of_evasions() result is the number of pseudo legal evasions (in case we have no ttMove).
But we would need the legal evasions for proper extension handling.
As a result the single evasion extensions fire rather randomly.
Stockfish - single evasion extensions
Moderators: hgm, Rebel, chrisw
-
- Posts: 408
- Joined: Sat Mar 06, 2010 9:28 am
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Stockfish - single evasion extensions
Well regarding your second point, because pseudo legal evasions are always >= legal evasions then when we don't have a TT move and MovePicker::number_of_evasions() returns 1 we have only two cases:Ralph Stoesser wrote:There are problems with single evasion extensions in search() and pv_search() when the side to move is in check.
In case we have a move from TT the MovePicker::number_of_evasions() result is wrong.
If we must search more evasion moves than the ttMove, then the result is correct, but the condition
mp.number_of_evasions() == 1
never can become true. Therfore it makes no sense to use this condition
singleEvasion = (isCheck && mp.number_of_evasions() == 1);
within the pick move loop.
Forthermore the MovePicker::number_of_evasions() result is the number of pseudo legal evasions (in case we have no ttMove).
But we would need the legal evasions for proper extension handling.
As a result the single evasion extensions fire rather randomly.
pseudo legal evasions == legal evasions == 1
or
pseudo legal evasions == 1 and legal evasions == 0
In the first case extension fires as it should, in the second case we never enter the moves loop so we don't have the problem.
Instead your observation on ttove is correct, if we have only a TT move as possible move the extension never fires, this is the only case where we get things wrong, but it is so rare and very probably with almost zero impact on ELO that if the fix is not very small and nice (and I didn't found such a fix) better leave things as they are.
-
- Posts: 408
- Joined: Sat Mar 06, 2010 9:28 am
Re: Stockfish - single evasion extensions
This is not quite right. If we have 2 (or more) pseudo legal evasions, but only 1 legal evasion, we will enter the move picker loop and we will miss to fire the single evasion extension. By placing the single evasion evaluation within the move picker while loop we don't fix the problem. Sometimes we extend positions with 1 legal evasion and sometimes we don't. Now we compare the search results with each other and may come to wrong conclusions.mcostalba wrote:Well regarding your second point, because pseudo legal evasions are always >= legal evasions then when we don't have a TT move and MovePicker::number_of_evasions() returns 1 we have only two cases:
pseudo legal evasions == legal evasions == 1
or
pseudo legal evasions == 1 and legal evasions == 0
In the first case extension fires as it should, in the second case we never enter the moves loop so we don't have the problem.
Furthermore it makes the code difficult to understand. The single evasion condition depends on actual position, not on the moves to make and search from actual position. Therefore it would be better to understand (and faster!) to place this line
singleEvasion = (isCheck && mp.number_of_evasions() == 1);
before the while loop.
Also it makes the evasion condition difficult to extend. For example if you want to extend by OnePly/2 in case you have 2 evasions, you face the next problem. The single evasion extension could be also helpful on other places, for example in qsearch. There it could help a lot in finding mate attacks and perpetual checks faster.
A possible solution would be to change the MovePicker class so that if in check the legal evasions will be computed already when entering the TT_MOVES phase. Now MovePicker::number_of_evasions() will always return the correct number of legal evasions.
From my trials the performance impact is moderate. In return you get more accurate extensions, better to understand and extend code and last but not least probably a slight ELO increase.
Instead your observation on ttove is correct, if we have only a TT move as possible move the extension never fires, this is the only case where we get things wrong, but it is so rare and very probably with almost zero impact on ELO that if the fix is not very small and nice (and I didn't found such a fix) better leave things as they are.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Stockfish - single evasion extensions
This seems a nice idea.Ralph Stoesser wrote:Therefore it would be better to understand (and faster!) to place this line
singleEvasion = (isCheck && mp.number_of_evasions() == 1);
before the while loop.
This seems notRalph Stoesser wrote: A possible solution would be to change the MovePicker class so that if in check the legal evasions will be computed already when entering the TT_MOVES phase.
When I have delayed evasion generation to after trying the TT move I got a benefit in terms of ELO, so I won't revert.
-
- Posts: 408
- Joined: Sat Mar 06, 2010 9:28 am
Re: Stockfish - single evasion extensions
Just in case somebody want to try it out, here is the code.
MovePicker::number_of_evasions() will now return the number of legal evasions, also in case we have a TT move.
movepick.h.
Note the new MoveStack pointer lastEvasion which is used in MovePicker::number_of_evasions().
movepick.cpp.
In case we have a TT move we already compute legal evasions. When entering the evasions phase we point to the already computed moves. In case we have no TT move we compute legal evasions in the evasions phase.
movepick.cpp, legality test removed here.
MovePicker::number_of_evasions() will now return the number of legal evasions, also in case we have a TT move.
movepick.h.
Note the new MoveStack pointer lastEvasion which is used in MovePicker::number_of_evasions().
Code: Select all
class MovePicker {
MovePicker& operator=(const MovePicker&); // silence a warning under MSVC
public:
MovePicker(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss = NULL, Value beta = -VALUE_INFINITE);
Move get_next_move();
int number_of_evasions() const;
private:
void score_captures();
void score_noncaptures();
void score_evasions_or_checks();
void go_next_phase();
const Position& pos;
const History& H;
MoveStack ttMoves[2], killers[2];
int badCaptureThreshold, phase;
const uint8_t* phasePtr;
MoveStack *curMove, *lastMove, *lastEvasion, *lastGoodNonCapture, *lastBadCapture;
Bitboard pinned;
MoveStack moves[256], badCaptures[64];
};
////
//// Inline functions
////
/// MovePicker::number_of_evasions() simply returns the number of moves in
/// evasions phase. It is intended to be used in positions where the side to
/// move is in check, for detecting checkmates or situations where there is
/// only a single reply to check.
/// WARNING: It works as long as PH_EVASIONS is the _only_ phase for evasions.
inline int MovePicker::number_of_evasions() const {
return int(lastEvasion - moves);
}
#endif // !defined(MOVEPICK_H_INCLUDED)
In case we have a TT move we already compute legal evasions. When entering the evasions phase we point to the already computed moves. In case we have no TT move we compute legal evasions in the evasions phase.
Code: Select all
void MovePicker::go_next_phase() {
curMove = moves;
phase = *(++phasePtr);
switch (phase) {
case PH_TT_MOVES:
curMove = ttMoves;
lastMove = curMove + 2;
if (pos.is_check())
lastEvasion = generate_moves(pos, moves, false);
return;
...
case PH_EVASIONS:
assert(pos.is_check());
if (!ttMoves[0].move)
lastMove = lastEvasion = generate_moves(pos, moves, false);
else
lastMove = lastEvasion;
score_evasions_or_checks();
return;
...
Code: Select all
Move MovePicker::get_next_move() {
Move move;
while (true)
{
while (curMove != lastMove)
{
switch (phase) {
...
case PH_EVASIONS:
move = pick_best(curMove++, lastMove).move;
if (move != ttMoves[0].move)
return move;
break;
...
-
- Posts: 408
- Joined: Sat Mar 06, 2010 9:28 am
Re: Stockfish - single evasion extensions
Also I have noticed that the single evasion extension is not used in the multi thread search functions sp_search() and sp_search_pv().
What is the reason for it?
What is the reason for it?
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: Stockfish - single evasion extensions
Because we are using the "Young Brothers Wait Concept", which means that we only try to split after the first move has been searched at a node. Therefore, sp_search and sp_search_pv will never be called in a position where there is only a single legal move.Ralph Stoesser wrote:Also I have noticed that the single evasion extension is not used in the multi thread search functions sp_search() and sp_search_pv().
What is the reason for it?
-
- Posts: 408
- Joined: Sat Mar 06, 2010 9:28 am
Re: Stockfish - single evasion extensions
Ok, I see. Thank you.Tord Romstad wrote:Because we are using the "Young Brothers Wait Concept", which means that we only try to split after the first move has been searched at a node. Therefore, sp_search and sp_search_pv will never be called in a position where there is only a single legal move.Ralph Stoesser wrote:Also I have noticed that the single evasion extension is not used in the multi thread search functions sp_search() and sp_search_pv().
What is the reason for it?
There has been several cases of search instabilities reported for SF 1.7.1. Maybe the inaccurate single evasion extension handling is one of the reasons for search instability.
What do you think about single evasion extensions which do not trigger in all positions with only 1 legal move. Critical or a negligible issue?
-
- Posts: 408
- Joined: Sat Mar 06, 2010 9:28 am
Re: Stockfish - single evasion extensions
It may seem so, but have you tried in the other direction: generate legal evasions already in TT_MOVE phase instead of delaying pseudo legal move generation to after TT_MOVE phase? Note that I'm talking about legal moves at move generation time, not at move pick time.mcostalba wrote:This seems notRalph Stoesser wrote: A possible solution would be to change the MovePicker class so that if in check the legal evasions will be computed already when entering the TT_MOVES phase.
When I have delayed evasion generation to after trying the TT move I got a benefit in terms of ELO, so I won't revert.
I think a correct extension triggering could well pay in terms of performance, if tuned correctly, because the search tree would be smaller.
Apropos ELO. How is it going in the actual SF branch. Do you still fight against ELO regression or have you found a way to increase ELO significantly over SF 1.7.1?
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Stockfish - single evasion extensions
We have tried very hard to find the regression but without success, actually we are thinking to release the new version with only few features in although we have done a lot of cleanup and code changes.Ralph Stoesser wrote:
Apropos ELO. How is it going in the actual SF branch. Do you still fight against ELO regression or have you found a way to increase ELO significantly over SF 1.7.1?
So we don't expect big ELO gains this time, there are some tests ongoing right now so probably at the end of this week we will know a bit better how is with this version.
The main reason to release is to give people like you an up to date codebase to play with.