Author: Vincent Diepeveen
Date: 05:26:03 08/08/00
Go up one level in this thread
On August 07, 2000 at 05:46:40, Andrew Williams wrote: >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 So i must give huge evidence, though it's dead obvious, here the average research thinking a new idea out, only need to proof his search algorithms at a testset of 24 positions, from which a bunch are mate in 2, and where all other positions each ply fail high more? On the other hand my proof is quite evident: in important positions in your game, always middlegame or start of an endgame, there you don't search that deep as for the easy moves in your game, like recaptures. Exactly there the score is flipping up and down. That happens each iteration. Now what would be the best search algorithm in such positions? Something that needs 10 researches to get a new PV? That for several moves each iteration? Or using PVS with at most 1 research? >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.