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.