Author: David Eppstein
Date: 12:12:39 11/10/97
Go up one level in this thread
In previous messages to this thread, Robert Hyatt described how Crafty generally aborts its search immediately when it reaches the target time, unless the PV has recently failed low. I compared this to a scheme with two timers, in which a completed ply after the first timer goes off will stop the search, but the search isn't aborted until the second timer goes off, and I asked Hyatt what useful information was gained from a partial search. He replied: > ... consider two cases that can happen when you start a new ply but don't > finish it, or don't even get the PV back before running out of time: > > 1. you fail low, which happens quickly. Now you know that you need to > use more time as your "best" move is going to crash and burn. ... > > 2. you don't fail low, but run out of time before completing the PV. I > stop, announce the move, then make the move and start thinking on the > opponent's time. The hash table is *not* cleared in Crafty, so the search > effectively resumes right where it left off ... The second point is merely that the search time isn't totally wasted, and would be true no matter what you use for your time management strategy. I am more interested in the first point, that it is valuable to be given a chance to fail low. How valuable? More valuable than a full ply of search? (Perhaps some statistics on what fraction of the time the program changes its move because of a fail-low vs because of an alternate move failing high would help resolve this question.) If the chance to fail low is so useful, maybe you should consider a modification of the two-timer approach. After the first timer goes off, instead of stopping the search at the completion of a ply, stop if you reach a point where the PV has just had a chance to fail low but didn't. Again, if you get to the second timer before reaching this point, abort the search. My argument is that it seems reasonable to assume that some parts of the search time are more valuable than others. So, you want to arrange your timing so that the program spends as large a fraction of its time as possible in the more valuable parts. The two-timer approach seems to (try to) do that, the only question is determining which part of the search time to try to maximize. -- David Eppstein UC Irvine Dept. Inf. & Comp. Sci. eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
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.