Author: Andrew Williams
Date: 11:10:03 07/18/99
Go up one level in this thread
On July 18, 1999 at 12:16:40, Vincent Diepeveen wrote: >On July 18, 1999 at 09:52:08, Andrew Williams wrote: > [ snipped ] >> >>So the question is, has anyone who is using MTD(f) got any ideas on how >>to retrieve the PV? Of course, I'm also interested in ideas/opinions from >>those who aren't using MTD(f) - even if the opinion is "you should switch >>to PVS"! >> > >well before explaining my bad experiences with MTD, >first a tip how to get the pv. > >Just get the Principal variation from the hashtable. > >What i use is 8 probe in DIEP, so for every PV >diep can garantueed get 8 out of the hashtable. > Are you saying that on a collision you then try stepping to another slot, and that you do this eight times? If so, that is what I'm intending for my PV hash table idea. >However, considering the fact that hashtable is >around 150mb or something, which means roughly 8 million entries, >the chance that one overwrites principal variation entries >is rather small. > >As you write "near the leafs" one might fear such things, >but those worst case scenario's (that positions near >leafs get overwritten) only occur in diep after overnight >searches using a rather small hashtable (4 million >entries or something). > I agree with Bob on this one. My PV entries are often overwritten. In fact, until I started taking precautions, my *ply 1* entries would sometimes get overwritten (by extended nodes further down), with predictable (and hard to reproduce) consequences! [ DIEP's search output snipped ] > >We all don't doubt that MTD is a fine algorithm. Regrettably it only >works for programs using an evaluation which gives very little deviation; > >See the score differences the first few ply in DIEP's lines: > >0.87 >1.21 >0.63 >0.87 >1.29 >0.93 >0.94 >0.94 >1.00 >1.03 >0.77 >0.78 >0.82 >0.89 >1.03 >0.80 >0.81 >0.80 >0.86 >0.84 >1.03 >0.65 >0.97 >1.04 >1.20 >1.02 >1.15 >0.88 >0.98 >0.86 > >And those deviations still considering it's a position where there is >not too much tactics. > >Getting the big fail low at 14 ply caused a jump from 1.03 to 0.65 >which took 28.00M / 12.49 = 2.24 branching factor > >Just imagine the huge number of researches that MTD needs >to get to 0.65! > In PostModernist's case it would search 1.03, then 1.02, then 0.98, then 0.89, then 0.73, then 0.48. It would then start to work its way back up, 0.48, 0.49, 0.51, 0.54 etc. So in this example, PM needs a lot of re-searches, but it's not just to do with the gap between the iteration scores - for example, going from 1.03 down to 0.48 would be considerably faster than going from 1.03 to 0.72, because of where the scores lie and because of my approach to traversing gaps. Clearly a good TT is required for this sort of thing to work, but what program doesn't need this anyway. AFAIK, MTD programs are not significantly significantly faster OR slower than PVS programs. The difficulties with MTD are with practical issues like the PV - hence my question. >Because let's face it, what program *actually* use MTD currently: > >parallel version of fritz (?) : evaluation of it under 200 clocks >cilkchess : evaluation also is very limited and > definitely doesn't have huge scores, > we all know that cilkchess evaluation is > always very close to the number of pawns that > it sees. >SOS : same comment valid as for cilkchess > >So the programs using MTD currently have hardly anything in their evaluation >not many things causing big scores, >so claiming that MTD is doing a good job is only true when taking into >account this restriction, which a lot of programs do not wish to have. I don't know anything about the programs you cite, but PostModernist's evaluation is certainly not simple. And it would definitely be incorrect to say that its evaluation is close to the number of Pawns it sees :-). And PostModernist is doing a reasonable job these days (yesterday it managed to beat a crafty at 15 0 on equal HW). It's very tough to separate the influence of the search control method from the influence of the evaluation, so it's very hard to compare MTD with PVS unless you have both in the same program. Is Don Dailey still around? I thought that he said that one of his programs was switchable between the two methods (actually that was Cilkchess I think, so if you're right about the simplicity of eval, that might not help us much). I'd be interested to hear other opinions. Anyway, thanks very much for taking the time to give such a detailed answer. regards Andrew
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.