Computer Chess Club Archives




Subject: MTD is a big win.

Author: Don Dailey

Date: 20:35:50 07/19/99

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

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