Author: Andrew Williams
Date: 13:18:43 09/30/99
Go up one level in this thread
On September 30, 1999 at 13:33:26, David Eppstein wrote: >On September 29, 1999 at 06:40:29, Andrew Williams wrote: >>MTD(f) is a bit different. Here the search proceeds by successively asking >>the question "is the score for this position greater than or less than this >>guess?". You ask an alphabeta search this question by setting >>alpha=beta-1 at the root of the search. If the score returned by the search >>is greater than the guess, you increase the guess by some amount and then >>ask again. Equally if the score of the search is < the guess, you decrease >>guess by some amount and then ask again. You successively ask the question, >>keeping track of the upperbound and lowerbound established by the search. >>When the upperbound and lowerbound meet, you have found your score. > >You shouldn't need to keep going all the way until the upperbound and lowerbound >meet. It is enough to get to a search where one move is above the current >guess, and all other moves are below the current guess. > >Of course, normally, once you see that one move is above the current guess, you >get a fail high and stop the search without waiting to see whether the other >ones are below. So, it seems hard to tell when you should stop. > >But, you could keep a flag for each root move, saying whether it failed low in >the current window. If the flag is set, you don't bother searching that move in >later windows. If the search for a given guess fails low, you narrow the window >without updating any of the flags. If the search for a given guess fails high, >you narrow the window and flag any move that failed low in that search. Then, >you can stop when there is only one unflagged move. > >(I'm not really sure how much of a difference this would make compared to what >you describe -- I use aspiration+PVS myself.) That's a good tip. Thanks. I think I used to do something similar when I first started with MTD. In the distant past, I've also used something like this as a "sanity" check to investigate problems with convergence. But in the end, I ditched it as using the hash-table is simpler, as Dave Gomboc suggests. Andrew
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.