Author: David Eppstein
Date: 10:33:26 09/30/99
Go up one level in this thread
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.)
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.