Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD is a big disaster

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.21 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.