Author: Andrew Williams
Date: 04:07:30 09/29/99
Go up one level in this thread
On September 29, 1999 at 06:40:29, Andrew Williams wrote:
>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.
SORRY - HATE TO RESPOND TO MY OWN POST, BUT THAT SHOULD SAY:
You ask an alphabeta search this question by setting beta=guess and
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.