Author: Vincent Diepeveen
Date: 17:15:42 07/20/99
Go up one level in this thread
On July 20, 1999 at 12:00:18, Rudolf Huber wrote: >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? Some people don't have an *idea* how much time i've put in testing out algorithms. Biggest time waste was FHR. One can even prove this theoretical incorrect although with a tough invariant. >The problem is that people change a few lines in their program >and then expect some 15% speedup. This is why i'm angry. NO i didn't change a few lines. Really, this is hard for people to understand. Example: i'm rewriting big parts of my eval currently for several reasons, mainreason being that i want it to play the endgame better. I see that when using a different way to store my eval in the eval table (different method), i get different node counts. So i spent whole day to figure out that it was not a bug. If i waste some weeks time on testing and implementing an algorithm, yeah sometimes a year, then i'm really dissappointed in something. If i sound angry, please don't read it like that. To give you what i wasted my time on last year: i wasted my time on searching selective last year. Directly after the big bummer of wccc99, i've turned off all forward pruning. I'm just doing PVS now and nullmove R=3. Nothing more. After extensive testing it took a world championship for me to figure out that for blitz forward pruning works great, but it doesn't work in the long term. At analysis level (overnight) not forward pruning might even outperform depthwise the same search forward pruning! If diep initially plays bad at blitz, so be it. Basic idea was that bad lines we don't need to look much deeper. This is of course something different than just doing last ply pruning. I'm talking about heavy pruning, like junior does it (but junior is doing it alfabeta dependant seemingly, and that's not what i did in DIEP). I've wasted a part of a year onto that! >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. Lucky for me i don't prune at alpha in the qsearch, so this is no problem for DIEP. I'm already using only 1 bound there, except for the first few leaves. >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. Just the thought that you think i didn't test it well already makes me laugh. >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). This is not true. The same time management i would also want to use for pvs then. Then you have again the same worst case problem. In fact i already do it in DIEP. start of game diep uses *a lot* of time. Many testers of DIEP have complained in the past that it used so much time at the start of the game and in the middlegame. Hardly anything it has left to play the endgame (except of course when things go ok for it in the game). To say that working at time management would solve this, is of course not true. It's like an engineer seeing that a motor doesn't perform well and saying to a tester who sees this: "doesn't matter, it's just a matter of getting new tires". Well instead of getting new tires i would prefer the better engine *and* the new tires. Get my point? >Rudolf In fact MTD and PVS are to some extend quite similar. The basic difference of it is that in PVS you first visit a few leafs with [alfa,beta] and in MTD you only care about alfa and beta. So in PVS the qsearch does basically the tough work, and researching isn't needed that much. Only a handful of positions have alfa+1 != beta So all other positions you do the same in both MTD and PVS, however in PVS you solve your window problems *realtime*. in MTD you solve them only afterwards (when the cow is drowned) in the root. >>>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.07 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.