Author: Andrew Williams
Date: 06:10:47 08/08/00
Go up one level in this thread
On August 08, 2000 at 08:26:03, Vincent Diepeveen wrote: >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? > You can either give "huge evidence", OR you can refrain from making statements with nothing to back them up :-) Remember, my point is not that my way is better than yours, rather it is that there is not enough evidence to make sweeping generalizations. >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? > But this is the whole point of the question, isn't it? It's difficult to compare 10 zero-window re-searches with one re-search with a wide open window. Surely you have to agree with this? Otherwise, why use PVS? Cheers Andrew > > >>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.