Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD is a big win.

Author: Bruce Moreland

Date: 13:37:48 07/20/99

Go up one level in this thread



On July 20, 1999 at 15:06:25, Don Dailey wrote:

>I got tired of dealing with  the MTD problems with Cilkchess and spent
>a  signficant  amount of  time  creating a  version  with  a good  PVS
>implementation.   I was  highly motivated  to make  this work  and the
>effort is  what convinced me that  MTD was better,  certainly at least
>for me.  I actually didn't want to  use MTD and was looking for a good
>excuse not to.
>
>The  version I  had could  switch between  MTD and  PVS with  a simple
>command line  switch and  I ran timings  with all sorts  of positions.
>When I tune and do timing comparisons, I use a large set of positions,
>not just a  single one.  I mention this because I  have seen people do
>this and  draw conclusions based on  it.  What stood out  was that MTD
>was  pretty consistantly  faster (less  nodes) to  do a  given search.
>Occasionally PVS beats it but not often.

Yes.  With a single position I think that you run a high risk of achieving a
local optimum that has minimal relation to the truth.  My evidence for this is
simply common sense, which I think is good enough in this case.

I use LCTI to do speed tests, since it has no mates, has both tactical and
positional problems, and has both endgame and middlegame positions.  I think
that this is probably still not good enough, since I've notice wide variation
between parallel runs due to search indeterminism.  If I can get repeatable
results with a single version the odds that I can compare two versions properly
are low, I think.  But it's better than guessing, and I take my results with a
healthy degree of skepticism.

>But what really  stood out was that I was  expecting the difference to
>be trivial, after all I was comparing to a good PVS implementation.  I
>really don't  remember the exact  numbers, but it was  substantial and
>way too much to ignore.  It was over a 15% speedup.
>
>If I used MTD with NO lazy evaluation versus PVS with lazy evaluation,
>PVS  would be a  win because  lazy evaluation  is a  big win.   If you
>measure  improvement by  the  number of  nodes  needed to  do a  given
>iteration then  MTD is  a big  win there is  simply no  question about
>this, certainly  not with Cilkchess.   Lazy evaluation is a  nodes per
>second optimization and I have  no reason to believe it would suddenly
>not work with MTD.  MTD is simply another kind of aspiration search.

I'm not sure first that I'm understanding why you can't use lazy eval with MTD.
Is it because you trash your hash table and get search instabilities?  If so,
that sounds like a serious practical problem.

I'm not sure why it's fair to factor out lazy eval.  My own goal here is not to
do the fewest nodes necessary to reach depth D, my goal is to get to depth D in
the least amount of time.  And if PVS + lazy eval < MTD, I'll take PVS + lazy
eval.

I'm not dismissing MTD though, certainly.

>I did implement lazy evaluation the  right way with Cilkchess and I do
>get big speedups,  I don't think MTD has anything to  do with this now
>that I  know what I  was doing wrong.   But I haven't  actually proved
>that I get the  same lazy eval speedups.  If I still  had the PVS code
>in cilkchess I would go chase down  all these things to but I'm not to
>motivated to  do this since I have  no reason to believe  there is any
>relationship.
>
>I talked to Franz Morsch and he also tried MTD and verified that it it
>was a  speed improvement for his  already very fast  program.  I don't
>know the exact detail of  his implementation and which of his programs
>are now  using it, but it was  nice to hear this  kind of verification
>that  others are having  good results  with it.   There is  always the
>possiblity that I simply implemented  MTD better than PVS or there are
>errors somewhere and I am being fooled.  Maybe Vincent is right and it
>doesn't work on certain  programs because of implementation details, I
>can't say that  it's right for everyone,  all I can say is  that it is
>right for me.
>
>It turns out  that MTD implentation is actually  a big simplification.
>All  the re-search  code and  crap suddenly  gets simple  and  all the
>details are in  the driver routine (which is  actually simple too once
>you  figure it  out.)  The  recursive search  is trivial  stuff.  Lazy
>evaluation and PV  reporting has to be handled  correctly however, but
>this is true of any search implementation.
>
>
>I have a primitive program  called "Occam" playing on the chess server
>now.  I  don't have  any kind  of aspiration search  in it,  just pure
>alpha/beta, no PVS, no MTD or anything.  I will implement PVS first so
>that I  can do comparisions.  Whenever  I finally get  around to doing
>all of  this I'll post some  solid numbers over  some random positions
>and then some with the ECM problems.

Cool.

>By the way, what is the state  of the ECM problems?  Is there a subset
>of  them available that  have been  culled and  de-cooked that  are in
>common usage?

Several of us including you did some preliminary work on this last year.  I
don't think it went anywhere after that.  I use the un-culled set.  I think it
is fine for trying to measure effective tactical speed.  I simply hope that it's
large enough that the problems will plague distinct runs equally, still allowing
for decent comparison.

bruce



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.