Author: Andrew Williams
Date: 02:46:40 08/07/00
Go up one level in this thread
On August 06, 2000 at 20:26:06, Vincent Diepeveen wrote: >On August 06, 2000 at 20:15:46, Vincent Diepeveen wrote: > >>On August 06, 2000 at 16:48:16, Andrew Williams wrote: >> >>>On August 06, 2000 at 16:36:15, Vincent Diepeveen wrote: >>> >>>>Show me an MTD program that uses less nodes a ply as DIEP does. >>>> >>> >>>I've no idea if Diep uses fewer nodes than others. However, even >>>if it does, would you say this is due purely to the superiority >>>of PVS over MTD? Surely your evaluation is different to other >>>programs too? >>> >>>The point I want to make is that it's not helpful to Larry (or anyone >>>anyone else) if you just say "MTD(f) sux! PVS rox!" UNLESS you provide >>>some rationale for your opinion. >> >>DIEP uses hell of a lot nodes more if i use MTD. >> >>A pawn in DIEP is 1000 points worth. >> >>So correct me if i'm wrong: >> >>If this iteration i'm at +0.300 next iteration i'm at +0.600 with PVS, >>then how many researches do i need with MTD? > >Now you'll answer probably: IF no other node is above 0.300 then it'll >directly figure that out and you can skip ply. Ok there you get away. > >As i mentionned th eproblem aren't scores getting a bit higher. > >Actually MTD is great for testsets. MTD is having a huge problem if >you start playing games with it however and the vice versa happens. > >If i'm at 0.600 now with PVS at iteration is 8, and the chess prog >starts smelling trouble, then suppose we fail low to 0.300, now >aren't that 300 researches with MTD? > > THREEHUNDERD RESEARCHES? > >Or how do you tackle that problem? We've already had this debate, I think. What my program does is to accelerate the steps. So it sees how many steps it has made in a particular direction then reduces the guess by steps*steps. In the old days, I was a bit more creative about this. Once I'd dropped more than 50 centipawns, I assumed I was losing a pawn, so went straight to (guess-100) in the hope that I would have straddled the real score. I wasn't completely convinced that that was better, so I went for the simpler approach. > >If you jump BINARY to that value 0.300 from 0.600, then you also needed >a lot of researches still and basically you don't profit from the MTD >idea. Now DIEP stores with 8 probes a lot in the hashtable, so actually >too many new nodes don't need to be searched, but if you fail low, >knowing you still need another 3 ply to search in a game to get that 11 ply, >and each ply you fail low with the next concept. > I'm not sure I fully understand this. Are you saying that your 8-probe HT approach means that your researches are less of a problem than mine? If that's what you mean, what has that to do with MTD? >Move A gets best at ply n, then move A fails at ply n+1, there another >2 new moves pop up before getting to ply = n+1, there the process repeats >so a lot of researches till you get say 11 or 12 ply, if you ever get it. > >In the end you see huge depth differences with MTD, then i simply use my >lemma: "chess is a game where the weakest chain counts". In contradictoin >to throwing dices, where only 1 throw needs to be a hell of an end and >a valid throw, we are not throwing to get a local maximum. > >If you search 40 moves, from which 10 moves are searched to 8 ply, >and 30 are searched to 12 ply, then that sucks in my eyes bigtime >using the above lemma compared to 40 searches of each 10 ply. > >Now in scientific magazines you quickly conclude: "that's a total of >400 plies searched for the "weakest link approach", but for me as a >researcher i see i did much more: 12*30 + 10 * 8 = 360 + 80 = 440. > >So if we look just to numbers: in positions where we fail high plies >jump to huge numbers, but in positions where doubt rules, there the >problem appears bigtime. > >So the data we had on our output is probably the same, but is chess >a game of solving testsets as quick as possible? > Maybe it's because I don't understand some of what you are writing, but I am unconvinced by your evidence. Let me be clear about what *I* am claiming: you have not presented any evidence to suggest that MTD is inferior to PVS. Note that I am not claiming that MTD is better than PVS; my view would be that I just don't know. If forced to guess, I would say that I don't think that the difference between the two approaches would be significant. In other words, if I ripped out my mtdf() loop from PostModernist and replaced it with a PVS implementation and worked on it for a couple of years, I would end up with a program which was approximately as good as what I've already got. You seem to be trying to make a much stronger claim, namely that if I replaced MTD with PVS, I would end up with something significantly stronger than what I've already got. I don't think you (or anyone else) has any evidence to support that claim. Andrew >>>Andrew >>> >>>PS Your "there are no commercial programs using MTD" argument doesn't >>>really represent a rationale, in my opinion. >>> >>> >>>>What diep is doing is very simple in search: >>>> >>>> PVS (starting with -infinite) >>>> check extensions >>>> checks in qsearch >>>> nullmove R=3 >>>> no other crap. no pruning. Perhaps at WMCC i prune a bit, >>>> but that's because against computers playing is different. >>>> >>>> Yet i'm missing programs using less nodes a ply with MTD. >>>> I"m missing *any* deep searching program that uses MTD actually. >>>> >>>>On August 06, 2000 at 10:31:58, An >>>> >>>> >>>> >>>>drew Williams wrote: >>>> >>>>>On August 06, 2000 at 09:38:18, Vincent Diepeveen wrote: >>>>> >>>>>>On August 05, 2000 at 11:37:01, Larry Griffiths wrote: >>>>>> >>>>>>>Which Algorithm is considered the best now-adays. >>>>>> >>>>>>Depends upon what kind of program you make. >>>>>> >>>>>>If you have an evaluation function that has patterns which all deliver >>>>>>very small penalties and bonusses, from which the summation also adds up >>>>>>to a near to material only evaluation, then MTD is an interesting >>>>>>alternative. >>>>> >>>>>PostModernist uses MTD. It would be incorrect to describe its evaluation >>>>>as being "near to material-only". This opinion (on MTD) is one that Vincent >>>>>has expounded before, without much in the way of supporting evidence. >>>>> >>>>>> >>>>>>If the evaluation function is either big, using a pawn as being >>>>>>worth 1000 points instead of 1 point, the eval is huge, or having high scores >>>>>>for for example king safety and or passers, >>>>>>then you have only 1 option that outperforms >>>>>>*anything*, and that's nullwindow search also called principal variation >>>>>>search which is pretty easy to implement. >>>>>> >>>>>>Usually at the start of your program MTD looks interesting, if your >>>>>>program gets better (more knowledge in eval, less bugs in search and >>>>>>better move ordering), then PVS usually outperforms anything. >>>>>> >>>>> >>>>>I don't think there is any evidence anywhere that supports Vincent's opinion >>>>>about MTD. Just stating an opinion does not make it true :-) >>>>> >>>>>>My advice is to start with PVS and not look to the rest. >>>>>> >>>>>>>NegaScout? MTD? PVS? Others? I am looking to implement one of the best search >>>>>>>type algorithms in my program. I would like to get it into the 2000 rated range >>>>>>>as this has been my lifetime goal. Then, maybe install winboard or something so >>>>>>>it can compete against other programs to get a rating. >>>>>>>I dont like MTD as it seems to be complex. >>>>>>> >>>>>>>Larry. >>>>> >>>>>My advice would be to get a straight alpha-beta search working, starting >>>>>with bounds of -inf..+inf. This won't be terribly competitive, but you >>>>>can use it as a stable reference when you move on to more sophisticated >>>>>approaches. When you're happy with your alpha-beta search, try implementing >>>>>an aspiration-search, which is like alpha-beta except that you start with >>>>>bounds of score-50 .. score+50, where score is the value returned from the >>>>>previous iteration. You will need to provide some way of handling the case >>>>>where the returned score from *this* search falls outside this "window". >>>>>Once you've got your aspiration search working properly, you'll be in a >>>>>strong position to decide where you want to go with your program. >>>>> >>>>>Above all, have fun with your program! >>>>> >>>>>Andrew Williams
This page took 0 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.