Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f)

Author: Tony Werten

Date: 00:50:50 07/27/04

Go up one level in this thread


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

>where MAXNUM is an arbitrarily chosen high number (higher than all
>evaluations, special return values, mate, etc.) MINNUM is the reverse
>and MATE can go to -MAXNUM+100 (MAXNUM=-MINNUM), less the value of
>depth at which the MATE is found. MAXNUM and MINNUM are set to 999,999
>and -999,999 respectively.
>
>Note: MAXNUM and MINNUM are not the max and min of the signed integer
>values for the architecture the program is running on. I tried that
>  #include <limits.h>
>  #define MAXNUM INT_MAX
>  #define MAXNUM INT_MIN
>
>but mtdf() did the same thing as above.
>
>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.