Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD is a big win.

Author: Don Dailey

Date: 12:06:25 07/20/99

Go up one level in this thread


> How do you know it is a big win?  Is it possible for you to shift back and forth
> between a version with MTD and no lazy eval and one that uses normal PVS and
> lazy eval?  If so, do you have any sort of numbers?
>
> I think the best evidence would be a post that says:
>
> 1) MTD allows solution of X ECM positions in Y seconds as opposed to Z positions
> in the same time without MTD.
>
> 2) In a well known positional suite, MTD allows completion to depth D in X% of
> the time it takes to get through ply D without MTD.
>
> bruce


Hi Bruce,

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.

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

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?

- Don



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.