Author: Robert Hyatt
Date: 18:15:38 11/10/97
Go up one level in this thread
On November 10, 1997 at 15:12:39, David Eppstein wrote: >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.) It is hard to quantify. But I'd bet that in *every* game I look at, the basic fail-low time extension comes into play and avoids losing a game that moving too quickly would have lost. For the case of a fail low just before running out of time, I will look thru 10 games to get a real number, but I'd bet it happens at least once every 10 games, and more likely it happens maybe once every 3-4 games. Is it important? Hard to say. In one of those 3-4 games it probably avoids losing a pawn it might have lost, even if it were enough ahead that losing it would not matter. But I'd suspect that 1 of every 10 games has a different result based on failing low at the last minute and continuing to search. I'll get some real data however... > >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. could possibly work, although it is sometimes hard to figure out how long it will take to fail low. Are you failing low or just confirming the PV score from the last iteration? Hard to say... > >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.