out of time in PVS

[AxolotlFever]

Hi all,

My engine is currently single-threaded, and does ok when I search to some fixed depth, or when I wait for a complete Iterative Deepening search to complete. However, if I try to interrupt my search in the middle of a PVS, then my program starts returning completely crazy moves, and it becomes terrible.

Have you implemented something to interrupt your search in the middle of PVS? If so, what do you return? Do you return eval? Alpha? Drop into Qsearch?

Thanks kindly in advance,
Louis

[Guenther]

Hi all,

My engine is currently single-threaded, and does ok when I search to some fixed depth, or when I wait for a complete Iterative Deepening search to complete. However, if I try to interrupt my search in the middle of a PVS, then my program starts returning completely crazy moves, and it becomes terrible.

Have you implemented something to interrupt your search in the middle of PVS? If so, what do you return? Do you return eval? Alpha? Drop into Qsearch?

Thanks kindly in advance,
Louis

This thread gives some advice for this
http://talkchess.com/forum3/viewtopic.p ... +iteration

[AxolotlFever]

Hi there Guether,

Thansk very much for this link, it is very useful!

Kind regs,
Louis

[Henk]

Easiest but inefficient is just clear the line and use previous line which did finish.

[if you do iterative deepening and are researching move from previous iteration first, you can do some optimizations on (ply) depth = 0 for on ply depth = 0 each move searched gives added value. But at this moment doing position analysis with my engine fails so I might have a similar bug]

[Ras]

You can add something like this in the loop that iterates over the moves in your search recursion:

Code: Select all

if (time_is_up != TM_NO_TIMEOUT)
    return a;

    if (t > a)
    {
        a = t;
        *best_move_index = i;
        
    ...

That makes sure that in case of timeout, no nonsense moves can raise alpha. In your main iterative deepening move, you check whether you get any move at all. This may fail if the timeout occured during the search of the first root move. In this case, you take the line from the depth iteration before. Otherwise, at least the first move has been searched, and you can take the PV. This relies on moving the best move to the top of the root list after every iteration.

[elcabesa]

One usually stop the PVS search and use the result of the previous finished iterative deepening result.
Remember that after you decide to stop the search you have also to stop saving killers, sving info to transposition tables and so on.

[AlvaroBegue]

Here's what I do: Whenever I find a move that becomes the best move at the root, I move it to the top of the list. At the end, I just return the top move. This handles aborted searches very naturally.

Code: Select all

Move search_root(Board const &board) {
  std::vector<Move> moves = board.generate_moves();
  
  try {
    for (int depth = 1; !out_of_time(); ++depth) {
      int alpha = -Infinity;
      for (size_t i = 0; i < moves.size(); ++i) {
        // Here you do the usual make_move, PVS search, yadda, yadda, yadda
        if (score > alpha) {
          alpha = score;
          std::rotate(moves, moves + i, moves + i + 1); // Move the best move to the top of the list
          // print some info about the best move and PV
        }
      }
    }
  }
  catch (...) {
    // I use an exception from the middle of the search if I run out of time or the GUI asks me to stop, and I catch it here
  }
  
  return moves[0]; // No matter how we got out of the loop, this is the best move we've found so far.
}

[RubiChess]

I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.

Andreas

[Sven]

I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.

Do you also use a flag indicating that the search is being stopped? If you don't then just returning alpha on detecting a timeout might be wrong since the direct parent node negates the score and performs a beta cutoff but then the parent's parent just continues with the next move after noticing that its current move has been refuted.

[RubiChess]

I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.

Do you also use a flag indicating that the search is being stopped? If you don't then just returning alpha on detecting a timeout might be wrong since the direct parent node negates the score and performs a beta cutoff but then the parent's parent just continues with the next move after noticing that its current move has been refuted.

Yes, I have a global flag "IMMEDIATESTOP" that lets every parent node just return its alpha.