Author: Vincent Diepeveen
Date: 04:55:47 08/11/00
Go up one level in this thread
On August 08, 2000 at 09:10:47, Andrew Williams wrote: >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 No i do 1 search with zero-window. only the RESEARCH i do with open window. If you research that's needed. Note that the NUMBER of nodes that don't have a zerowindow is very very little. Now that can have to do with a good fliprate in DIEP (chance is very little that a node <= alfa flips to >= beta) but i'm sure that doing tens of zero window searches which mess up my hashtable (which is 8 probes by the way so don't blame my hashtable as it's better working as most progs hashtable as i'm using more probes!) bigtime. Every time you research a new tree, where in DIEP i'm used to search every time the SAME tree. The number of new nodes that DIEP sees each search is very small. So i just can't afford doing tens of researches. I still wonder how MTD objectively could work in cilkchess, as they original did only a single probe in hashtable, which is extremely bad for MTD. I just can't believe that MTD works then, but Don assured me it did. It has to do with the simple eval i guess, because my point is real simple: How in the world can you afford tens of searches, where i for 99.9999% of all nodes only need a single one? I'm sure that you measured in a period where some bugs were in the program. No objectively good testing person i know can use MTD. > >> >> >>>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.