Author: Vincent Diepeveen
Date: 17:26:06 08/06/00
Go up one level in this thread
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? 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. 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? >>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.01 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.