Author: Don Dailey
Date: 11:07:18 07/20/99
Go up one level in this thread
Hi Vincent, First, let me clarify a few points. I didn't have anyone in mind when I made that post, I was talking to the general audience and I was trying to help people understand one of the hairy issues that you can encounter with MTD. Also, I posted that it was a big win because I believe that it is, not as a political statement or to refute anyone. I didn't know you were religiously dead set against it or that anyone really was. I know that people have tried it and some use it now, and others have decided the problems they had were not worth the trouble. My post was not to criticize any one of them either. You took offense at this statement: "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." I would like to say that I was not thinking of you at all when I made this statement. I can't even figure out why you thought this. However I am sorry about the unfortunate wording I used, it sounds like a criticism when it wasn't meant to be. I DO feel that a lot of people "haven't bothered" to stick with it long enough to solve all the problems, but I don't fault them for it or consider it a personality flaw or anything like this! There are a million problems and issue in my own chess program I haven't taken the time yet to fix or look at, instead using the time for other things. So I haven't bothered to do a lot of things yet that need to be done. I do however still encourage people to give this a good hard look. Especially if you have a well developed fine tuned program and are now looking for hard to get incremental improvements. It's my belief that for these people, it's probably the biggest single improvement you will find. I will make another post soon describing my experiences with it for those who are willing to listen and why I can't give it up even though I would like to. I have some specific answers to some of the points you bring up below: 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. Don't be, it was meant for everyone. I don't think I fully understand all the various intraccies of game tree searching and yet I believe I am an expert on it. > 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 no longer use lazy evaluation, probably a loss for me. My evaluation has gotten so complicated and aggressive that it is really hard to do this well. You can do it in a perfectly correct way with no problems whatsover or you can use the approach where you are willing to accept some error in the worst cases (or anywhere in between.) I have chosen to "not bother" with this problem any longer and I take the slowdown because I have too many terms with agressive weights and I don't want to accept the errors. If I took the practical approach I would probably accept the errors and have a stronger program for it. If I wanted to be really meticulous I would develop a "meta language" for creating evaluation terms and whenever I changed the weights or added a new term it would recompile the code in such a way as to make the lazy evaluation completely correct and doing only the minimal computation needed. I have no illusions about this however, I think lazy evaluation makes sense and is a big win, especially if you have a big fat evaluator like you and I do. If you have much simpler evaluation you can do it with much less effort however. > 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. Wow, this is impressive. We do this with Cilkchess too but don't get very much for it. I think Diep probably has a bigger evaluator that almost any program. >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! I think you miss the whole point of MTD. It's not the number of researches needed, it's the number of nodes you look at. The whole idea of MTD is that the search tree is basically kept in memory. When you research with a different beta value, you won't traverse the same tree, so you can think of it as not doing ANY extra work. DON'T think of it as doing a bunch of searches over and over again wasting your time, that's NOT what's going on. Also, you can choose a different MTD increment. You don't have to use a single point, it might take some experimentation. However I use 100 for a pawn and a single point increment works fine for me. > - 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. I'm not sure whether this matters a lot or not. If you do a lot of strange window based extensions, that could be an issue though. But I can't guarantee that MTD would work for every program, I only suggest that it's worth a try. But you do use aspriation windows don't you like PVS? If these things work I can't see why MTD wouldn't work, it's just a variation on a theme and PVS requires researches too. > - 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! It sounds like your program is more complicated than mine. My program has the behavior that it will virtually always try to return the same exact score no matter what the search window, at least to the extent that the aspiration window allows it. In other words two searches won't contradict each other. If you have this behavior I can't see why any kind of aspiration search would be a problem. The way you make it sound you shouldn't be using PVS or any variant that does any kind of speculation because the research will kill you. For instance it would be unusual to see my program fail hi and then on a research fail low with a contradiction. I don't think this behavior is guaranteed with any chess program unless no selectivity or hash tables are used, but it rarely happens with my program. With parallel versions it of course can happen a lot more, but it still responds very well to parallelization and I haven't noticed a problem. This bad behavior can also result with lazy evaluation if it's not coded exactly right. But I'm not even sure that would make MTD wrong to use, but perhaps it would. > 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? I believe one characteristic of a very good evaluation is that you will get less variation from iteration to iteration. The whole idea is to get the most accurate possible evaluation so in a sense your scores should "smooth out" with better evaluation, not fluctuate even more. For instance, if your evaluation is only material, your score doesn't gradually get lower as a backward pawn becomes impossible to defend, it simply jumps to a pawn down when the tactics see it. > 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.