Author: Robert Hyatt
Date: 05:46:16 02/04/98
Go up one level in this thread
On February 04, 1998 at 07:24:03, Rudolf Posch wrote: >I have a problem in my personal chess program with handling properly >search timeout (stopping search after an preallocated time). >I usually dont start a new iteration when timeout has occured, but I >have also some time management code at this place (comparing remaining >time with spent time, spending extra time under certain conditions like >if the search result is low,...). >But this measure is not sufficent, it can take quite a long time until >the search finishes one iteration. For instance when there are 5 seconds >allocated for a computer ply, the search stops actually after e.g. 12 >seconds, because the last iteration lasted longer as expected (because >of excessive quiescence search, deepening at chess etc.). > >So my problem lies in interrupting a running search. > >In the recursive procedure call search() I have in the move loop a point >where I test the timeout condition. >If timeout is true,the search may be in a node in some depth i with a >current minmax value and current principal variations in all searched >depths <= i. Usually not all plies at this node (and shallower nodes) >have been searched. >So what do to ? >1) Exit search()in depth i at timeout=true unconditionally, returning >the current minmax value. The search continues in depth i-1 and comes >again to the timeout test, only 1 level shallower, ... and so on, until >depth 0 is reached. >A principal variation at depth null builds up, which may contain the >wrong move. >This plain method seemingly doesnt work. there are several issues here. I always start a new iteration unless I am totally out of time, because a fail-low happens *very* quickly and can let me know to use more time. when I run out of time, I instantly back out of search, returning a special value that says "don't use me, I am no good" so that I can unwind the recursive calls. I simply use the best thing backed up to the root so far... Do *not* back up partial values when timing out, as they are totally useless. If you have not yet backed up a good score/PV to ply=1 for this iteration, you bail out and use the best PV from the previous iteration. To do otherwise is to invite massive blunders. one other important idea is that after you run out of time, do *not* stop the search until you complete searching the current move at the root, because you just might be about to change your mind and there's no point in quitting before you find this out, if you've been stuck on this move for a good bit of time searching it.. >2) Exit search in depth i at timeout=true only under certain conditions: >for instance only if the principal variation at depth null contains >already a move with minmax0 > alfa0 (remark: my program makes a ply >entry into the principal variation already at best> minmax, not at >best>alfa, because of better research results with the >Negamax-algorithm). >In this implementation, I forbid with timeout=true further updates of >the principal variations and set minmax= ((+/-) current minmax at depth >0) before exiting search() at depth i, propagating this fixed >minmax-value through until depth 0. >This is in principle a "simulated BREAK TO LEVEL 0", solving the problem >of immediately leaving a recursive function call to level 0. >The disadvantage of this method is, that it doesnt stop search when >(current minmax at depth 0)< (alfa at depth 0) and even worse that it >interrupts maybe an already found better variation, not storing the >moves into the the principal variation. >3) Exit search at depth i at timeout=true (and successivly at other >search depths) only when minmax>=alfa. There exists a best move at depth >i, i-1,.. and a principial variation builds up, the worth of it is >doubtful. And the search doesnt stop when alfa is not reached. > >I think there are different ways to handle the problem and I would be >interested what methods use other chess programs?
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.