Computer Chess Club Archives




Subject: Re: Couple of chess programming questions

Author: Dann Corbit

Date: 10:11:02 09/10/02

Go up one level in this thread

On September 10, 2002 at 12:07:37, Vincent Diepeveen wrote:
>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f)
>>is something of a magic bullet.  But I note it seems that more programs don't
>>use it than do (for example Crafty).  What is wrong with mtd(f) which Plaat
>>doesn't say?
>There is nothing wrong with it. However a softwareprogram must have certain
>conditions to let it work well (in hardware other issues play a role)
>  a) it must be a static evaluation with a small granularity;
>     if pawn=32 it will work great, if pawn=1000 like in DIEP it won't
>     work at all, other things aren't interesting then.

I have found this to be true also with experiments, and the reason is obvious.

The MTD(f) algorithm basically does a binary search between two bounds (on
average -- it might be faster or slower in individual cases).  If the interval
varies from 3276700 to -327600 you have between 22 and 23 searches to resolve
it.  If the interval varies from  3276 to -3276 you have between 12 and 13
searches to resolve it.

Therefore, you have a paradox.  The more accurately you search, the slower
MTD(f) will become.  I can't see any solution to it, unless you use progressive
accuracy to quickly narrow the search.  If you went to long double accuracy in
your evaluation function, it will take a very long time to resolve the search
with MTD(f), unless you double the accuracy with each iteration.  So for the
first search, only (ugh) one significant digit is used.  Then two digits of
accuracy, then 4, etc.

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