Author: Uri Blass
Date: 23:48:19 03/15/01
Go up one level in this thread
On March 16, 2001 at 02:29:59, David Rasmussen wrote: >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. It is not clear. Stopping at the end of the iteration and deciding when to stop only based on the time that you finished the iteration and the time limit of the game(except cases when you are in danger of losing on time) is not the best strategy but I do not think that you can earn more than 50 elo from a better strategy. The gap between chess programs in tournaments is often more than 50 elo so if a program is losing often there must be other reasons for it and not only poor time allocation. Uri
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.