Author: Robert Hyatt
Date: 05:56:51 11/10/97
Go up one level in this thread
On November 09, 1997 at 23:02:49, David Eppstein wrote: >On November 09, 1997 at 17:04:11, Robert Hyatt wrote: >> Crafty has *always* done this. Right before the "depth time ... " heading, >> you see a "target time: " line. This is the anticipated search time for >> this move, assuming the bottom doesn't fall out right at the end. [snip] >> for normal moves, the "target" is within 1 second of how long it will take... > >You must cut the search in the middle of a ply, if you can predict so >precisely how long it will take. Does this distort the search results >much? Do you get much useful information from the time you spend after >the last full ply? turns out the answer is "yes". IE, 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. Now, at least you know, and can use whatever time you want to find something better if possible. 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 after running out of time. After years of trying various alternatives such as a time "window" with a lower and upper bound (time < lower -> continue, time > lower, stop after end of current iteration, time > upper -> quit *now*) we stabilized on this approach in Cray Blitz. I've kept it ever since as simple and direct, but mainly because of the fail low "panic"... > >I've been playing with a timing strategy that involves two time bounds >T1 and T2. If a ply finishes after time T1, I stop instead of going on >to the next ply. If I get to time T2 without having stopped, I abort >the search. This way the search result is usually a search of a complete >ply rather than all of one ply and part of the next. But this is just >for a program I wrote as a web applet, I haven't tried this in a real >timed game, so I'm not sure whether it's a good idea. it's been used by most everyone at some point in time. Nothing wrong with it, except it is less predictable in terms of "when are you going to move?"... and you don't see that extra occasional fail-low if you quit after the current iteration because you are pretty sure you can't complete the next before running out of time. > >Also this way my program naturally allocates more time to some moves >than others, which most people seem to think would be a good idea if you >knew how; I'm not sure if the moves it's allocating more time to are the >ones that need the extra time, though. Deep Blue seems to do particularly well at this. They somehow notice that things are "unsettled" without having to fail low to "wake up." I've not found a good way to pull this off yet, although I haven't spent months looking for one to be honest... >-- >David Eppstein UC Irvine Dept. of Information & Computer >Science >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.