Author: David Rasmussen
Date: 23:29:59 03/15/01
Go up one level in this thread
On March 16, 2001 at 00:23:21, Pham Minh Tri wrote: >Hi, > >Suppose the time for searching a move is limited in T minus. And a program has >just finished the iterative loop of depth N. My question: How to decide that the >time left is enough for the next loop (depth N+1) or not? > >(Some books suggested me to continue searching next depth and interrupt when >time is over. But I don't like this method because of wasting time.) > >Any suggestions would be very appreciated. >Pham Most people check the time during search, and if the time exceeds the time limit, they immediately stop searching, and use the latest usable result. Of course, when to stop searching, isn't necessarily easy to establish, unless you're searching for fixed time intervals (say 30 seconds). The subject of time management is a complex one. If a program plays by a 2 hours for 40 moves time control, when should it refrain from using to much time? Forced recaptures and other "easy" moves would fall in this category, but it's not easy to define what "easy" means. Ideally, I would like to be able to identify whenever a best move from one iteration, is "much" better than the next best move of that iteration. If this has happened when you've used, say, half of the time you would normally use for a move, you could stop searching and moving. But with alpha-beta, it's not easy to know what the next best score is. On the other hand, we would want to extend the time used for a move, whenever the position is difficult and the program is likely to need more time to find the right move, or just a good move. How to do that? There are ways that people do this, also, which primarily has to do with search stability. If the program has found that one particular move is the best for all iterations, it probably wont change its mind, if it searched more. On the other hand, if the program can't make up it's mind, and shifts from move to move from iteration to iteration, it's probably a good idea to extend the time. The same thing applies for the score. If the score swings wildly we would like to search more etc. If you just want to search a maximum of, say, 30 seconds, and you don't want to poll the time during search, but only to check the time between iterations, to see if you could continue searching (which is a bad idea, because you can't really control how much time is being used), you could look at the factor that you have to multiply the time used in one iteration, to get the time that is used at the next. This is also a good indicator of your branching factor. If searching one more iteration takes 6 times longer than the previous, you just do the simple math between iterations to estimate whether you should continue searching or not. But as I've said: I wouldn't recommend this, as it can't really be used in real life. If such a program were to participate in a tournament, it would probably lose often because of it's poor time allocation strategy.
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.