Computer Chess Club Archives




Subject: Re: MTD is a big win.

Author: Bruce Moreland

Date: 09:09:55 07/20/99

Go up one level in this thread

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

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.


This page took 0.2 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.