Author: Eelco de Groot
Date: 03:39:28 03/16/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's funny I was just thinking a bit about this too. I wanted to suggest to Ed if it maybe was an idea for Century 3.x to display a "preliminary result:" or you could call it a "halfway result" or "first reply analyzed:" whenever for a root move the first reply fully analyzed does not cause an alpha-beta cut-off (or for the principal rootmove when the first reply is fully analyzed) to display this result. It was just an idea for the end-user also because at deeper iterations you would often like to know how long the next result will take and if it is likely to be a different result in score. But the same thing applies to the program, it would also like to know these things! Maybe this is very crude thinking but I figure that for every iteration the principal move takes about half the time. So if I borrow a bit from christophe's philosophy I thought that in priciple the search-tree should be roughly fractal and the first reply to the principal rootmove should take about a quarter of the total time to the next iteration. So ΒΌ times the branching factor to get there? And with good moveordering I think that this "halfway result" of a move would be correct in roughly 80% of the cases? (just an optimistic guess). If this is actually correct I would call this a usable result, not just here but in the whole search-tree. If you have a selective program you could go with this preliminary result some of the time, especially if there doesn't seem to be much change. And for the principal rootmove if the score hasn't changed much you could stop there if time is short. If it is "different enough" higher from the last iteration decide to go on searching 2x longer to complete this first root move. If it is still higher then you could stop and make this move (on the board if principal rootmove or in the tree if you want to be very selective even though the move doesn't cause a immediate cut-off. But this is more complex I realize, I'll concentrate on the rootmoves). If the halfway result is "different enough" lower you could actually stop and first get a full half-way result of the second-best root-move (or a "preliminary!" AB-cutoff of this move even with the low halfway-result of the first move, this means you have to fully search the first move now). This next-best root-move halfway again; if there is no cut-off and if the half-way score is holding "high enough" you might actually then choose to make this move, especially in Blitz-like timecontrols or time-trouble! If no cut-off and not much difference in score, compare the two and decide which of the two is more likely and search that one further or if time is now very short make that move on the board (Or in the searchtree?). Suppose it was the second move searched fully then you now have an accurate result for the second move which can be displayed. You already have a full halfway result of the first move, if that doesn't cause a cut-off you have to search further. If only very near the end there is a cut-off it might be worthwhile to just search the first move fully also to get two accurate results. I think this should be just an option because then you lose again any time you may have gained, but it improves moveordering, gives useful 2-best like information for the user and would have been the result of a normal alpha-beta search if the second move wasn't cut off. Or first do a halfway alpha-beta search of the third move to see how good that one is likely to be and how much time it takes. I don't know if this still makes sense with all the refinements, of smaller windows etc., of alpha-beta variants, but I thought there might be something in it, collecting some of these halflings, as maybe Tolkien would call them if he had been a chess-programmer.. Am I saying something new here? Or is the idea just no good.. Regards, Eelco
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.