Author: Rudolf Posch
Date: 04:24:03 02/04/98
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. 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.01 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.