Author: Andrew Williams
Date: 03:40:29 09/29/99
Go up one level in this thread
On September 28, 1999 at 17:57:40, Nicolas Carrasco wrote:
>I only saw one site of MTD(f) and the phseoudo code uses an mixture of C and
>Pascal. Can anybody explain it to me? Can anybody send me a C phseoudo code?
>
>Thanks
On September 28, 1999 at 17:57:40, Nicolas Carrasco wrote:
>I only saw one site of MTD(f) and the phseoudo code uses an mixture of C and
>Pascal. Can anybody explain it to me? Can anybody send me a C phseoudo code?
>
>Thanks
Normal alphabeta approaches start with two bounds (alpha and beta) around the
score. During the course of the search, the gap between these two bounds is
narrowed until the two bounds meet. The point at which the two bounds meet
is the correct score. You can see this happening in TSCP: the two bounds
start at -10000 and +10000 (in think()). The gap between them is narrowed
in quiesce() and search() (look for the lines where it says alpha=x).
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. Your
alphabeta function should return scores rather than bounds, because otherwise
this will go pretty slowly. Because you are repeatedly asking the same question
you need a good hash table. Because you never establish the exact score for
positions in the search, you need to keep an upper bound and a lower bound in
the hash table for each position you insert. Again, because you never establish
exact scores, you can't keep the PV in the normal way; you need to use your
hashtable to keep track of it.
Below is PostModernist's mtdf loop with some stuff omitted (the omissions
relate to creating the PV and reporting information about the search to
xboard, or to the user or to the epd testing functions). There's nothing
secret about the omitted stuff, it just that I've recently changed this
significantly and it's a bit untidy (while looking at this, I've noticed at
least two ifs that could have been ditched).
int mtdf(int firstguess, int depth) {
int score;
int beta;
int movesDown = 0;
int movesUp = 0;
upperbound = 10000;
lowerbound = -10000;
beta = firstguess;
while(upperbound > (lowerbound+1)) {
score = root_AB(depth, beta - 1, beta);
if(score < beta) {
upperbound = beta;
movesDown++;
movesUp=0;
beta = score - ((movesDown+1)*(movesDown+1));
if(beta <= lowerbound) {
beta = lowerbound+1;
movesDown = 0;
}
} else {
lowerbound = beta;
movesUp++;
movesDown = 0;
beta = score + (movesUp*movesUp);
if(beta >= upperbound) {
beta = upperbound - 1;
movesUp = 0;
}
}
}
return lowerbound;
}
Andrew Williams
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.