Author: Andrew Williams
Date: 08:22:44 08/14/00
Go up one level in this thread
On August 11, 2000 at 07:55:47, Vincent Diepeveen wrote: >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. > > I don't think that is a meaningful assertion. Let me ask you a couple of questions: Do you believe that replacing MTD(f) by PVS is going to make a significant difference to the play of a program? In other words, do you think that SOS, PostModernist and AnMon would all be improved by replacing MTD(f) with PVS? As I said before, I don't think there would be a measurable difference. Andrew PS Sorry I've taken a while to get back to this. I've been away for a few days. > >> >>> >>> >>>>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.