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.