Page 1 of 2
out of time in PVS
Posted: Thu Dec 13, 2018 12:38 pm
by 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
Re: out of time in PVS
Posted: Thu Dec 13, 2018 12:54 pm
by Guenther
AxolotlFever wrote: ↑Thu Dec 13, 2018 12:38 pm
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
Re: out of time in PVS
Posted: Thu Dec 13, 2018 1:01 pm
by AxolotlFever
Hi there Guether,
Thansk very much for this link, it is very useful!
Kind regs,
Louis
Re: out of time in PVS
Posted: Thu Dec 13, 2018 1:13 pm
by 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]
Re: out of time in PVS
Posted: Thu Dec 13, 2018 5:39 pm
by 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.
Re: out of time in PVS
Posted: Thu Dec 13, 2018 7:28 pm
by 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.
Re: out of time in PVS
Posted: Thu Dec 13, 2018 8:39 pm
by 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.
}
Re: out of time in PVS
Posted: Fri Dec 14, 2018 7:31 pm
by RubiChess
I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.
Andreas
Re: out of time in PVS
Posted: Sat Dec 15, 2018 1:15 am
by Sven
RubiChess wrote: ↑Fri Dec 14, 2018 7:31 pm
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.
Re: out of time in PVS
Posted: Sat Dec 15, 2018 7:56 am
by RubiChess
Sven wrote: ↑Sat Dec 15, 2018 1:15 am
RubiChess wrote: ↑Fri Dec 14, 2018 7:31 pm
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.