Author: Robert Hyatt
Date: 05:58:02 03/16/01
Go up one level in this thread
On March 16, 2001 at 06:39:28, Eelco de Groot wrote: >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. I think the fraction is larger. IE I often see Crafty use 1/2 to 3/4 of the total search time on the first move. Because null-move causes the remainder of the moves at the root to whiz by. > 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.