Author: Rudolf Huber
Date: 09:00:18 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. Vincent, what makes you so angry? The problem is that people change a few lines in their program and then expect some 15% speedup. But there are a number of things you should do when using MTD (e.g. q-search hashing) and some things you should not do. E.g. most current programs use the alpha and/or beta bound to tweak the search. With MTD you have no alpha, and no real beta. So those things do not work. You have to test the highly optimized PVS/NegaScout Diep against an equally optimized MTD Diep. Therefore the result of your tests can never be that MTD does not work for you. My own experience with MTD is very good. However your argument below about MTD beeing a worst case/best case algorithm is valid. But this can be addressed with a different time management and a different f in MTD(f). Rudolf > >>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. > >>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
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.