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.