Author: Georg v. Zimmermann
Date: 07:37:07 03/19/03
Go up one level in this thread
>>>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
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.