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
out of time in PVS
Moderators: hgm, Rebel, chrisw
-
- Posts: 50
- Joined: Sun Nov 11, 2018 9:26 pm
- Location: Germany
- Full name: Louis Mackenzie-Smith
out of time in PVS
My chess engine is Axolotl: https://github.com/louism33/Axolotl
And it uses: https://github.com/louism33/
Othello/Reversi: https://github.com/louism33/Mudpuppy
And it uses: https://github.com/louism33/
Othello/Reversi: https://github.com/louism33/Mudpuppy
-
- Posts: 4611
- Joined: Wed Oct 01, 2008 6:33 am
- Location: Regensburg, Germany
- Full name: Guenther Simon
Re: out of time in PVS
This thread gives some advice for thisAxolotlFever 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
http://talkchess.com/forum3/viewtopic.p ... +iteration
https://rwbc-chess.de
trollwatch:
Talkchess nowadays is a joke - it is full of trolls/idiots/people stuck in the pleistocene > 80% of the posts fall into this category...
trollwatch:
Talkchess nowadays is a joke - it is full of trolls/idiots/people stuck in the pleistocene > 80% of the posts fall into this category...
-
- Posts: 50
- Joined: Sun Nov 11, 2018 9:26 pm
- Location: Germany
- Full name: Louis Mackenzie-Smith
Re: out of time in PVS
Hi there Guether,
Thansk very much for this link, it is very useful!
Kind regs,
Louis
Thansk very much for this link, it is very useful!
Kind regs,
Louis
My chess engine is Axolotl: https://github.com/louism33/Axolotl
And it uses: https://github.com/louism33/
Othello/Reversi: https://github.com/louism33/Mudpuppy
And it uses: https://github.com/louism33/
Othello/Reversi: https://github.com/louism33/Mudpuppy
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: out of time in PVS
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]
[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]
-
- Posts: 2488
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: out of time in PVS
You can add something like this in the loop that iterates over the moves in your search recursion:
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.
Code: Select all
if (time_is_up != TM_NO_TIMEOUT)
return a;
if (t > a)
{
a = t;
*best_move_index = i;
...
Rasmus Althoff
https://www.ct800.net
https://www.ct800.net
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: out of time in PVS
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.
Remember that after you decide to stop the search you have also to stop saving killers, sving info to transposition tables and so on.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: out of time in PVS
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.
}
-
- Posts: 587
- Joined: Fri Mar 30, 2018 7:20 am
- Full name: Andreas Matthies
Re: out of time in PVS
I return alpha immediately without storing to TT.
This should just throw away all unfinished searches.
Andreas
This should just throw away all unfinished searches.
Andreas
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: out of time in PVS
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 587
- Joined: Fri Mar 30, 2018 7:20 am
- Full name: Andreas Matthies
Re: out of time in PVS
Yes, I have a global flag "IMMEDIATESTOP" that lets every parent node just return its alpha.Sven wrote: ↑Sat Dec 15, 2018 1:15 amDo 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.