Author: Sven Reichard
Date: 16:45:53 09/28/99
Go up one level in this thread
MTD(f) relies on the following two observations regarding fail-soft alpha-beta
(FSAB):
1) If FSAB fails, it still gives valuable information (namely, a bound for the
score);
2) The smaller the AB-window, the more pruning is done.
So we call FSAB with a minimal window (|A-B|=1) repeatedly to get better and
better bounds, thereby basically doing a "binary search" for the actual score.
Some C-pseudocode:
score max, min, bound, alpha; // score is your favorite int type
max = MAX_SCORE; // greater than the actual score
min = MIN_SCORE; // definitely less than the actual score, e.g., -Mate in 0
while (max - min > 1){
alpha = (max+min)/2; // take the average
bound = FailSoftAB(alpha, alpha+1);
if (bound == alpha) // exact score
return bound;
if (bound < alpha) // we get an upper bound
max = bound;
else // we get a lower bound
min = bound;
}
return max;
Due to heavy researching, you definitely should use a hashtable that stores
bounds for the evaluation.
You can speed this up in the following way:
1) make the initial window (max-min) smaller; you have to take care about what
happens if the actual score is outside these bounds;
2) since you do this only at the root, you don't really need the exact score;
you can stop if you know that one move is definitely better than the other.
This is my understanding of this algorithm; I hope it is not too inaccurate, and
these lines help. Any comments welcome.
Sven.
/* Excuse the c++ type comments :) */
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.