Author: Uri Blass
Date: 08:16:13 03/19/03
Go up one level in this thread
On March 19, 2003 at 10:37:07, Georg v. Zimmermann wrote: >>>>Im having troubles trying to figure out what to do with my search results when a >>>>timeout occurs. eg I could have searched 10 plies fully, and am part way through >>>>the 11th ply when time runs out. >>>> >>>>The simplest thing to do is ditch all results from the last incomplete search >>>>and just go with what you had after 10 plies. But this seems a big waste. >>>> >>>>Thoughts? >>> > >You can use *completed* subtrees of root-moves, and ignore the current, >uncompleted subtree of the root-moves you are searching when time_is_up. To do >that you just check whether time_is_up at the start of search() and return if >true. Then in search_root() you ignore the subtree if time_is_up. > >That is a simple solution and better than ignoring the whole ply. > >Especially when you do not use plain alpha-beta but aspiration windows. Then you >can use the result of a completed subtree which is better than the best so far, >even if you dont have time to find the exact value. > >But what Ed suggests is even better ... (more below) > > >>>It's quite simple, just check the "time_is_up" condition after your "undo_move" >>>call and jump to the place where you climb back one ply in the tree (as if there >>>are no more moves to search on the current ply). >>> >>>My best, >>> >>>Ed >> >> >>This can be a fatal error. You are at ply=N and have 10 legal moves to search. >>The first is horrible, but the second wins everything. If you quit after >>searching the first move and return that score, and since it has now searched every move, it backs the >>score up. And so forth. > >IMHO what Ed is doing is correct. When jumping to the place "where you climb one >ply back in the tree" you do not have a chance to fail high from the incompleted >subtree at the current depth-to-root. Ergo in your example the horrible result >gets returned quite right, but at the parent node it would have to improve >best_value to matter, which it doesnt get a chance to, since time_is_up and we >directly jump to return the prior best_value. That means that the current >subtree up to the last PV node (where a completed subtree already pushed >best_value over original_alpha) gets ignored. That is the difference compared to >the simple method above where the whole subtree under the root-move got ignored. > >Can that matter ? Not in MTD programs, where every search is done with a null >window and we therefore never have a node that is above alpha but below beta. >In programs using aspiration search correctly, it does not matter for which move >is seen best at any time by the program. But it can matter for time management >if you extend time if the first root move fails low by a certain margin. >In programs doing vanilla alpha-beta it will be better even for the move >selection. > > >Questions or corrections ? > >Georg I admit that I do not understand. I do not use MTD but I think that example for a tree and decisions based on the tree can be more productive. I know from experience that even when a move fail high I cannot trust the fail high in 100% so deciding that a move that I even did not get a score for it is good is going to be too big risk. In case of fail high I usually try to solve the fail high and cases that I cannot do it are rare so I did not consider them as very important(my decision is not to trust the fail high in case that I have not time to solve it). 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.