Computer Chess Club Archives




Subject: MTD(f)

Author: Tord Romstad

Date: 13:49:29 01/14/04

Go up one level in this thread

Hi Ed,

On January 14, 2004 at 16:26:42, Ed Trice wrote:

>>Have you considered trying MTD(f) instead of PVS?  I am not sure it is any
>>more efficient in practice, but it is easier to code, and has the additional
>>benefit of making you feel different, original, interesting, intelligent,
>>handsome and attractive.

I forgot to include "brave" and "charming" in the list of adjectives.  MTD(f)
is guaranteed to be at least as effective for attracting the opposite sex as
most of the products the spammers try to sell you.

>Well Aske Plaat would love to hear that :)
>But doesn't MTD(f) trigger a great deal of researches? I remember trying that
>once and it bloated the tree.

The whole idea of MTD(f) is that most of the re-searches will be extremely fast
because your hash table is packed with upper and lower bounds which give you
lots of instant cutoffs everywhere in the tree.

But there are also ways to reduce the number of re-searches.  Plain
MTD(f) as described in Plaat's paper never worked well for me, but
adding what is commonly known as a "convergence accelerator" improved
the situation a lot.  When the search fails in the same direction more
than once, I increase the step size.  If it still fails in the same
direction, I increase it even more.  This continues until I finally manage
to make the search fail in the opposite direction.  Doing like this also
gives you an additional advantage:  You will often have an upper *and*
a lower bound for the root score.  These bounds can be very useful for
pruning decisions.

Another simple trick is to reduce the resolution of your evaluation
function.  In my pre-MTD(f) days, I used pawn=128.  I still use pawn=128
as the internal unit in my evaluation function, but before returning
the final score I divide the score by 2.  This simple change made my
search noticably more efficient.


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