Author: Vincent Diepeveen
Date: 11:22:14 07/18/99
Go up one level in this thread
On July 18, 1999 at 14:10:03, Andrew Williams wrote: >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! Well using like 1 probe that's like 0.40 chance, using 8 probes that's like 0.0006 chance, where are we talking about? 0.0006 chance that our long line is 1 ply shorter, a line which most already don't follow? >[ 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. The idea of having more than 1 research is laughable. Now you can of course make a statement that the overhead isn't *that* high, which is more or less true, but still... >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. I completely disagree here. I can simply not use MTD in DIEP, or i might need up to 6 times more nodes a search. What counts for me is not the average plydepth diep gets in a game, but the minimum it gets. I want to maximize the minimum it gets; example: if i have a game of 50 moves, and i search 1 move only 6 plies, and all other moves 15 ply, then i might lose. If i search however all moves 14 ply then i'm very happy. MTD works way worse for DIEP in those positions. In positions where my PVS has problems, MTD has even bigger problems, so that already directly aborts all interest in MTD. I remember a few games of DIEP in paderborn 1999, where DIEP made because of a bug a few moves a move using a 1 ply search. However most moves were searched 14 or 15 ply... ...it definitely hurted its performance. Your weakest chain! So apart from the fact that for DIEP i need way more nodes average for my searches, a major concern is the worst case behaviour of MTD. >>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). I didn't make a statemanet about PM as i don't know PM. I can only advice you to also implement PVS and see what it does for you. >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. Crafty is freeware, source is open, crafty has some high scores in eval. Try MTD on crafty and you'll see. >Anyway, thanks very much for taking the time to give such a detailed answer. No problems. I don't intend to get down the research of Aske. It's really very good of him that he has invented a way of searching using only 1 bound instead of 2, where near to no one these days invents new search ideas. However nowadays this method is not usable for me, as there is too much deviation in my programs evaluation. If the average evaluation difference is more than a few hundreds a plydepth, then we can forget about MTD. Doesn't take away that MTD *might* be interesting to research for use at huge search depths in the endgame, where most programs don't change score that much. >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.