Author: Robert Hyatt
Date: 07:53:06 07/20/99
Go up one level in this thread
On July 20, 1999 at 08:52:18, Vincent Diepeveen wrote: >On July 19, 1999 at 23:35:50, Don Dailey wrote: > >>I have noticed a lot of posts lately on the subject of MTD and thought >>I would give my observations and experiences. First of all, I would say >>that MTD is simply a big win. A lot of people have reported various problems >>with it including myself. But all the problems are correctable and you >>will be rewarded with the fastest possible aspriation search on the planet. >>All of the problems are based on not completely understanding what is going >>on and not bothering to stick with it until you figure it out. Even regular >>alpha beta searching is full of gotcha's and a lot of people don't fully >>understand the proper way of doing aspiration searching. This is forgivable, >>though, it's complicated and very easy to overlook some of the hairy issues. >>It's one of those things that seems ridiculously simple once you understand >>it, but until then is not so simple. > >Note that i perfectly understand both algorithms. I don't mind you saying: >"Even regular alpha beta searching is full of gotcha's and a lot of > people don't fully understand the proper way of doing aspiration searching." > >If however that line is meant for me, then i'm insulted till my bones. > >>The lazy evaluation problem is one I ran into with Cilkchess. When I tried >>to use lazy evaluation I got big speedups in terms of nodes per second, >>but the number of nodes inflated to make it NOT a win. This was quite >>annoying but was caused because the value you return to the mtd driver >>was often "weaker" because of the "cheat margin" you used with your >>evaluation. The solution is not to use beta (the single goal value >>of an mtd probe) but to use the global lower/upper bound that the mtd >>driver itself keeps track of. Apply your scoring margins to THOSE values >>because they are "true" bounds, not speculative bounds. I learned about >>this from discussions with others at the world computer chess championship. >>It was one of those things that should have been obvious to me but wasn't. > >In DIEP i don't have a lazy eval problem, as i don't use lazy eval. >I'm completely against it. Let's say i know too much about lazy eval >to let my hashtables be spoiled with them. > >I get however a 60% speedup by using a simple hashtable that only >stores my eval. This goes down to 50% speedup when loading factor >becomes huge (way above 1). > >As i know most programs are not using a eval hashtable, i think >i may point to my eval table for this reason. What they achieve >with lazy eval, i achieve more or less with an eval table. > make that "less". I did this for two years in crafty. The problem is that Lazy Eval can give you a 30-50% speed increase. No way you will get 30-50% hash hits to fetch the eval and speed up your code that same amount. I stopped hashing evals when I stopped hashing qsearch nodes, since there was no point when not hashing qsearch. However _I_ consider lazy eval to be a winner... and the win gets bigger as the eval gets bigger... >>I would like to mention that I was forced to use MTD and solve these >>problems (also problems like bad PV's) because it was simply faster, >>and if the speedup was trivial I would have gladly just avoided the >>issue! >>- Don > >Don, i don't doubt MTD is faster for your programs. > >Let's however write down some facts why my prog is unhappy with MTD. >It's up to others to generalize it to their progs: > > - the huge number of researches needed. In DIEP my evaluation is nowadays > in 1/1000 of a pawn. For a long time i had 1/200 of a pawn (in the time > i experimented with MTD), but now i have 1/1000 of a pawn. So a drop > of 0.20 pawn, which is a normal drop in DIEP, is in fact a drop of 200 > points. Happy researching! > - My evaluation has a lot of knowledge, so i can expect every iteration > a different behaviour of it, although the ups and downs in evaluation > every ply i've figured out are mainly caused by the mobility component, > this means nevertheless that i'm sure that i need a lot of researches. > - As my DIEP needs very little nodes a ply (must see the first prog > needing less when also turning off the forward pruning, except for > nullmove), although i don't dare to say that my sorting is optimal, > *everything* but near optimal i prefer to say, this means however > that all overhead i have to search is too much overhead for it. > > Secondly it simply happens to be the case that > when searching using a bound of 0.10 that all scores that get returned > are very near to it (nullmove). This has the nasty habit that a lot > of bounds stored > in the transpositiontable will not work next research, and as we know we > have a lot of researches to do, then it's easy to realize that this > gives a lot of overhead which is simply unnecessary. > - Chess is a worst case game. That means that if you have one big weak spot, > that you are complete history. Even at nowadays hardware a weak spot of > DIEP is its search speed. It's getting 15k nodes a second at a PII450. > Now i can have a branching factor like heaven, but still it won't search > very deep, unless i give it a lot of time. At very slow levels like 3 > minutes a move it usual will even search near the opponents depth, or > sometimes even deeper, because of this branching factor, but up to the > first 90 seconds or so, for sure a program that's 20 times slower than > its opponents is not likely to search deeper. > > So it's important to realize that it already doesn't search deeply, > when getting to my point: > in very complicated positions where the score goes up and down a lot, > or where a few fail lows occur, that usual are very important points in > a game. Now we all give our programs more time, but still those positions > it not seldom searches 2 or 3 ply less or so than in other middlegame > positions. In those complicated positions a lot of games get decided. > It is in those positions that MTD has a major weak spot. > MTD can't stand a lot of researches. So there where one needs its search > algorithm the most, there MTD has a major shortcoming. There MTD shows its > worst case and simply abandons you, needing up to 6 times more nodes. > > Now you can do the math. That's a laughable DEPTH i get then. If i > search a few moves at a depth of 9 ply, and all others at like 13 > or 14 ply, then i'm completely smoked. > > Even the tactical barrier where we talked about some years ago, > and was estimated by me at 12 ply, is 3 plies off that. > > Doing 9 ply searches is back to the old days! > Now 9 versus 13/14 ply is an example, but it clearly shows my point. > > MTD is simply a worst case/ best case algorithm. If scores are > very close to each other (usually when there is only 1 obvious move > to make), then it will not perform bad, but quickly get to the next ply. > If MTD scores are not close, and a lot of different PVs follow each other > up, then MTD has a major problem. > >It's obvious that MTD is a dead wrong algorithm for computerchess! > >If Don would say: "average it needs less nodes in Cilkchess", then considering >how Cilkchess has been made and how all progs of Don are, i directly >believe him on his word. > >What will remain of those results when you get a better eval in the future? >How about a worst case analysis of MTD versus PVS? > >Vincent Diepeveen >diep@xs4all.nl I personally think mtd(f) can probably work fine. I think it takes the same kind of commitment I made to bitboards 5 years ago... that is that I was going to use them for at least 5 years before giving up. Because it took me a big part of that time to get everything "right". I think mtd(f) is the same. I spent 3 months fiddling with it and didn't like what I saw. But possibly if I spent 2 years I might like it better. It takes time for a lot of 'tricks' to surface with any algorightmmm.
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.