Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f)

Author: Stuart Cracraft

Date: 21:09:12 07/27/04

Go up one level in this thread


On July 27, 2004 at 03:50:50, Tony Werten wrote:

>On July 26, 2004 at 23:28:04, Stuart Cracraft wrote:
>
>>I visited Aske Plaat's site and slapped MTD(f) into my
>>program, keeping the existing PVS/NEGASCOUNT in lieu of implementing
>>his AlphaBetaWithMemory(). This is perfectly okay according to Aske.
>>
>>Then, ina normal game from the starting position, no problem.
>>Iteration count of about 15 or so, as predicted, prior to convergence
>>by mtdf() (see below).
>>
>>But in this position (Reinfeld Win-at-Chess, position #1) I get millions of
>>iterations, no convergence, and a never-ending mtdf() loop.
>>
>>[D] 2rr3k/pp3pp1/1nnqbN1p/3pN3/2pP4/2P3Q1/PPB4P/R4RK1 w - Qg6 0 32
>>
>>This is the output deep into the run of the code below.
>>
>>:
>>:
>>mtdf iteration=9026 lowerbound=7038 upperbound= 9999999 g = 7038 beta = 7038
>>mtdf iteration=9027 lowerbound=7039 upperbound= 9999999 g = 7039 beta = 7039
>>:
>>:
>>
>>It should normally finish in 15 or so iterations and does when I start
>>playing a normal game from the starting position.
>>
>>But the above position gives it a problem.
>>
>>My code is just Aske's:
>>
>>int mtdf(int *bd, int f, int d)
>>{
>>  int iteration=0;
>>  int beta;
>>  int g = f, upperbound = MAXNUM, lowerbound = MINNUM;
>>  while (++iteration) {
>>    if (g == lowerbound) beta=g+1; else beta=g;
>>    g = pvsnegascount(bd, d, 0, beta-1,beta);
>>    if (g < beta) upperbound=g; else lowerbound=g;
>>    if (lowerbound >= upperbound) break;
>>    printf("mtdf iteration=%d lowerbound=%d upperbound= %d g = %d beta = %d\n",
>>        iteration,lowerbound,upperbound,g,beta);
>>  }
>>  return g;
>>}
>>
>>I suspect something to do with the mate in the position
>>not agreeing with the upperbound/lowerbound of mtdf() or
>>something related to my mate values confusing mtdf().
>>
>>Fyi, I measure in millipawns and MATE is MAXNUM-depth
>
>That means your score can only get up a millipawn per search. ie 1000 searches
>to go up a pawn etc.
>
>There are several ways to improve this:
>
>- Divide your evaluation score by 10 before returning (or 100 :)
>
>- Use fail soft alpha beta
>
>- Increase your beta with more than 1 millipawn. fe start with 1 millipawn, then
>2 then 4, 8,16 ,32 etc and when you overshoot, lower beta with etc,32,16,8
>
>Tony

Okay I attempted to do this last one with the following revision.
When I uncomment the //'s below, I see the 1-2-4-8-etc you're
talking about and then a reversal occasionally back down by powers
of 2.

This did produce a good increase from about 50% on a small test suite
up to about 83%. PVS/NEGASCOUT does about 90-93%, so we're not far off.
Have a look at this and please let me know if you see anything wrong.

(P.S. I tried g /= 10; after the search() return but it didn't help
to reduce from millipawns to centipawns this way.

int mtdf(int *bd, int f, int d)
{
  int iteration=0,beta,g=f,upperbound=MAXNUM,lowerbound=MINNUM;
  int step=0,stepdir=1,change=0,mod;
  while (++iteration < 30 && lowerbound < upperbound && !(flags&TIMEOUT)) {
    if (1<<step > 1) change=1<<step; else change=1;
    if (stepdir) step++; else step--;
    if (step<0) step = 0;
    if (g == lowerbound) {
      beta=g+change;
      mod=1;
    } else {
      beta=g;
      mod=change;
    }
    g = search(bd, d, 0, beta-mod,beta);
    if (g < beta) {
      upperbound=g; stepdir=0;
    } else {
      lowerbound=g; stepdir=1;
    }
//    printf("mtdf i=%d lb=%d ub=%d g=%d beta=%d change=%d\n",
//      iteration,lowerbound,upperbound,g,beta,change);
  }
  return g;
}


Stuart



This page took 0.01 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.