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.