Stockfish - single evasion extensions

[Ralph Stoesser]

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.

[mcostalba]

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.

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.

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.

[Ralph Stoesser]

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.

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.

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.

[mcostalba]

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 a nice idea.

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.

This seems not

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.

[Ralph Stoesser]

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().

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)

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.

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;
...

movepick.cpp, legality test removed here.

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;

         ...

[Ralph Stoesser]

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?

[Tord Romstad]

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?

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]

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?

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.

Ok, I see. Thank you.

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?

[Ralph Stoesser]

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.

This seems not

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.

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.

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?

[mcostalba]

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?

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.

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.