Computer Chess Club Archives




Subject: MTD(f)

Author: Stuart Cracraft

Date: 20:28:04 07/26/04

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",
  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
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.


This page took 0.08 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.